双向循环链表

绝活蛋炒饭

发布于 2024-12-16 15:43:33

10200

代码可运行

文章被收录于专栏：绝活编程学习绝活编程学习

运行总次数：0

代码可运行

以下是一个使用C语言实现的双向链表操作函数，包括创建节点、创建链表、销毁链表、打印链表、插入节点、删除节点等功能。这些函数可以用于实现各种链表操作，例如排序、查找等。

1.链表节点的定义

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

2.创造一个新的节点

// 创造一个新的节点
ListNode* BuyNewnode(LTDataType x)
{
	// 分配内存给新节点
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	// 检查内存分配是否成功
	if (newnode == NULL)
	{
		perror("malloc");
	}
	// 初始化新节点的prev, next, 和data属性
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	// 返回新节点
	return newnode;
}

3.创建一个头结点

// 创建返回链表的头结点.
ListNode* ListCreate()
{
	// 分配内存给头结点
	ListNode* head = (ListNode*)malloc(sizeof(struct ListNode));
	// 检查内存分配是否成功
	if (head == NULL)
	{
		perror("malloc");
	}
	// 初始化头结点的prev和next属性，使之指向自身
	head->prev = head;
	head->next = head;
	// 返回头结点
	return head;
}

4.双向链表的销毁

// 双向链表销毁
void ListDestory(ListNode* plist)
{
	// 从头开始释放每个节点的内存
	ListNode* cur = plist;
	ListNode* next = cur->next;
	while (cur)
	{
		free(cur);
		cur = next;
		next = cur->next;
	}
}

5双向链表打印

// 双向链表打印
void ListPrint(ListNode* plist)
{
	// 从第一个节点开始，打印每一个节点的数据
	ListNode* cur = plist->next;
	printf("head<=>");
	while (cur != plist)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

6.双向链表尾插

void ListPushBack(ListNode* plist, LTDataType x)
{
	// 创建新节点
	ListNode* newnode = BuyNewnode(x);
	// 获取尾节点
	ListNode* tail = plist->prev;
	// 更新链表指针
	plist->prev = newnode;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
}

7.双向链表尾删

void ListPopBack(ListNode* plist)
{
	// 获取尾节点和尾节点的前一个节点
	ListNode* tail = plist->prev;
	ListNode* prev = tail->prev;

	// 更新链表指针，删除尾节点
	plist->prev = prev;
	prev->next = plist;
	free(tail);
}

8.双向链表头插

void ListPushFront(ListNode* plist, LTDataType x)
{
	// 创建新节点
	ListNode* newnode = BuyNewnode(x);
	// 获取第一个节点
	ListNode* first = plist->next;
	// 更新链表指针
	plist->next = newnode;
	first->prev = newnode;
	newnode->prev = plist;
	newnode->next = first;
}

9。双向链表头删

// 双向链表头删
void ListPopFront(ListNode* plist)
{
	// 获取第一个节点和第二个节点
	ListNode* first = plist->next;
	ListNode* next = first->next;
	// 更新链表指针，删除第一个节点
	plist->next = next;
	next->prev = plist;

	free(first);
}

10.双向链表查找

ListNode* ListFind(ListNode* plist, LTDataType x)
{
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	printf("没找到");
}

11.双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x)
{
	// 获取插入位置的前一个节点
	ListNode* prev = pos->prev;
	// 创建新节点
	ListNode* newnode = BuyNewnode(x);

	// 更新链表指针，进行插入操作
	prev->next = newnode;
	pos->prev = newnode;

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

}

12.双向链表删除pos位置的结点

void ListErase(ListNode* pos)
{
	// 获取删除位置的前一个节点和后一个节点
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	// 更新链表指针，删除节点
	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

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

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

内存