链接未来：深入理解链表数据结构（二.c语言实现带头双向循环链表）

是Nero哦

发布于 2024-01-18 18:40:16

1200

发布于 2024-01-18 18:40:16

文章被收录于专栏：c/c++学习与分享

上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表：链接未来：深入理解链表数据结构（一.c语言实现无头单向非循环链表）-CSDN博

那今天接着给大家带来带头双向循环链表的实现：

一.项目文件规划

头文件DoubleList.h:用来基础准备（常量定义，typedef），链表表的基本框架，函数的声明
源文件DoubleList.h:用来各种功能函数的具体实现
源文件test.c:用来测试功能是否有问题，进行基本功能的使用

二.基本结构及功能一览(DoubleList.h)

结构体定义

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;//下一个节点
	struct ListNode* prev;//上一个节点
	LTDataType val;//数据
}LTNode;

接口功能一览

LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印数据

void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删

LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//在pos前插入
void LTErase(LTNode* pos);//删除pos

void LTDestroy(LTNode* phead);//销毁

三.各功能接口具体实现

1.创建节点

因为后面尾插，头插，插入，初始化都要用到创建新节点，所以抽出来作为一个函数

LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态开辟
	if (newnode == NULL)
	{
		perror("malloc");
		return -1;
	}

	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

2.初始化

1.第一种：返回动态开辟的地址（不会销毁）

LTNode* LTInit()
{
	LTNode* a =CreateLTNode(-1);
	a->next = a;//一开始一个节点时，下一个和上一个都指向自己
	a->prev = a;//
	return a;
}

2.第二种：传入二级指针（要直接改变头节点的值）

void LTInit(LTNode** pphead)
{
	*pphead = CreateLTNode(-1);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}

这两种皆可

3.打印

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//头结点数据无效，不需要打印
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

4.尾插

void LTPushBack(LTNode* phead, LTDataType x)//无有效节点也适用
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
	LTNode* tail = phead->prev;
	// phead               tail  newnode  位置展示
	newnode->next = phead;
	phead->prev = newnode;

	newnode->prev = tail;
	tail->next = newnode;
}

5.尾删

void LTPopBack(LTNode* phead)//只有一个有效节点也适用
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* pretail = tail->prev;
	// phead               pretail  tail  位置展示
	free(tail);
	tail = NULL;
	phead->prev = pretail;
	pretail->next = phead;
}

6.头插

void LTPushFront(LTNode* phead, LTDataType x)//无有效节点也适用
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
	//phead   newnode  firest                tail  位置展示
	newnode->next = phead->next;
	phead->next->prev = newnode;

	newnode->prev = phead;
	phead->next = newnode;
}

7.头删

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//只有哨兵位时不能删
	LTNode* first = phead->next;
	LTNode* second = first->next;
	//phead    first   second             tail  位置展示
	free(first);
	first = NULL;

	phead->next = second;
	second->prev = phead;
}

8.查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	assert(phead->next != phead);//只有哨兵位时没必要查
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

9.插入pos前

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = CreateLTNode(x);
	LTNode* pre = pos->prev;
	//pre  newnode   pos             tail  位置展示
	pre->next = newnode;
	newnode->prev = pre;

	newnode->next = pos;
	pos->prev = newnode;
}

将前一个节点 pre 的 next 指针指向新节点 newnode
将新节点 newnode 的 prev 指针指向前一个节点 pre
将新节点 newnode 的 next 指针指向指定节点 pos
将指定节点 pos 的 prev 指针指向新节点 newnode

10.删除pos位置

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* pre = pos->prev;
	LTNode* next = pos->next;
	//pre    pos   next          tail  位置展示
	pre->next = next;
	next->prev = pre;
	free(pos);
	pos = NULL;
}

11.销毁

因为每个节点时malloc动态开辟出来的，要把每个节点都依次销毁

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur->next != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

四.利用插入和删除改变“两插两删”（快速写出链表）

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);//尾插就是在phead前插入
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTErase(phead->prev);
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead->next, x);//头插就是插入到phead的下一个
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTErase(phead->next);
}

那这次就先到这里啦！两种常见的链表都已经实现完毕，接下来大概率是栈和队列了，感谢大家支持

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-18，如有侵权请联系 cloudcommunity@tencent.com 删除

函数