【数据结构——线性表之链表】

- 日理万妓 2022-12-11 07:59 387阅读 0赞

# 【数据结构——线性表之链表】 #

### 目录 ###

*  【数据结构——线性表之链表】
 *  一、单链表
 *   *  （一）单链表的描述
     *  （一）单链表的操作实现
     *   *  1、初始化
         *  2、查找
         *  3、插入
         *  4、删除
         *  5、单链表的建立（前插法）
         *  6、单链表的建立（后插法）
 *  二、循环链表
 *  三、双向链表
 *   *   *  1、插入
         *  1、删除

# 一、单链表 #

## （一）单链表的描述 ##

typedef struct LNode {
        
    	ElemType data;//结点数据域
    	struct LNode* next;//结点指针域
    }LNode ,*LinkList;
    
    变量定义：
    LNode* p, * q     LinkList L;
    p, q, L都是指针变量，* p, * q, * L都是结点变量
    
    指针变量p : 表示结点地址
    结点变量* p：表示一个结点
    
    p->data;//表示数据域
    p->next;//表示指针域

typedef struct LNode {
        
    	ElemType data;//结点数据域
    	struct LNode* next;//结点指针域
    }LNode ,*LinkList;
    
    LinkList p, s, L;//指针变量的定义
    L = new LNode;//为指针变量L分配内存空间
    p = L;//p指向头结点
    s = L->next;//s指向首元结点

## （一）单链表的操作实现 ##

### 1、初始化 ###

> 算法思想：  
> （1）、生成新结点作为头结点，用头指针L指向头结点  
> （2）、头结点的指针域置为空

/*初始化*/
    Status InitList(LinkList& L)
    {
        
    	L = new LNode;//生成新结点作为头结点，用头指针L指向头结点
    	L->next = NULL;//头结点的指针域置为空
    	return OK;
    }

### 2、查找 ###

![在这里插入图片描述][20201004215217796.png_pic_center]

> 算法思想：  
> （1）、初始化，p指向第一个结点，j为计数器  
> （2）、从链表头依次向后扫描，直到p为空或p指向第i个元素  
> （3）、更新p指向当前结点，计数器+1  
> （4）、i 值不合法（i<=0或者i>n)  
> （5）、取第i个结点的数据域

/*按序号查找*/
    Status GetElem(LinkList L, int i, ElemType& e)
    {
        
    	LinkList p;
    	int j;
    	p = L->next;j = 1;//初始化，p指向第一个结点，j为计数器
    	while (p && j < i)//从链表头依次向后扫描，直到p为空或p指向第i个元素
    	{
        
    		p = p->next;//更新p指向当前结点
    		++j;//计数器+1
    	}
    	if (!p || j > i) return ERROR;//i 值不合法（i<=0或者i>n)
    	e = p->data;//取第i个结点的数据域
    	return OK;
    }

### 3、插入 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

> 算法思想：  
> (1)找到a i - 1的存储位置p  
> (2)生成一个新结点 \* s  
> (3)将新结点 \* s的数据域置为e  
> (4)新结点 \* s的指针域指向a i  
> (5)结点*p指针域指向结点*s

/*插入*/
    Status ListInsert(LinkList & L, int i, ElemType e)
    {
        
    	p = L;
    	int j = 0;
    	while (p && j < i - 1)//寻找第i - 1个结点
    	{
        
    		p = p->next;//指向当前结点
    		++j;
    	}
    	if (!p || j > i - 1) return ERROR;//i值不合法
    	LinkList s;
    	s = new LNode;//生成新结点s
    	s->data = e;//新结点的数据域置为e
    	s->next = p->next;//新结点 * s的指针域指向a i
    	p->next = s;//结点*p指针域指向结点*s
    	return OK;
    }

### 4、删除 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

> 算法思想：  
> (1)查找结点a i-1所在位置，并由指针p指向该结点  
> (2)临时保存待删除结点ai的地址在q中，以备释放  
> (3)将结点\*p指向结点ai的直接后继结点  
> (4)释放结点ai的空间

Status LinkDelete(LinkList & L, int i)
    {
        
    	p = L;
    	j = 0;
    	while (p->next && j < i - 1)//寻找第i-1个结点
    	{
        
    		p = p->next;
    		++j;
    	}
    	if (!(p->next) || j > i - 1) return ERROR;
    	q = p->next;//临时保存待删除结点ai的地址在q中，以备释放
    	p->next = q->next;//将结点*p指向结点ai的直接后继结点
    	delete q;//释放结点ai的空间
    	return OK;
    }

### 5、单链表的建立（前插法） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]

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

> 算法思想  
> （1）创建一个只有头结点的空链表。  
> （2）根据待创建链表包括的元素个数n，循环n次执行以下操作：  
> 1、生成一个新结点*p;  
> 2、输入元素值赋值给新结点*p的数据域；  
> 3、将新结点\*p插入到头结点之后。

/*单链表的建立（前插法）*/
    void CreateList(LinkList& L, int n)
    {
        
    	L = new LNode;//建立一个带头结点的空链表
    	L->next = NULL;
    
    	for (i = n;i > 0;--i)//循环插入新结点
    	{
        
    		p = new LNode;//生成新结点*p
    		scanf_s("%d", &p->data);//输入元素赋值给p->data
    		p->next = L->next;//将新结点*p插入到头结点后
    		L->next = p;
    	}
    }

### 6、单链表的建立（后插法） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]

**描述：后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。**

> 算法思想：  
> （1）创建一个只有头结点的空链表  
> （2）尾指针r初始化，指向头结点  
> （3）根据创建链表包括的元素个数n,循环n次执行以下操作：  
> 1、生成一个新结点*p;  
> 2、输入元素值赋给新结点*p的数据域  
> 3、将新结点*p插入到尾结点*r之后；  
> 4、尾指针r指向新的尾结点\*p.

/*单链表的建立（后插法）*/
    void CreateList(LinkList& L, int n)
    {
        
    	L = new LNode;//建立带头结点的空链表
    	L->next = NULL;
    	r = L;//尾指针指向头结点
    
    	for (i = 0;i < n;i++)
    	{
        
    		p = new LNode;//生成新结点p
    		scanf_s("%d", &p->data);//输入数据域
    		p->next = NULL;
    		r->next = p;//插入到尾表
    		r = p;//r指向新的尾结点
    	}
    }

# 二、循环链表 #

**特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]  
**从循环链表中的任何一个结点的位置都可以找到其他所有的结点，而单链表做不到，循环链表中没有明显的尾端。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]  
**实现**

p->next = B->next;
    B->next = A->next;
    A->next = p->next;
    delete p;
    A = B;

# 三、双向链表 #

**有两个指针域的链表，称为双链表**

/*双向链表的存储结构*/
    typedef struct DuLNode {
        
    	ElemType data;//数据域
    	struct DuLNode *prior;//前指针域
    	struct DuLNode* next;//后指针域
    }DuLNode,*DuLinkLst;

![在这里插入图片描述][20201004211818712.png_pic_center]

### 1、插入 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]

/*双向链表的插入*/
    Status ListInsert_DuL(DuLinkList& L, int i, ElemType e)
    {
        
    	if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
    		retrun ERROR;//p为NULL时，第i个元素不存在
    	s = new DuLNode;//生成一个新结点s
    	s->data = e;//将数据e存入到结点s的数据域data中
    	s->prior = p->prior;//将结点s的前指针指向前一个结点
    	p->prior->next = s;//将前一个结点的后指针指向新结点s
    	s->next = p;//新结点s的后指针指向p
    	p->prior = s;//p的前指针指向新结点
    	return OK;
    }

### 1、删除 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]

/*双向链表的删除*/
    Status ListDelete_DuL(DuLinkList& L, int i, ElemType &e)
    {
        
    	if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
    		retrun ERROR;//p为NULL时，第i个元素不存在
    	e = p->data;//保存被删除结点的数据域
    	p->prior->next = p->next;//修改被删除结点的前驱结点的后继指针
    	p->next->prior = p->prior;//修改被删除结点的后继结点的前驱指针
    	delete p;//释放被删除结点的空间
    	return OK;
    }

[20201004215217796.png_pic_center]: /images/20221123/63259dfbabc04a629a46eb1caeb8e33a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/258475cb8379436397cb41619f8f411a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/e4717721b1ef4ad3b22fbca656e984ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/4d9de644edcd495682882681578e5e9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/270805fab7c04f71b1e6f4495aa8f6b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/f6c86cab71754e13a6e5a9e49cb466c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/4a51295df9504e1883d5ae24fe8b71d8.png
[20201004211818712.png_pic_center]: /images/20221123/7348ade7357c44c298cecda1bcf4fa40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/c28d4db54b6c45ada047729a6b2c4666.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/f403d0a0d5cd44d18eb09e52de613983.png