当前位置：首页 > news >正文

【数据结构：链表】——带头双向循环链表的实现（C语言）

news 来源：原创 2024/4/29 12:09:48

本片接上一篇【数据结构：链表】——无头单向非循环链表的实现（C语言）

1、链表实现

带头双向循环链表： 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向
循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而
简单了，后面我们代码实现了就知道了。
在这里插入图片描述

2、代码实现

从上图我们可以看出双向链表的节点数据结构就有了些许不同，一个节点有两个指针域和一个数据域组成，两个指针域一个是指向节点前一个prev前驱指针一个是指向节点后一个
next指针，而循环也就说明了该链表左后一个节点不是指向NULL，而是指向头结点，而头结点的前驱同时也就指向位节点。
链表节点数据结构定义：

typedef int LTDateType;

typedef struct ListNode//链表节点结构体
{
	LTDateType val;
	struct ListNode *_prev;
	struct ListNode *_next;
}ListNode;

typedef struct List//链表头结构体
{
	ListNode *_head;
}List;

解释一下在节点结构声明完成后为什么还要再声明一个结构；因为方便在对链表进行操作，防止二级指针操作失误。链表的操作都是用指针来完成的当传入链表的头结点就要传该节点的地址就要用二级指针，而声明结构体后就完美的解决了传二级指针的问题了。
【注意】：这里不给出头文件，读者自己加上
List.h文件

void ListInit(List* plt);//初始化
void ListDestory(List* plt);//销毁链表
void ListPushBack(List* plt, LTDateType x);//尾部插入
void ListPopBack(List* plt);//尾部删除
void ListPushFront(List* plt, LTDateType x);//头部插入
void ListPopFront(List* plt);//头部删除
ListNode* BuyNode(LTDateType x);//创建一个链表节点
ListNode* ListFind(List* plt, LTDateType x);//查找链表位置
void ListInsert(ListNode* pos, LTDateType x);//在pos的前面插入
void ListErase(ListNode* pos);//删除pos节点
void ListPrint(List* plt);//输出链表

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

ListNode* BuyNode(LTDateType x)//创建一个链表节点
{
	ListNode *p = (ListNode*)malloc(sizeof(ListNode));
	assert(p);
	p->val = x;
	p->_next = NULL;
	p->_prev = NULL;

	return p;
}

void ListInit(List* plt)//初始化
{
	assert(plt);
	plt->_head = BuyNode(0);/头结点 不存任何值
	plt->_head->_next = plt->_head;
	plt->_head->_prev = plt->_head;
}

void ListPushBack(List* plt, LTDateType x)//尾部插入
{
	assert(plt);
	ListNode *head = plt->_head;
	ListNode *next = head->_prev;
	ListNode *newnode = BuyNode(x);

	next->_next = newnode;
	head->_prev = newnode;

	newnode->_prev = next;
	newnode->_next = head;
}

void ListPopBack(List* plt)//尾部删除
{
	assert(plt);

	ListNode *head = plt->_head;
	ListNode *prev = head->_prev->_prev;
	ListNode *tail = head->_prev;

	prev->_next = head;
	head->_prev = prev;
	free(tail);
	tail = NULL;

}

void ListPushFront(List* plt, LTDateType x)//头部插入
{
	assert(plt);

	ListNode *head = plt->_head;
	ListNode *next = head->_next;
	ListNode *newnode = BuyNode(x);

	newnode->_next = next;
	next->_prev = newnode;

	head->_next = newnode;
	newnode->_prev = head;
}

void ListPopFront(List* plt)//头部删除
{
	assert(plt);

	ListNode *head = plt->_head;
	ListNode *next = head->_next;
	ListNode *cur = next->_next;

	head->_next = cur;
	cur->_prev = head;
	free(next);
	next = NULL;

}

ListNode* ListFind(List* plt, LTDateType x)//查找链表位置
{
	assert(plt);

	ListNode* head = plt->_head;
	ListNode* cur = head->_next;

	while (cur != head)
	{
		if (cur->val == x)
		{
			return cur;
		}

		cur = cur->_next;
	}
	return NULL;
}

void ListInsert(ListNode* pos, LTDateType x)//在pos的前面插入
{
	assert(pos);

	ListNode* newnode = BuyNode(x);
	ListNode* prev = pos->_prev;

	newnode->_next = pos;
	pos->_prev = newnode;

	prev->_next = newnode;
	newnode->_prev = prev;
}

void ListErase(ListNode* pos)//删除pos节点
{
	assert(pos);

	ListNode* prev = pos->_prev;
	ListNode* next = pos->_next;

	prev->_next = next;
	next->_prev = prev;
	free(pos);
	pos = NULL;
}

void ListPrint(List* plt)//输出链表
{
	ListNode *head = plt->_head;
	ListNode *cur =head->_next;

	printf("head");
	while (cur != head)
	{
		printf("<=>%d", cur->val);
		cur = cur->_next;
	}
	printf("\n");
}

main.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

int main()
{
	Test()
{
    List pl;
	ListInit(&pl);
	ListPushBack(&pl, 1);
	ListPushBack(&pl, 2);
	ListPushBack(&pl, 3);
	ListPushBack(&pl, 4);
	ListPushBack(&pl, 5);
	ListPushBack(&pl, 6);
	ListPrint(&pl);
	
	ListNode* pos_1 = ListFind(&pl, 4);
	ListInsert(pos_1, 50);
	ListPrint(&pl);

	ListNode* pos_2 = ListFind(&pl, 50);
	ListErase(pos_2);
	ListPrint(&pl);

	ListPushFront(&pl, 0);
	ListPrint(&pl);
	ListPopFront(&pl);
	ListPrint(&pl);
	ListPopBack(&pl);
	ListPopBack(&pl);
	ListPrint(&pl);
}
	system("pause");
	return 0;
}