亲宝软件园·资讯

展开

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、有些算法不适合在它上面进行,如:二分查找、排序等。

加载全部内容

相关教程
猜你喜欢
用户评论