数据结构学习笔记3——链表(数组、单链表、双链表、循环链表)

叁歲伎倆 2022-09-07 12:16 203阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70][]

# 1.线性表的定义 #

定义：由n(n>=0)个数据特性相同的元素构成的有限序列称为**线性表**。  
线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为**空表**。

对于非空的线性表或线性结构，其**特点**是：

*  (1)存在唯一的一个被称作"第一个"的数据元素；
 *  (2)存在唯一的一个被称作"最后一个"的数据元素；
 *  (3)除第一个之外，结构中的每个数据元素均只有一个前驱；
 *  (4)除最后一个之外，结构中的每个数据元素均只有一个后继。

# 2.顺序表的定义 #

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为**顺序表**(SequentialList)。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

##  ##

## 2.1 线性表的顺序存储结构 ##

#define MAXSIZE 100    //顺序表可能达到的最大长度
    typedef struct
    {
        ElemType *elem;//存储空间的基地址
        int length;//当前长度
    }SqList;//顺序表的结构类型为SqList

## 2.2 线性表的抽象数据类型定义 ##

抽象数据类型仅是一个模袒的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。在实际应用中，数据元素可能有多种类型，到时可根据具体需要选择使用不同的数据类型。

ADT List
    {
    数据对象：D={ai|ai属于ElemSet,i=l,2,…,n}
    
    数据关系：R=(<ai-1,ai>|ai-1,ai属于D,i=2,…,n}
    
    基本操作：
    InitList(&L)
    	操作结果：构造一个空的线性表L。
    	
    DestroyList(&L)
    	初始条件：线性表L已存在。
    	操作结果：销毁线性表L。
    	
    ClearList(&L)
    	初始条件：线性表L已存在。
    	操作结果：将L重置为空表。
    	
    ListEmpty(L)
    	初始条件：线性表L已存在。
    	操作结果：若L为空表，则返回true,否则返回false。
    	
    ListLength(L)
    	初始条件：线性表L已存在。
    	操作结果：返回L中数据元素个数。
    
    GetElem(L,i,&e)
    	初始条件：线性表L巳存在，且1:,s;i:os;ListLength(L)。
    	操作结果：用e返回L中第1个数据元素的值。
    	
    LocateElem(L,e)
    	初始条件：线性表L已存在。
    	操作结果：返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0。
    	
    PriorElem(r,,cur_e,&pre_e)
    	初始条件：线性表L已存在。
    	操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。
    	
    NextElem(L,cur_e,&next_e)
    	初始条件：线性表L已存在。
    	操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。
    	
    Listinsert(&L,i,e)
    	初始条件：线性表L已存在，且1:,s;i:os;ListLength(L)+l。
    	操作结果：在L中第1个位置之前插入新的数据元素e,L的长度加1。
    	
    ListDelete(&L,i)
    	初始条件：线性表L已存在且非空，且l:os;i:os;ListLength(L)。
    	操作结果：删除L的第1个数据元素，L的长度减1。
    	
    TraverseList(L)
    	初始条件：线性表L已存在。
    	操作结果：对线性表L进行遍历，在遍历过程中对L的每个结点访问一次。
    )ADT List

# 3.单链表的定义 #

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单  
元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素![a\_\{i\}][a_i]与其直接后继数据元素  
![a\_\{i+1\}][a_i_1] 之间的逻辑关系，对数据元素![a\_\{i\}][a_i]来说，除了存储其本身的信息之外，还需存储一个指示其直  
接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素![a\_\{i\}][a_i]的存储映像，称为结点(node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称  
为指针域。指针域中存储的信息称作指针或链。n个结点(![a\_\{i\}][a_i](1![\\leqslant][leqslant] **i **![\\leqslant][leqslant]n)的存储映像）链结成一  
个链表，即为线性表

![20210823150835923.png][]

的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或**单链表**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 2][]

## 3.1 单链表的存储结构 ##

typedef struct LNode
    	ElemType data; //结点的数据域
    	struct LNode *next;//结点的指针域
    }LNode,*LinkList;//LinkList为指向结构体LNode的指针类型

## 3.2 首元结点、头结点、头指针 ##

一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为**头结点**。

![2021082315190558.png][]

下面对首元结点、头结点、头指针三个容易混淆的概念加以说明。

*  (I) 首元结点是指链表中存储第一个数据元素a1 的结点。如图2.8 或图2.9 所示的结点"ZHAO"。
 *  (2) 头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。
 *  (3) 头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

# 4.循环链表 #

循环链表(CircularLinked List)是另一种形式的链式存储结构。其特点是表中最后一个结点  
的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，  
图2.17所示为单链的循环链表。类似地，还可以有多重链的循环链表。

![20210823152213453.png][]

循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时， 判别当前指针p是否  
指向表尾结点的终止条件不同。在单链表中，判别条件为p != NULL或p->next != NULL,而循环  
单链表的判别条件为p != L或p->next != L。

# 5.双向链表 #

上面讨论的链式存储结构的结点中只有一个指示直接后继的指针域， 由此， 从某个结点出发  
只能顺指针向后寻查其他结点。若要寻查结点的直接前驱， 则必须从表头指针出发。换句话说，  
在单链表中，查找直接后继结点的执行时间为0(1), 而查找直接前驱的执行时间为O(n)。为克服  
单链表这种单向性的缺点，可利用**双向链表**(Double Linked List)。在双向链表的结点中有两个指针域， 一个指向直接后继， 另一个指向直接前驱，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 3][]

##  双向链表的存储结构 ##

typedef struct DuLNode
    {
    	ElemType data;//数据域
    	struct DuLNode *prior;//直接前驱
    	S七ruct DuLNode *next;//直接后继
    }DuLNode,*DuLinkList;

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

## 6.1 空问性能的比较 ##

(1)存储空间的分配  
顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。  
(2)存储密度的大小  
链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即

![2021082315303429.png][]

存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1 ，而链表的存储密度小于1。如果每个元素数据域占据的空间较小， 则指针的结构性开销就占用了整个结点的大部分空间，这样存储密度较小。例如， 若单链表的结点数据均为整数，指针所占用的空间和整型量相同，则单链表的存储密度为0.5。因此，如果不考虑顺序表中的空闲区，则顺序表的存储空间利用率为100%, 而单链表的存储空间利用率仅为50%。  
基于此，当线性表的长度变化不大，易千事先确定其大小时，为了节约存储空间，宜采用顺  
序表作为存储结构。

## 6.2 时间性能的比较 ##

(l)存取元素的效率  
顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号i' 都可以在![O(1)][O_1]  
时间内直接存取该位置上的元素， 即取值操作的效率高；而链表是一种顺序存取结构，按位置访  
问链表中第！个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时  
间复杂度为![O(n)][O_n] 即取值操作的效率低。  
基于此，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，  
宜采用顺序表作为存储结构。  
(2)插入和删除操作的效率  
对千链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为![O(1)][O_1]。而对千顺序表，进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为![O(n)][O_n]。尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。  
基千此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。

## 6.3 表格对比 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70]: /images/20220829/446df332fc2a43e48d6fea89f67f0e56.png
[a_i]: https://latex.codecogs.com/gif.latex?a_%7Bi%7D
[a_i_1]: https://latex.codecogs.com/gif.latex?a_%7Bi&plus;1%7D
[leqslant]: https://latex.codecogs.com/gif.latex?%5Cleqslant
[20210823150835923.png]: /images/20220829/c238588ec41b4b8bae2f2f3503c71431.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 1]: /images/20220829/3e0a41e555f14c349df0c0d9e58888da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 2]: /images/20220829/2e8c8f4f55bc4126800184c175c18399.png
[2021082315190558.png]: /images/20220829/a148f89cc4dc476ca85d8f144ac66734.png
[20210823152213453.png]: /images/20220829/8739f2e7bdd743f188567f66c7a6f678.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 3]: /images/20220829/fa66d337bff3470abcaefbe75cf5f15f.png
[2021082315303429.png]: /images/20220829/d915355dc60643f494cbaf4dd4ba3e5a.png
[O_1]: https://latex.codecogs.com/gif.latex?O%281%29
[O_n]: https://latex.codecogs.com/gif.latex?O%28n%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 4]: /images/20220829/10cd5adf927b4f6f8e25eb92f779c538.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 5]: /images/20220829/a00bbdd10f2f4424a49cb2d848fbff07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvbGluNjc4_size_16_color_FFFFFF_t_70 6]: /images/20220829/2acf1dfbad8b4d13a437bfd0b4c9290e.png