Hello everybody!今天打算跟大家聊聊动态顺序表。顺序表是最基础的数据结构，也是最实用的数据结构。在今后学习栈和队列时，会基于顺序表去实现它们。动态顺序表顾名思义，就是容量可变的顺序表。我们可以随意在该顺序表中插入数值，并且会自动扩容，十分具有实际应用的价值。那废话不多说，让我们开始叭！
1.顺序表的概念及结构
顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数值存储。在数值上完成数据的增删查改。
顺序表一般可以分为：
由于静态顺序表实用价值极低，实现思路上不如动态顺序表，且会实现动态顺序表的话实现静态顺序表也没有太大的问题。因此在这里只给大家详细讲解一下动态顺序表的实现！
2.动态顺序表的实现
2.1创建新项目
进入数据结构，我们要写的代码量会有十分明显的增加。例如今天的动态顺序表，代码量将会轻轻松松突破100行。所以我建议创建三个文件。这样便于理清代码逻辑以及后期代码的维护。我在上一篇文章和上上篇文章中有更详细的介绍，如果有疑问可以参考栈详解或队列详解。
2.2动态顺序表的创建
首先我们要把需要用到的头文件包含进来，下面的结构体就是咱们的顺序表。其中各个变量的作用我已经注释出来。结构体的下面是顺序表的各种接口。
2.3接口的实现及测其功能
2.3.1初始化
首先我们来解释一下为什么要传结构体指针而不是结构体：要知道，函数传参是对实际参数的拷贝。如果传结构体的话，在函数体内部的一切操作都不会对函数外部的结构体有任何改变，所以我们需要传指针。
2.3.2尾插
在测试功能中，我们首先初始化，然后依次尾插了1，2，3，4，5，五个数据。该动态顺序表应该会扩容两次，因此容积是8，有效数据有5个，size为5。测试结果符合预期，这两个接口功能正常。
2.3.3头插
由于头插依然会涉及到顺序表容量不够用从而自动扩容的情况，那么这个接口会有相当一部分代码和尾插一模一样。考虑到代码的简洁性，我们把自动扩容功能单独拎出来形成一个函数：
有了这个函数，头插和尾插直接调用它就ok了！
在头插中，我们需要移动数据。在while循环中把所有的数据向后移动一位，再把要插入的数据把顺序表中的第一个数据覆盖掉。移动数据的时间复杂度是O(n)，效率不高。由此可见顺序表并不适合头插。同样的，也不适合头删。
2.3.4尾删&头删
尾删和头删的逻辑就比较简单了。但是要特别说明一下，尾删和头删并不是正在意义上的和数据删除了，对于尾删，只需把size减小一个就可以了，以后插入数据的话自然会把原数据覆盖掉。头删就是用后面的数据向前覆盖，也是同样的道理。
2.3.5打印&从任意位置插入
2.3.6删除任意位置的数据
2.3.7查找
2.3.8销毁顺序表
3.结语
好啦，关于动态顺序表的讨论就到这里喽。看完这篇文章依然没有搞懂的宝子可以把自己的疑惑发在评论区呦！
原文地址:https://blog.csdn.net/c565114/article/details/134564863
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_2960.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
![[H数据结构] lc295. 数据流的中位数(对顶堆+技巧+思维+代码实现)](http://www.7code.cn/wp-content/uploads/2023/11/ee6748cbc735e6105405f8a984d954c804b93f34bc916-Z0IqTf_fw1200.png)
