【数据结构篇】顺序表 超详细

devtools/2025/1/22 22:47:32/

目录

一.顺序表的定义

1.顺序表的概念及结构

1.1线性表

2.顺序表的分类

2.1静态顺序表

2.2动态顺序表 

二.动态顺序表的实现

1.准备工作和注意事项

2.顺序表的基本接口:

   2.0 创建一个顺序表

   2.1 顺序表的初始化

2.2 顺序表的销毁

2.3 顺序表的打印

3.顺序表的尾插和尾删接口:

4.顺序表的扩容接口:

5.顺序表的头插和头删接口:

6.顺序表的指定位置插入和删除接口:

7.顺序表的查找接口:

 三.完整代码

SeqList.c: 

SeqList.h:

test.c :


一.顺序表的定义

1.顺序表的概念及结构

1.1线性表

2.顺序表的分类

顺序表的底层是数组,但和数组不一样的是,它对数组进行了分装,增加了增删查改等接口

2.1静态顺序表

概念:使用定长的数组存储元素(用存储整型举例)

缺陷: 空间给多了造成空间浪费,给少了空间不够

这里我解释一下为什么用 replace 代替 int : 这样是方便以后修改顺序表存储别的数据类型,用N代替数组的元素个数同理,修改时更方便

2.2动态顺序表 

二.动态顺序表的实现

1.准备工作和注意事项

 创建3个文件:

  第一个文件:用于接口函数和所有需要用到的库函数头文件的声明,定义顺序表的结构

  第二个文件:用于对接口函数的定义

  第三个文件:用于接口的测试

  注意事项:建议每个函数接口写完对其进行调试,避免最后产生大量报错而束手无措

                    我在每个接口的代码上面都添加了很多注释,帮助各位未来的大佬增加理解哦

2.顺序表的基本接口:

   2.0 创建一个顺序表

   2.1 顺序表的初始化

对于我为什么要先用arr来接收开辟好的空间,我本来是想着开辟失败会影响先前开辟好的空间,但转念一想先前本来也没有开辟空间那,如果开辟失败的还用arr接收还是直接用结构体成员指针接收都一样那,但从更广泛的编程实践和代码质量的角度考虑,先用arr接收是一种更好的编程习惯,有助于提高代码的严谨性和可读性,减少潜在的错误和问题。 

2.2 顺序表的销毁

2.3 顺序表的打印

 提前将打印接口写好,方便后面的观察

3.顺序表的尾插和尾删接口:

尾插:

切记:在插入数据后都要让有效数据个数+1

尾删:

4.顺序表的扩容接口:

由于顺序表的插入接口都要进行扩容判断,所以我们可以把扩容单独分装成一个函数

这样在后续的代码中我们直接调用这个函数就可以了 

5.顺序表的头插和头删接口:

头插:

头删:

6.顺序表的指定位置插入和删除接口:

插入:

删除:

由于下面这些代码逻辑都差不多,我也就没做注释了,指定位置的插入删除无非就是要挪动数据,这个你自己画图后就可以看懂了

7.顺序表的查找接口:

 三.完整代码

SeqList.c: 

 SeqList.h:

test.c :

这部分我只调用了部分函数(仅供参考)

四.顺序表的问题及思考  

1. 中间/头部的插⼊删除,时间复杂度为O(N)
2. 增容需要申请新空间,拷⻉数据,释放旧空间。会有不⼩的消耗。
3. 增容⼀般是呈2倍的增⻓,势必会有⼀定的空间浪费。例如当前容量为100,满了以后增容到
200,我们再继续插⼊了5个数据,后⾯没有数据插⼊了,那么就浪费了95个数据空间。
思考:如何解决以上问题呢?
这就需要我们另一种数据结构了,卖个关子,后续内容就等下一篇文章了,顺序表哪块不理解的欢迎评论区提问,同时哪块有问题的也麻烦各位大佬及时指出我的问题,笔芯!!!


http://www.ppmy.cn/devtools/152709.html

相关文章

微服务学习-OpenFeign 简化服务间调用

使用 OpenFeign 简化服务间调用 1. 作用 服务间的远程调用,比如通过 OpenFeign 可以实现订单服务调用远程的库存服务 已经有了 LoadBalancer 为什么还要用 OpenFeign? 在微服务架构中,LoadBalancer 和 OpenFeign 虽然都提供服务间调用的能…

C# 控制打印机:从入门到实践

在开发一些涉及打印功能的应用程序时,使用 C# 控制打印机是一项很实用的技能。这篇文章就来详细介绍下如何在 C# 中实现对打印机的控制。 一、准备工作 安装相关库:在 C# 中操作打印机,我们可以借助System.Drawing.Printing命名空间&#x…

备赛蓝桥杯之第十五届职业院校组省赛第一题:智能停车系统

提示:本篇文章仅仅是作者自己目前在备赛蓝桥杯中,自己学习与刷题的学习笔记,写的不好,欢迎大家批评与建议 由于个别题目代码量与题目量偏大,请大家自己去蓝桥杯官网【连接高校和企业 - 蓝桥云课】去寻找原题&#xff0…

IDEA构建JavaWeb项目,并通过Tomcat成功运行

目录 一、Tomcat简介 二、Tomcat安装步骤 1.选择分支下载 2.点击下载zip安装包 3.解压到没有中文、空格和特殊字符的目录下 4.双击bin目录下的startup.bat脚本启动Tomcat 5.浏览器访问Tomcat 6.关闭Tomcat服务器 三、Tomcat目录介绍 四、WEB项目的标准结构 五、WEB…

跨站脚本攻击(XSS)原理及防护方案

跨站脚本攻击(XSS,Cross-Site Scripting)是一种常见的网络安全漏洞,攻击者通过在网页中注入恶意脚本,使其在用户的浏览器中执行。XSS攻击可以窃取用户的敏感信息,如cookies、会话令牌等,甚至可以…

基于STM32单片机火灾安全监测一氧化碳火灾

功能描述 0. STM32单片机为控制核心 1. 液晶显示当前温湿度和CO浓度等信息 2. 温湿度传感器检测当前环境温湿度 3. 火焰传感器检测是否发生明火 4. 一氧化碳传感器检测一氧化碳浓度 5. 功能按键可以设置加减和参数阈值,超过阈值蜂鸣器进行报警 6. 当发…

简述mysql 主从复制原理及其工作过程,配置一主两从并验证

第一种基于binlog的主从同步 首先对主库进行配置: [rootopenEuler-1 ~]# vim /etc/my.cnf 启动服务 [rootopenEuler-1 ~]# systemctl enable --now mysqld 主库的配置 从库的配置 第一个从库 [rootopenEuler-1 ~]# vim /etc/my.cnf [rootopenEuler-1 ~]# sys…

规避路由冲突

路由冲突是指在网络中存在两个或多个路由器在进行路由选择时出现矛盾,导致网络数据包无法正确传输,影响网络的正常运行。为了规避路由冲突,可以采取以下措施: 一、合理规划IP地址 分配唯一IP:确保每个设备在网络中都有…