[C++知识库]C语言【双向循环链表】的模拟！（根据C++库的实现）

目录

一、什么是双向循环链表

二、双向循环链表的成员

三、双向循环链表的实现

一、什么是双向循环链表

双向循环链表是结合了单链表与顺序表的各自优势，做到了单链表与顺序表不能或者难以做到的事情。它的结构如下图所示：

它由一个头节点带上若干个节点首尾相连形成循环。?

二、双向循环链表的成员

typedef int DListDate;
typedef struct DListNode
{
	DListDate val;
	struct DListNode* prev;
	struct DListNode* next;
}DListNode;

由它的结构不难发现，它应该有一个存储数据的变量val,因为头尾相连要形成循环，所以应该有两个指针为prev，next，分别指向前一个节点的与后一个节点。?

三、双向循环链表的实现

我们得先创建一个双向循环链表

1.DListNode* DListInit()链表初始化

DListNode* DListInit()
{
	DListNode* phead = (DListNode*)malloc(sizeof(DListNode));
	if (phead==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

这里初始化链表时next与prev应该要指向头节点，这样在后面方便增加节点。

2.void DListDestory(DListNode* phead)链表的销毁

void DListDestory(DListNode* phead)
{
	DListNode* cur = phead->next;
	DListNode* next = NULL;
	while (cur!=phead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
}

有初始化就应该有销毁，因为链表申请的内存空间是动态内存开辟的，不销毁会导致内存泄漏。

3。void DListPrint(DListNode* phead)链表数据的打印

void DListPrint(DListNode* phead)
{
	assert(phead);
	DListNode* cur = phead->next;
	printf("phead<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

4.DListNode* BuyDListNode(DListDate n)创建新节点并返回新节点的地址

DListNode* BuyDListNode(DListDate n)
{
	DListNode* node = (DListNode*)malloc(sizeof(DListNode));
	if (node==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->val = n;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

5.void DListPushFront(DListNode* phead, DListDate n)链表头插

void DListPushFront(DListNode* phead, DListDate n)
{
	assert(phead);
	DListNode* newnode = BuyDListNode(n);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

6.void DListPushBack(DListNode* phead, DListDate n)链表尾插

void DListPushBack(DListNode* phead, DListDate n)
{
	assert(phead);
	DListNode* newnode = BuyDListNode(n);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	phead->prev = newnode;
	newnode->next = phead;
}

7.void DListPopFront(DListNode* phead)链表头删

void DListPopFront(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	phead->next = phead->next->next;
	free(phead->next->prev);
	phead->next->prev = phead;
}

8.void DListPopBack(DListNode* phead)链表尾删

void DListPopBack(DListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	phead->prev = phead->prev->prev;
	free(phead->prev->next);
	phead->prev->next = phead;
}

9.DListNode* DListFind(DListNode* phead, DListDate n)链表查找

DListNode* DListFind(DListNode* phead, DListDate n)
{
	assert(phead);
	DListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == n)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

查找到则返回所在节点地址，否则返回NULL。

10.void DListInsert(DListNode* pos, DListDate n)链表在pos前插入节点

void DListInsert(DListNode* pos, DListDate n)
{
	assert(pos);
	DListNode* prev = pos->prev;
	DListNode* newnode = BuyDListNode(n);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

11.void DListErase(DListNode* pos)链表删除pos位置节点

void DListErase(DListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

由于我们还实现了在pos位置的(前)插入与删除，所以我们可以对头插头删，尾插尾删进行修改

void DListPushFront(DListNode* phead, DListDate n)//头插
{
	//assert(phead);
	//DListNode* newnode = BuyDListNode(n);
	//newnode->next = phead->next;
	//phead->next->prev = newnode;
	//phead->next = newnode;
	//newnode->prev = phead;
	DListInsert(phead->next, n);
}

void DListPushBack(DListNode* phead, DListDate n)//尾插
{
	assert(phead);
	//DListNode* newnode = BuyDListNode(n);
	//phead->prev->next = newnode;
	//newnode->prev = phead->prev;
	//phead->prev = newnode;
	//newnode->next = phead;
	DListInsert(phead, n);
}

void DListPopFront(DListNode* phead)//头删
{
	//assert(phead);
	//assert(phead->next != phead);
	//phead->next = phead->next->next;
	//free(phead->next->prev);
	//phead->next->prev = phead;
	DListErase(phead->next);
}

void DListPopBack(DListNode* phead)//尾删
{
	//assert(phead);
	//assert(phead->next != phead);
	//phead->prev = phead->prev->prev;
	//free(phead->prev->next);
	//phead->prev->next = phead;
	DListErase(phead->prev);
}

通常来说链表的查找与修改搭配来使用，如代码：

DListNode* pos = DListFind(plist, 要查找的值);
if (pos == NULL)
{
	printf("没找到！\n");
}
else
{
	pos->val = 要修改的值;
}

一键三连！！！礼尚往来！！！