C语言实现带头双向循环链表功能_C/C++

双向链表的结构

有了之前不带头单链表的基础,现在再来看看双向链表,全称带头双向循环链表

这里的带头并不是指的之前单链表中的头节点,实际称为哨兵位。哨兵位节点不存储任何有效数据,只是用于避免遍历链表时进入死循环。

带头双向循环链表的实现

本文手写的带头双向循环链表存储的数据类型为 int

带头双向循环链表的结构

// 重命名方便书写和修改
typedef int ldatatype;
typedef struct listnode
{
	ldatatype data;
	struct listnode* prev;
	struct listnode* next;
}listnode;

prev 指向的是前一个节点的, next 指向的是后一个节点, data 用于存放数据

带头双向循环链表的方法

头文件包含

#include <stdio.h> //标准输入输出
#include <stdlib.h> // 主要使用动态开辟内存
#include <assert.h> // 主要使用断言

带头双向循环链表节点的申请

申请的一个节点要让他自循环

listnode* buynode(ldatatype data)
{
	// 动态申请空间
	listnode* node = (listnode*)malloc(sizeof(listnode));
	if (!node)
	{
		// 没有开辟成功
		perror("malloc error");
		exit(1);
	}
	node->data = data;
	// 要让这个节点自循环
	node->prev = node;
	node->next = node;
	return node;
}

动态申请的内存空间存放于堆区,不主动释放出函数后不会被系统收回

测试

int main()
{
	// 测试节点的申请
	listnode* n = buynode(1);
	return 0;
}

带头双向循环链表的插入

带头双向循环链表数据的打印

打印整个链表数据就涉及到遍历链表,需要找到尾节点,尾节点的下一个节点是哨兵位

void print_list(listnode* phead)
{
	// 打印链表
	// 判空,传进来的 phead 不能为 null
	assert(phead);
	if (phead->next == phead)
	{
		// 处理只有一个哨兵位的情况
		printf("null\n");
		return;
	}
	listnode* pcur = phead-> next; // 用 pcur 去进行遍历
	while (pcur != phead)
	{
		// 当 pcur 走到 phead 的位置时说明整个链表都已经走完了
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
void reverse_print_list(listnode* phead)
{
	// 逆序打印链表
	// 判空,传进来的 phead 不能为 null
	assert(phead);
	if (phead->prev == phead)
	{
		// 处理只有一个哨兵位的情况
		printf("null\n");
		return;
	}
	listnode* pcur = phead->prev; // 用 pcur 去进行遍历
	while (pcur != phead)
	{
		// 当 pcur 走到 phead 的位置时说明整个链表都已经走完了
		printf("%d->", pcur->data);
		pcur = pcur->prev;
	}
	printf("\n");
}

头插

让新节点的 next 指向原头节点(哨兵位的 next 指向的节点), prev 指向哨兵位。原头节点(哨兵位的 next 指向的节点)的 prev 指向新节点,哨兵位的 next 指向这个新节点。

void pushfront(listnode* phead, ldatatype data)
{
	// 双向链表的头插
	// 因为哨兵位不用存放有效数据,且哨兵位本身不能被修改,所以用传值调用即可
	// 判空,传进来的 phead 不能为 null
	assert(phead);
	// 调用申请节点函数
	listnode* newnode = buynode(data);
	// 让新节点的 next 指向原头节点(哨兵位的 next 指向的节点)
	newnode->next = phead->next;
	// 让新节点的 prev 指向哨兵位
	newnode->prev = phead;
	//原头节点(哨兵位的 next 指向的节点)的 prev 指向新节点
	phead->next->prev = newnode;
	// 哨兵位的 next 指向这个新节点
	phead->next = newnode;
}

测试

int main()
{
	// 测试头插和打印
	listnode* head = buynode(-1);// 申请哨兵位
	print_list(head);
	reverse_print_list(head);
	pushfront(head, 2);
	pushfront(head, 3);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

尾插

让新节点的 prev 指向原尾节点,next 指向哨兵位,原尾节点的 next 指向新节点,哨兵位的 prev 指向新节点。

void pushback(listnode* phead, ldatatype data)
{
	// 尾插
	// 因为哨兵位不用存放有效数据,且哨兵位本身不能被修改,所以用传值调用即可
	// 判空,传进来的 phead 不能为 null
	assert(phead);
	// 调用申请节点函数
	listnode* newnode = buynode(data);
	// 让新节点的 prev 指向原尾节点
	newnode->prev = phead->prev;
	// 让新节点的 next 指向哨兵位
	newnode->next = phead;
	// 原尾节点的 next 指向新节点
	phead->prev->next = newnode;
	// 哨兵位的 prev 指向新节点
	phead->prev = newnode;
}

测试

int main()
{
	// 测试尾插
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	pushback(head, 2);
	pushback(head, 3);
	pushback(head, 4);
	pushback(head, 5);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

带头双向循环链表的查找

遍历链表查找节点，找到了返回,找不到返回 null

listnode* find(listnode* phead, ldatatype data)
{
	// 双向链表的查找
	// 传进来的 phead 不能是 null
	assert(phead);
	if (phead->prev == phead)
	{
		// 处理只有一个哨兵位的情况,这是个空链表
		printf("当前链表为空!\n");
		return null;
	}
	listnode* pcur = phead->next;// 用 pcur 去遍历
	while (pcur != phead)
	{
		if (pcur->data == data)
		{
			// 找到了就返回
			return pcur;
		}
		pcur = pcur->next;
	}
	// 出来说明遍历完了链表都没找到
	return null;
}

指定位置前插入

让新节点的 prev 指向原节点的 prev 指向的节点,next 指向原节点,原节点的 prev 指向新节点,原节点的 next 指向的节点指向新节点。

void push_pos_before(listnode* pos, ldatatype data)
{
	// 指定为之前插入
	// 判空,传进来的 pos 不能为 null
	assert(pos);
	listnode* prev = pos->prev; // 用 prev 来记住 pos 前的节点
	// 调用申请节点函数
	listnode* newnode = buynode(data);
	//让新节点的 prev 指向原节点的 prev 指向的节点
	newnode->prev = prev;
	// 让新节点的 next 指向原节点
	newnode->next = pos;
	// 原节点的 prev 指向新节点
	pos->prev = newnode;
	// 原节点的 next 指向的节点指向新节点
	prev->next = newnode;
}

测试

int main()
{
	// 测试指定位置插入
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	push_pos_before(head, 1);
	push_pos_before(head, 2);
	push_pos_before(head, 3);
	print_list(head);
	reverse_print_list(head);
	listnode* find = find(head, 2);
	push_pos_before(find, 4);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

带头双向循环链表的删除

节点都是动态申请的空间,删除需要用到 free

尾删

让尾节点的 prev 指向的节点的 next 指向头节点,头节点的 prev 指向新的尾节点,再释放尾节点

void popback(listnode* phead)
{
	// 双向链表尾删
	// 判空,传进来的 phead 不能为 null
	assert(phead);
	if (phead->next == phead)
	{
		// 只有一个哨兵位,说明链表是空的
		printf("当前链表为空!\n");
		return;
	}
	listnode* pcur = phead; // 让 pcur 去遍历链表
	listnode* prev = pcur->prev; // 用 ptail 去记录 pcur->next 指向的节点
	while (pcur->next != phead)
	{
		// pcur->next 为 phead 时说明 pcur 已经到尾节点了
		pcur = pcur->next;
		prev = pcur->prev;
	}
	// 让尾节点的 prev 指向的节点的 next 指向头节点
	prev->next = phead;
	// 让头节点的 prev 指向新的尾节点
	phead->prev = prev;
	// 释放原尾节点
	free(pcur);
}

测试

int main()
{
	// 测试尾删
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	push_pos_before(head, 1);
	push_pos_before(head, 2);
	push_pos_before(head, 3);
	print_list(head);
	reverse_print_list(head);
	popback(head);
	print_list(head);
	reverse_print_list(head);
	popback(head);
	print_list(head);
	reverse_print_list(head);
	popback(head);
	print_list(head);
	reverse_print_list(head);
	popback(head);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

头删

哨兵位的 next 指向要删除节点的 next 指向的节点,要删除节点的 next 指向的节点的 prev 指向哨兵位，最后释放要删除的节点。

void popfront(listnode* phead)
{
	// 头删
	// 判空,传进来的 phead 不能为 null
	assert(phead);
	if (phead->next == phead)
	{
		// 只有一个哨兵位,说明链表是空的
		printf("当前链表为空!\n");
		return;
	}
	// 记录要删除的节点
	listnode* del = phead->next;
	// 哨兵位的 next 指向要删除节点的 next 指向的节点
	phead->next = del->next;
	// 要删除节点的 next 指向的节点的 prev 指向哨兵位
	del->next->prev = phead;
	// 释放要删除的节点
	free(del);
}

测试

int main()
{
	// 测试头删
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	push_pos_before(head, 1);
	push_pos_before(head, 2);
	push_pos_before(head, 3);
	print_list(head);
	reverse_print_list(head);
	popfront(head);
	print_list(head);
	reverse_print_list(head);
	popfront(head);
	print_list(head);
	reverse_print_list(head);
	popfront(head);
	print_list(head);
	reverse_print_list(head);
	popfront(head);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

指定位置删除

void pop_pos_del(listnode* phead, listnode* pos)
{
	// 指定位置删除
	// 判空,传进来的 pos 和 phead 不能为空
	assert(phead && pos);
	if (pos == phead)
	{
		printf("哨兵位不能删除!\n");
		return;
	}
	listnode* prev = pos->prev;
	listnode* next = pos->next;
	// 让 pos 前的节点的 next 指向 pos 后的节点
	prev->next = next;
	// 让 pos 后的节点的 prev 指向 pos 前的节点
	next->prev = prev;
	// 释放节点
	free(pos);
}

测试

int main()
{
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	push_pos_before(head, 1);
	push_pos_before(head, 2);
	push_pos_before(head, 3);
	push_pos_before(head, 4);
	push_pos_before(head, 5);
	print_list(head);
	reverse_print_list(head);
	listnode* find1 = find(head, 1);
	listnode* find2 = find(head, 2);
	listnode* find3 = find(head, 5);
	//测试删中间
	pop_pos_del(head, find2);
	print_list(head);
	reverse_print_list(head);
	//测试删头
	pop_pos_del(head, find1);
	print_list(head);
	reverse_print_list(head);
	//测试删尾
	pop_pos_del(head, find3);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

带头双向循环链表值的修改

void pos_edit(listnode* phead, listnode* pos, ldatatype data)
{
	// 链表值的修改
	// 判空,传进来的 phead 和 pos 不允许修改
	assert(phead && pos);
	if (phead == pos)
	{
		printf("哨兵位不允许修改!\n");
		return;
	}
	// 修改
	pos->data = data;
}

测试

int main()
{
	// 测试修改
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	push_pos_before(head, 1);
	push_pos_before(head, 2);
	push_pos_before(head, 3);
	print_list(head);
	reverse_print_list(head);
	listnode* find = find(head, 2);
	pos_edit(head, find, 4);
	print_list(head);
	reverse_print_list(head);
	find = find(head, 3);
	pos_edit(head, find, 5);
	print_list(head);
	reverse_print_list(head);
	return 0;
}

带头双向循环链表的销毁

从头节点开始释放,最后释放尾节点

void destory(listnode** pphead)
{
	// 链表的销毁
	// 判空,传进来的 phead 不能为 null
	// 因为这里会销毁哨兵位所以传二级指针
	assert(pphead && *pphead);
	listnode* pcur = (*pphead)->next;// 用 pcur 来遍历,从头节点开始释放
	listnode* ptail = pcur->next; // 用 ptail 来记录 pcur 的下一个节点
	while (pcur != *pphead)
	{
		// 释放当前节点
		free(pcur);
		// 走向下一个节点
		// 当 pcur 走到哨兵位的时候, 哨兵位还没有被释放
		// 所以 ptail 还可以向前走
		pcur = ptail;
		ptail = ptail->next;
	}
	//最后释放哨兵位
	free(*pphead);
	*pphead = null;
}

测试

int main()
{
	// 测试销毁链表
	listnode* head = buynode(-1); // 申请哨兵位
	print_list(head);
	push_pos_before(head, 1);
	push_pos_before(head, 2);
	push_pos_before(head, 3);
	print_list(head);
	reverse_print_list(head);

	destory(&head);
	return 0;
}