前言
现在是北京时间11月24号0点2分，天气有一些冷，我现在很困，但是博客还没写，我很想睡觉，假如我现在放弃的码字，往床上一趟，其实也不怎么样，但是我们不能有拖延症，所以干，顺便记录一下，今天世界杯小日子过的不错队赢了，然后群里的消息很是搞笑，然后我有一个好同学买2:1，买小日子不错队10块，赢了200多，跟我吹了一下牛，好了，剩下的也没啥了，咱们开始讲一讲什么是顺序表。
一、顺序表的概念
1.数据结构就是为了可以更好的存储我们的数据（所以今天我们先学的就是最简单的线性表中的顺序表）线性表就是有想同特性的数据元素的有限序列（常见的线性表有：顺序表、链表、栈、队列、字符串……）
2.顺序表（简单理解顺序表就是我们的数组），一个数组而已且顺序表此时分为两种（一种是静态的，一种是动态的），并且此时我们在往顺序表中存储数据时（这个数据是连续储存的（意思就是我们在存储数据是必须是有顺序的（假设就是要从下标为0 1 2，这三个位置开始存储,不能一会存1，一会存5，一会存8，必须连续并且有序）））
3.顺序表的概念及其结构：顺序表是用一段物理地址的连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改，反正总的凯硕顺序表就是数组，但是在数组的基础上，他还要求数据是连续存储的，不能跳跃间隔
4…我们从调用代码开始：因为要使用规范的工程，此时我们就要使用头文件这种东西（并且不使用中文为文件名），并且还要再创建一个实现接口函数的.c文件，这样才比较的合理，在头文件中准备好了一些我要用到的东西和各种数据处理功能函数的接口的声明，此时我这边就可以来实现这些接口函数了代码：(此时要知道这些接口函数的实现是在我想对应头文件中的那个.c文件中实现的，test.c文件只是为了用来调试和调用整个工程用到的)
二、结构体详解
1.因为我们在实现顺序表的时候会使用到结构体的创建，所以我们这边对结构体的创建进行一个非常详细的讲解，如图：
2.如图就是在结构体创建时我们应该要注意的点和改进的点
三、顺序表的实现
1.头文件中各种接口函数的声明
2.各种接口函数的实现
已经没有以前的干劲了，不然肯定一个一个函数打过来，现在还是容我复制一下
（1.）初始化函数的实现
void SeqListInit(SL* ps) { ps->a = NULL;//此时就是把结构体中可以控制结构体空间大小的那个指针给赋值成一个空指针 ps->size = 0; ps->capacity = 0;//然后此时这边的开始的容量可以是一个数值，不一定就是一个0，按我自己的想法（假设此时这个位置像鹏哥一样，直接给一个3，那么此时也就是多进行一个参数的传递而已，不仅要传地址，还要传一个变量而已，然后接收的时候也多用一个参数接收就行） }
（2.）尾插函数的实现
void SeqListPushBack(SL* ps, SLDataType x) { SeqListCheckCapacity(ps);//这边为什么不能传地址 //尾插的直接放元素法（什么都不考虑的情况下就是以下的放数据的方法） ps->a[ps->size] = x;//将此时的这个a指针直接就指向此时的最后一个元素（也就是size，因为size此时就是代表总元素的个数，它就是最后一个），然后size++就代表我在最后一个元素后面再插入一个元素 ps->size++; }
（3.）容量检查函数
此时的尾插时为了防止造成非法访问，此时就嵌套了一个检查容量的函数
void SeqListCheckCapacity(SL* ps) { //此时应该要多方面考虑，此时的顺序表中到底有没有空间，有就直接放，无就申请空间，空间满了就扩容空间 if (ps->size == ps->capacity) { //此时满足这个条件的话就有两种情况（1.根本就没有空间 2.此时的空间满了） //所以这边就就要考虑进行增加空间了，不管是无空间的增加还是满了的增加，我这边就一定要进行一步空间的增加 //int newcapacity = ps->capacity * 2;//但是此时这种写法就没有考虑到无空间的情况（0），所以这样写不好，要改进 int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//这步真的是很有道理，要多模仿 //下面这步就是表明此时如果没有空间或者空间不足我就可以进行动态内存的扩容 SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//这边有一个小知识点，就是你扩容的空间不应该是元素的个数，应该是字节数（所以一定要乘上相应的类型的字节才对） //然后这边按照我们的动态内存分配中的基础知识，我们这边肯定是要进行一个指针的判断（也就是看一下这个内存是否开辟成功） if (tmp == NULL) { printf("realloc fail\n"); exit(-1);//这边不用return 0 ;因为这边用这个exit是一个系统程序，可以直接退出整个程序，所以更好（然后又因为这边的函数的返回类型是void，所以不能用return） } //程序如果来到这个位置就表明此时是增容成功了，所以此时我就可以对这个空间进行使用了 ps->a = tmp; ps->capacity = newcapacity; } }
（4）.打印函数的实现
void SeqListPrint(SL* ps) { int i; for (i = 0; i < ps->size; i++) { printf("%d ",ps->a[i]); } printf("\n"); }
（5.）动态内存的释放（销毁空间函数的实现）
void SeqListDestory(SL* ps) { free(ps->a); ps->a = NULL;//这步就是为了防止别人误使用了这块空间，所以直接赋值成空指针就行 }
（6.）尾删功能的实现（删除最后一个元素）
void SeqListPoptBack(SL* ps) { //这些什么什么删什么什么插都可以通过画图得到具体的解题方法，所以一定要多画图哦 //ps->a[ps->size - 1] = 0;//这个就是为了找到size个数据中的最后一个数据，然后把这个数据赋值成0，然后整个size的数据的个数减一，这样就代表删除了一个数据的意思 //但是其实上面这句话是可以不要的，直接进行size的减减就已经可以达到删除最后一个数据的功能了 if (ps->size > 0) { //上面这个条件也可以该成（一个粗暴的方式：assert(ps->size > 0);） ps->size--;//但是此时这边要考虑全面一些（就是我在执行减减操作的时候，此时的顺序表中是要有数据的（也就是此时的size一定是要大于0的，不然就会造成越界访问了），所以这边一定还要给一个条件才行） } }
（7.）头插功能的实现、
void SeqListPushFront(SL* ps, SLDataType x) { SeqListCheckCapacity(ps);//这样我的头插功能就不会出问题了 //此时头插就会涉及到鹏哥以前讲的那个从前完后插入还是从后往前插入的问题的，所以此时进行头插我们就要从后插入，不能从前往后插入了 //此时又涉及到代码的规范（再也不用a b c……了） //1.我的写法 int i; int end = ps->size - 1; for (i = 0; i < ps->size; i++) { ps->a[end + 1 - i] = ps->a[end - i];//这个就表示把最后一个往前移一个下标的意思 } //此时移动完之后就要到我的最关键的一步，也就是在最前面插入我的数据 ps->a[0] = x; ps->size++;//移动完就减减就行 } //另一种写法 //{ // int end = ps->size - 1; // while (end >= 0) // { // ps->a[end + 1] = ps->a[end]; // end--; // } // ps->a[0] = x; // ps->size++; // // }
（8.）头删函数的实现
void SeqListPopFront(SL* ps) { //头删首先要有数据，所以这边要有一个条件 //1.我自己的写法（虽然一开始没写对，但是还是我自己的） if (ps->size > 0) { int i; //int begin = ps->size - 1;错误写法 int begin = 1; for (i = 0; i < ps->size; i++) { //ps->a[begin - 1 - i] = ps->a[begin - i];//不敢这样写，这样写的意思就会变成把最后一个数据赋值size次而已，并不是我要的数据的向前移动 ps->a[begin - 1 + i] = ps->a[begin + i]; } ps->size--; } //2.另一种写法 assert(ps->size > 0); int begin = 1; //此时这个begin的位置是可以变的，只是下面的那个位置的转换顺便跟着换一下就行了 //int begin = 0; //while (begin < ps->size-1) while (begin < ps->size)//就是为了控制次数而已 { ps->a[begin - 1] = ps->a[begin]; //ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; }
（9.） 查找函数的实现 O(N)的时间复杂度 (暴力求解)
int SeqListFind(SL* ps, SLDataType x) { int i; for (i = 0; i < ps->size; i++) { if (ps->a[i] == x)//这个就是表示找到了(这边if里面的==又给你吃掉一个) { return i;//返回下标 } } }
（10.）任意位置数据插入函数
void SeqListInsert(SL* ps, int pos, SLDataType x) { SeqListCheckCapacity(ps); if (pos > ps->size || pos < 0)//这个范围都是非法访问，所以错误 { printf("pos invalid");//不能用perror return; } //这个assert(pos>=0 || pos<=ps->size);这个就是检查此时传过来的条件是否符合括号内的要求，不符合就报错，符合就继续往下走 else { //其实这个任意位置插入跟我的头插尾插是非常像的，只不过是在我要求的pos的位置进行插入而已 //1.我的写法 int i; int end = ps->size - 1; for (i = 0; i <= ps->size - pos; i++)//这步本来可以用i=pos到ps->size,但是如果这样写，就会导致我的循环中下标不好调整，所以这边写成这样才是最好的，有点细节的感觉 { ps->a[end + 1 - i] = ps->a[end - i]; } ps->a[pos] = x; ps->size++; } //2.老师的写法 //{ //assert(pos >= 0 || pos <= ps->size); //SeqListCheckCapacity(ps); //int end = ps->size - 1; //while (end >= pos) //{ // ps->a[end + 1] = ps->a[end]; // end--; //} //ps->a[pos] = x; //ps->size++; //} }
（11.） 任意位置数据删除函数
void SeqListErase(SL* ps, int pos) { assert(pos >= 0 || pos < ps->size); int i; int begin = pos + 1; for (i = 0; i < ps->size; i++) { ps->a[begin - 1 + i] = ps->a[begin + i]; } ps->size--; }
3.测试文件的实现：目录省略
#include<stdio.h> #include "SeqList.h" //1.测试尾插和尾删功能 void TestSeqList1() { SL s1; SeqListInit(&s1);//因为我想调用这些接口函数，所以这边我们一点要传地址，这样才能将接口函数外部的值进行改变，不然不传地址的话，出了接口函数就会销毁，无法改变外部数据 //1.此时就完成了我结构体的初始化（就是使我的结构体中的变量不在是一个地址，而是一个整形数字0） //2.并且此时完成了初始化，那么就轮到使用结构体这一步了 //3.使用结构体就是调用结构体数据中相应的函数的接口函数来进行对数据的存储 //4.调用SeqListPushBack接口（但是我还没有实现这个函数的功能，所以此时要实现功能去） //5.尾插功能（将1到10的数据都给插入到我的顺序表中就行了） SeqListPushBack(&s1, 1); SeqListPushBack(&s1, 2); SeqListPushBack(&s1, 3); SeqListPushBack(&s1, 4); SeqListPushBack(&s1, 5); SeqListPushBack(&s1, 6); SeqListPushBack(&s1, 7); SeqListPushBack(&s1, 8); SeqListPushBack(&s1, 9); SeqListPushBack(&s1, 10); //6.这个就是尾删功能 SeqListPoptBack(&s1); SeqListPoptBack(&s1); //7.这个就是打印功能 SeqListPrint(&s1);//打印函数实现完之后一定要懂得把它拿过来用，不然你写来干嘛 //8.这个就是动态内存释放功能 SeqListDestory(&s1);//使用完动态开辟的内存之后，就需要这个函数来释放空间了，所以这边要调用一下这个函数 }
//2.测试头插和头删功能 void TestSeqList2() { //定义结构体变量 SL s1; //初始化结构体 SeqListInit(&s1); //尾插 SeqListPushBack(&s1, 1); SeqListPushBack(&s1, 2); SeqListPushBack(&s1, 3); SeqListPushBack(&s1, 4); SeqListPushBack(&s1, 5); //头插 SeqListPushFront(&s1, 10); SeqListPushFront(&s1, 20); SeqListPushFront(&s1, 30); SeqListPushFront(&s1, 40); //头删 SeqListPopFront(&s1); //打印 SeqListPrint(&s1); //销毁 SeqListDestory(&s1); }
//3.测试任意插入和查找功能 void TestSeqList3() { SL s1; SeqListInit(&s1); //尾插 SeqListPushBack(&s1, 1); SeqListPushBack(&s1, 2); SeqListPushBack(&s1, 3); SeqListPushBack(&s1, 4); SeqListPushBack(&s1, 5); //任意位置插入元素（其实这个函数是可以替代头插和尾插的，头插就是pos为0，尾插就是pos为size的位置） SeqListInsert(&s1, 3, 10); //任意位置插入元素配合上查找功能的使用 int pos = SeqListFind(&s1, 4);//接收找到的那个元素的下标 { if (pos != -1) { SeqListInsert(&s1, pos, 40);//这步的意思并不是把4换成了40，而是在4的前面插入一个40，如果想要把4替换成40的话就应该要找5的下标 } } //打印 SeqListPrint(&s1); //销毁 SeqListDestory(&s1); }
//4.测试任意位置删 void TestSeqList4() { SL s1; SeqListInit(&s1); //尾插 SeqListPushBack(&s1, 1); SeqListPushBack(&s1, 2); SeqListPushBack(&s1, 3); SeqListPushBack(&s1, 4); SeqListPushBack(&s1, 5); //任意位置删 SeqListErase(&s1, 0);//所以此时有了这个任意位置删除那么此时的我就可以把头删尾删给替换掉了，替不替随我 //寻找指定元素的下标 int pos = SeqListFind(&s1, 4); { if (pos != -1) { SeqListErase(&s1, pos);//这样就是删除指定那个元素 } } //打印 SeqListPrint(&s1); //销毁 SeqListDestory(&s1); }
int main() { //不先写菜单，先写每一块的功能（方便我们调式） TestSeqList1(); TestSeqList2(); TestSeqList3(); TestSeqList4(); return 0; }
此时这样我们分成了4个部分写，每写一个函数我们就可以非常方便的进行调试，所以这样写是非常合理的
