【C语言】双向带头循环链表

[TOC]

前言

在之前的数据结构学习中，我们学习了顺序表、链表这两种结构

顺序表：博客链接1
单链表：博客链接2
链表OJ：博客链接3

之前本来是不想写双链表的博客的，但是看着自己的数据结构专栏少了一part，有强迫症的我感觉很不爽，于是补上了本篇大水文

1.双链表的结构

除了单链表以外，还有一个结构，是双向带头循环链表。这个链表的形式如下

头节点的prev指向尾部节点
尾节点的next指向头节点，构成循环

别看它的形式有些复杂，实际代码的实现，比单链表还简单！

因为head->prev指向了尾节点，所以不需要找尾。尾删的时候也不需要遍历找尾节点的前一位，因为尾节点的prev就存放了前一位的地址。

2.代码实现

下面贴出双链表实现的源码，如果大家有问题，可以在评论区提出

只要你学会了单链表的编写，也看完了我的链表OJ题博客，那双链表对于你来说肯定是信手拈来的

2.1头文件

DoubleList.h头文件

如果你想尝试自己编写双链表的代码，可以先把头文件复制到你的本地编译器，将这些函数的实现搞出来

#pragma once

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


// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建并返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
//倒着打印，检查双链表是否完整
void ListPrintReverse(ListNode* pHead);

// 创建新的节点
ListNode* BuyNode(LTDataType x);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

2.2源文件

DoubleList.c源文件

还是建议你写完之后再来和我的函数对比对比。

一定要记住：写完一个模块，测试一个模块，不要等到最后再测试！

#define _CRT_SECURE_NO_WARNINGS 1

#include "DoubleList.h"

ListNode* ListCreate()
{
	ListNode* Createnode = (ListNode*)malloc(sizeof(ListNode));
	if (Createnode == NULL)
		printf("CreateNode failed\n");
	else
	{
		Createnode->next = Createnode;
		Createnode->prev = Createnode;
	}

	return Createnode;
}

void ListDestory(ListNode* pHead)
{
	assert(pHead);

	while (pHead->prev!=pHead)
	{
		ListNode* tail = pHead->prev;
		ListNode* tailprev = tail->prev;
		free(tail);
		pHead->prev = tailprev;
	}
	free(pHead);
}

void ListPrint(ListNode* pHead)
{
	assert(pHead);
	
	ListNode* cur = pHead->next;
	while (cur->next!=pHead)
	{
		printf("%d -> ",cur->data);
		cur = cur->next;
	}
	printf("%d", cur->data);//打印最后一个节点
	printf("\n");

}

void ListPrintReverse(ListNode* pHead)
{
	assert(pHead);

	ListNode* tail = pHead->prev;
	while (tail->prev != pHead)
	{
		printf("%d -> ", tail->data);
		tail = tail->prev;
	}
	printf("%d", tail->data);
	printf("\n\n");
	
}

ListNode* BuyNode(LTDataType x)
{
	ListNode* Buy = (ListNode*)malloc(sizeof(ListNode));
	if (Buy == NULL)
		printf("BuyNode failed\n");
	else
	{
		Buy->data = x;
		Buy->next = NULL;
		Buy->prev = NULL;
	}

	return Buy;
}


void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* newnode = BuyNode(x);

	ListNode* tail = pHead->prev;
	tail->next = newnode;

	newnode->next = pHead;
	newnode->prev = tail;

	pHead->prev = newnode;
}

void ListPopBack(ListNode* pHead)
{
	assert(pHead);

	ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;

	free(tail);
	tailprev->next = pHead;
	pHead->prev = tailprev;

}

void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* newnode= BuyNode(x);
	newnode->prev = pHead;
	newnode->next = pHead->next;
	pHead->next = newnode;
	newnode->next->prev = newnode;
}

void ListPopFront(ListNode* pHead)
{
	assert(pHead);

	ListNode* front = pHead->next->next;
	ListNode* Popnode = pHead->next;//待爆破的头节点
	pHead->next = front;
	free(Popnode);
	front->prev = pHead;
}

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur!=pHead)
	{
		if (cur->data == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}


void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newnode = BuyNode(x);
	ListNode* Prev = pos->prev;
	Prev->next = newnode;
	newnode->prev = Prev;
	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* Prev = pos->prev;
	ListNode* Next = pos->next;
	Prev->next = pos->next;
	Next->prev = Prev;
	free(pos);

}