数据结构-（顺序表篇）_数据结构顺序表
赞
踩
目录
简介
顺序表：顺序表可以通俗的理解成数组。
但是顺序表分为1：可变顺序表
2：固定顺序表
定义的顺序表时候不管是动态的还是静态的，都要以结构体的形式来进行定义（因为一个顺序表中的成员变量很多）
顺序表的定义
1：静态顺序表的定义
- #include<stdio.h>
- #include<stdlib.h>
- #define N 1000 //顺序表的大小 静态才会需要 设置一个固定大小 后期添加元素还需要空间时 ,继续增容
- typedef int DataType; //DataType是一个数据的类型 , 如果需要更改类型的话,只需要将前面的int改掉就行
-
-
-
- //静态顺序表：空间是固定的 ， 缺点:给大了浪费，给小了不够
- typedef struct SeqList { //使用typedef来将结构体进行起别名
- DataType a[N]; //数组的总大小 我们总是要照顾到数组的大小,因为不知道会添加多少元素
- DataType size; //数据存储的数据大小
- }SQL; //SQL就是对顺序表的别名
对于上述的静态数据表我们了解到：由于是静态的顺序表，所以导致内存空间总是一定的，空间的不确定，导致数据存储的时候总是出现多余的空间(空间开大了)这种情况和空间不足(空间开小了)的这种情况，这就是“开辟多了浪费，开辟少了不够”的解释。
2：动态顺序表的定义
- #include<stdio.h>
- #include<stdlib.h>
- typedef int DataType; //可以随时改变存储数据的类型
-
-
-
-
- //动态顺序表：空间是动态的，可以随用随时开辟
- typedef struct SeqList {
- DataType* a; //动态开辟的顺序表 柔性数组（空间大小可变）
- int size; //顺序表目前所存在的元素的个数 , size的功能就是提醒我们此时顺序表(数组)内存储了多少个元素 ,用来和Capacity来进行比较 , 看是否需要动态扩容
- int Capacity; //顺序表的总大小
- }SQL; ///结构体重命名
-
当然我们肯定不能只仅仅对于顺序表只有定义的单个操作，不能说循序表创建出来却不能用，这就很可笑了，于是乎我们就有了“接口”的存在，所谓“接口”通俗的来说就是实现的功能，我们创建顺序表，通过调用接口来获得其中的功能，但是顺序表需要那些接口呢？
3：接口的分类：
顺序表的接口无非就是：初始化，增删改查（只不过增删改查的位置有区别）
在这里先把需要的接口放在下面：
void SeqListInit(SQL* ps); //初始化
void SeqListDestroy(SQL* ps); //顺序表销毁
void SeqListPushFront(SQL* ps , DataType x); //头插
void SeqListPushBack(SQL* ps , DataType x); //尾插
void SeqListPopFront(SQL* ps); //头删
void SeqListPopBack(SQL* ps); //尾删void SeqListPrint(SQL* ps); //数据打印，用于查看数据
void CheckCapacity(SQL* ps); ///检查顺序表长度，若满或空就开始增容
bool SeaListFind(SQL* ps, int key); //在顺序表中寻找元素
void SeqListBeforeInsert(SQL* ps, int pos, DataType x); //在指定的位置前面插入元素void SeqListAfterInsert(SQL* ps, int pos, DataType x); //在指定的位置后面插入元素
void SeqListBeforeEarse(SQL* ps, int pos) //在指定的位置前面删除元素
void SeqLisAfterEarse(SQL* ps, int pos) //在指定的位置后面删除元素
从现在开始所有的接口都是针对于动态数组所使用的
3.1： 顺序表初始化：
void SeqListInit(SQL* ps); //初始化
这就是初始化的接口，但是具体的功能怎么实现呢？请看：
- void SeqListInit(SQL* ps) //初始化 想要初始化的结果与实参是相互匹配的，那就必须传递结构体指针
- {
- //结构体成员变量的访问直接使用.来访问结构体的成员变量
- ps->a = NULL; //此时的动态顺序表就是NULL
- ps->Capacity = 0; //此时的动态顺序表的总大小为0
- ps->size = 0; //此时的动态顺序表的元素个数为0
- }
温馨提示：传递的接口的功能如果想要与实参相匹配（能够改变实参的方式）就去传递结构体指针，因为只有地址一致，才能被正确地改变内存中的数据。
3.2 ：顺序表尾插
void SeqListPushBack(SQL* ps , DataType x); //尾插
那么顺序表的尾插该如何实现呢？对于是否需要扩容有以下两种情况：
具体实现代码在下面的“代码段”中呈现！！！
1：刚刚初始化，顺序表为空的时候：此时数据存储的个数 , 和线性表的容量大小都是0
2：顺序表已经满了的时候（满了的时候会选择2倍扩容）：
详细解释说明都在代码内部
- void SeqListPushBack(SQL* ps, DataType x) //尾插
- {
- //当我们需要尾插的时候，就必须注意一个问题，那就是这个顺序表是不是满的。
- //如果是满的，那就必须开辟空间来存储数据（在这里空间满不满还有一个小的问题）
- // 1：如果空间正如初始化的那样，大小是0并且数据存储量也是0的话，那就必须开辟一个新的空间来放置数据
- // 2：如果空间不是刚开始的初始化，而是已经满了的情况，此时size = Capacity,我们就需要给他扩容到2倍的大小
- //如果是不满的，那就直接存入数据
- if (ps->size == ps->Capacity) {
- //第一种情况：刚开始初始化，size = Capzcity = 0
- int newCapacity = (ps->Capacity == 0) ? 4 : ps->Capacity * 2;
- //如果初始化的大小是0的话，那就开辟4个默认大小的长度，但是要是数据长度与顺序表总长度一
- 致的话（也就是满了的情况），此时就扩容2倍，Tips：扩容2倍是最经济的做法
- DataType* tmp = (DataType*)realloc(ps->a, newCapacity * sizeof(DataType));
- //先开辟一个新的柔性数组的长度，用来后面直接存储到顺序表的长度中去
- if (tmp == NULL) {
- printf("realloc Failed!");
- exit(-1); //遇到动态开辟内存失败的情况，就自动地退出，-1为异常退出，0为正常退出
- }
- //现在是开辟成功的情况
- ps->a = tmp; //将柔性数组直接传递到原来的顺序表中，
- ps->Capacity = newCapacity; //将新的数组长度赋值到旧的顺序表中 ,此时的顺序表的长度就是新的柔性数组的长度
-
- }
- ps->a[ps->size++] = x; //将数据直接存储到顺序表中，并且让顺序表的内部的实际元素数量+1
-
-
- }
3.3： 顺序表打印
我们经常写出来的接口实现了什么功能，我们想要查看的时候，就可以直接调用此打印的接口
顺序表的打印有两种形式：1：指针传递 2：结构体传递
1： 传递结构体指针版本：
void SeqListPrint(SQL* ps); //数据打印，用于查看数据 传递
2：传递结构体本身版本：
void SeqListPrint(SQL ps); //数据打印，用于查看数据
1： 传递结构体指针版本：
但是有一说一 , 传递结构体指针是一个很冒风险的做法 ,而且也不建议 , 因为一旦传入结构体的指针 , 那么我们使用结构体进行查询数据的时候 , 不经意间如果操作有误的话 , 就会影响顺序表本身 , 因为指针传递会改变顺序表中原有的数据 ,这是一个比较不推荐的做法 ,我们只需要打印数据 , 并不需要修改数据.
- //1：对于指针结构体的传递就会做到自同步的作用（形参跟着实参走）
- void SeqListPrint(SQL* ps) //数据打印，用于查看数据
- {
- int i = 0;
- while (i < ps->size) { //用i来查看顺序表的具体位置，但是i也就是指针的偏移量，偏
- 移量就像是数组的下标一样
- if (i == ps->size - 1) { //当数组的具体位置是在倒数第二个的位置的时候，就打印如
- 下的内容
- printf("%d ", ps->a[i]);
- }
- else {
- printf("%d -> ", ps->a[i]); //当数组的具体位置是非最后一个的时候，就直接打印此内容
- }
- i++;
- }
- }
2：传递结构体本身版本：
如果我们传递的时候 , 只仅仅传递结构体
- //对于直接传递结构体的函数来说，可以直接利用结构体的姓名再加以使用（.）成员访问符
- 来直接访问结构体成员
- void SeqListPrint(SQL ps) //数据打印，用于查看数据
- {
- int i = 0;
- while (i < ps.size) { //用i来查看顺序表的具体位置，但是i也就是指针的偏移量，偏移
- 量就像是数组的下标一样
- if (i == ps.size - 1) { //当数组的具体位置是在倒数第二个的位置的时候，就打印如
- 下的内容
- printf("%d ", ps.a[i]);
- }
- else {
- printf("%d -> ", ps.a[i]); //当数组的具体位置是非最后一个的时候，就直接打印
- 此内容
- }
- i++; //每次打印完之后 , 我们就要让i自增一次 , 为的就是为了避免结构体的数据一直处于一个位置,而不移动的情况
- }
- }
3.4：顺序表销毁
顺序表销毁的主要目的就是为了释放内存，当功能实现完了之后，如果不需要数据的时候，就可以清除内存空间，释放内存。
void SeqListDestroy(SQL* ps); //顺序表销毁
代码如下：
- void SeqListDestroy(SQL* ps) //顺序表销毁
- {
- free(ps->a); //先释放空间使其内部的数据消失
- ps->a = NULL; //再让这个顺序表指向空指针
- ps->size = ps->Capacity = 0; //让顺序表存储的数据量和总大小都赋值0，使其内部没有一个元素
- （因为内部的元素已经被释放了（free））
-
- }
有很多同学就会问了 , 那你自己直接将数组置空了 , 那已经保留的元素留在了内存空间中成了垃圾数据了 , 对于这个疑问我觉得大可不必担心 , 内存空间不管在任何时候 , 只要你想要使用数据 , 其实底层都是垃圾数据 , 你得重新赋值(或者置空之后再去使用) , 这就是为什么我们经常使用指针的时候一直强调必须要先初始化指针 , 把指针用的时候先开辟好内存 , 再去赋值 , 或者不要定义指针但是不给他初始化,这就造成了野指针的问题.
3.5 ：顺序表尾删
void SeqListPopBack(SQL* ps); //尾删
顺序表的尾删分两种情况：
1：顺序表本身已经为空，要是继续删除的话，就会出现数组越界的情况（当ps->size == 0时，不能再删减元素，否则就会ps->size == -1,数组越界）
2：顺序表不为空，继续删除
继续讨论一下顺序表为空的情况下，如何阻止顺序表继续删除元素而造成数组越界的问题
第一种方式：温柔的方式——使用if语句，当不符合条件的时候，就什么都不做
- void SeqListPopBack(SQL* ps) //尾删
- {
- //先来判断此顺序表是否为空？若为空，那就不能让他继续进行尾删操作，否则将数组越界
- //方式一：使用if限制条件，当顺序表为空时直接跳过函数本身，不去执行此函数
- if (ps->size ==0) //如果size = 0还能进去继续删减的话，那么就会删减到-1的位置，就会数
- 组越界
- {
- break;
- }else{
- ps->a[ps->size - 1] = NULL; //先将内部的元素置空
- ps->size--; //直接将顺序表中的
- }
- }
第二种方式：assert断言，当顺序表继续删除元素的时候，要是遇到数组越界的情况的时候，就自己直接出现警告。
- void SeqListPopBack(SQL* ps) //尾删
- {
- //先来判断此顺序表是否为空？若为空，那就不能让他继续进行尾删操作，否则将数组越界
- //方式2：使用assert断言来直接跳出编译错误
- assert(ps->size > 0); //当符合条件ps->size > 0的时候就正常运行，一旦ps->size == 0的时
- 候就自动警告，因为此时已经准备要数组越界使得下标变为-1了
- ps->a[ps->size - 1] = NULL; //先将元素置空
- ps->size--; //然后再将顺序表中的元素的数量减少1个
-
- }
3.6 ：顺序表头插
顺序表头插的时候必须将顺序表所有的数都往后挪动一位，留出第一个元素的位置，为准备插入而做准备。
那我们挪动之后 , 就需要把需要插入的元素插入到下标为0的位置了
void SeqListPushFront(SQL* ps , DataType x); //头插
插入一句：因为插入的时候，我们并不知道顺序表是否仍然有内存，如果有内存的话，那就直接插入，要是没有内存的时候，那就开辟一片内存来供顺序表继续头部插入
也就是说 , 在插入数据之前 , 看一下顺序表的内存空间是否满了 , 如果满了的话 , 那么我们就需要去开辟一个更大的空间(一般是2倍) , 来去存储数据元素
那么还会遇到一种情况 , 就是我们刚刚初始化完顺序表之后 , 要是想要头插的话 , 是不是就会遇到 , 空间大小为0的情况 , 那么我们此时再写一个接口来判断一下顺序表的容量是否为0 , 要是为0的话 , 我们就需要扩容 , 还有一种情况就是我们要判断一下顺序表是不是已经满了 , 要是满了的话, 同样需要开辟新的空间来存储数据 , 于是我打算写一个直接判断顺序表空间大小的函数接口 , 来判断顺序表的目前容量大小情况.
此时的检查顺序表的大小的函数接口如下
void CheckCapacity(SQL* ps); ///检查顺序表长度，若满或空就开始增容
- void CheckCapacity(SQL* ps) {
- if (ps->Capacity == ps->size) { //如果顺序表的内存中的元素数 == 总大小 或者两者
- 都等于0的时候，就开始扩容
- int NewCapacity = (ps->Capacity == 0) ? 4 : ps->Capacity * 2;
- //创建出来的新顺序表长度在检查的时候，如果结构体指针ps的大小为0的时候，那就开辟4个大小的内
- 存，要是满了的话，那几句扩容2倍
- DataType* tmp = (DataType*)realloc(ps->a , NewCapacity * sizeof(DataType));
- // 将新顺序表准备好，将上述的是否扩容的大小准备好，准备为新顺序表进行扩容
- if (tmp == NULL) { //如果扩容失败
- printf("realloc Failed!");
- exit(-1); //exit的内部若为-1的话，那就直接退出，若为0的时候，就继续执行
- }
- ps->a = tmp; //将新的顺序表放置在旧的顺序表中
- ps->Capacity = NewCapacity; //将新的扩容后的长度，放置在旧的顺序表长度中，完成扩容
- }
- }
具体实现：
- //比较麻烦的头部插入：
- //
- void SeqListPushFront(SQL* ps, DataType x) //头插
- {
- /*头插两种情况：
- 1：如果准备头插的时候若为空顺序表的时候
- 2：准备头插的时候不为空的顺序表的时候*/
-
-
- //1：如果准备头插的时候若为空顺序表的时候
- if (ps->size == 0) {
- CheckCapacity(ps);
- ps->a[ps->size++] = x; //直接插入数据在第一个元素的位置
- }
- //2：准备头插的时候不为空的顺序表的时候 * /
- else {
- //首先应该先让所有的数都往后挪动一位，为头部准备要插入的数据留出位置
- int end = ps->size - 1; //end为数组下标的最后一位
- while (end >= 0) //当一直挪动到第一个元素的位置的时候，就停止，准备插入数据
- {
- ps->a[end + 1] = ps->a[end];
- end--;
- }
- //此时就全部挪动完毕了,但是此刻的end的大小已经等于-1了
- ps->a[0] = x; //把数据放置到头部的位置
- ps->size++; //数据个数++
- }
- }
或者使用另外一种更为简便的方式来插入头部数据
- //较为方便的头部插入
- void SeqListPushFront(SQL* ps, DataType x) {
- CheckCapacity(ps); //若为空就扩容空间，若不为空什么也不干
- int end = ps->size - 1;
- for (int i = end; i >= 0 ; i++) {
- ps->a[end + 1] = ps->a[end];
- }
- //此时所有的数据就都已经挪动完毕了
- ps->a[0] = x; //放入数据
- ps->size++; //数据量+1
- }
3.7：顺序表的头删
顺序表的头删是有两种情况的：
1：顺序表已经为空
当顺序表为空的时候 , 我们必须使用assert来断言一下 , 否则我们直接删除头结点的话 , 就会出现数组越界 , 就像是顺序表size = -1的情况
2：顺序表不为空
顺序表不为空的时候 , 就可以直接进行头删
这两种情况的具体代码实现在下方呈现：
void SeqListPopFront(SQL* ps); //头删
- void SeqListPopFront(SQL* ps) //头删
- {
- //想要删除一个头部的数据，最简单的方法就是直接让后面的数据覆盖它，但是覆盖的方式应该是从第二个数据开始
- //要是从顺序表的最后一个元素开始往前覆盖的话 , 就会导致数据全部出错
- // 例如: 1 2 3 4 5
- // 如果从后往前开始覆盖的话就会出现这种情况
- // 2 3 4 5 5
- // 这种情况就会违背我们头删的想法 , 导致数据全部出错
- //但是当顺序表已经为空的时候，就不能进行头删了
- assert(ps->size > 0); //当顺序表的长度为0的时候，就说明顺序表为空，此时要是继续删除头
- 部元素的话就会越界访问，此时需要断言来警告
-
- for (int i = 0; i < ps->size - 1; i++) { //最后一个元素等到i = ps->size - 1的时候就
- 会被覆盖到前面去，最后一个元素的位置不需要覆
- 盖，直接删除就好了
- ps->a[i] = ps->a[i + 1];
- }
- ps->size--; //已经删除一个元素了 , 那就更新一下此时顺序表的内部状况
- }
3.8： 顺序表中查找元素
在顺序表中寻找元素，只需要挨个遍历，看是否有元素与需要寻找的元素的数值一致，如果有一致的就返回true，如果没有则返回false。
bool SeaListFind(SQL* ps, int key); //在顺序表中寻找元素
在这里有的小伙伴就提出疑问，这个bool类型是怎么不报错的了？
我们只需要在头文件中引入 , 就实现了对于bool类型的库函数引入 , 此时就不会报错啦
#include<stdbool.h>
具体函数接口实现：
- bool SeaListFind(SQL* ps, int key) //在顺序表中寻找元素
- {
- for (int i = 0; i < ps->size; i++) {
- if (ps->a[i] == key) {
- return true; //找到了就直接返回true
- }
- }
- return false; //没找到就直接返回false
- }
3.9：顺序表检查长度
void CheckCapacity(SQL* ps); ///检查顺序表长度，若满或空就开始增容
顺序表检查长度经常会用在顺序表的头插和尾插的部分上，所以在头插和尾插的时候，我们需要先检查一下顺序表是不是满了，要是满了的话CheckCapacity的函数功能就是为内存开辟空间使得能够有足够的空间去供插入的位置。
- void CheckCapacity(SQL* ps) {
- if (ps->Capacity == ps->size) { //如果顺序表的内存中的元素数 == 总大小 或者两者
- 都等于0的时候，就开始扩容
- int NewCapacity = (ps->Capacity == 0) ? 4 : ps->Capacity * 2;
- //创建出来的新顺序表长度在检查的时候，如果结构体指针ps的大小为0的时候，那就开辟4个大小的内
- 存，要是满了的话，那几句扩容2倍
- DataType* tmp = (DataType*)realloc(ps->a , NewCapacity * sizeof(DataType));
- //将新顺序表准备好，将上述的是否扩容的大小准备好，准备为新顺序表进行扩容
- if (tmp == NULL) { //如果扩容失败
- printf("realloc Failed!");
- exit(-1); //exit的内部若为-1的话，那就直接退出，若为0的时候，就继续执行
- }
- ps->a = tmp; //将新的顺序表放置在旧的顺序表中
- ps->Capacity = NewCapacity; //将新的扩容后的长度，放置在旧的顺序表长度中，完成扩容
- }
- }
3.10：顺序表元素插入（顺序表中任意前面位置）
顺序表的元素插入其实分为两种的：
第一种：在任意元素的前面插入
void SeqListBeforeInsert(SQL* ps, int pos, DataType x); //在指定的位置插入元素
- void SeqListBeforeInsert(SQL* ps, int pos, DataType x) //在指定的位置插入元素 ,默认为位置元素前面插入
- {
- //先检查一下顺序表是不是空的或者满的
- CheckCapacity(ps);
- //再看一下插入的位置是不是有效位置：（有效位置就是 [0 , ps->size - 1] 这个区间之内，也可以插
- 在头插，也可以插在尾插）
- assert(pos >= 0 && pos <= ps->size - 1); //位置错误报告器 ,则会让pos的位置变得合法
- for (int i = ps->size - 1; i >= pos; i--) { //pos的起始挪动位置是ps->size - 1
- ps->a[i+1] = ps->a[i];
- }
- ps->a[pos] = x;
- ps->size++;
- }
3.11：顺序表元素插入（顺序表中任意后面位置）
第二种：在任意位置的后面插入
void SeqListAfterInsert(SQL* ps, int pos, DataType x); //在指定的位置插入元素
- void SeqListAfterInsert(SQL* ps, int pos, DataType x) //在指定的位置插入元素
- {
- //先检查一下顺序表是不是空的或者满的
- CheckCapacity(ps);
- //再看一下插入的位置是不是有效位置：（有效位置就是 [0 , ps->size - 1] 这个区间之内，也可以插
- 在头插，也可以插在尾插）
- assert(pos >= 0 && pos <= ps->size - 1); //位置错误报告器
- for (int i = ps->size - 1; i >= pos + 1; i--) { //pos的起始挪动位置是ps->size - 1
- ps->a[i + 1] = ps->a[i];
- }
- ps->a[pos + 1] = x; //在pos位置后面位置进行插入
- ps->size++;
- }
3.12：顺序表删除元素（删除任意位置的前面元素）
顺序表删除元素，得看两点：
1：位置是否合理？
2：顺序表是否为空？
下面的代码中都会涉及到：
void SeqListBeforeEarse(SQL* ps, int pos) //在指定的位置前面删除元素
- void SeqListBeforeEarse(SQL* ps, int pos) //在指定的位置前面删除元素
- {
- //先检查位置是否正确？
- assert(pos >= 0 && pos <= ps->size - 1);
- //检查顺序表是否为空？
- assert(ps->size != 0); //若顺序表为空，那就不能删除
- //开始删除元素
- for (int i = pos - 1; i < ps->size ; i++) {
- ps->a[i] = ps->a[i + 1]; //直接将需要删除的元素的前一个位置的元素开始进行覆盖
- }
- ps->size--; //最后ps->size--
-
- }
3.13：顺序表删除元素（删除任意位置的后面元素）
顺序表删除元素，得看两点：
1：位置是否合理？
2：顺序表是否为空？
void SeqListAfterEarse(SQL* ps, int pos) //在指定的位置后面删除元素
- void SeqListAfterEarse(SQL* ps, int pos) //在指定的位置后面删除元素
- {
- //先检查位置是否正确？
- assert(pos >= 0 && pos <= ps->size - 1);
- //检查顺序表是否为空？
- assert(ps->size != 0); //若顺序表为空，那就不能删除
- //开始删除元素
- for (int i = pos + 1; i < ps->size; i++) {
- ps->a[i] = ps->a[i + 1]; //将需要删除位置的后面的元素开始进行
- }
- ps->size--;
- }
但是大家不要觉得顺序表就很好了，上面的这些例子无一例外都说明了顺序表的缺陷，顺序表的缺陷在于内存的申请，不管是动态的顺序表还是静态的顺序表都是有缺陷的
缺陷：
1、当我们插入或者删除数据的时候，总是需要大量的挪动数据，这就导致我们的时间复杂度就会急剧增加
2、内存的开销太大了，对于动态顺序表来说动态增容的代价十分巨大
下面来谈一谈增容的小知识：
增容无非就是给原来的内存空间增加容量，就是为了存储更多的数据，但是有两种增容分别是：
2.1：
原地增容：内存地址不变，在原地的基础上增容（但是只仅仅适合小空间的增容）
我们在指针变量p1的基础上进行增容，增容大小是10，此时他们的内存地址都是：0x01236c68
但是还有一种叫做“异地扩容”
异地扩容：
此时的内存地址就已经发生了变化，就说明已经不是在原地进行扩容，而是开辟了一片新地址来将新的数据进行存储（此时相比于原地扩容而言，异地扩容已经重新开辟了内存空间，开销已经很大了）
3：对于动态扩容我们总是要不断地进行2倍扩容，会导致内存的浪费或者不够使用的尴尬情况。
当你要随机插入数据，而且时间复杂度还很低的时候，所以此时顺序表有可能已经不太实用了，于是就产生了我们众所周知的“链表”
接下来就跟着我来开始“数据结构”的篇章吧！
关注我，我将持续更新数据结构的知识点！让我们一起开始快乐的学习编程吧！！！
