酷酷是懒虫

这个屌丝很懒，什么也没留下！

热门标签

C语言数据结构——带头双向循环链表_listnode** current = head;的意思

作者：酷酷是懒虫 | 2024-07-05 06:57:30

踩

listnode** current = head;的意思

1、链表的分类

实际中链表的结构非常多样，组合起来就有 8 种链表结构：无头单向非循环链表、无头单向循环链表、带头单向非循环链表、带头单向循环链表、无头双向非循环链表、无头双向循环链表、带头双向非循环链表、带头双向循环链表等。上篇博客讲到无头单向非循环链表，该链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。本篇博客讲到的是带头双向循环链表。带头双向循环链表结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

2、带头双向循环链表

2.1 概念及其结构分析

双链表，也是基于单链表的。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表则是添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。但双链表还是不够灵活，所以，实际编程中比较常用的是带头双向循环链表，但带头双向循环链表使用较为麻烦。

双链表的一个存储结点包含三个部分内容：

data 部分称为数据域，用于存储线性表的一个数据元素；previous 和 next 两部分称为指针域，都是用于存放一个指针。previous 指针是指向该链表上一个结点的地址，next 指针是指向该链表下一个结点的地址。

带头是什么意思？意思就是带哨兵卫的链表，也就是说哨兵卫就是链表的头，但是真正的头结点不是哨兵卫结点，而是哨兵卫结点的下一个结点。带头的链表不需要我们单独定义一个指针用来存储头结点的地址，当然传参的时候也不需要使用二级指针了。还有，哨兵卫是不存任何有效数据的，链表的长度也不行。因为如果链表要存储的数据类型为 char 类型，当链表的长度超过 128 后，那么就会发生错误。至于链表循环是什么样子，请看逻辑图的结构。

下面对带头双向循环链表的逻辑结构和物理图结构作分析。

双链表逻辑结构：

逻辑结构：想象出来的，形象，方便理解。结构图如下：

双链表物理结构：

物理结构：在内存中实实在在如何存储的。物理结构图如下：

2.2 带头双向循环链表的实现

为了有效地存储结点数据，并且实现双链表的链式功能，可建立 ListNode 结构体。代码如下：


typedef int LTDataType;
 
typedef struct ListNode
{
	LTDataType data;	//结点数据
	struct ListNode* next;	//指向下一个结点的地址
	struct ListNode* previous;//指向前一个结点的地址
}ListNode;

1.链表的初始化(哨兵卫结点的创建)


ListNode* ListInint()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	head->next = head;
	head->previous = head;
 
	return head;
}

带头双向循环链表在插入数据之前，要先创建好头链表，再进行其他相关的操作。因为是循环双链表，所以需要把 previous 和 next 指向本身，最后返回 head 的地址。这个初始化的作用就是为了创建一个充当头结点的哨兵卫结点，这个头结点不存储任何有效数据。如下图：

2.创建一个结点


ListNode* BuyListNode(LTDataType x)//创建一个链表结点
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->previous = NULL;
	newnode->data = x;
 
	return newnode;
}

使用 malloc() 或者使用动态内存开辟的其他函数创建链表结点，因为是双向链表结点，所以有两个指针域。

3.尾插


void ListPushBack(ListNode* head, LTDataType x)//尾插
{
	//尾插之前找到尾结点
	assert(head);//检查哨兵卫结点是否为空
	ListNode* newnode = BuyListNode(x);//接收创建的新结点的地址
	ListNode* tail = head->previous;//找到尾结点
 
	//开始尾插
	tail->next = newnode;//尾结点的下一个就是newnode
	newnode->previous = tail;//newnode的前一个就是尾结点
	newnode->next = head;//newnode的下一结点是head（哨兵卫结点）
	head->previous = newnode;//哨兵位结点的前一个是newnode
}

4.尾删


void ListPopBack(ListNode* head)//尾删
{
	//尾删之前先找到尾结点
	assert(head);//检查哨兵卫结点是否为空
	assert(head->next!=head);//删除到哨兵卫结点就停止删除
	//尾删之前先找到尾结点和尾结点之前的一个结点
	ListNode* tail = head->previous;//尾结点
	ListNode* tailPrevious = tail->previous;//尾结点的前一个结点
	//删除之前，先把尾结点的前一个结点和哨兵卫结点链接好
	tailPrevious->next = head;
	head->previous = tailPrevious;
	free(tail);//开始删除
	tail = NULL;
}

5.头插


void ListPushFront(ListNode* head, LTDataType x)//头插
{
	//头插之前先找到头
	assert(head);//检查哨兵卫结点是否为空
	ListNode* newnode = BuyListNode(x);//接收创建的新结点的地址
	ListNode* current = head->next;//找到头
	//开始头插
	head->next = newnode;
	newnode->previous = head;//先把要插入的新结点和哨兵卫结点链接好
	//再把插入的新结点和current（正真的头）链接好
	newnode->next = current;
	current->previous = newnode;
}

6.头删


void ListPopFront(ListNode* head)//头删
{
	//头删之前先找到头
	assert(head);//检查哨兵卫结点是否为空
	assert(head->next != head);//删到哨兵卫结点就停止删除
	ListNode* current = head->next;//找到头
	ListNode* currentNext = current->next;//找到头的下一个
	//删除之前先把哨兵卫结点和头结点的下一个结点链接好
	head->next = currentNext;
	currentNext->previous = head;
	free(current);//开始删除
	current = NULL;
}

7.查找数据 x 的地址


ListNode* ListFind(ListNode* head, LTDataType x)//查找数据 x 的地址
{
	assert(head);//检查哨兵卫结点是否为空
	ListNode* current = head->next;//从头开始遍历查找
	while (current != head)//直到循环到哨兵卫就停止
	{
		if (current->data == x)//找到数据 x ，就返回数据 x 的地址
		{
			return current;
		}
		current = current->next;//当前结点就等于下一个结点
	}
	return NULL;//找不到就返回空
}

8.在 pos 位置之前插入一个数据


void ListInsert(ListNode* pos, LTDataType x)//在 pos 位置之前插入一个数据
{
	assert(pos);//判断pos是否为空，如果 pos 为空，那么在空的前面插入一个数据，就是不可能了
	ListNode* newnode = BuyListNode(x);//接收创建的新结点的地址
	//在插入之前先找到 pos 的前一个结点
	ListNode* posPrevious = pos->previous;//pos位置的前一个结点
	//开始插入，先让 pos 的前一个结点和新结点链接好
	posPrevious->next = newnode;
	newnode->previous = posPrevious;
	//再让新结点和 pos 结点链接好
	newnode->next = pos;
	pos->previous = newnode;
}

假设 pos 位置如图下所示：

9.删除 pos 位置的结点


void ListErase(ListNode* pos)//删除 pos 位置的结点
{
	//删除掉 pos 位置的结点，就要找到 pos 位置的前一个结点和下一个结点
	assert(pos);//判断pos是否为空，如果 pos 为空，删除一个空，就没有意义了
	ListNode* posPrevious = pos->previous;//找到 pos 前一个结点
	ListNode* posNext = pos->next;//找到 pos 下一个结点
	//开始链接 pos 的前一个结点和 pos 的下一个结点
	posPrevious->next = posNext;
	posNext->previous = posPrevious;
	//开始删除
	free(pos);
	pos = NULL;
}

10.释放链表结点


void ListDestroy(ListNode** head)//释放链表结点
{
	assert(*head);//判断哨兵卫结点是否为空
	ListNode* current = (*head)->next;//从头结点开始释放
	while (current != *head)
	{
		ListNode* next = current->next;//记录释放结点的下一个结点
		free(current);//释放链表结点
		current = next;
	}
	free(*head);//释放哨兵卫结点
	*head = NULL;//将指向哨兵卫结点的指针置空，防止成为野指针
}

从头结点开始释放，释放之前记录下一个结点，防止找不到下一个结点。直到循环到哨兵卫结点。这里为什么传二级指针呢？是因为释放了哨兵卫结点后，要把指向哨兵卫结点的指针置空，防止成为野指针，再次强调一下，需要改变指针的指向，传二级指针。也就是说，我们要改变 head 指针的指向，需要我们传 head 的地址，才能改变 head 的指向。

11.打印链表节点数据


void ListPrint(ListNode* head)//打印链表节点数据
{
	assert(head);//判断哨兵卫结点是不是空
	ListNode* current = head->next;//从头结点开始打印
	while (current!= head)
	{
		printf("%d ", current->data);
		current=current->next;
	}
	printf("\n");
}

2.3 带头双向循环链表源码

list.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int LTDataType;
 
typedef struct ListNode
{
	LTDataType data;	//结点数据
	struct ListNode* next;	//指向下一个结点的地址
	struct ListNode* previous;//指向前一个结点的地址
}ListNode;
 
//初始化
ListNode* ListInint();
//打印链表结点数据
void ListPrint(ListNode* head);
//创建一个链表结点
ListNode* BuyListNode(LTDataType x);
//尾插
void ListPushBack(ListNode* head, LTDataType x);
//尾删
void ListPopBack(ListNode* head);
//头插
void ListPushFront(ListNode* head, LTDataType x);
//头删
void ListPopFront(ListNode* head);
//查找数据 x 的地址
ListNode* ListFind(ListNode* head, LTDataType x);
//在 pos 之前插入一个数据
void ListInsert(ListNode* pos, LTDataType x);
//删除 pos 地址的结点
void ListErase(ListNode* pos);
//释放链表结点
void ListDestroy(ListNode** head);

list.c


#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
 
ListNode* ListInint()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	head->next = head;
	head->previous = head;
 
	return head;
}
 
void ListPrint(ListNode* head)//打印链表节点数据
{
	assert(head);//判断哨兵卫结点是不是空
	ListNode* current = head->next;//从头结点开始打印
	while (current!= head)
	{
		printf("%d ", current->data);
		current=current->next;
	}
	printf("\n");
}
 
ListNode* BuyListNode(LTDataType x)//创建一个链表结点
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->previous = NULL;
	newnode->data = x;
 
	return newnode;
}
 
void ListPushBack(ListNode* head, LTDataType x)//尾插
{
	//尾插之前找到尾结点
	assert(head);//检查哨兵卫结点是否为空
	ListNode* newnode = BuyListNode(x);//接收创建的新结点的地址
	ListNode* tail = head->previous;//找到尾结点
 
	//开始尾插
	tail->next = newnode;//尾结点的下一个就是newnode
	newnode->previous = tail;//newnode的前一个就是尾结点
	newnode->next = head;//newnode的下一结点是head（哨兵卫结点）
	head->previous = newnode;//哨兵位结点的前一个是newnode
}
 
void ListPopBack(ListNode* head)//尾删
{
	//尾删之前先找到尾结点
	assert(head);//检查哨兵卫结点是否为空
	assert(head->next!=head);//删除到哨兵卫结点就停止删除
	//尾删之前先找到尾结点和尾结点之前的一个结点
	ListNode* tail = head->previous;//尾结点
	ListNode* tailPrevious = tail->previous;//尾结点的前一个结点
	//删除之前，先把尾结点的前一个结点和哨兵卫结点链接好
	tailPrevious->next = head;
	head->previous = tailPrevious;
	free(tail);//开始删除
	tail = NULL;
}
 
void ListPushFront(ListNode* head, LTDataType x)//头插
{
	//头插之前先找到头
	assert(head);//检查哨兵卫结点是否为空
	ListNode* newnode = BuyListNode(x);//接收创建的新结点的地址
	ListNode* current = head->next;//找到头
	//开始头插
	head->next = newnode;
	newnode->previous = head;//先把要插入的新结点和哨兵卫结点链接好
	//再把插入的新结点和current（正真的头）链接好
	newnode->next = current;
	current->previous = newnode;
}
 
void ListPopFront(ListNode* head)//头删
{
	//头删之前先找到头
	assert(head);//检查哨兵卫结点是否为空
	assert(head->next != head);//删到哨兵卫结点就停止删除
	ListNode* current = head->next;//找到头
	ListNode* currentNext = current->next;//找到头的下一个
	//删除之前先把哨兵卫结点和头结点的下一个结点链接好
	head->next = currentNext;
	currentNext->previous = head;
	free(current);//开始删除
	current = NULL;
}
 
ListNode* ListFind(ListNode* head, LTDataType x)//查找数据 x 的地址
{
	assert(head);//检查哨兵卫结点是否为空
	ListNode* current = head->next;//从头开始遍历查找
	while (current != head)//直到循环到哨兵卫就停止
	{
		if (current->data == x)//找到数据 x ，就返回数据 x 的地址
		{
			return current;
		}
		current = current->next;
	}
	return NULL;//找不到就返回空
}
 
void ListInsert(ListNode* pos, LTDataType x)//在 pos 之前插入一个数据
{
	assert(pos);//判断pos是否为空，如果 pos 为空，那么在空的前面插入一个数据，就是不可能了
	ListNode* newnode = BuyListNode(x);//接收创建的新结点的地址
	//在插入之前先找到 pos 的前一个结点
	ListNode* posPrevious = pos->previous;//pos位置的前一个结点
	//开始插入，先让 pos 的前一个结点和新结点链接好
	posPrevious->next = newnode;
	newnode->previous = posPrevious;
	//再让新结点和 pos 结点链接好
	newnode->next = pos;
	pos->previous = newnode;
}
 
void ListErase(ListNode* pos)//删除 pos 位置的结点
{
	//删除掉 pos 位置的结点，就要找到 pos 位置的前一个结点和下一个结点
	assert(pos);//判断pos是否为空，如果 pos 为空，删除一个空，就没有意义了
	ListNode* posPrevious = pos->previous;//找到 pos 前一个结点
	ListNode* posNext = pos->next;//找到 pos 下一个结点
	//开始链接 pos 的前一个结点和 pos 的下一个结点
	posPrevious->next = posNext;
	posNext->previous = posPrevious;
	//开始删除
	free(pos);
	pos = NULL;
}
 
void ListDestroy(ListNode** head)//释放链表结点
{
	assert(*head);//判断哨兵卫结点是否为空
	ListNode* current = (*head)->next;//从头结点开始释放
	while (current != *head)
	{
		ListNode* next = current->next;//记录释放结点的下一个结点
		free(current);//释放链表结点
		current = next;
	}
	free(*head);//释放哨兵卫结点
	*head = NULL;//将指向哨兵卫结点的指针置空，防止成为野指针
}

test.c


#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
//带头双向循环链表
 
void TestList()
{
	ListNode* head = ListInint();//创建哨兵位头结点
	ListPushBack(head, 1);//尾插
	ListPushBack(head, 2);
	ListPushBack(head, 3);
	ListPushBack(head, 4);
	ListPushBack(head, 5);
	printf("尾插1、2、3、4、5>\n");
	ListPrint(head);//打印
 
	ListPopBack(head);//尾删
	ListPopBack(head);
	ListPopBack(head);
	ListPopBack(head);
	printf("尾删三个结点>\n");
	ListPrint(head);
 
	ListPushFront(head, 1);//头插
	ListPushFront(head, 2);
	ListPushFront(head, 3);
	ListPushFront(head, 4);
	ListPushFront(head, 5);
	printf("头插1、2、3、4、5>\n");
	ListPrint(head);
 
	ListPopFront(head);//头删
	ListPopFront(head);
	printf("头删两个结点>\n");
	ListPrint(head);
 
	ListNode* pos = ListFind(head, 2);
	ListInsert(pos, 20);
	printf("在 pos(数据 2 ) 位置之前插入( 20 )一个结点>\n");
	ListPrint(head);
 
	ListErase(pos);//删除pos位置的结点
	printf("删除 pos(数据 2 ) 位置的结点>\n");
	ListPrint(head);
 
	ListDestroy(&head);//释放链表结点。因为释放其他结点的同时，也要把哨兵卫结点给释放了，
					//释放哨兵卫的同时需要把 head 指针的指向置空，所以需要传 head 的地址。需要二级指针来接收指针 head 的地址
}
 
int main()
{
	TestList();
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/789492