引言
经过一段时间的学习，博主也是学到了数据结构和算法这块，那么在接下来的时间里，我也将继续分享我在数据结构这块的学习心得和重点内容。那么第一个我将分享的是动态顺序表的实现，这一块内容将对大家c语言动态内存管理有一定的要求，之前博主也有介绍，如有问题还请前往: 【c语言】详解动态内存管理
一、顺序表的介绍
当谈及顺序表结构式时，我们便会引入线性表的概念，如下：
线性表（
linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。我们今天介绍的顺序表就是以类似数组结构的形式存储的
二、顺序表的两种分类
- 静态顺序表
一般使用定长数组存储数据，如下这般申请静态顺序表：
//静态顺序表 typedef int SLDataType; #define N 10 typedef struct SeqList { SLDataType arr[N];//定长数组 int size;//有效数据个数 }SList;
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。
- 动态顺序表
为了解决静态顺序表的问题，便有了动态顺序表，一般如下定义：
//动态顺序表--按需申请空间 typedef int SLDataType; typedef struct SeqList { SLDataType* head; int size;//有效数据个数 int capacity;//空间容量 }SL;
在初次动态申请内存空间时，我们便可用capacity记录空间容量，size记录已存的有效数字个数，用realloc()函数来动态开辟内存，用head来指向动态开辟的空间的起始地址，这样便可通过下表来访问顺序表元素。例如，我们想访问第三个元素：head[2]。
三、动态顺序表的一些常用接口
我们定义如下结构体，表示动态顺序表：
typedef int SLDataType; // 动态顺序表 -- 按需申请 typedef struct SeqList { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 }SL;
下面各接口函数都是基于此动态顺序表。
3.1空间容量检测
每当我们插入数据时都要检测空间剩余容量，即ps->capacity == ps->size与否，不足便要增容，如果每次写插入数据函数时都写这一段代码那就太麻烦了，所以我们封装一个这样的函数。
在此函数中要先判读ps->capacity大小，如果为0，便要赋值为4；有值时，便翻倍。
还要一点要注意的是，realloc()开辟新空间时，如果原空间后面内存不够，便会释放此空间，在其他地方重新开辟，并拷贝原始数据，所以在这我们重新定义一个指针new_p。
//空间检测 void SLcapacity_check(SL* ps) { assert(ps); if (ps->capacity == ps->size) { //判断新开辟的空间容量mewcapacity int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2; SLDataType* new_p = (SLDataType*)realloc(ps->p, sizeof(SLDataType) * newcapacity); //检测开辟成功与否 if (new_p == NULL) { printf("realloc fail\n"); exit(-1); } //赋值新空间地址，空间容量 ps->p = new_p; ps->capacity = newcapacity; } }
3.2尾插数据
在检测空间后，便可直接插入数据，相对简单就不多介绍了。
//尾插 void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLcapacity_check(ps); ps->p[ps->size] = x; ps->size++; }
3.3头插数据
在检测剩余空间后，要实现头插，便要将原始数据都后移一位，需要注意的是，要从尾节点开始后移，然后再插到下标为0的位置。
//头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLcapacity_check(ps); //原数据后移 for (int i = ps->size; i > 0; i--) ps->p[i] = ps->p[i - 1]; ps->p[0] = x; ps->size++; }
3.4尾删数据
事实上尾删数据后，我们的有效数据个数就会减少一个，那么直接
ps->size--，便可在逻辑上实现尾删。
//尾删 void SLPopBack(SL* ps) { assert(ps->size > 0); ps->size--;
3.5头删数据
对于头删数据，其实和头插极其相似。头插是从后向前拷贝数据，头删则是从前向后拷贝数据，即将第
i个拷贝到第i-1个的位置，最后再将ps->size--。如果有效数据已经为0了，那么在函数内部不会进行任何操作。
//头删 void SLPopFront(SL* ps) { assert(ps); if (ps->size > 0) { for (int i = 0; i < ps->size - 1; i++) { ps->p[i] = ps->p[i + 1]; } ps->p[ps->size - 1] = 0; ps->size--; } }
3.6寻找某个数
通过遍历顺序表，便可实现此函数，另外只需要注意一点：找到返回下标，未找到返回
-1，返回值类型为int。此函数主要为下面要介绍的两个函数服务。
//顺序表查找--返回下标 int SListFind(SL* ps, SLDateType x) { for (int i = 0; i < ps->size; ++i) { if (ps->a[i] == x) { return i; } } return -1; }
3.7指定位置插入数据
在执行插入操作前就要判断，给定的位置是否超过有效数据个数。插入部分代码就是与头插类似的版本，只不过
SListPushFront()函数是从下标ps->size-1到0的数据向后拷贝；而SListInsert()函数是从ps->size-1到pos的数据向后拷贝。// 顺序表在pos位置插入x void SListInsert(SL* ps, size_t pos, SLDateType x) { assert(ps); assert(pos <= ps->size);//指定位置不能超过有效数据个数 SLcapacity_check(ps); //此操作与头插相似，拷贝数据，再插入 int end = ps->size ; while (end > pos) { ps->a[end] = ps->a[end - 1]; --end; } ps->a[pos] = x; ps->size++; }
3.8指定位置删除数据
与头删类似，从下标为
pos+1的位置向前拷贝，最后ps->size--，其他就不多解释了。
// 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int pos) { assert(ps && pos < ps->size); //与头删相似，从下标为pos+1的位置向前拷贝 int start = pos+1; while (start < ps->size) { ps->a[start-1] = ps->a[start]; ++start; } ps->size--; }
四、小结
通过上面对动态顺序表的实现的讲解后，我们不难发现其实动态顺序表也是有很多缺点的：
1. 当空间不够时需要增容，而增容是有代价的；
2. 为了避免频繁扩容，我本每次扩2倍，这样可能导致空间的浪费；3. 顺序表要求从开始位置连续存储，那么我们在头部和中部位置插入/删除数据就需要挪动数据，这样的效率并不高
但除了一些缺点外，顺序表当然也是有优点的：
1. 顺序表支持随机访问（下标）；
2. cpu高速缓存命中率更高
