【数据结构与算法】双向带头循环链表（附源码）

2024-01-23 13:59:29 浏览数 (1)

一.前言

在前面的博客中，我们学习了顺序表和结构最简单的链表——单链表，但是单链表存在在着一些不足，比如单链表的插入和删除的操作，总是要找到指定节点的前驱或是后继，这样就会比较麻烦。 那么本篇文章所讲述的双向带头循环链表（以后简称双链表），就可以很好解决这个问题。

二.双向带头循环链表的结构

1.该链表有一个哨兵位节点，即头节点； 2.每个节点都包含一个prev 指针和 next 指针，分别指向当前节点的前驱和后继； 3.头节点的 prev 指向的是尾节点，尾节点的next 指向的是头节点，这样就实现了循环。 请看图示：

别看结构这么复杂，但其实它是一个很厉害的结构，代码实现会很简单。

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

这个接口用来创建哨兵位头节点，并使该节点的 prev 和 next 都指向自己以实现循环的目的。

代码语言：javascript复制
LNode* Buynewnode(DLdatatype x)   //定义一个 malloc 新节点的函数，以便后续需要
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	assert(newnode);
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}
LNode* ListNodeinit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));
	assert(phead);
	phead->prev = phead;  //使其都指向自己
	phead->next = phead;
	phead->data = -1;
	return phead;
}
2.Listdestroy

我们需要遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点； 注意：应该是从头节点的 next 开始遍历。

代码语言：javascript复制
void ListNodedestroy(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

B.插入

1.头插 ListNodepushfront

1.这里要头插就太简单了，但是我们最好保存一下头节点的 next ，这样就不应考虑链接时的顺序问题； 2.使头节点的 next 指向新节点，然后新节点的 prev 指向头节点； 3.新节点的 next 指向保存的节点，保存的节点的 prev 指向新节点； 这里并不需要考虑链表为空的情况，这就是双链表的强大之处。

代码语言：javascript复制
void ListNodepushfront(LNode* phead, DLdatatype x)
{
	assert(phead);

	LNode* newnode = Buynewnode(x);

	LNode* first = phead->next;  //保存头节点的下一个

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
2.尾插 ListNodepushback

1.尾插就需要找尾； 2.这里的找尾很简单，就是头节点的 prev； 3.将尾节点与新节点链接起来。

代码语言：javascript复制
void ListNodepushback(LNode* phead, DLdatatype x)
{
	assert(phead);

	LNode* newnode = Buynewnode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

}
3.插入 ListNodeinsert

1.再插入前需要写一个 find 函数，用来寻找指定的位置 pos； 2.找到 pos 的前驱 prev ； 3.将前驱，pos，新节点链接起来。

代码语言：javascript复制
LNode* ListNodefind(LNode* phead,DLdatatype x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;

	}

	return NULL;
}

void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
{
	assert(phead);
	assert(pos);

	LNode* newnode = Buynewnode(x);
	LNode* prev = pos->prev;

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

总结：其实可以用一个插入接口就可以实现头插和尾插这两个接口。

C.删除

1.删除时要注意的点是不能把头节点也给删了，如果删了就破坏了双链表的结构； 2.如果是空链表也不能删除。

1.头删 ListNodepopfront

1.删除时保存其下一个节点； 2.链接头节点 phead 和 保存的下一个节点； 3.删除 phead 的next。

代码语言：javascript复制
void ListNodepopfront(LNode* phead)
{
	assert(phead);
	assert(ListNodeempty(phead));
	if (phead->next == phead)
	{
		perror("ListNodepopfront");
		return;
	}

	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

	
}
2.尾删 ListNodepopback

1.找尾，即：phead的prev； 2.找尾节点的前驱 prev ，使其next指向phead，phead的prev指向该前驱；

代码语言：javascript复制
void ListNodepopback(LNode* phead)
{
	assert(phead);
	assert(ListNodeempty(phead));

	if (phead->next == phead)
	{
		perror("ListNodepopback");
		exit(-1);
	}

	LNode* tail = phead->prev;
	LNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}
3.删除 ListNodeerase

1.调用 find 函数找到要删除的节点pos； 2.找到 pos 的前驱和后继； 3.链接其前驱，后继； 4.删除pos。

代码语言：javascript复制
void ListNodeerase(LNode* pos, LNode* phead)
{
	assert(phead);
	assert(pos);

	if (phead->next == phead)
	{
		perror("ListNodeerase");
		exit(-1);
	}
	LNode* prev = pos->prev;
	LNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

总结：这里可以复用删除函数去实现头删和尾删。

D.打印 ListNodeprint

注意是从头节点的下一个节点开始遍历，且循环终止条件是看是否等于 phead，因为双链表没有 NULL。

代码语言：javascript复制
void ListNodeprint(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d <=> ", cur->data);
		cur = cur->next;
	}

	printf("n");

	
}

四.源码

List.h
代码语言：javascript复制
#pragma once


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DLdatatype;

typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	DLdatatype data;
}LNode;

LNode* ListNodeinit();

void ListNodeprint(LNode* phead);

void ListNodepushback(LNode*phead,DLdatatype x);

void ListNodepushfront(LNode* phead, DLdatatype x);

void ListNodepopback(LNode* phead);

void ListNodepopfront(LNode* phead);

LNode* ListNodefind(LNode* phead,DLdatatype x);

void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x);

void ListNodeerase(LNode* pos, LNode* phead);

void ListNodedestroy(LNode* phead);
List.c
代码语言：javascript复制
#define _CRT_SECURE_NO_WARNINGS

#include "List.h"

LNode* Buynewnode(DLdatatype x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	assert(newnode);
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}

LNode* ListNodeinit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));
	assert(phead);
	phead->prev = phead;
	phead->next = phead;
	phead->data = -1;
	return phead;
}

void ListNodeprint(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d <=> ", cur->data);
		cur = cur->next;
	}

	printf("n");

	
}

void ListNodepushback(LNode* phead, DLdatatype x)
{
	assert(phead);

	/*LNode* newnode = Buynewnode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/

	ListNodeinsert(phead, phead, x);

	
}

void ListNodepushfront(LNode* phead, DLdatatype x)
{
	assert(phead);

	/*LNode* newnode = Buynewnode(x);

	LNode* first = phead->next;

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;*/

	ListNodeinsert(phead->next, phead, x);
}

bool ListNodeempty(LNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

void ListNodepopback(LNode* phead)
{
	assert(phead);
	//assert(ListNodeempty(phead));

	if (phead->next == phead)
	{
		perror("ListNodepopback");
		exit(-1);
	}

	/*LNode* tail = phead->prev;
	LNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;*/

	ListNodeerase(phead->prev, phead);
}

void ListNodepopfront(LNode* phead)
{
	assert(phead);
	//assert(ListNodeempty(phead));
	if (phead->next == phead)
	{
		perror("ListNodepopfront");
		return;
	}

	/*LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;*/

	ListNodeerase(phead->next, phead);
}

LNode* ListNodefind(LNode* phead,DLdatatype x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;

	}

	return NULL;
}

void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
{
	assert(phead);
	assert(pos);

	LNode* newnode = Buynewnode(x);
	LNode* prev = pos->prev;

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

void ListNodeerase(LNode* pos, LNode* phead)
{
	assert(phead);
	assert(pos);

	if (phead->next == phead)
	{
		perror("ListNodeerase");
		exit(-1);
	}
	LNode* prev = pos->prev;
	LNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

void ListNodedestroy(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;

}
test.c

至于test.c 就不贴出来了，这里面主要是一些测试接口的代码，没必要贴出来

函数 接口 链表 数据结构与算法 源码

0 人点赞