【数据结构系列】双向链表

落日映苍穹つ 2023-06-14 04:11 37阅读 0赞

### 课后习题 ###

上一篇文章中我们说到单链表，然后最后有一道习题，不知道大家有没有做出来，为了照顾一些还不太会的同学，这里专门对这道题进行一个简单的讲解，先来看看原题内容：

有一个带头结点的单链表L = \{a1,b1,a2,b2,…,a(n),b(n)\}，试设计一个算法将其拆分成两个带头结点的单链表L1和L2，L1 = \{a1,a2,…,a(n)\}，L2 = \{b(n),b(n - 1),…,b(1)\}，要求L1使用L的头结点。

从题目中我们就可以看出，L1通过尾插法建立，L2通过头插法建立。

这道题本身并没有太大难度，我们通过画图的方式来分析一下，如下图是单链表L的一部分：  
![在这里插入图片描述][20191118112217731.png]

既然是要拆分成两个链表，我们需要定义出两个结点类型的变量p，q，可以先让p指向第一个有效结点，即：存放数据a1的结点，然后将a1插入到L1中；接着让q指向p的下一个结点，即：存放数据b1的结点，然后将b1插入到L2中，以此循环，即可完成。

看代码如何实现：

PNode split(PNode L){ 
    	PNode L1,L2,R1,p,q;
    	L1 = L;//这里我们仍然使用链表L的头结点作为链表L1的头结点
    	R1 = L1;//R1为链表L1的尾结点，初始指向头结点
    	p = L->next;//p初始指向链表L的第一个有效结点，用于找出链表L1的结点
    	//创建链表L2的头结点
    	L2 = (PNode) malloc(sizeof(Node));
    	if(L2 == NULL){ 
    		printf("内存分配失败，程序终止！\n");
    		exit(-1);
    	}
    	L2->next = NULL;//L2的头结点初始指针域为NULL
    	while(p != NULL){ 
    		q = p->next;//q初始指向链表L的第二个有效结点，用于找出链表L2的结点
    		//尾插法插入结点到链表L1
    		R1->next = p;
    		R1 = p;
    		//判断q是否空
    		if(q == NULL){ 
    			break;
    		}
    		//将p后移
    		p = q->next;
    		//头插法插入结点到链表L2
    		q->next = L2->next;
    		L2->next = q;
    	}
    	//L1尾结点指针域为NULL
    	R1->next = NULL;
    	return L2;//返回链表L2的头结点
    }

如果你掌握了头插法和尾插法的话，这道题相信难不倒你，唯一需要注意的就是循环里有一个判断条件，为什么要判断q非空？而且该判断语句的位置可不能乱写，否则程序就会出错。这里其实涉及到两种情况，链表L的结点数为奇数个或者结点数为偶数个，我们先看奇数个(假设链表L1有三个有效结点)：  
![在这里插入图片描述][20191118112230336.png]

那么一开始，p将指向存储数据1的结点，而循环体的第一条语句就是找到了q，q为存储数据2的结点，当把p插入到链表L1之后，我们需要找出链表L1的下一个结点，也就是q->next，即：存放数据3的结点；之后把q结点插入到了链表L2，我们又需要找出链表L2的下一个结点，也就是p->next，而此时p为链表L的尾结点，它的指针域为NULL，所以此时q为NULL，而如果你没有对q进行非空判断的话，执行p=q->next语句时就会报错，程序就出现问题了，所以要在使用q变量之前对q进行一个非空的判断。

而如果是偶数个，就比如上面的这个链表，再加入一个结点，那么p就不会是链表的尾结点，而当执行p=q->next语句后，尾结点q的指针域为NULL，所以p为NULL，此时循环就终止了，也就不会出现程序错误。

编写测试代码：

void main(){ 
    	PNode pHead,L2;
    	int a[] = { 1,2,3,4,5,6,7,8};
    	pHead = create_listT(a,8);
    	traverse_list(pHead);
    	L2 = split(pHead);
    	printf("链表L1:\t");
    	traverse_list(pHead);
    	printf("\n链表L2:\t");
    	traverse_list(L2);
    	getchar();
    }

首先你肯定得建立一个链表作为链表L，如何建立链表在这里就不重复说了，不了解的可以看上一篇文章，然后将头结点传入，就拆分成了两个链表。

运行结果：

1 2 3 4 5 6 7 8 9
    链表L1: 1 3 5 7
    链表L2: 8 6 4 2

### 双链表定义 ###

在文章开头我们对单链表进行了一个简单的复习，下面我们进入本篇文章的主题，双链表。

先来看看定义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

从定义中能够知道，双链表和单链表的唯一区别就是，双链表多了一个能够指向直接前驱结点的指针域，能够实现双向访问。

那么在双链表中，我们假设每个结点的类型用Node表示，它应该有一个存储元素的数据域，这里用data表示，有一个存储直接后继结点地址的指针域，这里用next表示，还应该有一个存储直接前驱结点地址的指针域，这里用prior表示，Node类型定义如下：

typedef struct Node{ 
    	int data;
    	struct Node *next;
    	struct Node *prior;
    }Node,*PNode;

![在这里插入图片描述][20191118112241847.png]

### 双链表的初始化 ###

那么如何建立一个空的双链表呢？

PNode create_list(){ 
    	//创建头结点
    	PNode pHead = (PNode) malloc(sizeof(Node));
    	pHead->next = NULL;
    	pHead->prior = NULL;
    	return pHead;
    }

非常简单，分配一块内存用于头结点，然后将头结点的两个指针域都置为NULL即可。

对于非空双链表的建立，我们同样需要掌握头插法和尾插法两种建立方式。

先看头插法：

![在这里插入图片描述][20191118112249648.png]

这是一个双链表的头结点，如何通过头插法将一个结点插入到该链表上呢？

![在这里插入图片描述][20191118112256605.png]

这样便完成了插入，如何实现呢？假设头结点为p，第一个结点为s，则`s = p->next`，此时s的指针域为NULL，然后`s->prior = p`，此时s结点指向它的直接前驱结点p(头结点)，最后`p->next = s`，此时头结点指向第一个结点s。

貌似没有什么问题，然而再插入一个元素你就会发现，第一个结点的prior指针域没有改变，它仍然指向的是头结点，而事实上它应该指向第二个结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]

那该如何解决呢？我们可以发现一个规律，就是如果向一个空链表插入结点，也就是`p->next = NULL`的时候，是没有出现问题的，然而插入第二个结点的时候出现问题，所以我们可以对p的指针域做一个非空的判断，下面看代码实现：

PNode create_listH(int *a,int n){ 
    	PNode pHead,pNew;
    	int i;
    	//创建头结点
    	pHead = (PNode) malloc(sizeof(Node));
    	if(pHead == NULL){ 
    		printf("内存分配失败，程序终止！\n");
    		exit(-1);
    	}
    	pHead->next = NULL;//头结点初始指针域为NULL
    	for(i = 0;i < n;i++){ 
    		//创建新结点
    		pNew = (PNode) malloc(sizeof(Node));
    		if(pNew == NULL){ 
    			printf("内存分配失败，程序终止！\n");
    			exit(-1);
    		}
    		//保存数据
    		pNew->data = a[i];
    		pNew->next = pHead->next;//将新结点指针域置为NULL，该结点为链表的尾结点
    		//判断头结点后面是否有结点
    		if(pHead ->next != NULL){ 
    			//将头结点指向的结点的prior指针域指向新创建的结点
    			pHead->next->prior = pNew;
    		}
    		pHead->next = pNew;//头结点指向新结点
    	}
    	return pHead;
    }

为了验证代码的正确性，我们编写一个遍历函数，双链表的遍历方式和单链表一样，这里就直接贴代码了：

PNode create_list(){ 
    	//创建头结点
    	PNode pHead = (PNode) malloc(sizeof(Node));
    	pHead->next = NULL;
    	pHead->prior = NULL;
    	return pHead;
    }

编写测试代码：

void main(){ 
    	PNode pHead;
    	int a[] = { 1,2,3,4,5,6};
    	pHead = create_listH(a,6);
    	traverse_list(pHead);
    	getchar();
    }

运行结果：

6 5 4 3 2 1

下面看看尾插法如何建立双链表。  
![在这里插入图片描述][20191118112515261.png]

同样是这样的一个头节点，如何将第一个结点插入到链表上呢？  
![在这里插入图片描述][20191118112525512.png]

我们暂且把头节点叫做p，第一个结点叫做s，和单链表一样，我们仍然需要定义一个结点类型的pTail作为指向链表的尾结点，初始指向头结点`pTail = p`，然后我们只需`pTail->next = s`，也就是让头结点指向第一个结点，接着`s->prior = pTail`，让第一个结点指回头结点，最后`pTail = s`，此时插入的结点为链表的尾结点，不要忘了在结尾将pTail的next指针域置为空。

下面看代码实现：

PNode create_listR(int *a,int n){ 
    	PNode pHead,pNew,pTail;
    	int i;
    	//创建头结点
    	pHead = (PNode) malloc(sizeof(Node));
    	if(pHead == NULL){ 
    		printf("内存分配失败，程序终止！\n");
    		exit(-1);
    	}
    	pTail = pHead;//初始指向头结点
    	for(i = 0;i < n;i++){ 
    		//创建新结点
    		pNew = (PNode) malloc(sizeof(Node));
    		if(pNew == NULL){ 
    			printf("内存分配失败，程序终止！\n");
    			exit(-1);
    		}
    		//保存数据
    		pNew->data = a[i];
    		pTail->next = pNew;
    		pNew->prior = pTail;
    		pTail = pNew;
    	}
    	pTail->next = NULL;//尾结点指针域为NULL
    	return pHead;
    }

我们测试一下：

void main(){ 
    	PNode pHead;
    	int a[] = { 1,2,3,4,5,6};
    	pHead = create_listR(a,6);
    	traverse_list(pHead);
    	getchar();
    }

运行结果：

1 2 3 4 5 6

### 求双链表长度 ###

这个和单链表的操作一样，没什么说的，直接看代码：

int length_list(PNode pHead){ 
    	int i = 0;
    	PNode p = pHead->next;
    	while(p != NULL){ 
    		i++;
    		p = p->next;
    	}
    	return i;
    }

这个在单链表中已经说过了，我就不测试了。

### 判断是否为空表 ###

判断是否为空表也和单链表操作相同，看代码：

int isEmpty_list(PNode pHead){ 
    	if(pHead->next == NULL){ 
    		return 1;
    	}else{ 
    		return 0;
    	}
    }

### 插入结点 ###

接下来又到了比较难的环节了，在双链表中的插入、删除操作和单链表十分类似，但又有些许不同，在双链表中，插入和删除的操作涉及到两个指针域的变化，所以相对要更复杂一些，但仔细品味，也很容易理解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]  
假设现在我需要将结点s插入到q的位置，则插入完成后链表结构如下：  
![在这里插入图片描述][20191118112554500.png]

那么如何实现插入呢？同样地，我们需要找到插入位置的前一个结点，例如在这里，需要将结点s插入到节点q的位置，则需要找到q的前一个结点也就是结点p，然后将结点s的指针域next指向p结点的指针域next，也就是让结点s指向结点q。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]

接着让结点q的指针域prior指向结点s，从而建立起结点s和结点q的双向关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]

然后让结点s的指针域prior指向结点p，最后让结点p的指针域next指向结点s，建立起结点p和结点s的双向关系。

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

这样即可完成插入。

下面看代码实现：

int insert_list(PNode pHead,int pos,int val){ 
    	PNode p,pNew;
    	int len,i = 0;
    	p = pHead;//p初始指向头结点
    	len = length_list(pHead);
    	//判断pos值的合法性
    	if(pos < 1 || pos > len + 1){ 
    		return 0;
    	}
    	//找到插入位置的前一个结点
    	while(i < pos - 1 && p != NULL){ 
    		i++;
    		p = p->next;
    	}
    	if(p == NULL){ 
    		return 0;
    	}
    	//此时p为插入位置的前一个结点
    	//创建新结点
    	pNew = (PNode) malloc(sizeof(Node));
    	if(pNew == NULL){ 
    		printf("内存分配失败，程序终止！\n");
    		exit(-1);
    	}
    	//保存数据
    	pNew->data = val;
    	//插入结点
    	pNew->next = p->next;
    	//判断p是否为尾结点
    	if(p->next != NULL){ 
    		p->next->prior = pNew;
    	}
    	pNew->prior = p;
    	p->next = pNew;
    	return 1;
    }

插入操作中同样需要注意一个问题，那就是插入的位置如果是链表的末尾的话，通过循环找到的结点p即为链表的尾结点，而尾结点的指针域next为NULL，就无需考虑后面结点的指针域prior的指向问题，如果不加以判断，当你插入结点到链表末尾时，程序就会报错。

编写测试代码：

void main(){ 
    	PNode pHead;
    	int a[] = { 1,2,3,4,5,6};
    	pHead = create_listR(a,6);
    	traverse_list(pHead);
    	if(insert_list(pHead,5,50)){ 
    		printf("插入后：\n");
    		traverse_list(pHead);
    	}else{ 
    		printf("插入失败！\n");
    	}
    	getchar();
    }

运行结果：

1 2 3 4 5 6
    插入后：
    1 2 3 4 50 5 6

### 删除结点 ###

看下面一个双链表：  
![在这里插入图片描述][20191118112655904.png]

如何将结点s从链表中删除呢？

原理很简单，首先将结点p的指针域next指向结点s的指针域，也就是`p->next = p->next->next`，然后将结点q的指针域prior指向结点p，也就是`q->prior = p`，此时结点p和结点q之间建立起了双向关系，最后释放结点s的内存即可。  
![在这里插入图片描述][2019111811270958.png]  
看代码如何实现：

int delete_list(PNode pHead,int pos,int *val){ 
    	PNode p,q;
    	int len,i = 0;
    	len = length_list(pHead);
    	p = pHead;//初始指向头结点
    	//判断pos值的合法性
    	if(pos < 1 || pos > len){ 
    		return 0;
    	}
    	//找到待删除结点的前一个结点
    	while(i < pos - 1 && p != NULL){ 
    		i++;
    		p = p->next;
    	}
    	//此时p为待删除结点的前一个结点
    	q = p->next;//q为待删除结点
    	//保存数据
    	*val = q->data;
    	//删除结点
    	p->next = q->next;
    	if(p->next!= NULL){ 
    		p->next->prior = p;
    	}
    	free(q);
    	return 1;
    }

这里同样需要考虑删除尾结点的问题，如果要删除的是尾结点，那么尾结点后面已经没有结点了，所以直接后继结点可以不用处理，处理就会报错，我们应该对p的指针域next进行非空判断，千万不要把`p->next != NULL`写成`q != NULL`，有些同学想当然地认为，`q = p->next`，所以if语句里也就写了`q != NULL`，这样是错误的。因为在判断之前，p的指针域next已经被改变了，只有判断p是否为空，当删除尾结点时，p指向q的指向，而q是尾结点，所以p的指向为NULL，q并不为空，它是尾结点，这是需要注意的一点。

下面是测试代码：

void main(){ 
    	PNode pHead;
    	int a[] = { 1,2,3,4,5,6};
    	int val;
    	pHead = create_listR(a,6);
    	traverse_list(pHead);
    	if(delete_list(pHead,6,&val)){ 
    		printf("删除后：\n");
    		traverse_list(pHead);
    		printf("删除结点的元素值为：%d\n",val);
    	}else{ 
    		printf("删除失败！\n");
    	}
    	getchar();
    }

运行结果：

1 2 3 4 5 6
    删除后：
    1 2 3 4 5
    删除结点的元素值为：6

至于查找指定元素值的结点位置，或者是查找指定结点位置的元素值，还有链表的销毁，这些操作都与单链表的操作一模一样，也就没有必要重复讲解了。不了解的可以看我的上一篇文章。

### 课后习题 ###

按照惯例，我同样留下一道算法题：

有一个带头结点的双链表L，试设计一个算法将其所有元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，……，最后一个元素变为第1个元素。

同样简单分析一下，这道题其实很简单，通过遍历双链表L，然后使用头插法建立链表即可完成，具体如何实现就看大家的了。我会在下一篇专栏文章中揭晓此题答案。

[20191118112217731.png]: https://img-blog.csdnimg.cn/20191118112217731.png
[20191118112230336.png]: https://img-blog.csdnimg.cn/20191118112230336.png
[20191118112241847.png]: https://img-blog.csdnimg.cn/20191118112241847.png
[20191118112249648.png]: https://img-blog.csdnimg.cn/20191118112249648.png
[20191118112256605.png]: https://img-blog.csdnimg.cn/20191118112256605.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019111811230426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191118112515261.png]: https://img-blog.csdnimg.cn/20191118112515261.png
[20191118112525512.png]: https://img-blog.csdnimg.cn/20191118112525512.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191118112542355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191118112554500.png]: https://img-blog.csdnimg.cn/20191118112554500.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191118112610540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191118112624175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191118112638924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibGl6emF3YW5nLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191118112655904.png]: https://img-blog.csdnimg.cn/20191118112655904.png
[2019111811270958.png]: https://img-blog.csdnimg.cn/2019111811270958.png