1.什么是顺序表
这篇文章我们来讲一下基础数据结构的顺序表，相信大家在学习C语言的时候接触过数组这种数据结构，但是它又跟顺序表又有什么关系呢？
我们知道数组的内存是连续的，一个下标对应着一片内存，而且支持随机访问。这就叫做顺序结构，而数组就是这种结构。果不其然我们的顺序表也是这种结构，但是顺序表就是数组吗？答案是是的，只是其描述角度不同。
- 线性表是数据结构中的逻辑结构。
- 线性表采用顺序存储的方式存储就称之为顺序表。
- 数组是顺序表在实际编程中的具体实现方式之一。
顺序表的优势和缺点
前面介绍完了顺序表的定义，我们说说它的优势和不足的地方：
我们知道顺序表的优势如下 ：
支持随机访问，查找速度O(1)
空间利用率高
那缺点就显而易见了：
增加和删除的速度较慢，如果要在中间插入一个元素则需要挪动后面的所有的元素，造成多余的时间开销，删除同理。 时间复杂度是O（n）, 如果不经常删除和改动元素则不推荐使用顺序表这种顺序结构，而用链表则效率更高。
顺序表的长度需要提前指定，长度受到限制。 有同学说我可以进行动态内存分配啊，这样不就行了？其实动态内存分配是解决了长度受限的问题，但存在一个潜在的问题，顺序表扩容我们一般一次就扩充两倍，但是用的可能没有这么多，那多出来的内存空间不就浪费了吗？这是我们说的多余的内存开销问题。
顺序表预备知识
动态内存分配(malloc)
结构体(struct)
顺序表的代码实现
以下为所有的代码实现：
函数接口：
void Sequential_table_deletion(SL*ps,int pos); void Sequential_table_lookup(SL*ps,int pos,int x); //顺序表中插入数据 int Seqlistwo(SL*ps,int n);//顺序表中查找元素 void SeqlistPopBack(SL*ps,int n);//尾插函数 void Array_expansion(SL*ps); //扩容 void Seqlistfis(SL*ps);//(3) //头删 void Seqlistpuch(SL*ps,int n); // 头插法 void Array_expansion(SL*ps) //扩容
结构体定义：
typedef struct Seqlist { int *a; int size; //表示数组中存储了多少个数据 int ciap;// 数组能实际存储的容量大小 }SL;
顺序表头部插入
顺序表的头部插入就是先把顺序表的第一个元素空出来，然后把所有的数据往后挪动达到头插的目的
void Seqlistpuch(SL*ps,int n) // 头插法 { Array_expansion(ps); //检查增容 int end = ps->size-1; while(end>=0) { ps->a[end+1]=ps->a[end]; end--; } ps->a[0] = n; ps->size++; }
顺序表的销毁
顺序表的销毁就简单了，只要当前表不为空指针，一直释放就可以了
void SeqListDestroy(SeqList* ps) { //断言 assert(ps); //释放空间 if (ps->a != NULL) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->size = 0; } }
顺序表的头插
在使用头插函数前，我们需要检查当前顺序表的空间是否足够我们使用；然后再对顺序表进行操作，当然我们传进来的参数不能为空指针，我们把长度定义为end,让它后一个数等于前一个数，同时长度-1.我们的头插就完成了。
void SeqListPushFront(SeqList*ps,SLDateType x) { 断言 //assert(ps); 检查扩容 //SeqListCheck(ps); //int end = ps->size-1; 挪动数据 //while (end >= 0) //{ // ps->a[end + 1] = ps->a[end]; // end--; //} 在头部插入数据 //ps->a[0] = x; //ps->size++; SeqListInsert(ps, 0, x); }
顺序表的尾删
当前下标大于0 ，长度-1
void SeqListPopBack(SeqList* ps) { //断言 assert(ps->size>0); ps->size--; }
顺序表的尾插
所有元素向前挪动一个位置，长度+1
void SeqListPushBack(SeqList* ps, SLDateType x) { //断言 assert(ps); //检查扩容 SeqListCheck(ps); //插入数据 ps->a[ps->size] = x; ps->size++; }
顺序表的任意位置插入
顺序表的任意插入，这个比头部或尾部插入有点麻烦，不过实现起来也不难。我们先要断言一下要插入的下标的有效性。
void removeElem(STL*ps,substitute pos,substitute elem)//在指定位置插入元素 { assert(pos<0&&pos>ps->size); int i = 0; for(i = 0;i<ps->size;i++) { ps->a[i]=ps->a[i-1]; } ps->a[pos]=elem; ps->size++; }
顺序表的查找
顺序表的查找和数组是一样的，如果当前顺序表的元素等于要查找的值，则立即返回该数据的下标。否则返回空。
int SeqListFind(SeqList* ps, SLDateType x,int begain) { assert(ps); int i = 0; //遍历数组进行查找 for (i = begain; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } //查找不到，返回-1 return -1; }
顺序表的打印
void Sequential_table_printing(STL*ps) { int i = 0; for(i = 0;i<ps->size;++i)//打印顺序表的元素 { printf("%d ",ps->a[i]); } }
顺序表的打印和数组是一样的，通过访问其下标。
