1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

2.1. 静态顺序表：使用定长数组存储元素

#pragmaoncetypedefintSLDataType;//顺序表数据类型#defineN10//顺序表的大小structSeqList{SLDataType a[N];//定长数组intsize;//有效数据的个数};

这就是静态顺序表，我们可以看到，其实也就是个套壳的数组，没办法动态的改变空间；
所以，这里的静态的意思就是固定大小。

2.2. 动态顺序表：使用动态开辟的数组存储。

typedefintSLDataType;structSeqList{SLDataType*arr;intsize;intcapacity;};

3.顺序表的接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

我们用C语言实现顺序表的以下接口：

//检查扩容函数voidSLCheckCapacity(SeqList*psl);//打印函数voidSeqListPrint(SeqList*psl);// 顺序表初始化voidSeqListInit(SeqList*psl);// 检查空间，如果满了，进行增容voidSLCheckCapacity(SeqList*psl);// 顺序表尾插voidSeqListPushBack(SeqList*psl,SLDataType x);// 顺序表尾删voidSeqListPopBack(SeqList*psl);// 顺序表头插voidSeqListPushFront(SeqList*psl,SLDataType x);// 顺序表头删voidSeqListPopFront(SeqList*psl);// 顺序表查找intSeqListFind(SeqList*psl,SLDataType x);// 顺序表在pos位置插入xvoidSeqListInsert(SeqList*psl,size_tpos,SLDataType x);// 顺序表删除pos位置的值voidSeqListErase(SeqList*psl,size_tpos);// 顺序表销毁voidSeqListDestory(SeqList*psl);// 顺序表打印voidSeqListPrint(SeqList*psl);//顺序表的排序voidSeqListSort(SeqList*psl);//二分查找intSeqBinarySearch(SeqList*psl,size_tleft,size_tright,SLDataType x);

3.1. 顺序表基本功能接口

3.1.1. 打印函数

为了测试我们所写的接口是否正确，我们需要写一个打印函数，用来打印顺序表的元素：

voidSeqListPrint(SeqList*psl){assert(psl);for(inti=0;i<psl->size;i++){printf("%d ",psl->arr[i]);}printf("\n");}

3.1.2. 初始化函数

voidSeqListInit(SeqList*s){/*s.size = 0; s.arr = NULL; s.capacity = 0;*/s->arr=(SLDataType*)malloc(sizeof(SLDataType)*4);if(s->arr==NULL){perror("malloc");exit(-1);//退出程序}s->size=0;s->capacity=4;}

3.1.3. 顺序表销毁

我们在创建顺序表的时候我们对顺序表进行malloc开辟空间，既然我们开辟了空间，在对空间使用结束后我们要将空间归还；

// 顺序表销毁voidSeqListDestory(SeqList*psl){if(psl!=NULL){free(psl->arr);psl->arr=NULL;psl->size=psl->capacity=0;}}

3.2. 顺序表内存检查扩容接口

3.2.1. 检查容量函数

我们在执行顺序表的插入操作时，可能会造成空间的容量不足，这时候我们就要对空间进行扩容，很明显，我们既然使用malloc函数来初始化函数，就可以用realloc函数进行空间的扩容；一般我们对空间进行2倍的扩容。

voidSLCheckCapacity(SeqList*psl){// 检查容量if(psl->size==psl->capacity){// 开辟空间时注意，当capacity初始化为 0 时，直接相乘的结果还是 0 ！！// 所以要先判断一下, 并且需要做 申请空间是否成功的判断，// 还不能直接将申请的空间赋值给 目标数组，先给一个 临时变量size_tnewCapcity=psl->capacity==0?4:psl->capacity*2;SLDataType*tmp=(SLDataType*)realloc(psl->arr,newCapcity*sizeof(SLDataType));if(tmp==NULL){perror("realloc fail");return;//exit(-1);}psl->arr=tmp;psl->capacity=newCapcity;}}

3.3. 顺序表增加功能接口

3.3.1. 顺序表的头插

voidSeqListPushFront(SeqList*psl,SLDataType x){assert(psl);SLCheckCapacity(psl);intend=(int)psl->size-1;while(end>=0){psl->arr[end+1]=psl->arr[end];end--;}psl->arr[0]=x;psl->size++;}

3.3.2. 顺序表尾插

我们在对顺序表进行尾部插入的时候，我们在插入前要对顺序表进行容量检查，即调用检查容量函数；插入结束后顺序表的容量不变，有效数据的个数加1；

voidSeqListPushBack(SeqList*psl,SLDataType x){assert(psl);//如果满了需要增容//一般我们增2倍SLCheckCapacity(psl);psl->arr[psl->size]=x;psl->size++;}

3.3.3. 在顺序表pos位置前插入x

首先我们要检查传入的指针 psl 是否为 NULL。如果 psl 是 NULL，则程序会触发断言并终止执行。
接着我们要检查插入位置 pos 是否有效。插入位置必须在当前顺序表的范围内，即从 0 到 psl->size（包括 psl->size，如果需要在末尾插入）；
插入前我们要先将pos及后面的元素向后移动，给插入的位置腾出空间，当然，插入前我们要进行空间容量的检查。

voidSeqListInsert(SeqList*psl,size_tpos,SLDataType x){assert(psl);assert(pos<=psl->size);SLCheckCapacity(psl);//插入前先检查一下满了没。//向后挪位置size_tend=psl->size;while(pos<end){psl->arr[end]=psl->arr[end-1];end--;}psl->arr[pos]=x;psl->size++;}

3.3.4. 在顺序表pos位置后插入x

和在pos位置前插入同理，我们只要在向后挪的操作少一次即可；

//在pos之后位置插入xvoidSeqListInsertBack(SeqList*ps1,size_t pos,SLDataType x){assert(ps1);assert(pos<=ps1->size&&pos>=0);SLCheckCapacity(ps1);size_t end=ps1->size;for(end;end>pos+1;end--){ps1->arr[end]=ps1->arr[end-1];}ps1->arr[pos+1]=x;ps1->size++;}

3.4. 顺序表删除功能接口

3.4.1. 顺序表的头删

我们直接从第二个元素向前移动，覆盖第一个元素，也就完成了头删操作，最后不要忘记修改size的值；

voidSeqListPopFront(SeqList*psl){assert(psl);intstart=0;while(start<psl->size){psl->arr[start]=psl->arr[start+1];start++;}psl->size--;}

3.4.2. 顺序表尾删

voidSeqListPopBack(SeqList*psl){assert(psl);//psl->arr[psl->size - 1] = 0; //可以不加，没什么意义psl->size--;}

3.4.3. 顺序表删除pos位置的值

voidSeqListErase(SeqList*psl,size_tpos){assert(psl);assert(pos<psl->size);size_tend=--psl->size;while(pos<end){psl->arr[pos]=psl->arr[pos+1];end--;}}

3.5. 顺序表查找接口

3.5.1. 顺序表查找函数

我们遍历顺序表，如果找到x，则返回这个顺序表的下标；若没找到返回-1；

intSeqListFind(SeqList*psl,SLDataType x){assert(psl);for(inti=0;i<psl->size;i++){if(psl->arr[i]==x){returni;//返回数组下标}}return-1;//没找到}

3.6. 顺序表其他接口

3.6.1. 顺序表的排序（小到大）

我们利用冒泡排序法进行排序：

//顺序表的排序voidSeqListSort(SeqList*psl){if(psl->size<2)return;bool swapped=false;for(inti=0;i<psl->size-1;i++){for(intj=0;j<psl->size-i-1;j++){if(psl->arr[j]>psl->arr[j+1]){inttemp=psl->arr[j];psl->arr[j]=psl->arr[j+1];psl->arr[j+1]=temp;swapped=true;}}if(!swapped)break;}}

3.6.2. 二分查找法

intSeqBinarySearch(SeqList*psl,size_tleft,size_tright,SLDataType x){intmid=0;intfind=0;while(left<=right){mid=(int)(left+right)/2;if(psl->arr[mid]>x){right=mid-1;}elseif(psl->arr[mid]<x){left=mid+1;}else{find=1;break;}}if(1==find){returnmid;}else{return-1;//没找到}}

源代码已绑定了这篇文章，需要者自取；

3.7. 测试函数

我们可以在test.c文件进行测试:

#define_CRT_SECURE_NO_WARNINGS#include"SeqList.h"voidTestSeqList1(){SeqList s;SeqListInit(&s);//初始化SeqListPushBack(&s,1);//尾插1SeqListPushBack(&s,2);//尾插2SeqListPushBack(&s,3);//尾插3SeqListPushBack(&s,3);//尾插3SeqListPushBack(&s,3);//尾插3SeqListPushBack(&s,3);//尾插3SeqListPushBack(&s,3);//尾插3SeqListPopBack(&s);//尾删SeqListPopBack(&s);//尾删SeqListPopBack(&s);//尾删SeqListPopBack(&s);//尾删SeqListPrint(&s);//打印输出顺序表SeqListPushFront(&s,6);//头插6SeqListPushFront(&s,7);//头插7SeqListPushFront(&s,8);//头插8SeqListPrint(&s);//打印输出顺序表SeqListPopFront(&s);//头删SeqListPopFront(&s);//头删SeqListPopFront(&s);//头删SeqListPrint(&s);//打印输出顺序表printf("%d\n",SeqListFind(&s,2));//找2在顺序表的位置SeqListInsert(&s,1,6);//在下标为1的地方插入6SeqListPrint(&s);//打印输出顺序表SeqListErase(&s,2);//删除顺序表下标为2的位置SeqListPrint(&s);//打印输出顺序表SeqListPushBack(&s,10);//尾插10SeqListPushBack(&s,4);//尾插4SeqListSort(&s);//排序顺序表SeqListPrint(&s);//打印输出顺序表printf("已找到！数组下标是%d\n",SeqBinarySearch(&s,0,s.size-1,10));//二分查找SeqListDestory(&s);//销毁}intmain(){TestSeqList1();return0;}

测试结果：

接口均正确；