亲宝软件园·资讯

展开

C语言 双向带头循环链表

三分苦 人气:0

一、概念

前文我们已经学习了单向链表，并通过oj题目深入了解了带头节点的链表以及带环链表，来画张图总体回顾下：

在我们学习的链表中，其实总共有8种，都是单双向和带不带头以及带不带环的任意组合

今儿要学习的是双向 - 带头 - 循环链表，听名字就觉着结构很复杂，要比曾经学的单向 - 不带头 - 不循环 链表的结构复杂的多 ，确实也是。先来画张图整体感受下：

解释：

正文开始：

二、必备工作

2.1、创建双向链表结构

因为是双向链表，所以在结构体里头必然有两个指针，一个next指向下一个节点，一个prev指向上一个节点。

List.h 文件：

//创建双向链表结构
typedef int LTDataType;   //方便后续更改数据类型，本文以int整型为主
typedef struct ListNode
{
	LTDataType data; //存储数据
	struct ListNode* next; //指向下一个
	struct ListNode* prev; //指向上一个
}LTNode; //方便后续使用，不需要重复些struct

2.2、初始化链表

思路：

在初始化的时候要传地址，因为形参的改变不会影响实参，pphead的改变不会影响pList，要传pList的地址，用**pphead来接收，此时就要assert断言了，因为二级指针地址不可能位空。因为是双向循环链表，所以要将创建好的哨兵位节点的next和prev均指向自己。

List.h 文件：（1）

//初始化链表（二级指针版）
void ListInit(LTNode* pphead);

List.c 文件：（1）

//初始化链表（二级指针版）
void ListInit(LTNode** pphead)
{
	//传二级指针，那么当然要断言
	assert(pphead);
	*pphead = BuyLTNode(0);//因为是带哨兵位的头节点，所以一开始就要给一个节点
	//为了循环，要让哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意优先级，*pphead要加括号
	(*pphead)->prev = *pphead;
}

注意：

上一种方法我们传的是二级指针，那么可以传一级指针吗，其实也是可以的，只需写个函数返回指针即可

List.h 文件：（2）

//初始化链表（一级指针版本）
LTNode* ListInit();

List.c 文件：（2）

//初始化链表（一级指针版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.3、动态申请节点

List.c 文件：

//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新创建的节点
}

2.4、打印链表

思路：

既然是打印，首先要搞明白一点，哨兵位不用来存放有效数据，那么就不需要打印，定义一个cur指针来迭代，那么应该从phead的next开始打印，当cur走完一遍，重又回到phead的时候停止

List.h 文件：

//打印链表
void ListPrint(LTNode* phead);

List.c 文件：

//打印链表
void ListPrint(LTNode* phead)
{
	assert(phead);//断言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5、销毁链表

思路：

既然是销毁链表了，那么自然是要把链表的所有元素包括哨兵位都给销毁掉，但毕竟刚开始传phead的时候是不能为空的，所以要断言，在把所有有效数据销毁后最后再销毁哨兵位即可。

法一：遍历

定义一个指针cur，从phead的next第一个有效数据开始free，保存下一个，再free，依次遍历下去

法二：附用ListErase函数

此法也可以，不过每次Erase完，都会把前后两个节点再链接起来，虽说最后都会销毁，但duck不必多此一举，所有直接采用法一比较好

List.h 文件：

//销毁链表
void ListDestory(LTNode* phead);

List.c 文件：

//销毁链表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//销毁从第一个节点到尾部的数据
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位节点phead
	free(phead);
	phead = NULL;
}

Test.c 文件：

void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//销毁链表
	ListDestory(pList);
	pList = NULL;
}

三、主要功能

3.1、在pos节点前插入数据

思路：

假设我们已经进行了尾插4个数字，现在想在数字3的前面插入30，那么首先就要查找有无数字3，若有，则插入。注意：这里需要用到后文才讲到的查找函数，这里直接引用了，详解看后文即可，问题不大！

首先，将30放到新创建的节点newnode里头，为了实现双向，要先把3的前一个数据2的next指向新节点newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。

 List.h 文件：

//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x);

List.c 文件：

//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//创建插入数据的新节点
	LTNode* newnode = BuyLTNode(x);
	//链接左侧
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//链接右侧
	newnode->next = pos;
	pos->prev = newnode;
}

Test.c 文件：

void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到数字3就插入
	}
	ListPrint(pList);//打印
}

效果如下：

尾插

思路：

首先，因为此链表是带哨兵位的头节点，所以头节点必然不为空，刚开始就要assert断言。其次，单链表尾插需要找尾，双向链表虽然也需要，不过非常简单，不需要再遍历链表了，因为哨兵位头节点的phead的上一个节点指向的就是尾，这就充分体现了双向循环的好处，找到了尾节点就需要再创建一个节点存储插入数据，方便尾插。

List.h 文件：

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

List.c 文件：1.0

//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //断言，防止头节点为空
	LTNode* tail = phead->prev; //找到尾节点，便于后续插入数据
	LTNode* newnode = BuyLTNode(x);//创建新节点
	//将此新插入的尾节点与上一个节点链接起来
	tail->next = newnode;
	newnode->prev = tail;
	//将尾节点与哨兵位phead链接起来构成循环
	newnode->next = phead;
	phead->prev = newnode;
}

Test.c 文件：

void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
}

效果如下：

注意：

在上文中，我们学习了在pos前插入数据，那么设想一下，当pos就等于phead的时候，它（phead）的前不就是链表的尾部吗，那么理所应当，尾插也可以这样完成：

List.c 文件：2.0

//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); 
	ListInsert(phead, x);
}

头插

思路：

前面我们已经学习了在pos前插入数据，那么头插的实现就尤为简单了，当pos为原第一个数据phead->next时，此时就是在其之前插入数据，那么实现的不久是头插吗，如下：

List.h 文件：

//头插
void ListPushFront(LTNode* phead, LTDataType x);

List.c 文件：

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

Test.c 文件：

void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //头插3个数字
	}
	ListPrint(pList);//打印
}

效果如下：

3.2、删除pos处节点数据

思路：

删除pos处数据其实也很简单，有点类似于把pos处直接忽略的思想，或者说是绕过去。首先，需要找到pos的上一个节点prev和下一个节点next，将prev和next互相链接即可，直接跳过了pos，这样就实现了删除pos处节点的数据，记得把pos处给free释放掉。这里我们以pos为2示例：

 List.h 文件：

//删除pos处数据
void ListErase(LTNode* pos);

List.c 文件：

//删除pos处数据
void ListErase(LTNode* pos)
{
	assert(pos);
	//定义两个指针保存pos两边的节点
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//将prev和next链接起来
	prev->next = next;
	next->prev = prev;
	//free释放
	free(pos);
	pos = NULL;
}

Test.c 文件：

void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //删除pos处数据
		pos = NULL; //形参的改变不会影响实参，最好在这置空pos
	}
	ListPrint(pList);//打印
}

效果如下：

尾删

思路：

双向循环链表的特点将再次得以体现，根据其特性，我们知道phead的prev指向尾节点，用tail指针保存，再定义一个指针tailPrev指向tail的prev，现仅需将tailPrev的next指向哨兵位节点phead，再把哨兵位phead的prev重新置成tailPrev即可，但是别忘记把删掉的尾节点给释放掉，得free(tail)。记得要断言链表不能为空，因为不能删除哨兵位节点。

List.H 文件：

//尾删
void ListPopBack(LTNode* phead);

List.c 文件：1.0

//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能为空，要断言
	assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//释放尾节点
	free(tail);
	tail = NULL;
	//将链表循环起来
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

Test.c 文件：

void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//尾删两次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}

效果如下：

 注意：

前文我们已经学了删除pos处节点的数据，那么当pos为phead->prev时，删除的是不是就是尾节点，所以，尾删理所应当可以这样写：

List.c 文件：2.0

//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能为空，要断言
	assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点
	ListErase(phead->prev);
}

头删

思路：

有了上文之鉴，我们可以直接利用前面写的删除pos处数据的函数来完成，当pos为phead->prev时，pos的位置就是尾，此时删除的就是尾。当然还得注意一点，需要额外assert断言防止删除的数据为哨兵位的节点。

List.h 文件：

//头删
void ListPopFront(LTNode* phead);

List.c 文件：

//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止删除哨兵位节点
	ListErase(phead->next);
}

Test.c 文件：

void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//头插3个数字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾删3个数字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//头删3个数字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
}

效果如下：

3.3、查找数据

思路：

查找数据其实也比较简单，首先，定义一个指针cur指向哨兵位phead的next，依次遍历cur看cur->data是否为查找的数据x，如果是，则返回cur，否则继续（cur=cur->next），若找不到则返回NULL。

List.h 文件：

//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x);

List.c 文件：

//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}

四、总代码

List.h 文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//创建双向链表结构
typedef int LTDataType;   //方便后续更改数据类型，本文以int整型为主
typedef struct ListNode
{
	LTDataType data; //存储数据
	struct ListNode* next; //指向下一个
	struct ListNode* prev; //指向上一个
}LTNode; //方便后续使用，不需要重复些struct
 
//初始化链表（二级指针版本）
/*void ListInit(LTNode** pphead);*/
//初始化链表（一级指针版本）
LTNode* ListInit();
 
//打印链表
void ListPrint(LTNode* phead);
//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
//销毁链表
void ListDestory(LTNode* phead);
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾删
void ListPopBack(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//头删
void ListPopFront(LTNode* phead);
 
//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x);
//删除pos处数据
void ListErase(LTNode* pos);

List.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新创建的节点
}
//初始化链表（二级指针版）
/*void ListInit(LTNode** pphead)
{
	//传二级指针，那么当然要断言
	assert(pphead);
	*pphead = BuyLTNode(0);//因为是带哨兵位的头节点，所以一开始就要给一个节点
	//为了循环，要让哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意优先级，*pphead要加括号
	(*pphead)->prev = *pphead;
}*/
//初始化链表（一级指针版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
//打印链表
void ListPrint(LTNode* phead)
{
	assert(phead);//断言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}
//销毁链表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//销毁从第一个节点到尾部的数据
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位节点phead
	free(phead);
	phead = NULL;
}
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //断言，防止头节点为空
	/*
	法一：
	LTNode* tail = phead->prev; //找到尾节点，便于后续插入数据
	LTNode* newnode = BuyLTNode(x);//创建新节点
	//将此新插入的尾节点与上一个节点链接起来
	tail->next = newnode;
	newnode->prev = tail;
	//将尾节点与哨兵位phead链接起来构成循环
	newnode->next = phead;
	phead->prev = newnode;
	*/
	//法二：
	ListInsert(phead, x);
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能为空，要断言
	assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点
	/*
	法一：
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//释放尾节点
	free(tail);
	tail = NULL;
	//将链表循环起来
	tailPrev->next = phead;
	phead->prev = tailPrev;
	*/
	//法二：
	ListErase(phead->prev);
}
 
//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止删除哨兵位节点
	ListErase(phead->next);
}
 
//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//创建插入数据的新节点
	LTNode* newnode = BuyLTNode(x);
	//链接左侧
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//链接右侧
	newnode->next = pos;
	pos->prev = newnode;
}
//删除pos处数据
void ListErase(LTNode* pos)
{
	assert(pos);
	//定义两个指针保存pos两边的节点
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//将prev和next链接起来
	prev->next = next;
	next->prev = prev;
	//free释放
	free(pos);
	pos = NULL;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
}
 
void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//尾删两次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}
 
void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到数字3就插入
	}
	ListPrint(pList);//打印
}
 
void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //头插3个数字
	}
	ListPrint(pList);//打印
}
 
void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //删除pos处数据
		pos = NULL; //形参的改变不会影响实参，最好在这置空pos
	}
	ListPrint(pList);//打印
}
 
void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//头插3个数字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾删3个数字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//头删3个数字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
	//销毁链表
	ListDestory(pList);
	pList = NULL;
}
 
void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//销毁链表
	ListDestory(pList);
	pList = NULL;
}
int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	TestList7();
	return 0;
}

五、拓展

对比顺序表和链表

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除数据
缓存利用率高低

优缺点对比：

 顺序表链表
优点

1、物理空间是连续的，方便用下标随机访问。

2、CPU高速缓存命中率会更高。（补充）

1、按需申请释放空间。

2、任意位置可以O(1)插入删除数据。

缺点

1、正因为物理空间连续，空间不够需要扩容，扩容本身又一定消耗，其次扩容机制还存在一定的空间浪费。

2、头部或者中部插入删除，挪动数据，效率低，O(N)。

1、不支持下标的随机访问。

2、有些算法不适合在它上面进行，如：二分查找、排序等。

加载全部内容
相关教程
猜你喜欢
用户评论