1. 顺序表的概念：
顺序表其实就是数组的升级版，也就是在数组的基础上，要求数据是连续存储的，并且是从头开始的，不能跳跃间隔。
2.顺序表接口函数实现：
3.顺序表的缺陷
一般来说，对顺序表的操作有顺序表的初始化，头插，头删，尾插，尾删，在某个位置插入或删除，查找某个值，还有销毁等功能，下面来逐一实现：
2.1首先看顺序表的结构定义：
typedef int SeqListDataType; typedef struct SeqList { SeqListDataType size; SeqListDataType* a; // 顺序表指针 SeqListDataType capacity; }SL;
2.2顺序表的初始化
void SeqListInit(SL* ps) { ps->size = ps->capacity = 0; ps->a = NULL; } * ps) {
2.3检查顺序表容量
void SeqCheckCapacity(SL* ps) { //1.满了，需要增容，2.容量为0，需要增容 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; SeqListDataType* tmp = realloc(ps->a, sizeof(SeqListDataType) * newcapacity); assert(tmp != NULL); ps->a = tmp; ps->capacity = newcapacity; } }
2.4顺序表尾插
void SeqListPushBack(SL* ps, SeqListDataType x) { //检查容量 SeqCheckCapacity(ps); int end = ps->size; //找到尾部了，插入数据 ps->a[end] = x; ps->size++; }
2.5顺序表尾删
void SeqListPopBack(SL* ps) { //检查ps->size有效性 assert(ps->size > 0); ps->size--; }
2.6顺序表头插
void SeqListPushFront(SL* ps, SeqListDataType x) { SeqCheckCapacity(ps); //检查容量 //1.挪动数据 int begin = ps->size - 1; while (begin >= 0) { ps->a[begin + 1] = ps->a[begin]; --begin; } ps->a[0] = x; ps->size++; }
2.7顺序表头删
void SeqListPopFront(SL* ps) { assert(ps->size > 0); int begin = 0; //if (ps->size == 1) //{ // ps->size--; //} //只有一个节点的情况(可有可无，只有一个节点相当于尾删了) while (begin < ps->size - 1) { ps->a[begin] = ps->a[begin + 1]; ++begin; } ps->size--; }
2.8顺序表在某个位置插入
void SeqListInsert(SL* ps, SeqListDataType pos, SeqListDataType x) { assert(pos >= 0 && pos <= ps->size); int begin = ps->size-1; while (begin >=pos) { ps->a[begin + 1] = ps->a[begin]; --begin; } ps->a[pos] = x; ps->size++; }
2.9顺序表在某个位置删除
void SeqListDelet(SL* ps, SeqListDataType pos) { assert(pos >= 0 && pos < ps->size); int end = pos + 1; while (end < ps->size) { ps->a[end - 1] = ps->a[end]; ++end; } ps->size--; }
2.10顺序表查找某个元素
SeqListDataType SeqListFind(SL* ps, SeqListDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; } pe x)
2.11打印顺序表的元素
void SeqListPrint(SL* ps) { for(int i=0;i<ps->size;i++) { printf("%d->", ps->a[i]); } printf("NULL\n"); }
2.12顺序表的销毁
void SeqListDestroy(SL* ps) { free(ps->a); ps->a = NULL; }
接口函数的声明
void SeqListInit(SL* ps); void SeqCheckCapacity(SL* ps); void SeqListPushBack(SL* ps, SeqListDataType x); void SeqListPushFront(SL* ps, SeqListDataType x); void SeqListPopBack(SL* ps); void SeqListPopFront(SL* ps); SeqListDataType SeqListFind(SL* ps, SeqListDataType x); void SeqListInsert(SL* ps, SeqListDataType pos, SeqListDataType x); void SeqListDelet(SL* ps, SeqListDataType pos); void SeqListPrint(SL*ps); void SeqListDestroy(SL* ps);
3.顺序表的缺陷
1.顺序表的容量如果满了需要扩容，扩容是要付出代价的：
1.1原地扩容：在原空间的基础上，向后进行扩容，代价较小。
1.2异地扩容：在原空间的基础上扩容时空间不足，所以需要在内存中另外寻找一块新的大小的空间来扩容，代价较大。
2.当空间不足时扩容，一般我们会扩容两倍，所以会有内存空间的浪费。
