酷酷是懒虫

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

热门标签

C语言数据结构之带头双向循环链表_c语言带头结点的双链表

作者：酷酷是懒虫 | 2024-07-05 07:25:48

踩

c语言带头结点的双链表

链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实的。

在现实中链表就像是火车每节车厢是相连，每节车厢都载着乘客或者货物。

链表也是一样，节点就像是车厢，它们都链接在一起，每个节点都有着数据。

双链表

双链表就是每个节点有两个储存地址的结构体指针，一个存的是前一个节点的地址

一个存的是下一个节点的地址，用于更好的查找节点。

头节点

头节点我们一般叫哨兵位，这个哨兵位我们不存什么数据，只存两个节点的地址。

命名：头 - phead 前一个节点 - prev 下一个节点 - next 要存的数据 - x 指定的位置 - pos

储存的数据 - data

上面是这个链表的一些命名。

带头双向循环链表的图

了解完这些我们再来实现下这个链表的增删查改

代码实现

用结构体来存三个变量。用typedef取一个别名叫：LTNode使用，给一个内置类型int也取个别名叫：LTDataType方便更改。


typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

创建返回链表的头结点

链表的初始化就要申请空间来储存哨兵位了，哨兵位只存地址不存数据。因为要申请的节点空间很多所以，就单独写个函数来用。

这里的初始化因为有哨兵位，所以用返回值来返回。

头文件的声明


//申请新的节点
LTNode* BuyLTNode(LTDataType x);
//创建返回链表的头结点
LTNode* LTInit();

实现


//申请新的节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
 
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}
 
// 创建返回链表的头结点
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
 
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}

初始化的状态图

双向链表的尾插

尾插建议定义一个tail来存头结点下一个的地址，这样就行链接的时候就可以随便连了。

tail是尾结点，newnode是新节点。如果不定义tail就靠着头结点的下一个（phead->next）来进行链接的话，我们链接的时候会很麻烦，需要分辨先后顺序，不然会找不到节点。
定义一个tail后，因为有下一个节点的地址了，所以我们可以随便进行链接，不需要分辨先后顺序。

插入后我们还可以打印一下插入的结果

声明


//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);

实现


//双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
 
	newnode->next = phead;
	newnode->prev = tail;
	tail->next = newnode;
	phead->prev = newnode;
}

运用


void LTTest1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
}
 
int main()
{
	LTTest1();
	return 0;
}

打印结果

双向链表的尾删

链表的尾删就很简单了，定义一个tail（尾）用来删除，然后找到前一个，叫tailprev。这样就记录了，两个节点。再把tail，free掉。这个时候tail被释放了，所以tailprev的next没有地址，需要存头结点phead的地址。phead的prev存一下tailprev的地址。所有的链接就完成了。

但是尾删删到最后把头结点删掉，我们在进行插入就会有问题。所以我们需要用assert进行断言一下，以防我们删到最后出现问题。

这里的断言的判断就写一个函数来返回真假。当LTEmpty判断phead的next等于phead的时候返回真，然后我们再取反一下，就可以assert判断就为假，为假就触发断言结束程序咯。

声明


//双链表的尾删
void LTPopBak(LTNode* phead);
//判空
bool LTEmpty(LTNode* phead);

实现


//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
 
	return phead->next == phead;
}
 
//双链表的尾删
void LTPopBak(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
 
	free(tail);
 
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

运用


void LTTest1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
 
	LTPopBak(plist);
	LTPrint(plist);
	LTPopBak(plist);
	LTPrint(plist);
	LTPopBak(plist);
	LTPrint(plist);
	LTPopBak(plist);
	LTPrint(plist);
}
 
int main()
{
	LTTest1();
	return 0;
}

打印结果

当然删完后断言就起作用了，可以看见是函数里出的问题，然后就可以顺藤摸瓜去找了。

双向链表的头插

链表的头插和尾插没有太大区别，用newnode来存新节点，然后next存头结点的下一个的地址，方便查找。

后面的就是和尾插一样的链接咯。因为存的头结点后面的地址，所以可以随便链接。

声明


//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);

实现


//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* newnode = BuyLTNode(x);
	LTNode* next = phead->next;
 
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

运用


void LTTest2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
 
	LTPrint(plist);
}
 
int main()
{
	LTTest2();
	return 0;
}

打印结果

双向链表的头删

链表的头删和尾删大同小异，first存phead的next的地址，second存first的next的地址。

因为要删的是first，所以phead的next存second的地址，second存prev存phead的地址。

声明


//链表的头删
void LTPopFront(LTNode* phead);

实现


//链表的头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* first = phead->next;
	LTNode* second = first->next;
 
	phead->next = second;
	second->prev = phead;
 
	free(first);
}

运用

这里是多删了一个，所以会被断言报错


void LTTest2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
 
	LTPrint(plist);
 
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPrint(plist);
}
 
int main()
{
	LTTest2();
	return 0;
}

结果打印

双向链表的查找

这个链表的查找需要配合，pos位置的插入使用，这个就是把链表来跑一遍来找值，找到了就返回，节点的地址。

声明


// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);

实现


// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
 
		cur = cur->next;
	}
	return NULL;
}

双向链表在pos位置的前面进行插入

pos位置前插入和头插，尾插没有什么区别。

运用这里用pos来存一下LTFind返回的地址，然后判断一下pos是不是为空，不是空就进行插入。

声明


// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);

实现


// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* posPrev = pos->prev;
 
	newnode->next = pos;
	newnode->prev = posPrev;
	posPrev->next = newnode;
	pos->prev = newnode;
}

运用


void LTTest3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
 
	LTNode* pos = LTFind(plist, 2);
	if (pos)
	{
		LTInsert(pos, 20);
	}
	LTPrint(plist);
 
}
 
int main()
{
	LTTest3();
	return 0;
}

打印

双向链表删除pos位置的节点

删除pos位置和尾删头删没什么区别就不写了。

声明


// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

实现


// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
	assert(pos);
	assert(!LTEmpty(pos));
 
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
 
	posPrev->next = posNext;
	posNext->prev = posPrev;
 
	free(pos);	
}

运用


void LTTest3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
 
	LTNode* pos = LTFind(plist, 2);
	if (pos)
	{
		LTInsert(pos, 20);
	}
	LTPrint(plist);
 
	LTErase(pos);
	LTPrint(plist);
}
 
int main()
{
	LTTest3();
	return 0;
}

打印

双向链表的销毁

销毁就是把链表所以的节点free删掉。用个循环来删除节点，删完后吧哨兵位（头结点）删除就好了。使用后顺便把plist也置空一下。

声明


// 双向链表销毁
void LTDestroy(LTNode* phead);

实现


// 双向链表销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

运用


void LTTest3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
 
	LTNode* pos = LTFind(plist, 2);
	if (pos)
	{
		LTInsert(pos, 20);
	}
	LTPrint(plist);
 
	LTErase(pos);
	LTPrint(plist);
 
	LTDestroy(plist);
	plist = NULL;
}
 
int main()
{
	LTTest3();
	return 0;
}

打印

关于链表的互用

在上边可以看见pos前插入，删除的pos位置。和头插尾插，头删尾删没有太大区别。

这样看来我们就可以直接用pos前插入的函数来实现头插尾插。删除pos位置，来实现头删尾删。

上边该实现的都实现了，下面就直接给实现的代码了。

尾插的互用

要尾删的节点就在phead的prev位置。pos前插入就给phead位置就行了。函数会自己找到


//双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead, x);
}

尾删的互用

尾删的位置就是phead的前一个


//双链表的尾删
void LTPopBak(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTErase(phead->prev);
}

头插的互用

头插的位置就是phead的下一个位置，把值传过去就好了


//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead->next, x);
}

头删的互用

头删的位置就是phead的下一个


//链表的头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTErase(phead->next);
}

完整代码

我用的文件有3个有头文件，函数的实现文件，主函数的文件。

头文件List.h


#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int LTDataType;
 
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}LTNode;
 
//申请新的节点
LTNode* BuyLTNode(LTDataType x);
//链表初始化
LTNode* LTInit();
//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
//双链表的尾删
void LTPopBak(LTNode* phead);
//判空
bool LTEmpty(LTNode* phead);
//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);
//链表的头删
void LTPopFront(LTNode* phead);
// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);
// 双向链表销毁
void LTDestroy(LTNode* phead);

函数实现的文件List.c


#include "List.h"
 
//申请新的节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
 
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}
 
//打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
//双向链表初始化
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
 
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}
 
//双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead, x);
	//LTNode* tail = phead->prev;
	//LTNode* newnode = BuyLTNode(x);
 
	//newnode->next = phead;
	//newnode->prev = tail;
	//tail->next = newnode;
	//phead->prev = newnode;
}
 
//双链表的尾删
void LTPopBak(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTErase(phead->prev);
	//LTNode* tail = phead->prev;
	//LTNode* tailPrev = tail->prev;
 
	//free(tail);
 
	//tailPrev->next = phead;
	//phead->prev = tailPrev;
}
 
//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTInsert(phead->next, x);
	//LTNode* newnode = BuyLTNode(x);
	//LTNode* next = phead->next;
 
	//phead->next = newnode;
	//newnode->prev = phead;
	//newnode->next = next;
	//next->prev = newnode;
}
 
//链表的头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTErase(phead->next);
	//LTNode* first = phead->next;
	//LTNode* second = first->next;
 
	//phead->next = second;
	//second->prev = phead;
 
	//free(first);
}
 
// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
 
		cur = cur->next;
	}
	return NULL;
}
 
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* posPrev = pos->prev;
 
	newnode->next = pos;
	newnode->prev = posPrev;
	posPrev->next = newnode;
	pos->prev = newnode;
}
 
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
	assert(pos);
	assert(!LTEmpty(pos));
 
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
 
	posPrev->next = posNext;
	posNext->prev = posPrev;
 
	free(pos);	
}
 
//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
 
	return phead->next == phead;
}
 
// 双向链表销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

主函数文件Test.c

这里有我对所有函数的使用测试。


#include "List.h"
 
void LTTest1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
 
	LTPopBak(plist);
	LTPrint(plist);
	LTPopBak(plist);
	LTPrint(plist);
	LTPopBak(plist);
	LTPrint(plist);
	LTPopBak(plist);
	LTPrint(plist);
	//LTPopBak(plist);
	//LTPrint(plist);
}
 
void LTTest2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
 
	LTPrint(plist);
 
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
}
 
void LTTest3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
 
	LTNode* pos = LTFind(plist, 2);
	if (pos)
	{
		LTInsert(pos, 20);
	}
	LTPrint(plist);
 
	LTErase(pos);
	LTPrint(plist);
 
	LTDestroy(plist);
	plist = NULL;
}
 
int main()
{
	LTTest3();
	return 0;
}

最后谢谢观看，如果那里写得不对的地方，欢迎提出，探讨。白白

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】