数据结构之线性表（链式表示）

￡神魔★判官ぃ 2022-04-23 15:10 352阅读 0赞

在上篇博文中，我们介绍了线性表的顺序存储，本文将介绍其链式表示方式。  
由于顺序表的插入、删除操作都需要移动大量的元素，这极大的影响了运行效率，所以引进了线性表的链式表示。链式存储线性表时，不需要使用地址连续的存储单元，对线性表的插入删除操作**只需要修改指针，不需要移动元素**。

我们将介绍4种链表形式：

1.  **单链表**
2.  **双链表**
3.  循环链表
4.  静态链表

### 单链表 ###

线性表的链式存储又称**单链表**。它是通过一组任意的存储单元来存储线性表中的数据元素。对于每个链表结点，除了存放元素自身信息外（**数据data**），还需要存放一个指向其后继的指针（**指针next**）。

**单链表中结点类型的描述如下：**

typedef struct LNode{
        
        ElemType data;        //数据域
        struct LNode *next;   //指针域
    }LNode,*LinkList;

**注意：单链表是非随机存取的存储结构，查找某个特定结点时，需要从表头开始遍历，依次查找。  
通常用头指针**来标识一个单链表。为了操作上的方便，\*\*在单链表第一个结点之前附加一个结点，称为头结点。\*\*头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

![1.png][]

**头结点和头指针的区别：**

1.  不管带不带头结点，头指针始终指向链表的第一个结点
2.  头结点是带头结点链表的第一个结点，结点内通常不存储信息

**引入头结点的优点：**

1.  开始结点的位置被放在头结点的指针域中，**链表的第一个位置上的操作和其他位置上的操作一致**，无须进行特殊处理
2.  无论链表是否为空，头指针都是指向头结点的非空指针（**空表中头结点指针域为空**），这样空表和非空表处理统一了

**头插法建立单链表：O(n)**  
该方法从一个空表开始，生成新结点，**将新结点插入到当前链表的表头**，如下所示：

![2.png][]

LinkList CreatList1(LinkList &L){
        
        LNode *s;int x;
        L=(LinkList)malloc(sizeof(LNode));    //创建头结点
        L->next=NULL;
        scanf("%d",&x);                       //输入值
        while(x!=9999){
        
            s=(LNode*)malloc(sizeof(LNode));  //创建新结点
            s->data=x;
            s->next=L-next;
            L-next=s;                        //将新结点插入表L中
            scanf("%d",&x);
        }
        return L;
    }

采用头插法建立单链表，读入数据的顺序与生成的链表中的元素顺序是相反的。

**尾插法建立单链表：O(n)**  
将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，让它始终指向当前链表的尾结点。如下所示：

![3.png][]

LinkList CreatList2(LinkList &L){
        
        int x;
        L=(LinkList)malloc(sizeof(LNode)); 
        LNode *s,*r=L;                           //r为表尾指针
        scanf("%d",&x); 
        while(x!=9999){
        
            s=(LNode*)malloc(sizeof(LNode)); 
            s->data=x;
            r->next=s;
            r=s;                               //r指向新的表尾结点
            scanf("%d",&x);
        }
        r->next=NULL;                          //尾结点指针置空
        return L;
    }

**按序号查找结点值：O(n)**  
从链表第一个结点开始，顺着指针域next向下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域为NULL。

LNode *GetElem(LinkList L,int i){
 
 int j=1;
 LNode *p=L->next;
 if(i==0)
 retuen L;
 if(i<1) //i无效，返回NULL
 return NLLL;
 while(p&&j<i){
 //顺序查找
 p=p->next;
 j++;
 }
 return p;
 }

**按值查找结点：O(n)**  
从链表第一个结点开始，顺着指针域next向下搜索，若某结点的值等于给定值e，返回该结点的指针，否则返回NULL。

LNode *LocateElem(LinkList L,ElemType e){
        
        LNode *p=L->next;
        while(p!=NULL&&p->data!=e)
            p=p->next;
        return p;
    }

**插入结点：** （后插，将s插在p后）复杂度为O(n)  
将值为x的新结点s插入到单链表的第i个位置上。分为3步：

*  调用按序号查找算法`GetElem(L,i-1)`,找到第i-1个结点，假设为p
 *  让新插入结点s的指针域指向p的后继结点
 *  最后让p结点的指针域指向新插入结点s

p=GetElem(L,i-1);
    s->next=p->next;
    p->next=s;

![4.png][]

前插操作均可以转化为后插操作，只需要先找到待插入结点的前驱结点即可。时间主要耗费在查找前驱结点上。

**插入结点：** （前插，将s插在p前）  
可以通过上面的后插方法，除此之外，下面介绍另外一种方法O(1)。

*  仍然将s插入p的后面
 *  **将p->data和s->data交换**

s->next=p->next;    //修改指针域
    p->next=s;
    temp=p->data;       //交换数据域
    p->data=s->data;
    s->data=temp

**删除结点操作：O(n)**  
将单链表的第i个结点删除。先查找表中的第i-1个结点，即被删结点（q）的前驱结点（p），再将其删除。

p=GetElem(L,i-1);
    q=p->next;
    p->next=q->next;
    free(q);

![5.png][]

要实现删除某一个给定结点，通常是找到其前驱结点，然后执行删除操作即可，这样的时间复杂度为O(n)，如上面所示。

**删除结点操作：O(1)**  
其实，删除某一结点也可以通过删除它的后继结点实现。实质上就是将其后继结点的值赋予自身，然后删除后继结点，这样的时间复杂度为O(1)。

**例如：删除给定结点p (q为p的后继结点)**

q=p->next;
    p->data=p->next->data; //和后继结点交换数据
    p->next=q->next;      //将结点q从链中断开 
    free(q);

![6.png][]

### 双链表 ###

单链表中结点只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序的向后遍历。如果想要访问某个节点的前驱结点（插入、删除），只能从头遍历。访问前驱结点的时间复杂度为O(n),访问后继结点的时间复杂度为O(1)。

**双链表的结点描述如下：**

typedef struct DNode{
        
        ElemType data;              //数据域
        struct DNode *prior,*next;  //前驱后后继指针
    }DNode,*DLinkList;

![7.png][]

双链表仅仅在单链表的结点中增加了一个指向其前驱的prior指针，因此，**双链表中执行按值查找和按位查找和单链表相同**。但双链表在插入和删除操作上和单链表不同，这是因为链变的同时prior也要做出修改。**双链表可以很快的找到其前驱结点，插入和删除的时间复杂度为O(1)**。

**插入操作（后插 ：将结点s插在p结点之后）**

s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;

![8.png][]

**插入操作（前插 ：将结点q插在p结点之前）**

p->prior->next=q;
    q->next=p;
    q->prior=p->prior;
    p->prior=q;

![9.png][]

**删除操作：删除p的后继结点q**

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

![10.png][]

**上面2节详细介绍了单链表和双链表的各种操作，接下来简要介绍一下循环链表和静态链表**。

### 循环链表 ###

**循环单链表：**  
与单链表区别在于，表中最后一个结点的指针不是NULL，而是指向头结点。

1.  \*\*判空条件：\*\*头结点的指针是否等于头指针。
2.  任何一个位置上的插入、删除操作等价，无须判断是否为表尾。
3.  可以从表中任意一个结点遍历整个链表。

**循环双链表：**

1.  若结点p为尾结点，p->next=L
2.  为空表时，头结点的prior和next都为L

### 静态链表 ###

1.  借助数组来描述线性表的链式存储结构，也有数据域和指针域
2.  以next==-1作为结束标志
3.  适合于不支持指针的高级语言（如Basic）

![11.png][]

### 顺序表和链表的比较 ###

1.  **存取方式**

> 顺序表：可以顺序存取，也可以随机存取  
> 链表：只能从表头顺序存取

1.  **逻辑和物理结构**

> 顺序表：逻辑相邻的，物理存储也相邻  
> 链表：逻辑相邻的，物理存储不一定相邻

1.  **查找、删除和插入操作**

<table> 
 <thead> 
 <tr> 
 <th align="center"></th> 
 <th align="center">按值查找</th> 
 <th align="center">按号查找</th> 
 <th align="center">插入删除</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">顺序表</td> 
 <td align="center">无序 O(n)；有序O( l o g 2 n log_2^n log2n)</td> 
 <td align="center">O(1)</td> 
 <td align="center">平均移动半个表长</td> 
 </tr> 
 <tr> 
 <td align="center">链表</td> 
 <td align="center">O(n)</td> 
 <td align="center">平均O(n)</td> 
 <td align="center">只需要修改相关结点指针域</td> 
 </tr> 
 </tbody> 
</table>

1.  **空间分配**

> 顺序表：静态（造成溢出）；动态（效率低）  
> 链表：灵活、高效

1.  **选取情况**

> 顺序表： 线性表较稳定；按号访问为O(1)  
> 链表： 线性表长度、规模难以估计；需要频繁插入、删除操作时

[1.png]: /images/20220226/8373e666515042e2b7f288d405d04b0e.png
[2.png]: /images/20220226/e8244eae35544ff7a6b2d2642fb7c994.png
[3.png]: /images/20220226/7cdbb2884cba472fa6ed1983b9f0d682.png
[4.png]: /images/20220226/a369015e23e34e459747bee9b85f74e1.png
[5.png]: /images/20220226/821baa26175a432e945375ed751e45ad.png
[6.png]: /images/20220226/11648abc506b457983f24e4388b45141.png
[7.png]: /images/20220226/01881612cbe54f3dabf7066b7141da4d.png
[8.png]: /images/20220226/4e2f3e05890647c88689679706ac1fbd.png
[9.png]: /images/20220226/4e2df93694af4fd0b95a14bfe420f294.png
[10.png]: /images/20220226/7029a0ae97b8408986d86cc1d518d309.png
[11.png]: /images/20220226/0c4eef118df4474db003f32f4a53db5f.png