【C语言】数据结构——顺序表超详解!!!（包含顺序表的实现)
【C语言】数据结构——顺序表超详解!!!--包含顺序表的实现--
前言：
往期，我们讲解了C语言的基础语法知识，知道了数组、函数、指针、结构体、文件等相关知识
现在，在掌握扎实的C语言语法基础后，我们可以来进一步学习数据结构
所以，从今天开始，小编将为大家带来数据结构的知识
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持!!!
谢谢大家 ! ! !
（结尾处有动态顺序表的完整代码，感兴趣的的可以自行尝试QwQ）
一、什么是数据结构
数据：
数据在生活中随处可见，包括数值（如1、2、3）、用户信息（姓名/性别/年龄）、网页内容（文字/图片/视频）等所有计算机处理的信息
结构：
通过羊圈管理羊群的比喻说明，无序数据也就是在草原散养羊群，难以管理；而有序结构也就是有编号的羊圈便于查找和操作
所以，数据结构=数据+结构，是计算机存储和组织数据的方式，反映数据内部构成和相互关系
二、顺序表
1.线性表
线性表（linearlist）是n个具有相同特性的数据元素的有限序列，是一种在实际中广泛使 用的数据结构常⻅的线性表有：顺序表、链表、栈、队列、字符串... 等
线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表定义
顺序表本质上是在数组基础上进行维护和封装的数据结构，其底层存储仍然使用数组,在数组的基础上增加了增删查改等方法
顺序表就是线性表的一种，而前面我们说过顺序表的底层存储仍然使用数组，数组在物理结构是连续的
所以，顺序表的物理结构和逻辑结构都是连续的
3.顺序表的分类
顺序表可以分为两类，一是静态顺序表，二是动态顺序表
(1) 静态顺序表
所谓静态，意思是内存是静态的，初始时内存多大就是多大，后续不会再 发生改变
代码演示：（内有注释）
//静态顺序表structSeqlist{int arr[1000];//一个定长数组int size;//表示该顺序表当前有效的数据个数};在代码中我们可以看到，这就是一个静态顺序表
有一个arr定长数组，申请了1000个 int 类型，也就是4000个字节大小内存
还有一个size表示该顺序表当前有效的数据个数
问题：
但是，静态顺序表有一个问题如果数组空间大小给小了，那么空间将不够用
如果数组空间大小给大了，那么空间将会浪费
而基于这一个问题，就产生了动态顺序表
动态顺序表就可以很好的解决这一个问题
(2) 动态顺序表
所谓动态，意思是内存是动态的，内存空间大小可以根据需要来进行增大减小
与静态顺序表的区别：
动态顺序表与静态顺序表最大的优势就在于动态顺序表可以进行动态增容，当空间不够用时，会适当的增加一些空间
因此，动态顺序表既不会出现空间不够用的问题，又没有空间浪费的烦恼
所以，在选择顺序表时，优选动态顺序表
代码演示：（内有注释）
//动态顺序表structSeqlist{int* arr;//一个数组指针int size;//表示该顺序表当前有效的数据个数int capacity;//表示当前顺序表的空间大小};在代码中我们可以看到，这就是一个动态顺序表
有一个arr数组指针
有一个size表示该顺序表当前有效的数据个数
还有一个capacity表示当前顺序表的空间大小
现在我们知道动态顺序表是优选，但我们该如何来实现一个动态顺序表呢？
三、动态顺序表的实现（重点！！！）
之前我们说过，顺序表本质上是在数组基础上在数组的基础上增加了增删查改等方法
现在我们就一一来实现（增加）、（删除）、（查找）、（修改）等操作
本文以创建一个 int 类型的动态顺序表为例
1.创建头文件&源文件
之前在讲解扫雷游戏中我就提到:
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱
如图:
创建了一个 “ Seqlist.h "头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个 “ Seqlist.c "源文件
用于用来放函数的定义(顺序表的主体)
还有一个 ” Test.c "源文件
用于测试顺序表的运行效果
2.定义动态顺序表（定义）
首先我们要定义一个动态顺序表
代码演示：（内有注释）
（在头文件“ Seqlist.h "中写）
//重定义，方便修改类型typedefint SLDataType;//定义动态顺序表typedefstructSeqlist{ SLDataType* arr;int size;int capacity;}SL;在定义动态顺序表代码中，有两个需要注意的点：本文是以int类型为例，但如果以后要将顺序表修改成char类型或是其他类型一个一个修改就很麻烦
所以我们重定义int类型为SLDataType,并将接下来代码中的int类型全部写成SLDataType
这是为了方便我们以后对类型进行修改，仅需将int改为其他类型即可在定义动态顺序表的同时重定义顺序表名为SL方便以后使用
3.顺序表的初始化（初始化）
定义完顺序表后，肯定要对顺序表进行初始化，全部置 0 / NULL代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
在“ Seqlist.h "头文件中写到：
//顺序表的初始化voidSLInit(SL* ps);在“ Seqlist.c "源文件中写到：
//顺序表的初始化voidSLInit(SL* ps){assert(ps);//断言空指针 ps->arr =NULL; ps->capacity = ps->size =0;//全部初始化置 0 / NULL}在写动态顺序表代码中，有一个很重要的点：
当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的
故为了我们的代码更加健壮，可以加入assert 断言来判断是否符合条件，在之后的代码中也都有
关于更加详细的assert 断言介绍可参见下文：
【C语言】带你层层深入指针——指针详解3（野指针、assert等）
4.顺序表的销毁（销毁）
在我们的程序运行完毕后，当然要对顺序表进行销毁，以免占用内存
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
在“ Seqlist.h "头文件中写到：
//顺序表的销毁voidSLDestroy(SL* ps);在“ Seqlist.c "源文件中写到：
//顺序表的销毁voidSLDestroy(SL* ps){if(ps->arr !=NULL)//当其不为空时再释放，避免释放空指针{assert(ps);//断言空指针free(ps->arr);//释放内存 ps->arr =NULL;//置NULL} ps->size = ps->capacity =0;//置0}5.顺序表的打印（打印）
顺序表肯定少不了打印啦，直接遍历顺序表进行打印
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
在“ Seqlist.h "头文件中写到：
//顺序表的打印voidSLshow(SL* ps);在“ Seqlist.c "源文件中写到：
//顺序表的打印voidSLshow(SL* ps){assert(ps);//断言空指针for(int i =0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n\n");}6.顺序表开辟空间（增容）
动态顺序表的空间是动态管理的，故当顺序表的空间不足时，可再开辟一些空间使用（动态增容）
但是存在一个问题：
我们到底要开辟多大的空间来使用呢？1. 若一次性开辟的空间过大，可能会造成空间的浪费
2. 若一次性开辟的空间过小，就可能会导频繁的开辟空间，这样运行的效率就会大大降低
经过科学研究，发现每次增容 2 倍 & 3 倍 空间最为合适
当原空间为 100 的空间不足时，就增容到 200 空间
（本文选择的是每次增容 2 倍 ）
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
在“ Seqlist.h "头文件中写到：
//顺序表开辟空间voidSLCheckCapacity(SL* ps);在“ Seqlist.c "源文件中写到：
//顺序表开辟空间voidSLCheckCapacity(SL* ps){assert(ps);//断言空指针if(ps->size == ps->capacity)//当size=capacity时就表示空间不足，此时需要增容，故进入if语句{//先设置新变量，增容后再赋值int newcapacity = ps->capacity ==0?4:2* ps->capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍 SLDataType* tmp =(SLDataType*)realloc(ps->arr,newcapacity *sizeof(SLDataType));//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *（类型大小）if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("realloc fail");exit(1);}//没有问题后就赋值 ps->arr = tmp; ps->capacity = newcapacity;}}在做完之前的准备工作后，现在我们可以开始进行操作了
依次写出增删查改等操作
7.在顺序表尾部插入数据（尾插）
这个很简单，直接用下标进行插入数据
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
（其中 x 是要插入的数据，下同）
在“ Seqlist.h "头文件中写到：
//在顺序表尾部插入数据voidSLPushBack(SL* ps, SLDataType x);在“ Seqlist.c "源文件中写到：
//在顺序表尾部插入数据voidSLPushBack(SL* ps, SLDataType x){assert(ps);//断言空指针SLCheckCapacity(ps);//用之前写的代码来判断空间是否足够，不够就开辟空间 ps->arr[ps->size++]= x;//给尾部赋值}8.在顺序表头部插入数据（头插）
头插就比尾插想的事情多了
因为当头插时，后面元素的下标都会发生改变，故所有元素都要向后挪动一位给头插腾出空间
文字解释不清，下面还是用图解来说明吧：
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
（其中 x 是要插入的数据，下同）
在“ Seqlist.h "头文件中写到：
//在顺序表头部插入数据voidSLPushFront(SL* ps, SLDataType x);在“ Seqlist.c "源文件中写到：
//在顺序表头部插入数据voidSLPushFront(SL* ps, SLDataType x){assert(ps);//断言空指针SLCheckCapacity(ps);//用之前写的代码来判断空间是否足够，不够就开辟空间for(int i = ps->size; i >0; i--)//将所有元素向后挪动一位给头插腾出空间{ ps->arr[i]= ps->arr[i -1];} ps->arr[0]= x;//赋值 ps->size++;//元素个数+1}9.在顺序表尾部删除数据（尾删）
这个很简单，直接用下标进行删除数据
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
在“ Seqlist.h "头文件中写到：
//在顺序表尾部删除数据voidSLPopBack(SL* ps);在“ Seqlist.c "源文件中写到：
//在顺序表尾部删除数据voidSLPopBack(SL* ps){assert(ps);//断言空指针assert(ps->arr !=NULL);//断言顺序表不能为空 ps->size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}10.在顺序表头部删除数据（头删）
头删就比尾删想的事情多了
因为当头删时，后面元素的下标都会发生改变，故所有元素都要向前挪动一位补齐头删留下的空间，恰恰与头插相反
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
在“ Seqlist.h "头文件中写到：
//在顺序表头部删除数据voidSLPopFront(SL* ps);在“ Seqlist.c "源文件中写到：
//在顺序表头部删除数据voidSLPopFront(SL* ps){assert(ps);//断言空指针assert(ps->arr !=NULL);//断言顺序表不能为空for(int i =0; i < ps->size -1; i++)//所有元素都要向前挪动一位补齐头删留下的空间{ ps->arr[i]= ps->arr[i +1];} ps->size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}11.在指定位置pos之前插入数据（随机插）
有了头插和尾插，那就还有随机插入了
当随机插入时，与头插同理 , 插入后后面元素的下标都会发生改变，故pos后面的元素从最后一个元素开始，都要向后挪动一位给要插入的元素腾出空间
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
（其中 pos 表示元素下标，下同）
（其中 x 是要插入的数据，下同）
在“ Seqlist.h "头文件中写到：
//在指定位置（pos）之前插入数据voidSLInsert(SL* ps,int pos, SLDataType x);在“ Seqlist.c "源文件中写到：
//在指定位置（pos）之前插入数据voidSLInsert(SL* ps,int pos, SLDataType x){assert(ps);//断言空指针assert(pos >=0&& pos <= ps->size);//断言pos是否超出顺序表范围SLCheckCapacity(ps);//用之前写的代码来判断空间是否足够，不够就开辟空间for(int i = ps->size; i > pos; i--)//将 pos 后面的元素从最后一个元素开始//向后挪动一位给要插入的元素腾出空间{ ps->arr[i]= ps->arr[i -1];} ps->arr[pos]= x;//赋值 ps->size++;//元素个数+1}12.在指定位置pos删除数据（随机删）
有了头删和尾删，那就还有随机删除了
当随机删除时，与头删同理 , 删除后后面元素的下标都会发生改变，故pos后面的元素从第一个元素开始，都要向前挪动一位来补齐删除元素后留下的空间
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
（其中 pos 表示要删除数据的下标，下同）
在“ Seqlist.h "头文件中写到：
//在指定位置（pos）删除数据voidSLErase(SL* ps,int pos);在“ Seqlist.c "源文件中写到：
//在指定位置（pos）删除数据voidSLErase(SL* ps,int pos){assert(ps);//断言空指针assert(pos >=0&& pos <= ps->size);//断言pos是否超出顺序表范围for(int i = pos; i < ps->size -1; i++)//将 pos 后面的元素从第一个元素开始//向前挪动一位来补齐删除元素后留下的空间{ ps->arr[i]= ps->arr[i +1];} ps->size--;//将元素个数进行 -1 就行//这样不会影响到后面的 增、删、查、改}13.在顺序表中查找数据（查找）
我们还可以实现查找数据
只需通过遍历顺序表就可以判断是否有该数据
并设置返回值：1. 若找到了就返回下标
2. 若没找到就返回一个负数
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
（其中 x 是要查找的数据，下同）
在“ Seqlist.h "头文件中写到：
//在顺序表中查找数据intSLFind(SL* ps, SLDataType x);在“ Seqlist.c "源文件中写到：
//在顺序表中查找数据intSLFind(SL* ps, SLDataType x){assert(ps);////断言空指针for(int i =0; i < ps->size; i++)//遍历顺序表查找该数据{if(ps->arr[i]== x){return i;//找到了就返回下标}}return-1;//没找到就返回一个负数}14.在顺序表中修改数据（修改）
修改数据就很简单了
只需要通过下标进行修改
代码演示：（内有注释）
（其中 ps 是一个顺序表类型的指针，下同）
（其中 pos 是要修改的数据的下标，下同）
（其中 x 是修改之后的数据，下同）
在“ Seqlist.h "头文件中写到：
//在顺序表中修改数据voidSLAlter(SL* ps,int pos, SLDataType x);在“ Seqlist.c "源文件中写到：
//在顺序表中修改数据voidSLAlter(SL* ps,int pos, SLDataType x){assert(ps);//断言空指针assert(pos >=0&& pos <= ps->size);//断言pos是否超出顺序表范围 ps->arr[pos]= x;//进行修改}四、完整代码
1. Seqlist.h
在“ Seqlist.h "头文件中写到：
#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<string.h>#include<assert.h>#include<stdlib.h>//重定义，方便修改类型typedefint SLDataType;//定义动态顺序表typedefstructSeqlist{ SLDataType* arr;int size;int capacity;}SL;//顺序表的初始化voidSLInit(SL* ps);//顺序表的销毁voidSLDestroy(SL* ps);//顺序表开辟空间voidSLCheckCapacity(SL* ps);//顺序表的打印voidSLshow(SL* ps);//在顺序表尾部插入数据voidSLPushBack(SL* ps, SLDataType x);//在顺序表头部插入数据voidSLPushFront(SL* ps, SLDataType x);//在顺序表尾部删除数据voidSLPopBack(SL* ps);//在顺序表头部删除数据voidSLPopFront(SL* ps);//在指定位置（pos）之前插入数据voidSLInsert(SL* ps,int pos, SLDataType x);//在指定位置（pos）删除数据voidSLErase(SL* ps,int pos);//在顺序表中查找数据intSLFind(SL* ps, SLDataType x);//在顺序表中修改数据voidSLAlter(SL* ps,int pos, SLDataType x);2. Seqlist.c
在“ Seqlist.c "源文件中写到：
#include"Seqlist.h"//顺序表的初始化voidSLInit(SL* ps){assert(ps); ps->arr =NULL; ps->capacity = ps->size =0;//全部初始化置 0 / NULL}//顺序表的销毁voidSLDestroy(SL* ps){assert(ps);if(ps->arr !=NULL)//当其不为空时再释放，避免释放空指针{free(ps->arr);//释放内存 ps->arr =NULL;//置NULL} ps->size = ps->capacity =0;//置0}//顺序表的打印voidSLshow(SL* ps){assert(ps);//断言for(int i =0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n\n");}//顺序表开辟空间voidSLCheckCapacity(SL* ps){assert(ps);//断言if(ps->size == ps->capacity)//当size=capacity时就表示空间不足，此时需要增容，故进入if语句{//先设置新变量，增容后再赋值int newcapacity = ps->capacity ==0?4:2* ps->capacity;//设置一个三目操作符判断原空间是否为 0//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍 SLDataType* tmp =(SLDataType*)realloc(ps->arr,newcapacity *sizeof(SLDataType));//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容//增容大小为上面的 newcapacity *（类型大小）if(tmp ==NULL)//加一个 if语句 防止增容失败{perror("realloc fail");exit(1);}//没有问题后就赋值 ps->arr = tmp; ps->capacity = newcapacity;}}//在顺序表尾部插入数据voidSLPushBack(SL* ps, SLDataType x){assert(ps);//断言SLCheckCapacity(ps);//用之前写的代码来判断空间是否足够，不够就开辟空间 ps->arr[ps->size++]= x;//给尾部赋值}//在顺序表头部插入数据voidSLPushFront(SL* ps, SLDataType x){assert(ps);//断言空指针SLCheckCapacity(ps);//用之前写的代码来判断空间是否足够，不够就开辟空间for(int i = ps->size; i >0; i--)//将所有元素向后挪动一位给头插腾出空间{ ps->arr[i]= ps->arr[i -1];} ps->arr[0]= x;//赋值 ps->size++;//元素个数+1}//在顺序表尾部删除数据voidSLPopBack(SL* ps){assert(ps);//断言空指针assert(ps->arr !=NULL);//断言顺序表不能为空 ps->size--;//将元素个数进行 -1 就行//这样也不会影响到后面的 增、删、查、改}//在顺序表头部删除数据voidSLPopFront(SL* ps){assert(ps);//断言空指针assert(ps->arr !=NULL);//断言顺序表不能为空for(int i =0; i < ps->size -1; i++)//所有元素都要向前挪动一位补齐头删留下的空间{ ps->arr[i]= ps->arr[i +1];} ps->size--;//将元素个数进行 -1 就行//这样不会影响到后面的 增、删、查、改}//在指定位置（pos）之前插入数据voidSLInsert(SL* ps,int pos, SLDataType x){assert(ps);//断言空指针assert(pos >=0&& pos <= ps->size);//断言pos是否超出顺序表范围SLCheckCapacity(ps);//用之前写的代码来判断空间是否足够，不够就开辟空间for(int i = ps->size; i > pos; i--)//将 pos 后面的元素从最后一个元素开始//向后挪动一位给要插入的元素腾出空间{ ps->arr[i]= ps->arr[i -1];} ps->arr[pos]= x;//赋值 ps->size++;//元素个数+1}//在指定位置（pos）删除数据voidSLErase(SL* ps,int pos){assert(ps);//断言空指针assert(pos >=0&& pos <= ps->size);//断言pos是否超出顺序表范围for(int i = pos; i < ps->size -1; i++)//将 pos 后面的元素从第一个元素开始//向前挪动一位来补齐删除元素后留下的空间{ ps->arr[i]= ps->arr[i +1];} ps->size--;//将元素个数进行 -1 就行//这样不会影响到后面的 增、删、查、改}//在顺序表中查找数据intSLFind(SL* ps, SLDataType x){assert(ps);////断言空指针for(int i =0; i < ps->size; i++)//遍历顺序表查找该数据{if(ps->arr[i]== x){return i;//找到了就返回下标}}return-1;//没找到就返回一个负数}//在顺序表中修改数据voidSLAlter(SL* ps,int pos, SLDataType x){assert(ps);//断言空指针assert(pos >=0&& pos <= ps->size);//断言pos是否超出顺序表范围 ps->arr[pos]= x;//进行修改}3. Test.c
最后，就是”Test.c“源文件啦
该文件包含了主函数，大家可以在里面测试自己写的函数
下面是小编自己测试写的代码：
#include"Seqlist.h"intmain(){ SL S1;SLInit(&S1);SLPushBack(&S1,0);SLPushBack(&S1,1);SLPushBack(&S1,2);SLPushBack(&S1,3);SLPushBack(&S1,4);SLPushBack(&S1,5);SLPushBack(&S1,6);SLPushBack(&S1,7);SLPushBack(&S1,8);SLshow(&S1);SLAlter(&S1,8,0);SLshow(&S1);SLDestroy(&S1);return0;}结语
本期资料来自于：
OK，本期的顺序表详解到这里就结束了
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持
本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！
新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！
支持一下（三连必回QwQ）
