C语言实现顺序表-创新互联
顺序表是C语言中一种基本的结构，可以存储各种基本类型的数据，而且不但可以存储基本类型的数据，也可以存储一种结构。所以顺序表是一种在学C的过程中必须掌握的结构，通过学习整理，下面来实现一下：
首先，先要想好用什么实现，一般实现最基本的顺序表的话直接用数组实现，我们在这用一个结构体来封装这个顺序表（封装这一概念是在C++中最常用的概念）
#define ARRAY_EMPTY -2
#define ARRAY_FULL -1
#define MAX_SIZE 10000
typedef int Datatype;
typedef struct Seqlist
{
Datatype array[MAX_SIZE];
size_t size;
}Seqlist;对于无法确定数组大小，我们可以用宏来表示。
把大体结构搭建好了之后，就可以思考一个顺序表应该具有的功能，头插，尾插，定点插入，排序等等都是一些最基本的功能：
void PrintSeqlist(Seqlist* pSeq); void InitSeqlist(Seqlist* pSeq); void PushBack(Seqlist* pSeq, Datatype x); void PushFront(Seqlist* pSeq, Datatype x); void PopBack(Seqlist* pSeq); void PopFront(Seqlist* pSeq); void Insert(Seqlist* pSeq,size_t pos, Datatype x); int Find(Seqlist* pSeq, size_t pos, Datatype x); void Erase(Seqlist* pSeq, size_t pos); int Remove(Seqlist* pSeq, Datatype x); int Removeall(Seqlist* pSeq, Datatype x); void Bubblesort(Seqlist* pSeq); void Selectsort(Seqlist* pSeq); int BinarySearch(Seqlist* pSeq, Datatype x);
下面就是一些关键函数的实现：
void PrintSeqlist(Seqlist* pSeq)//输出顺序表
{
assert(pSeq);
size_t i = 0;
if (pSeq->size <= 0)
{
printf("Array is empty\n");
return;
}
else if (pSeq->size >= MAX_SIZE)
{
printf("Array is full\n");
}
for (; i < pSeq->size; ++i)
{
printf("%-4d", pSeq->array[i]);
}
}
void InitSeqlist(Seqlist* pSeq)//初始化顺序表
{
pSeq->size = 0;
//printf("Initialization is complete\n");
}
void PushBack(Seqlist* pSeq, Datatype x)//后插入
{
assert(pSeq);
if (pSeq->size >= MAX_SIZE)
{
printf("Array is full, insert the failure\n");
return;
}
pSeq->array[pSeq->size] = x;
pSeq->size++;
}
void PushFront(Seqlist* pSeq, Datatype x)//前插入
{
assert(pSeq);
size_t i = 0;
if (pSeq->size >= MAX_SIZE)
{
printf("Array is full, insert the failure\n");
return;
}
for (i = pSeq->size; i > 0; --i)
{
pSeq->array[i] = pSeq->array[i - 1];
}
pSeq->array[0] = x;
pSeq->size++;
}
void PopBack(Seqlist* pSeq)//后删除
{
assert(pSeq);
if (pSeq->size <= 0)
{
printf("Array is empty,popback is eeror\n");
return;
}
pSeq->array[pSeq->size-1] = 0;
pSeq->size--;
}
void PopFront(Seqlist* pSeq)//前删除
{
assert(pSeq);
size_t i = 0;
if (pSeq->size <= 0)
{
printf("Array is empty,popback is eeror\n");
return;
}
for (i = 1; i < pSeq->size; i++)
{
pSeq->array[i - 1] = pSeq->array[i];
}
pSeq->size--;
}
void Insert(Seqlist* pSeq, size_t pos, Datatype x)//定点删除
{
assert(pSeq);
size_t i = 0;
if (pSeq->size >= MAX_SIZE)
{
printf("Array is full, insert the failure\n");
return;
}
for (i = pSeq->size ; i > pos; i--)
{
pSeq->array[i] = pSeq->array[i - 1];
}
pSeq->array[pos] = x;
pSeq->size++;
}
int Find(Seqlist* pSeq, size_t pos, Datatype x)//查找数据
{
assert(pSeq);
size_t i = 0;
if (pSeq->size <= 0)
{
printf("Array is empty,erase error\n");
return ARRAY_EMPTY;
}
if (pos < 0 || pos >= MAX_SIZE)
{
printf("Began to find the position error\n");
return -1;
}
for (i = pos; i < pSeq->size; i++)
{
if (pSeq->array[i] == x)
{
return i;
}
}
return -2;
}
void Erase(Seqlist* pSeq, size_t pos)//删除特定数据
{
assert(pSeq);
size_t i = 0;
if (pSeq->size <= 0)
{
printf("Array is empty,erase error\n");
return;
}
if (pos < 0 || pos >= MAX_SIZE)
{
printf("Began to find the position error\n");
return;
}
for (i = pos; i < pSeq->size; i++)
{
pSeq->array[i] = pSeq->array[i + 1];
}
pSeq->size--;
}
int Remove(Seqlist* pSeq, Datatype x)
{
assert(pSeq);
size_t i = 0;
if (pSeq->size <= 0)
{
printf("Array is empt,remove error\n");
return ARRAY_EMPTY;
}
for (; i < pSeq->size; i++)
{
if (pSeq->array[i] == x)
{
size_t j = i + 1;
for (; j < pSeq->size; j++)
{
pSeq->array[j - 1] = pSeq->array[j];
}
pSeq->size--;
return 0;
}
}
return -1;
}
int Removeall(Seqlist* pSeq, Datatype x)
{
assert(pSeq);
size_t i = 0;
int flag = 0;
if (pSeq->size <= 0)
{
printf("Array is empt,remove error\n");
return ARRAY_EMPTY;
}
for (; i < pSeq->size; i++)
{
if (pSeq->array[i] == x)
{
size_t j = i + 1;
for (; j < pSeq->size; j++)
{
pSeq->array[j - 1] = pSeq->array[j];
}
pSeq->size--;
flag++;
if (pSeq->size <= 0)//如果顺序表的元素为空就不能再删除了，返回
{
return 0;
}
else
{
i--;
}
}
}
if (flag > 0)
return 0;
else
return -1;
}
void Bubblesort(Seqlist* pSeq)//冒泡排序
{
assert(pSeq);
size_t i = 0;
for (; i < pSeq->size; i++)
{
size_t j = 0;
for (; j < pSeq->size - i - 1; j++)
{
if (pSeq->array[j] > pSeq->array[j + 1])
{
int tmp = pSeq->array[j];
pSeq->array[j] = pSeq->array[j + 1];
pSeq->array[j + 1] = tmp;
}
}
}
}
void Selectsort(Seqlist* pSeq)//选择排序
{
assert(pSeq);
size_t i = 0;
for (; i < pSeq->size; i++)
{
int flag = pSeq->array[i];
size_t j = i;
for (; j < pSeq->size; j++)
{
if (pSeq->array[j] < flag)
{
int tmp = pSeq->array[j];
pSeq->array[j] = flag;
flag = tmp;
}
}
pSeq->array[i] = flag;
}
}
int BinarySearch(Seqlist* pSeq, Datatype x)//二分查找
{
assert(pSeq);
size_t left = 0;
size_t right = pSeq->size - 1;
while (left <= right)
{
size_t mid = left + (right - left) / 2;
if (x > pSeq->array[mid])
{
left = mid + 1;
}
else if (x < pSeq->array[mid])
{
right = mid - 1;
}
else if (x == pSeq->array[mid])
{
return (int)mid;
}
}
return -1;
}这只是最基本的顺序表，只能够存储基本类型的数据，如果想要存储结构体或者string之类的数据的话会涉及C++的深浅拷贝问题，而且用一个数组来存未知大小的数据结构的话是做不到的。
本人的博客后面会更新顺序表的一些优化写法，希望对朋友微小的帮助。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站名称：C语言实现顺序表-创新互联
文章位置：http://shouzuofang.com/article/dcdogo.html