三、顺序表的实现（升级为动态顺序表）
想要实现一个动态的顺序表，那么我们得先将我们的思路给理清晰，然后在我们的静态顺序表上进行修改
1.动态顺序表的定义
静态的顺序表是通过一个宏来进行确定一个数组的，既然是动态，那么我们就不能用宏了，我们可以使用一个指针，当然使用指针以后，我们就没法确定总容量了，所以我们还需要一个参数capacitiy称为容量
所以新的动态顺序表的定义就如下所示
代码如下
typedef int SQDateType; typedef struct SeqList { SQDateType* a; //指向动态开辟的数组 int size; //当前的有效数据个数 int capacity; //容量空间的大小 }SL;
2.动态顺序表的初始化
定义修改完后，我们就修改一下顺序表的初始化
因为a已经是一个指针了，所以说我们直接让a指向一个空指针就可以了。然后就让其他两个都变成0就行了。当然我们也可以一开始给他一块空间，当然这都无所谓了，因为我们可以在后面插入顺序表的时候就判断一下容量是否还有，如果没有容量，在那个时候在进行扩容即可
代码如下
//顺序表初始化 void SeqListInit(SL* ps) { ps->a = NULL; ps->size = 0; ps->capacity = 0; }
3.动态顺序表的尾插
我们已经初始化好了，那么现在我们就来修改一下尾插
在静态顺序表的时候，如果满了，就拦截，但是在动态版的，我们就可以进行扩容了
下面是判断是否满了
满了就得扩容，那么如何扩容呢？我们使用realloc函数，我们去查看他的信息
当然如果我们看不懂也没有关系，打开有道字典，选择计算机，复制粘贴翻译即可
他的意思就是，重新分配一个内存，因为我们的内存都是一块一块的断开的片段，所以我们就先看一看在他原来的地址上够不够我们之前的内存，如果够的化，那么就在原来的地址上原地扩容，如果不够，找一块连续的空间，将原来的数据都移动到这个新的空间上，最后将这个新的空间的地址返回，这里返回的void类型，所以需要进行强制类型转换。当然也有可能因为内存不够了，导致扩容失败。此时返回的就是NULL空指针
所以由上面的分析可以得到如下所示的代码，先对其进行扩容，然后如果内存不够扩容失败，则直接退出，如果扩容成功，则将这个地址给a这个指针，并让总容量扩大二倍，注意，我们一般习惯上扩大二倍的容量
接下来我们就是扩容成功了，然后我们需要将这个数据给放进去，然后size++
写到这一块，细心的人已经发现这里有一个bug了。当然没发现也没要紧。我们可以测试一下
为了方便测试，我们在这里先写出打印数据的接口，这个很简单，我们就直接写出来吧
我们运行一下吧，我们发现程序挂了
这可不行，我们得调试一下，来看一看究竟是哪里错了，一开始的初始化是没有任何问题的
但是当我们下一步的时候，我们发现capacity的值居然是0。这说明这个函数内部出现问题了，于是我们知道了问题，就要进入这个函数里面去寻找问题
在这一步的时候，我们发现了问题，因为我们一开始capacity是0，零乘以任何数都为0，所以程序肯定会出错
所以为了避免这个错误，我们可以在定义一个变量，就可以完美的解决了
此时我们的运行结果为，这样结果就跟我们预期一样了
至此，我们的尾插就实现了
代码如下
//顺序表尾插 void SeqListPushBack(SL* ps, SQDateType x) { //判断是否满了，如果满了，就得扩容了 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SQDateType* tmp = (SQDateType*)realloc(ps->a, newcapacity * sizeof(SQDateType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity = newcapacity; } } ps->a[ps->size] = x; ps->size++; }
当然我们也把打印函数也给出来
//打印数据 void SeqListPrint(SL* ps) { int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
4.顺序表的头插
我们实现了尾插，但是有时候也需要往头插入数据，这个该如何实现呢？
我们的想法是这样的，从后往前，一个数据一个数据往后挪动即可，玩玩不可从前往后挪，因为这样会出问题的
所以基本逻辑的实现如下所示
而对于这段代码，其实面临着和尾插一样的问题，就是空间不够了呢？所以我们需要增容，既然头插也要增容，尾插也要增容，那我们不妨将增容封装成一个函数吧，仅仅这两个函数使用，如下图所示
然后我们就可以先测试一下我们的代码
测试结果如下
我们将这段代码给出
//扩容函数 void SeqListCheckCapacity(SL* ps) { //判断是否满了，如果满了，就得扩容了 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SQDateType* tmp = (SQDateType*)realloc(ps->a, newcapacity * sizeof(SQDateType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity = newcapacity; } } } //顺序表尾插 void SeqListPushBack(SL* ps, SQDateType x) { SeqListCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; } //顺序表的头插 void SeqListPushFront(SL* ps, SQDateType x) { SeqListCheckCapacity(ps); int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; }
5.顺序表的尾删
尾部删除其实就比较简单了，只要size>0，他就可以进行删除，我们删除的思想是这样的，我们的数据都是依靠size进行管理的，所以我们只需要让size--就可以了，这样也就访问不到后面的数据了，当然我们判断size>0的时候可以使用一下暴力一点的方式。使用断言。
代码如下
//顺序表的尾删 void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--; }
测试数据如下
运行结果如下
6.顺序表的头删
我们已经实现了顺序表的尾删，那么头删呢？其实头删跟头插是非常类似的，下图是我们的流程，从左往右走，让后面的数据覆盖前面的数据即可
代码实现如下
//顺序表的头删 void SeqListPopFront(SL* ps) { assert(ps->size > 0); int start = 1; while (start < ps->size) { ps->a[start - 1] = ps->a[start]; start++; } ps->size--; }
我们使用如下的测试用例
运行结果为
