【数据结构与算法】第四章：链表拓展与线性表总结

 🙊🙊作者主页：🔗求不脱发的博客

📔📔 精选专栏：🔗数据结构与算法

📋📋 精彩摘要：前面介绍了线性表的顺序表和链表，本章讲对链表应用拓展，具体介绍单链表、循环链表、双向链表等，并将顺序表与链表进行比较，更直观的感受两种不同结构的差异所在以及各自的优势短板，最后对线性表进行总结。

💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞

📚目录

📖【数据结构与算法】第四章：链表拓展与线性表总结

📝1️⃣单链表

📝2️⃣循环链表

📝3️⃣双向链表

📝4️⃣顺序表和链表的比较

📝5️⃣线性表的应用

📝6️⃣线性表总结

📖【数据结构与算法】第四章：链表拓展与线性表总结

📝1️⃣单链表

✨定义和表示

根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他用于实现树和图等非线线性结构。

用单链表标示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，由此，这种存储结构为非顺序映像或链式映像。

根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。

✨初始化（前插法）

前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后 编辑

【算法步骤】：

1. 创建一个只有头结点的空链表。
2. 根据待创建链表包括的元素个数n，循环n次执行以下操作：

1. 生成一个新结点*p；
   
2. 输入元素值赋给新结点*p的数据域；
   
3. 将新结点*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指向链表的尾结点。 编辑

【算法步骤】：

1. 创建一个只有头结点的空链表。
2. 尾指针r初始化，指向头结点。
3. 根据创建链表包括的元素个数n，循环n次执行以下操作：

1. 生成一个新结点*p；
2. 输入元素值赋给新结点*p的数据域；
3. 将新结点p插入到尾结点r之后；
4. 尾指针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。

对于循环链表，有时不给出头指针，而给出尾指针，这样可以更快的找出第一个和最后一个结点。

✨循环链表的合并

将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表循环链表作存储结构时，这个操作仅需改变两个指针值即可。

【算法步骤】：

1. 将第一个表的尾指针指向第二个表的第一个结点
2. 第二个表的尾指针指向第一个表的头结点
3. 释放第二个表的头结点。

【算法描述】：

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） 编辑

【算法步骤】：

1. 找到L中第i个元素的位置指针p。
2. 生成新结点s，并将结点s数据域置为要插入的元素e。
3. 将结点*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个元素）

编辑

【算法步骤】：

1. 找到第i个元素的位置指针p。
2. 修改被删结点的前驱结点的后继指针。
3. 修改被删结点的后继结点的前驱指针。

【算法描述】：

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. 创建一个表长为m+n的空表LC。
2. 指针pc初始化，指向LC的第一个元素。
3. 指针pa和pb初始化，分别指向LA和LB的第一个元素。
4. 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
5. 如果pb已到达LB的表尾，依次将LA的剩余元素插入LC的最后。
6. 如果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的最后
}

✨链式有序表的合并

【算法步骤】：

1. 指针pa和pb初始化，分别指向LA和LB的第一个结点。
2. LC的结点取值为LA的头结点。
3. 指针pc初始化，指向LC的头结点。
4. 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
5. 将非空表的剩余段插入到pc所指结点之后。
6. 释放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）对于链表，除了常用的单链表外，在本章还讨论了两种不同形式的链表，即循环链表和双向链表，它们有不同的应用场合。下表对三者的几项有差别的基本操作进行了比较。