数据结构：顺序表详解

🕗 发布于 2024-12-10 03:03 c语言 数据结构

1.顺序表的概念与定义

2.顺序表的初始化与销毁

3.顺序表的头/尾部的插入与删除

4.顺序表指定位置的插入和删除

4.对顺序表中的数据的查找

5.总结

我以过客之名，祝你前程似锦

一.顺序表的概念与定义

1.概念：

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中

2.定义：

（1）数据类型定义：

typedef struct   //定义数据类型
{
int size;
int capability;
}Seqlist;

（2）顺序表的定义：

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct   //定义数据类型
{
int size;
int capability;
}Seqlist;

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* a;
int size;     // 有效数据个数
int capacity; // 空间容量

}SL;              //命名了一个数据类型为struct Seqlist的叫SL的顺序表

二.顺序表的初始化与销毁

1.初始化：

以下是将初始化分装为函数并且在text.c里调用以便调试（接下来会有很多处这样的分装）

这里有一个非常值得注意的地方：就是对于顺序表的传址调用是用的一级指针，而在后续的链表却使用的是二级指针，这其中主要的原因是：

‌两者在内存管理方式上的差异。‌

顺序表和链表的基本概念和操作方式
‌顺序表‌：顺序表是将数据依次存储在连续的整块物理空间中，通过计算地址可以直接访问任何数据元素。顺序表的尾插操作是通过调整数组的容量和索引来实现的，不需要改变原有指针的指向，因此传递一级指针即可
‌链表‌：链表是通过节点之间的链接来存储数据，每个节点包含数据部分和指向下一个节点的指针。链表的尾插操作需要创建一个新节点，并将其链接到链表的末尾，同时更新尾指针。由于需要修改指针的指向，因此必须传递二级指针（即指针的地址）

如果这里不太理解的话不用担心，下面还会进行详细介绍的

2.销毁（置0）：

不同于链表的销毁，顺序表的销毁只不过是将原有的数据清零（覆盖），而顺序表需要通过使用free函数释放掉每个结点的内存（在顺序表的介绍里我会不时地提到链表，一是因为这俩确实很像，同时也方便你对这俩兄弟的理解，所有如果对于链表还不了解的兄弟可以适当忽略我在这里写的话，后面自然而然就会懂了，加油）

三.顺序表的头/尾部的插入与删除

1.尾插（从顺序表尾部插入）：

void SLPushBack(SL* ps, SLDataType x)
{

//方法一,判断用户传入的是否为空指针
//if (ps == NULL)
//{
//return;
//}
//方法二
assert(ps);

//ps->arr[ps->size++] = x;
//插入数据前看空间够不够
if(ps->capacity==ps->size)
{
//申请空间
int newCapacity = ps->capacity == 0 ? 4 : 2*sizeof(SLDataType);//防止初始化的capacity为0（也可以直接在初始化就申请）
//ps->arr = realloc(ps->arr, newCapacity * sizeof(SLDataType));
//万一申请空间不成功（malloc申请空间不一定成功）
SL*tmp =(SL*) realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc failed!");
exit(1);//直接退出程序
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->size++] = x;
}

别紧张，虽然代码量看着比较多，但也就那几个部分，我在这里详细讲讲这个尾插的解法，其他的代码就会很简单了

第二部分如果后续觉得在每一个插入的地方都重复使用的话会显得有些繁琐，所以这里我们也可以单独把他拎出来封装成另外一个函数（即我们的检验扩容函数）

同时我再说一下那个三目操作符为什么是2 * sizeof(SLDataType)，主要是通过数学逻辑证明每次扩大二倍的效率最高

//检验，扩容
void SLCheckCapacity(SL* ps)
{
    //插入数据前看空间够不够
if (ps->capacity == ps->size)
{
//申请空间
int newCapacity = ps->capacity == 0 ? 4 : 2 * sizeof(SLDataType);//防止初始化的capacity为0（也可以直接在初始化就申请）
//ps->arr = realloc(ps->arr, newCapacity * sizeof(SLDataType));
//万一申请空间不成功（malloc申请空间不一定成功）
SL* tmp = (SL*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc failed!");
exit(1);//直接退出程序
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}

2.头插（理解了尾插后头插就会显得容易多了）：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//先让顺序表中已有的数据往后挪动一位
for (int i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i - 1];//为了确保最后一次挪动为arr[0]=arr[1],故i的范围要注意
}
ps->arr[0] = x;
ps->size++;//插入数据的同时也要使size跟着变动
}

3.尾删：

//尾删
void SLPopBack(SL* ps)
{
assert(ps && ps->size);//尾删时一个要注意的时顺序表本身不为空，另外一个里面的有效数据个数（size）不为0
--ps->size;
}

注意：这里assert的两个限制条件都是为了确保顺序表里有元素的存在

4.头删：

//头删
void SLPopFront(SL* ps)
{
assert(ps && ps->size);//顺序表不为空
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//所有数据向前挪动一位，比如arr[1]=arr[0]
}
--ps->size;//有效数据再减一，兄弟，这里是真的容易忘（捂脸）
}

注意：最后一个有效数据减一

四.顺序表指定位置的插入和删除

1.指定位置的插入：

//指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)//pos是下标
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckcapacity(ps);//正常检查空间是否充足
int i = 0;
for (i = pos; i < ps->size; i++)
{
ps->arr[i + 1] = ps->arr[i];
}//使pos后面的数据一起往后挪动一位
ps->arr[pos] = x;
++ps->size;
}

2.指定位置的删除：

void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
int i = 0;
for (i = pos;i < ps->size-1;i++)
{
ps->arr[i] = ps->arr[i+1];
}
--ps->size;
}

五.对顺序表中的数据的查找

//查找
int SeqListFind(SL* ps, SLDateType x)
{
int i = 0;
for (i = 0;i < ps->size;i++)
{
if (ps->arr[i] == x)
{
return i;
}
}//遍历整个顺序表
return 0;//没找到
}

其实只要把开头的尾插搞懂，下面的一系列代码也就迎刃而解了，跟做减法一样

六.总结

顺序表要预先分配空间，会导致空间闲置或溢出，采用随机存取，

时间复杂度为O(1),但删除和插入要一项一项的移动，时间复杂度为O(n)

适用情况

1.表长变化不大，且能事先确定变化的范围

2.很少进行插入或删除操作，经常按元素序号访问数据元素

原文地址：https://blog.csdn.net/2403_87691282/article/details/144203616

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：mysql Kill脚本
下一篇：知乎数据分析面试题及参考答案

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14