【数据结构】动态顺序表详解

目录

1.顺序表的概念及结构

2.动态顺序表的实现

2.1创建新项目

2.2动态顺序表的创建

2.3接口的实现及测其功能

2.3.1初始化

2.3.2尾插

2.3.3头插

2.3.4尾删&头删

2.3.5打印&从任意位置插入

2.3.6删除任意位置的数据

2.3.7查找

2.3.8销毁顺序表

3.结语

---

Hello everybody!今天打算跟大家聊聊动态顺序表。顺序表是最基础的数据结构，也是最实用的数据结构。在今后学习栈和队列时，会基于顺序表去实现它们。动态顺序表顾名思义，就是容量可变的顺序表。我们可以随意在该顺序表中插入数值，并且会自动扩容，十分具有实际应用的价值。那废话不多说，让我们开始叭！

1.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数值存储。在数值上完成数据的增删查改。

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储元素

2.动态顺序表：使用动态开辟的数组存储

由于静态顺序表实用价值极低，实现思路上不如动态顺序表，且会实现动态顺序表的话实现静态顺序表也没有太大的问题。因此在这里只给大家详细讲解一下动态顺序表的实现！

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.结语

好啦，关于动态顺序表的讨论就到这里喽。看完这篇文章依然没有搞懂的宝子可以把自己的疑惑发在评论区呦！

顺序表是数据结构的基础，大家一定要熟悉它！