数据结构之带头双向链表（易学版）

目录

---

，又和大家见面了，今天要给大家分享的是双链表的知识，跟着我的脚步，包学包会哦~

规矩不乱，先赞后看！

ps：（孙权劝学）

1.问题引入

前期学习了单链表，我们尝到了它的甜头，但是容易越界访问这一个问题也是时有出现的，因此也是相对比较棘手的，为了解决这一个问题，特此向大家介绍带头双向链表

带头双向链表，顾名思义含有哨兵位，同时一个节点有两个指针（next / prev），这样的好处是让相邻指针的联系更加紧密，同时将首尾节点相连是其能够非常容易实现找尾。

话不多说，直接上代码！

2.结构实现

2.3.1接口实现

先在头文件（List.h)上进行顺序表结构的创建和对各函数的声明，目的是为了把各部分区分开，使程序便于理解，能清楚的看到各部分对于的作用和功能。

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


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

	LTDataType data;

}LTNode;

bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
LTNode* LTInit();
void LTPopFront(LTNode* phead);
void PushFront(LTNode* phead, LTDataType x);
void LTPrint(LTNode* phead);
LTNode* BuyLTNode(LTDataType x);
void LTPopBack(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

2.3.2函数实现

接着下来是单链表各函数的函数部分，我们在List.c中完成：

a.创造新节点

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

这些步骤都是和链表一模一样的。

b.初始化链表

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

都是链表的一套固定公式

c.查找链表

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);

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

		cur = cur->next;
	}

	return NULL;

}

d.在链表中插入节点

由于有了双链表，使得插入十分轻松，同时这一个函数就能简化头插和尾插两个函数，是相当方便的

//在pos前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

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

}

e.在链表中删除节点

void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;

	posprev->next = posnext;
	posnext->prev = posprev;

	free(pos);
	pos = NULL;
}

有了这个函数，也可以让头删和尾删变得相当的简洁。

f.判断链表是否为空

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

由于头删尾删会改变链表，因此需要一个判空函数来保证程序的安全性

g.头插尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)//不需要二级指针（没有改变phead）
{
	assert(phead);

	//LTNode* newnode = BuyLTNode(x);
	//LTNode* tail = phead->prev;
	//tail->next = newnode;
	//newnode->next = phead;
	//newnode->prev = tail;
	//phead->prev = newnode;

	LTInsert(phead, x);

}

//头插
//头插---指的是插在头结点之后，首个含数据的结点之前
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* newnode = BuyLTNode(x);
	//phead->next->prev = newnode;
	//newnode->next = phead->next;

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

	//香饽饽
	LTInsert(phead->next, x);
}

注释掉的是没有依靠Insert和Erase函数来写的头插尾插，是相当麻烦的，通过那两个函数，能让你不到10分钟就能写出双链表。

h.头删尾删

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	//LTNode* tail = phead->prev;
	//LTNode* tailprev = tail->prev;

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

	LTErase(phead->prev);

}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	//if (phead->next->next == NULL)
	//{
	//	phead->next = phead;
	//	phead->prev = phead;
	//}
	//else
	//{
	//	LTNode* cur = phead->next;
	//	LTNode* af = phead->next->next;

	//	assert(cur);
	//	assert(af);

	//	phead->next = af;
	//	af->prev = phead;
	//	free(cur);
	//	cur = NULL;
	//}

	LTErase(phead->next);

}

i.打印链表

 

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");
	LTNode* cur = phead->next;


	while (cur != phead)
	{
		printf("%d<==>", cur->data);

		cur = cur->next;
	}
	printf("\n");
}

j.销毁链表

程序执行完毕后需要销毁程序，这样才不会出现内存问题

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	//LTNode* tail = phead->prev;
	//LTNode* tailprev = tail->prev;

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

	LTErase(phead->prev);

}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	//if (phead->next->next == NULL)
	//{
	//	phead->next = phead;
	//	phead->prev = phead;
	//}
	//else
	//{
	//	LTNode* cur = phead->next;
	//	LTNode* af = phead->next->next;

	//	assert(cur);
	//	assert(af);

	//	phead->next = af;
	//	af->prev = phead;
	//	free(cur);
	//	cur = NULL;
	//}

	LTErase(phead->next);

}

2.3测试程序

实现完函数之后还需要对其进行测试

#include"List.h"

void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPopFront(plist);

	LTPrint(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;

}
void TestList2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPopFront(plist);

	LTPrint(plist);
	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	TestList1();
	TestList2();

	return 0;
}

最后在终端上运行一遍得到结果

 结果是这样的小伙伴就是正确掌握了的哟

如果没有跑起来的uu们也不用担心，细心调试一下，慢慢找错也是一种成长。 

3.总结

链表的学习我认为是一个先苦后甜的过程，把单链表的原理搞懂之后，再使用双链表就完全是如鱼得水了。学习也是一样，先吃苦，以后才能尝到生活的甜头。

最后关于链表的问题，我强烈建议大家刷题巩固，踏实稳重，才能把数据结构这个难关拿下。