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

server/2025/1/22 23:09:51/

目录

一.顺序表的定义

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/server/160581.html

相关文章

K8S-Pod的环境变量,重启策略,数据持久化,资源限制

1. Pod容器的三种重启策略 注意:k8s所谓的重启容器指的是重新创建容器 cat 07-restartPolicy.yaml apiVersion: v1 kind: Pod metadata:name: nginx-web-imagepullpolicy-always spec:nodeName: k8s233.oldboyedu.com## 当容器异常退出时,始终重启容器r…

商汤善惠获金沙江创投领投A轮融资,聚焦零售AI业务

1月20日,商汤善惠宣布完成A轮融资,本轮融资由金沙江创投数千万元领投,微木资本、嘉实基金和金弘基金等知名资管平台和产业资本数千万元跟投,鞍羽资本担任长期财务顾问。 此次融资将重点投向零售AI算法研发创新、海外市场拓展战略…

电子商务的安全

1 9 8 8年11月3日,美国数千名计算机系统操作员和系统管理员上班后都发现计算机系统不作了,不管他们怎么尝试,计算机都不响应。追查这个灾难事件后发现是康奈尔大学2 3岁的研究生小罗伯特莫里斯( Robert Morris Jr.)干的…

“深入浅出”系列之数通篇:(3)负载均衡

负载均衡:如果有多条等价路由(即目的地址、掩码、优先级和度量值都相同,但下一跳地址和出接口不同的路由),路由器可以实现负载分担,将流量分散到多条路径上。 分布式项目中负载均衡的实现 负载均衡的实现…

Linux——入门基本指令汇总

目录 1. ls指令2. pwd3. whoami指令4. cd指令5. clear指令6. touch指令7. mkdir指令8. rm指令9. man指令10. cp指令11. mv指令12. cat指令13. tac指令14. more指令15. less指令16. head指令17. tail指令18. date指令19. cal指令20. find指令21. which指令22. alias指令23. grep…

如何将本地电脑上的文件夹设置为和服务器的共享文件夹

将本地电脑上的文件夹设为与服务器共享的文件夹,通常是在本地开启文件共享,并配置相应的权限,使服务器可以访问该文件夹。以下以 Windows 系统为例说明具体操作步骤: 一、在本地电脑上设置共享文件夹 选择文件夹 找到需要共享的文…

图论DFS:黑红树

我的个人主页 {\large \mathsf{{\color{Red} 我的个人主页} } } 我的个人主页 往 {\color{Red} {\Huge 往} } 往 期 {\color{Green} {\Huge 期} } 期 文 {\color{Blue} {\Huge 文} } 文 章 {\color{Orange} {\Huge 章}} 章 DFS 算法:记忆化搜索DFS 算法&#xf…

jvm G1 垃圾收集日志分析示例(GC)

一、gc 日志 2023-11-07 12:40:53 GC log file created /opt/logs/query/gc.log.1 Java HotSpot(TM) 64-Bit Server VM (25.45-b02) for linux-amd64 JRE (1.8.0_45-b14), built on Apr 10 2015 10:07:45 by "java_re" with gcc 4.3.0 20080428 (Red Hat 4.3.0-8) M…