🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：前面介绍了线性表的顺序表和链表，本章讲对链表应用拓展，具体介绍单链表、循环链表、双向链表等，并将顺序表与链表进行比较，更直观的感受两种不同结构的差异所在以及各自的优势短板，最后对线性表进行总结。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第四章：链表拓展与线性表总结
📝1️⃣单链表
✨定义和表示
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他用于实现树和图等非线线性结构。
用单链表标示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，由此，这种存储结构为非顺序映像或链式映像。
根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。
✨初始化（前插法）
前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后
编辑
【算法步骤】：
- 创建一个只有头结点的空链表。
- 根据待创建链表包括的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p；
- 输入元素值赋给新结点*p的数据域；
- 将新结点*p插入到头结点之后。
【算法描述】：
void CreateList_H(LinkList &L,int n) { //逆位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 for(i=0;i>p->data; //输入元素值赋给新结点p的数据域 p->next=L->next; L->next=p; //将新结点p插入到头结点之后 } }
✨初始化（后插法）
后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。
编辑
【算法步骤】：
- 创建一个只有头结点的空链表。
- 尾指针r初始化，指向头结点。
- 根据创建链表包括的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p；
- 输入元素值赋给新结点*p的数据域；
- 将新结点p插入到尾结点r之后；
- 尾指针r指向新的尾结点*p。
【算法描述】：
void CreateList_R(LinkList &L,int n) { //正位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 r=L; //尾指针r指向头结点 for(i=0;i>p->data;//输入元素值赋给新结点p的数据域 p->next=NULL; r->next=p; //将新结点p插入尾结点r之后 r=p; //r指向新的尾结点p } }
📝2️⃣循环链表
编辑
✨定义和表示
循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，图所示为单链的循环链表。类似地，还可以有多重链的循环链表。
循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。
在单链表中，判别条件为 p!=NULL 或 p->next!=NULL，而循环单链表的判别条件为p!=L或p->next!=L。
对于循环链表，有时不给出头指针，而给出尾指针，这样可以更快的找出第一个和最后一个结点。
✨循环链表的合并
将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表循环链表作存储结构时，这个操作仅需改变两个指针值即可。
【算法步骤】：
- 将第一个表的尾指针指向第二个表的第一个结点
- 第二个表的尾指针指向第一个表的头结点
- 释放第二个表的头结点。
【算法描述】：
LinkList Connect(LinkList Ta,LinkList Tb) { //假设Ta、Tb都是非空的单循环链表 p = Ta->next;//p存表头结点 Ta->next = Tb->next->next;//Tb表头结点连接Ta表尾 delete Tb->next;//释放Tb表头结点 Tb->next = p;//修改指针 return Tb; }
📝3️⃣双向链表
编辑
✨定义和表示
对于单链表及循环链表这类链式存储结构的结点中，只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)
为克服单链表这种单向性的缺点，可利用双向链表（Double Linked List）。
顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。
✨双向链表的存储结构
和单链的循环表类似，双向链表也可以有循环表，链表中存有两个环，只有一个表头结点的空表。
typedef struct DuLNode { ElemType data; //数据域 struct DuLNode *prior; //直接前驱 struct DuLNode next; //直接后继 }DuLNode,DuLinkList;
✨双向链表的插入（在第i个位置上插入元素e）
编辑
【算法步骤】：
- 找到L中第i个元素的位置指针p。
- 生成新结点s，并将结点s数据域置为要插入的元素e。
- 将结点*s插入L中。
【算法描述】：
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e) {//在带头结点的双向链表L中第i个位置之前插入元素e if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p return ERROR; //p为NULL时，第i个元素不存在 s=new DuLNode; //生成新结点s s->data=e; //将结点s数据域置为e s->prior=p->prior; //将结点*s插入L中 p->prior->next=s;//指针转换 s->next=p; p->prior=s; return OK; }
✨双向链表的删除（删除带头结点的双向链表L中的第i个元素）
编辑
【算法步骤】：
- 找到第i个元素的位置指针p。
- 修改被删结点的前驱结点的后继指针。
- 修改被删结点的后继结点的前驱指针。
【算法描述】：
Status ListDelete_DuL(DuLinkList &L,int i) { //删除带头结点的双向链表L中的第i个元素 if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p return ERROR; //p为NULL时，第i个元素不存在 p->prior->next=p->next; //修改被删结点的前驱结点的后继指针，对应图2.21① p->next->prior=p->prior; //修改被删结点的后继结点的前驱指针，对应图2.21② delete p; //释放被删结点的空间 return OK; }
📝4️⃣ 顺序表和链表的比较
对于线性表的两种结构：顺序表和链表，在实际应用中，不能笼统地说哪种存储结构更好，由于它们各有优缺点，选用哪种存储结构，则应根据具体问题作具体分析，通常从空间性能和时间性能两个方面作比较分析。
| 比较项目 \ 存储结构 | 顺序表 | 链表 | |
| 空间 | 存储空间 | 5预先分配，会导致空间闲置或溢出现象 | 动态分配，不会出现存储空间闲置或溢出现象 |
| 存储密度 | 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1 | 需要借助指针来体现元素间的逻辑关系，存储密度小于1 | |
| 时间 | 存取元素 | 随机存取，按位置访问元素的时间复杂度为O(1) | 顺序存取，按位置访问元素的时间复杂度为O(n) |
| 插入、删除 | 平均移动约为表中一半元素，时间复杂度为O(n) | 不需要移动元素，确定插入、删除位置后，时间复杂度为O(1) | |
| 适用 | ① 表长变化不大，且能事先确定变化的范围。 ② 很少进行插入或者删除操作，经常按元素位置序号访问数据元素。 |
① 长度变化大。 ② 频繁进行插入或者删除操作。 |
|
📝5️⃣线性表的应用
✨顺序有序表的合并
【算法步骤】：
- 创建一个表长为m+n的空表LC。
- 指针pc初始化，指向LC的第一个元素。
- 指针pa和pb初始化，分别指向LA和LB的第一个元素。
- 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
- 如果pb已到达LB的表尾，依次将LA的剩余元素插入LC的最后。
- 如果pa已到达LA的表尾，依次将LB的剩余元素插入LC的最后。
【算法描述】：
void MergeList_Sq(SqList LA,SqList LB,SqList &LC) { //已知顺序有序表LA和LB的元素按值非递减排列 //归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列 LC.length=LA.length+LB.length; //新表长度为待合并两表的长度之和 LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间 pc=LC.elem; //指针pc指向新表的第一个元素 pa=LA.elem; pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素 pa_last=LA.elem+LA.length-1; //指针pa_last指向LA的最后一个元素 pb_last=LB.elem+LB.length-1; //指针pb_last指向LB的最后一个元素 while((pa<=pa_last)&&(pb<=pb_last)) //LA和LB均未到达表尾 { if(pa<=pb) pc++=pa++; //依次“摘取”两表中值较小的结点插入到LC的最后 else pc++=pb++; } while(pa<=pa_last) pc++=pa++; //LB已到达表尾，依次将LA的剩余元素插入LC的最后 while(pb<=pb_last) pc++=pb++; //LA已到达表尾，依次将LB的剩余元素插入LC的最后 }
✨链式有序表的合并
【算法步骤】：
- 指针pa和pb初始化，分别指向LA和LB的第一个结点。
- LC的结点取值为LA的头结点。
- 指针pc初始化，指向LC的头结点。
- 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
- 将非空表的剩余段插入到pc所指结点之后。
- 释放LB的头结点。
【算法描述】：
void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC) { //已知单链表LA和LB的元素按值非递减排列 //归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列 pa=LA->next;pb=LB->next; //pa和pb的初值分别指向两个表的第一个结点 LC=LA; //用LA的头结点作为LC的头结点 pc=LC; //pc的初值指向LC的头结点 while(pa&&pb) {//LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到LC的最后 if(pa->data<=pb->data) //“摘取”pa所指结点 { pc->next=pa; //将pa所指结点链接到pc所指结点之后 pc=pa; //pc指向pa pa=pa->next; //pa指向下一结点 } else //“摘取”pb所指结点 { pc->next=pb; //将pb所指结点链接到pc所指结点之后 pc=pb; //pc指向pb pb=pb->next; //pb指向下一结点 } } //while pc->next=pa?pa:pb; //将非空表的剩余段插入到pc所指结点之后 delete LB; //释放LB的头结点 }
📝6️⃣线性表总结
（1）线性表的逻辑结构特性是指数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。
（2）对于顺序表，元素存储的相邻位置反映出其逻辑上的线性关系，可借助数组来表示。给定数组的下标，便可以存取相应的元素，可称为随机存取结构。而对于链表，是依靠指针来反映其线性逻辑关系的，链表结点的存取都要从头指针开始，顺链而行，所以不属于随机存取结构，可称之为顺序存取结构。不同的特点使得顺序表和链表有不同的适用情况，表中分别从空间、时间和适用情况3方面对二者进行了比较。
（3）对于链表，除了常用的单链表外，在本章还讨论了两种不同形式的链表，即循环链表和双向链表，它们有不同的应用场合。下表对三者的几项有差别的基本操作进行了比较。
