线性表笔记之于大话数据结构

---

本文主要是通过阅读大话数据结构第三章，总结一些自己对线性表得所得与所想，希望能对您有所帮助，也为方便自己日后查阅。若有错误之处，请大佬指出:happy:

线性表得定义

定义：零个或多个数据元素的有限序列。

线性表有以下特性：

线性表是个序列。元素之间是有顺序的，除第一个和最后一个，每个元素都有且只有一个前驱和后继。

线性表是有限的。

数据元素的类型是一样的。

线性表的抽象数据类型

线性链表的抽象数据类型，也就是时说线性表应该有什么样的操作呢。

线性表的抽象数据类型定义如下：

线性表的顺序存储结构

顺序存储结构定义：用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的存储示意图如下：

顺序存储方式

可以通过一维数组来实现顺序存储结构。

线性表的顺序存储的结构代码：

数据长度与线性表长度区别

区别如下：

地址计算方法

由于存储器中的每个存储单元都有自己的编号，即地址。假设每个数据元素都占用一个固定的存储单元c，那么可以得到任意存储位置的地址：
$$
LOC(a_i)=LOC(a_1)+(i-1)*c
$$
对顺序存储结构的线性表来说，存入或者取出数据，的时间复杂度都为O(1)。通常把具有这一特点的存储结构称为随机存取结构。

顺序存储结构的插入与删除

获得元素操作

要是实现获得数据GetElem操作，只要 i 的数值在数组下标范围内，就是把数组第 i-1下标返回即可。代码如下：

插入操作

要实现ListInsert(*L,i,e)，即在线性表L中的第i个位置插入新元素e，该如何操作？

插入算法的思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置；
• 将要插入的元素填入位置i处；
• 表长加1；

代码实现如下：

删除操作

删除算法的思路：

• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素位置，开始遍历到最后一个元素位置，分别将它们都向前移动一个个位置；
• 表长减1；

实现代码如下：

插入和删除的时间复杂度都为O(n)

线性表顺序存储结构的优缺点

优缺点总结如下：

线性表的链式存储结构

线性链表的特点：

• 用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这些元素可以在未被占用内存的任意位置。

链式存储结构的组成部分：

• 数据域：用来存储数值信息；
• 指针域：用来指向后继元素存储地址的指针。

把一个元素的指针域和数据域组成的存储映像，称为节点。

把链表中第一个节点的存储位置叫做头指针，整个链表都是从头指针开始进行的。

最后一个节点的指针为空（通常用NULL或"^"表示）。

通常在第一个节点前添加一个头节点。头节点的数据域可以为空，也可以存储线性表的长度等附加信息。

头节点和头指针的区别：

通过下图可更加直观的明白头指针和头结点大的区别：

假设p是指向线性表的第i个元素的指针，该结点的数据域为p->data值是一个数据元素，指针域为p->next是一个指针。

单链表

单链表的读取

获得链表第i个数据的算法思路：

• 声明一个结点p指向链表第一个结点，初始化j从1开始；
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
• 若到链表末尾p为空，则说明第i个元素不存在；
• 否则查找成功，返回结点p的数据；

实现代码为：

简单说就是从头开始遍历，直到第i个元素为止。此时的时间复杂度，最差为O(n)

单链表插入

要把s结点插入，则只需，s->next=p->next和p->next=s即可。切记这两句命令不能顺序颠倒。把p的后继结点改为s的后继结点，再把结点s改成p的后继结点。

在表头和表尾的插入操作：

单链表第i个数据插入结点的算法思路：

• 声明一个结点p指向链表第一个结点，初始化j从1开始；
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
• 若到链表末尾p为空，则说明第i个元素不存在；
• 否则查找成功，在系统中生成一个空结点s；
• 将数据元素e赋值给s->data；
• 单链表的插入标准语句s->next=p->next; p->next=s;;
• 返回成功；

代码如下：

单链表删除

只需要做p->next=p->next->next,即可。令q=p->next。

单链表删除的算法步骤：

• 声明一结点p指向链表第一个结点，初始化j从1开始；
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
• 若链表末尾p为空，则说明第 i 个元素不存在；
• 否则查找成功，将欲删除的结点p->next赋值给q；
• 单链表的删除标准语句p->next=q->next;
• 将q结点中的数据赋值给e，作为返回；
• 释放q结点；
• 返回成功；

实现代码如下：

单链表的整表创建

创建单链表的过程是一个动态生成链表的过程，即从空表的初始状态，依次建立各元素结点，并逐个插入链表。

头插法：

单链表整表创建的算法思路：

• 声明一个结点p和计数器变量i;
• 初始化一个空链表L；
• 让L的头结点的指针指向NULL,即建立一个带头结点的单链表；
• 循环：
  • 生成一个新节点赋值给p；
  • 随机生成一个数字赋值给p的数据域p->data；
  • 将p插入到头结点与之前新一结点之间；

代码实现如下：

如图所示：

事实上很少有使用头插法的，因为自古以来都是“先来后到之说”。

尾插法代码如下：

流程图如下：

单链表的整表删除

单链表整表删除的算法思路如下：

• 声明一个结点p和q；
• 将第一个结点赋值给p；
• 循环：
  • 将下一个结点赋值给q；
  • 释放p；
  • 将q赋值给p；

实现代码如下：

代码中的q不能去除，因为q相当于寄存p结点后继结点的容器，若直接删除p而没有q会导致无法知道后继是谁，造成无法删除。

单链表结构与顺序存储结构优缺点

• 总之，若线性表中的元素个数变化较大，需要频繁的插入和删除操作时，宜采用单链表结构，反之对于知道数组大小，而且很少插入和删除的操作时宜采用顺序存储结构的线性表。

静态链表

静态链表主要是针对没有指针的语言，了解它更多的取其思想之精华，以为日后之借鉴。

对于没有指针的语言来说，就不能像单链表一样通过指针域来进行链接。但是大佬就是大佬，他们提出使用数组来代替指针。

让数组的每个元素都是由两个数据域组成，data和cur。数组的每个下标都对应一个data和一个cur。cur叫做游标，相当于单链表中的next指针，存放后继元素中的数组下标。

通常对数组中第一个和最后一个元素，不存数据。

数组的第一个元素的cur存放备用链表的第一个结点的下标；最后一个元素的cur存放第一个有数值的元素的下标，相当于单链表中的头结点。

初始化的空的静态链表代码如下：

静态链表的插入

为了找到数组中哪些分量未被使用，通过将所有未被使用过的以及删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入得新节点。

返回待插入结点得下标代码：

插入第i个元素的代码如下：

静态链表的删除

释放结点的实现代码：

其中Free_SSL(L, j)为：

静态链表的长度

实现代码：

根据下面这个图就明白了：

i的初始值为1，然后一直循环，知道最后一个元素的cur值为0，即i=0后跳出循环，通过计数j得出元素的个数。

静态链表的优缺点

总上可知，静态链表主要是针对没有指针的语言。对于有指针的语言，不会用到它的。主要是学习其思想。

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。

循环链表和单链表的主要差异在循环的判断条件上：

• 单链表是判断p->next是否为空，来判断是否停止；
• 循环链表是判断p->next是否等于头结点，来判断是否循环结束；

将两个循环链表合并：

只需要执行以下代码即可实现：

p = rearA->next;            //保留A的头，即①
rearA->next = rearB->next->next; // 即A的尾指针指向B的第一个结点,即②
rearB->next = p; // B的尾指针指向A头结点，形成循环链表，即③
free(p); // p是新建的一个指针，用完后要及时释放，否则可能会内存泄漏和占用            //内存

双向链表

为了克服链表单向性这一缺点，在单链表的每个结点中，再设置一个指向其前驱结点的指针域，形成双向链表。

双向循环链表：

p->next->prior = p = p->prior->next这应该很好理解吧！

双向链表很多都是由单向链表扩展的，基本操作大同小异。但是在插入操作时要注意顺序，千万不能反了。

由于第2步和第3步，都用到了p->next如果先执行第四步，则使p->next提前变为s。顺序使先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

删除操作：

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

---

感谢阅读:smile:.