前言
数据结构入门 — 顺序表详解
关注博主，后期持续更新系列文章
*****感谢观看，希望对你有所帮助*****
文章目录
前言
一、顺序表
1. 顺序表是什么
2. 优缺点
二、概念及结构
1. 静态顺序表
2. 动态顺序表
三、顺序表接口实现（代码演示）
1. 动态存储结构
2. 顺序表打印
3. 顺序表初始化
4. 检查空间大小
5. 增删查改接口
6. 顺序表销毁
四、所有文件代码
1. Gitee链接
一、顺序表
1. 顺序表是什么
顺序表是连续存储的
顺序表是一种线性表的数据结构，它的数据元素按照一定次序依次存储在计算机存储器中，使用连续的存储空间来存储。顺序表中每个数据元素的位置都有一个序号，这个序号也称为元素在顺序表中的下标。顺序表的特点是：元素的逻辑顺序与物理顺序相同，支持随机访问，插入和删除元素的时间复杂度为O(n)，查找元素的时间复杂度为O(1)。
2. 优缺点
优点
优点是访问速度快，因为它的元素在内存中是连续存储的，可以直接通过下标访问，而且不需要额外的空间来存储指向下一个节点的指针。
缺点
缺点是插入和删除元素的时间复杂度为O(n)，因为需要移动其他元素的位置，而且不利于动态扩展容量。
二、概念及结构
元素的类型、元素的个数、数组的大小和数组的指针
顺序表的实现需要预留一段连续的存储空间来存储所有的元素，目前常见的实现方式是使用数组来实现顺序表。数组的地址是连续的，因此可以通过数组下标进行快速访问元素。为了实现顺序表，需要定义一个数据结构，包含元素的类型、元素的个数、数组的大小和数组的指针等信息。
1. 静态顺序表
静态顺序表是一种使用连续存储空间实现的线性表结构，其特点是在创建表时就需要预先分配好固定长度的存储空间，表长也就固定了下来，不能动态扩展或缩小。
在静态顺序表中，数据元素按照顺序依次存放，每个元素都占用相同的存储空间，而且元素在内存中的地址也是连续的。
2. 动态顺序表
动态顺序表是一种线性表的实现方式，它在静态顺序表的基础上，将存储空间由固定长度改为动态分配。
当动态顺序表中存放的元素个数达到当前存储空间的上限时，可以重新申请更大的空间来存放更多的元素，因此动态顺序表的长度是可变的。动态顺序表的实现通常采用数组形式，通过realloc函数来动态分配空间。
三、顺序表接口实现（代码演示）
1. 动态存储结构
即定义顺序表的结构。由动态开辟的数组、有效数据个数和容量空间的大小组成
typedefintSLDataType; typedefstructSeqList{ SLDataType*a; // 指向动态开辟的数组intsize; // 有效数据个数intcapacity; // 容量空间的大小}SL;
2. 顺序表打印
使用循环，将顺序表遍历一遍，进行打印
//打印顺序表voidSLPrint(SL*pc) { assert(pc); inti=0; for (i=0; i<pc->size; i++) { printf("%d ", pc->a[i]); } printf("\n"); }
3. 顺序表初始化
在顺便表初始化时，先用malloc开辟4个空间，如果开启失败报错并返回
//初始化顺序表voidSLInit(SL*pc) { assert(pc); //开启内存 pc->a=(SLDataType*)malloc(sizeof(SLDataType) *4); //检查是否开辟成功if (pc->a==NULL) { perror("SLInit"); //return;exit(-1); } pc->capacity=4; pc->size=0; }
4. 检查空间大小
检查空间，当顺序表内的数据等于初始化开辟的空间时，再开辟4个空间（用realloc开辟乘2的空间）
//检查内存容量voidSLCheckCapacity(SL*pc) { assert(pc); if (pc->size==pc->capacity) { SLDataType*tem= (SLDataType*)realloc(pc->a, sizeof(SLDataType)*2*pc->capacity); //要乘以2if (tem==NULL) { perror("SLCheckCapacity"); exit(-1); } pc->a=tem; pc->capacity*=2; } }
5. 增删查改接口
以增删查改顺序依次编排
头插：
头插，即在顺序表头部进行插入数值，在SLCheckCapacity检查空间是否充足后，进行插入数值
//头插voidSLPushFront(SL*pc,SLDataTypex) { assert(pc); SLCheckCapacity(pc); intend=pc->size-1; while (end>=0) { pc->a[end+1] =pc->a[end]; --end; } pc->a[0] =x; pc->size++; }
尾插：
尾插，即找到顺序表的尾，下标为pc->size的位置插入数值
//尾插voidSLPushBack(SL*pc, SLDataTypex) { assert(pc); SLCheckCapacity(pc); pc->a[pc->size] =x; pc->size++; }
头删：
头删，将后面的数值依次向前覆盖。覆盖时要注意顺序，将在前的先覆盖，防止数组丢失，然后将顺序表的size(数据个数减一）
//头删voidSLPopFront(SL*pc) { assert(pc); intstart=1; while (start<pc->size) { pc->a[start] =pc->a[start+1]; ++start; } pc->size--; }
尾删：
尾删，即将有效数据减一，直接将pc所指向的size减一
//尾删voidSLPopBack(SL*pc) { assert(pc->size>0); pc->size--; }
查找：
查找方法有很多种，这里使用暴力查找，将顺序表遍历一遍，找到要找的元素并返回下标
//查找数字位置intSLFind(SL*pc, SLDataTypex) { inti=0; for (i=0; i<pc->size; i++) { if (pc->a[i] ==x) { returni; } } return-1; }
指定位置插入
这里配合查找函数使用，找到要找的数值的下标，进入下列函数，将pos之后的值依次下向后移动，在pos位置插入数值
// 在pos位置插入xvoidSLInsert(SL*pc, intpos, SLDataTypex) { assert(pc); assert(pos>=0&&pos<=pc->size); SLCheckCapacity(pc); intend=pc->size-1; while (end>=pos) { pc->a[end+1] =pc->a[end]; --end; } pc->a[pos] =x; pc->size++; }
指定位置删除
这里配合查找函数使用，找到要找的数值的下标，进入下列函数，将pos位置后的数值依次向前覆盖
// 删除pos位置的值voidSLErase(SL*pc, intpos) { assert(pc); assert(pos>=0&&pos<pc->size); intstart=pos+1; while (start<pc->size) { pc->a[start-1] =pc->a[start]; ++start; } pc->size--; }
更改指定位置
这里配合查找函数使用，找到要找的数值的下标，进入下列函数，将pos位置的值进行修改
//更改制定位置的数字voidSLModify(SL*pc, intpos, SLDataTypex) { assert(pc); assert(pos>=0&&pos<pc->size); pc->a[pos] =x; }
6. 顺序表销毁
顺序表进行销毁，将开辟的数值空间进行释放，并置为空（NULL）将空间和数据个数置为0 ，这样顺序表就销毁完成
//销毁释放内存voidSLDestroy(SL*pc) { assert(pc); free(pc->a); pc->a=NULL; pc->capacity=0; pc->size=0; }
四、所有文件代码
1. Gitee链接
***查看所有代码***
点击右边蓝色文字 DuckBro Gitee 代码仓库
总结
顺序表是一种线性表，它的重点是：
- 物理结构：顺序表的数据元素在内存中是连续存放的，即使用一段连续的存储空间来存储线性表的元素。
- 逻辑结构：顺序表是一种线性表，它的元素在逻辑上是依次排列的。
- 数据操作：顺序表支持基本的数据操作，包括插入、删除、查找等操作。其中，插入和删除操作需要移动大量元素，时间复杂度较高，而查找操作可以通过使用二分查找等算法来提高效率。
- 容量管理：顺序表的容量是由数组的长度来决定的。如果数组长度不够，顺序表需要进行扩容操作，如果数组长度过长，会浪费内存空间。
- 性能特点：由于顺序表的数据元素在内存中是连续存放的，所以顺序表具有快速的随机访问能力，但插入、删除操作较为耗时。因此，适合于需要随机访问元素，但不频繁进行插入、删除操作的场景。顺序表
如这篇博客对大家有帮助的话，希望 三连 支持一下 ！！！ 如果有错误感谢大佬的斧正 如有 其他见解发到评论区，一起学习 一起进步。
