第3章-线性表的定义与实现-六虎

敞开掘金生长之旅！这是我参与「掘金日新方案 12 月更文挑战」的第11天，点击查看活动概况

第一章《数据结构与算法是什么？》说过数据结构有四种逻辑结构，线性结构是最根本和最常用的一种，它表示的是线性结构，元素之间存在1对1的联系，数据元素之间按照某种规则存在一个次序联系。

一、界说

假设有 $n$ 个同类型数据元素的有限序列，记为：

L = (a_1,\ a_2,\ a_3,\ …, a_i,\ …,\ a_n)

它构成一个线性表，任何一种逻辑结构都能够运用次序存储和链式存储来完成，运用次序存储时，会在内存中分配接连的空间来存储数据元素，在程序中经常运用数组来完成。

但很多时分无法知道预先分配多大的空间合适，假如数据量较大时，内存中不存在那么大的接连空间，所以会导致内存分配失利，此刻就能够运用链式存储来完成。

链式存储能够运用任何地址的空间存放数据元素，能够空间不接连，它存放的数据结点，里边包括数据元素和指向另一个数据元素的引证（或指针）。

数据结构包括数据的根本操作，运用不同的存储结构来完成线性表的刺进、删去、查找、遍历等根本操作。

初始化一组数据 $a_1,\ a_2,\ a_3,\ a_4,\ a_5)$ ，然后在 $a_2$ 后边刺进数据 $a_6$ 。

次序存储中，定位到 $a_2$ ，需求将 $a_3,\ a_4,\ a_5$ 往后移动才干刺进。

链式存储中，定位到 $a_2$ ，然后把 $a_2$ 的指针指向 $a_6$ ，再把 $a_6$ 的指针指向 $a_3$ 就完成了新节点的刺进。

由此可得链表比次序表刺进的功率高。

次序存储需求预先分配内存空间，在刺进时初始化的空间不够会抛异常。

初始化一组数据 $a_1,\ a_2,\ a_3,\ a_4,\ a_5)$ ，然后删去数据 $a_3$ 。

次序存储中，定位到 $a_3$ 删去并开释内存，然后将 $a_4,\ a_5$ 往前移动。

链式存储中，定位到

a_2

，然后把

a_2

的指针指向

a_4

，开释内存即可删去。

由此可得链表比次序表删去的功率高。

初始化一组数据 $a_1,\ a_2,\ a_3,\ a_4,\ a_5)$ ，然后查找数据 $a_3$ 。

次序存储中，数据在内存中是接连的，假如已知 $a_3$ 的下标，能够直接获取到该数据元素。

在下标不知道的情况下，也能够经过遍向来查找。

链式存储中，数据在内存中是无序的，不能经过下标查找，只能经过遍向来查找数据。

而链式存储在遍历的时分，会添加寻址的操作。

由此可得次序表比链表查找的功率高。

初始化一组数据 $a_1,\ a_2,\ a_3,\ a_4,\ a_5)$ ，然后遍历所有数据。

次序存储中，遍历接连内存空间上的数据元素。

链式存储中，经过地址引证来找到下一个数据元素，来遍历所有数据。

链式存储添加了寻址的操作，所以遍历的功率低于次序存储。

前面讲的链式结构完成的线性表都是单向链表，能够添加结点的引证来创立更多的链表结构，比如：双向链表、单向循环链表和双向循环链表等。

具体的代码完成如下：

Gitee：gitee.com/code_artist…

GitHub：github.com/AiJiangnan/…