seqlist.h
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include <stdio.h>
#include <assert.h>
#include <string.h>
#define MAX 10
typedef int DateType;
typedef struct SeqList
{
DateType data[MAX];
int sz;
}SeqList, *pSeqList;
//初始化
void InitSeqList(pSeqList pSeq);
//尾部插入
void PushBack(pSeqList pSeq, DateType data);
//尾部删除
void PopBack(pSeqList pSeq);
//头部插入
void PushFront(pSeqList pSeq, DateType data);
//头部删除
void PopFront(pSeqList pSeq);
//查找指定元素
int Find(pSeqList pSeq, DateType data);
//指定位置插入
void Insert(pSeqList pSeq, int pos, DateType data);
//删除指定位置元素
void Erase(pSeqList pSeq, int pos);
//删除指定元素
void Remove(pSeqList pSeq, DateType data);
//删除所有的指定元素
void RemoveAll(pSeqList pSeq, DateType data);
//返回顺序表的大小
int Size(pSeqList pSeq);
//判断顺序表是否为空
int Empty(pSeqList pSeq);
//冒泡排序
void BubbleSort(pSeqList pSeq);
//选择排序
void SelectSort(pSeqList pSeq);
//选择排序的优化
void SelectSortOP(pSeqList pSeq);
//二分查找
int BinarySearch(pSeqList pSeq, DateType data);
//二分查找递归写法
int BinarySearch_R(pSeqList pSeq, int left, int right, DateType data);
//打印
void PrintSeqList(pSeqList pSeq);
#endif //__SEQLIST_H__
seqlist.c
#include"SeqList.h"
void InitSeqList(pSeqList pSeq)
{
assert(pSeq != NULL);
pSeq->sz = 0;
memset(pSeq->data, 0, sizeof(pSeq->data));
}
void PushBack(pSeqList pSeq, DateType data)
{
assert(pSeq != NULL);
if (pSeq->sz == MAX)
{
printf("顺序表已满\n");
return;
}
pSeq->data[pSeq->sz] = data;
pSeq->sz++;
}
void PopBack(pSeqList pSeq)
{
assert(pSeq != NULL);
if (pSeq->sz == 0)
return;
pSeq->sz--;
}
void PushFront(pSeqList pSeq, DateType data)
{
int i = 0;
assert(pSeq != NULL);
if (pSeq->sz == MAX)
{
printf("顺序表已满\n");
return;
}
for ( i = pSeq->sz-1 ; i >=0; i--)
{
pSeq->data[i + 1] = pSeq->data[i];
}
pSeq->data[0] = data;
pSeq->sz++;
}
void PopFront(pSeqList pSeq)
{
assert(pSeq!=NULL);
if (pSeq->sz == 0)
return;
for (int i = 1; i <= pSeq->sz - 1; i++)
{
pSeq->data[i - 1] = pSeq->data[i];
}
pSeq->sz--;
}
int Find(pSeqList pSeq, DateType data)
{
assert(pSeq != NULL);
for (int i = 0; i < pSeq->sz; i++)
{
if (pSeq->data[i] == data)
return i;
}
}
void Insert(pSeqList pSeq, int pos, DateType data) //指定位置插入
{
assert(pSeq!=NULL);
if (pSeq->sz == MAX)
return;
for (int i = pSeq->sz; i>=pos; i--)
{
pSeq->data[i+1]=pSeq->data[i];
}
pSeq->data[pos] = data;
pSeq->sz++;
}
void Erase(pSeqList pSeq, int pos)
{
assert(pSeq != NULL);
if (pSeq->sz == 0) //顺序表为空
return;
for (int i = pos; i < pSeq->sz; i++)
{
pSeq->data[i] = pSeq->data[i + 1];
}
pSeq->sz--;
}
void Remove(pSeqList pSeq, DateType data)//删除指定元素
{
int pos = 0;
assert(pSeq != NULL);
//查找
pos=Find(pSeq, data);
if (pos != -1)
{
Erase(pSeq, pos);
}
}
void RemoveAll(pSeqList pSeq, DateType data)//删除全部指定元素
{
assert(pSeq != NULL);
if (pSeq->sz == 0) //顺序表为空
return;
for (int i = 0; i < pSeq->sz; i++)
{
if (pSeq->data[i] == data)
{
for (int j = i; j < pSeq->sz; j++)
{
pSeq->data[j] = pSeq->data[j + 1];
}
pSeq->sz--;
i--;
}
}
}
int Size(pSeqList pSeq)
{
return pSeq->sz;
}
int Empty(pSeqList pSeq)
{
return pSeq->sz == 0;
}
void Swap(DateType*px,DateType*py)
{
DateType tmp = *px;
*px = *py;
*py = tmp;
}
void BubbleSort(pSeqList pSeq) //冒泡排序优化
{
int tmp = 0;
int flag = 0;
assert(pSeq != NULL);
for (int i = 0; i < pSeq->sz-1; i++)
{
flag = 0;
for (int j = 0; j < pSeq->sz - 1 - i; j++)
{
if (pSeq->data[j]>pSeq->data[j+1])
{
Swap(pSeq->data + j, pSeq->data + j + 1);
flag = 1;
}
if (flag == 0)
break;
}
}
}
int BinarySearch(pSeqList pSeq, DateType data)
{
assert(pSeq != NULL);
int left = 0;
int right = pSeq->sz - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (pSeq->data[mid] > data)
right = mid - 1;
else if (pSeq->data[mid] < data)
left = mid + 1;
else
return mid;
}
return -1;
}
int BinarySearch_R(pSeqList pSeq, int left, int right, DateType data)
{
int mid = 0;
if (left > right)
return -1;
mid = left + (right - left) / 2;
if (pSeq->data[mid] < data)
{
return BinarySearch_R(pSeq, mid + 1, right, data);
}
else if (pSeq->data[mid]>data)
{
return BinarySearch_R(pSeq, left, mid - 1, data);
}
else
return mid;
}
void SelectSort(pSeqList pSeq)
{
assert(pSeq != NULL);
int pos = 0;
int tmp = 0;
for (int i = 0; i < pSeq->sz - 1; i++)
{
for (int j = 0; j < pSeq->sz - 1 - i; j++)
{
if (pSeq->data[pos] < pSeq->data[j])
{
pos = j;
}
}
if (pos != pSeq->sz - 1 - i) //最大元素的下标不是最后一位就交换
{
tmp = pSeq->data[pos];
pSeq->data[pos] = pSeq->data[pSeq->sz - 1 - i-1];
pSeq->data[pSeq->sz - 1 - i-1] = tmp;
}
}
}
void SelectSortOP(pSeqList pSeq)
{
int temp;
if (pSeq->sz == 0 || pSeq->sz == 1)
{
return;
}
for (int i = 0; i < pSeq->sz - 1; i++)
{
int min = i;
for (int j = i + 1; j < pSeq->sz; j++)
{
if (pSeq->data[j]<pSeq->data[min])
{
min = j;
}
}
if (min != i)
{
temp = pSeq->data[min];
pSeq->data[min] = pSeq->data[i];
pSeq->data[i] = temp;
}
}
}
void PrintSeqList(pSeqList pSeq)
{
assert(pSeq != NULL);
for (int i = 0; i < pSeq->sz; i++)
printf("%d ", pSeq->data[i]);
printf("\n");
}
test.c
#include "SeqList.h"
void test()
{
SeqList seq;
int pos = 0;
InitSeqList(&seq);
PushBack(&seq, 4);
PushBack(&seq, 6);
PushBack(&seq, 5);
PushBack(&seq, 8);
PrintSeqList(&seq);
SelectSortOP(&seq);
PrintSeqList(&seq);
//测试二分查找
/*pos = BiarySearch(&seq, 3);
if (pos == -1)
{
printf("未找到该元素\n");
}
else
{
printf("找到了，该元素的下标:%d\n", pos);
}
*/
////测试二分查找递归
//pos = BinarySearch_R(&seq,0,seq.sz,4);
//if (pos == -1)
//{
// printf("未找到该元素\n");
//}
//else
//{
// printf("找到了，该元素的下标:%d\n", pos);
//}
}
int main()
{
test();
return 0;
}
运行结果：
C语言顺序表.png
网友评论