【C语言数据结构】双向循环链表_c语言双向循环链表

目录

前言

 一、双向循环链表

循环结构

1.双向循环链表头文件及函数声明

2.初始化

1.结点构造

2.初始化函数

3.结点申请

 4.数据插入

1.按位置插入

2.尾插

3.头插

 5.查找

 6.数据删除

1.按位置删除

 2.按值删除

3.尾删 

4.头删 

7.清空与销毁 

1.清空

2.销毁

8.双向循环链表源文件及整体函数实现 

总结

---

前言

这次我们将学习双向循环链表，首先了解双向链表和循环链表的定义和讲解。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，是单链表的进阶，比单链表的结点结构多出一个指向前驱的指针域，如下图所示：

循环链表是一种链式储存结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。方法是将尾结点中的指针域进行使用，指向首结点，如下图所示：

双向循环链表即是将上述二者联合起来使用，以达到完成各类工作的效用，在以后大多数链表结构的使用中，我们都会选择双向循环链表。

---

 一、双向循环链表

循环结构

 双向循环链表的循环方式是其尾结点的后继指针指向头结点(表头)，而头结点的前置指针指向尾结点，达到双向循环的目的，这样不仅使得对链表尾部的操作更为简单，也减少了对NULL指针的引用。

1.双向循环链表头文件及函数声明

新建头文件"dclist.h"(double circle list)对链表函数声明进行保存，方便我们后期查看及使用

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<ctype.h>
#include<stdlib.h>
 
typedef int Element;
 
typedef struct DNode
{
	Element data;
	DNode* next;
	DNode* prev;
}DNode, * PDNode;
 
//初始化链表
void InitList(PDNode plist);
 
//购买结点
PDNode BuyNode();
 
//头插
bool Push_Front(PDNode plist, Element val);
 
//尾插
bool Push_Back(PDNode plist, Element val);
 
//按位置插
bool Insert_Pos(PDNode plist, int pos, Element val);
 
//头删
bool Pop_Front(PDNode plist);
 
//尾删
bool Pop_Back(PDNode plist);
 
//按位置删
bool Erease_Pos(PDNode plist, int pos);
 
//按值删
bool Erease_Val(PDNode plist, Element val);
 
//查找  返回结点地址
PDNode Find(PDNode plist, Element val);
 
//判空
bool IsEmpty(PDNode plist);
 
//获取元素个数
int GetSize(PDNode plist);
 
//打印链表
void Print(PDNode plist);
 
//清空
void Clear(PDNode plist);
 
//销毁
void Destroy(PDNode plist);

 

2.初始化

在对使用链表进行数据的储存之前，我们需要进行链表的初始化

1.结点构造

如图所示，带双向循环链表的结点由三部分构成：

1.数据域

2.指针域1：指向后继结点的指针

3.指针域2：指向前置结点的指针

typedef int Element;//如此对数据类型进行改名操作，若要进行修改数据类型操作会更加方便
 
typedef struct DNode
{
	Element data;
	DNode* next;//后继指针
	DNode* prev;//前置指针
}DNode, * PDNode;

2.初始化函数

与单链表不同的是，在双向循环链表不存在数据时，头结点的指针域不置为NULL，其后继指针与前置指针都指向头结点本身，以形成最基础的循环形态：

//初始化链表
void InitList(PDNode plist)
{
	assert(plist != NULL);
	plist->next = plist->prev = plist;
}

3.结点申请

因为链表的结构特性，我们需要对结点进行多次申请，为了方便进行其他函数操作，并且为了优化代码，我们将结点的申请封装于一个函数

//购买结点
PDNode BuyNode()
{
	PDNode node = (PDNode)malloc(sizeof(DNode));
	if (node == NULL)
	{
		exit(1);
	}
	memset(node, 0, sizeof(*node));//将申请的结点内存重置，防止数据残留
	return node;
}

 4.数据插入

双向循环链表存在多个指针指向的断开和重新指向，我们在此先进行分析和讲解，如下图所示：

 

按照正常逻辑，我们再重新指定指针指向时，首先需要打破原有的指针指向，即上图中红叉部分，但实际编写程序中，我们会直接修改指针的指向，从而在代码中只会体现重新指向的过程。

在图中，已经标注出4个指针指向的修改，首先，我们应该对新申请的结点中指针(即图中34箭头的指向)进行指定，因为如果我们先对旧有指针进行修改，那么我们可能会丢失结点的地址信息，从而失去我们已经保存的数据。

其中指针具体的指向修改，我们不用太在意顺序，只需要记住先考虑新节点的指向，后修改旧结点的指向即可，下面的代码中，我们将采用4321的顺序：

1.按位置插入

我们先进行通用插入的实现：

//按位置插
bool Insert_Pos(PDNode plist, int pos, Element val)
{
	assert(plist != NULL);
    //判断插入位置是否合法
	if (pos < 0 || pos > GetSize(plist))
	{
		return false;
	}
	PDNode node = plist;//将结点指针定位至需要插入数据位置之前的结点
	for (int i = 0; i < pos; i++)
	{
		node = node->next;
	}
	PDNode newnode = BuyNode();//申请新节点 
	newnode->data = val;
    //以下为插入步骤
	newnode->next = node->next;//4
	newnode->prev = node;//3
	node->next->prev = newnode;//2
	node->next = newnode;//1
	return true;
}

2.尾插

因为表头的前置指针指向尾结点，所以我们不用像单链表一样进行遍历后才能尾插。

//尾插
bool Push_Back(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode newnode = BuyNode();
	newnode->data = val;
    //插入
	newnode->next = plist;//4
	newnode->prev = plist->prev;//3
    plist->prev = newnode;//2
	plist->prev->next = newnode;//1
	return true;
}

3.头插

直接调用按位置插入，插入位置为0

//头插
bool Push_Front(PDNode plist, Element val)
{
	assert(plist != NULL);
	return Insert_Pos(plist, 0, val);
}

 5.查找

查找与普通链表的查找基本相同，但是在while循环中的结束条件不同，以结点指针是否指向表头来判断

//查找  返回结点地址
PDNode Find(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode node = plist->next;
    //遍历链表查找与val 相同的值
	while (node != plist && node->data != val)
	{
		node = node->next;
	}
	if (plist == node)
	{
		return NULL;
	}
	return node;
}

 6.数据删除

双向循环链表的删除大致与单链表相同，但在两相隔结点的重新链接时需要连结两个指针，即被删除结点的前置结点的后继指针指向被删除结点的后继结点，而后继结点的前置指针指向前置结点

1.按位置删除

//按位置删
bool Erease_Pos(PDNode plist, int pos)
{
	assert(plist != NULL);
	if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist;
	for (int i = 0; i <= pos; i++)
	{
		delnode = delnode->next;
	}
    //重新连结
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

 2.按值删除

这里调用了查找函数，找到val值所在的结点

//按值删
bool Erease_Val(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode delnode = Find(plist, val);
	if (delnode == NULL)
	{
		return false;
	}
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

3.尾删 

同样的，因为表头的前置指针指向尾结点，则可以减少遍历链表所消耗的资源。

//尾删
bool Pop_Back(PDNode plist)
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist->prev;
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

4.头删 

直接调用按位置删除，删除位置为0

//头删
bool Pop_Front(PDNode plist)
{
	assert(plist != NULL);
	return Erease_Pos(plist, 0);
}

7.清空与销毁 

1.清空

这里我们使用比较简单的方法，一直头删即可，当然这里的尾删也可以使用，消耗资源相同。

//清空
void Clear(PDNode plist)
{
	assert(plist != NULL);
	while (!IsEmpty(plist))
	{
		Pop_Front(plist);
	}
}

2.销毁

调用清空函数，并使链表达到未初始化的状态。

//销毁
void Destroy(PDNode plist)
{
	Clear(plist);
	plist->next = plist->prev = NULL;
}

8.双向循环链表源文件及整体函数实现 

#include "dclist.h"
 
//初始化链表
void InitList(PDNode plist)
{
	assert(plist != NULL);
	plist->next = plist->prev = plist;
}
 
//购买结点
PDNode BuyNode()
{
	PDNode node = (PDNode)malloc(sizeof(DNode));
	if (node == NULL)
	{
		exit(1);
	}
	memset(node, 0, sizeof(*node));
	return node;
}
 
//头插
bool Push_Front(PDNode plist, Element val)
{
	assert(plist != NULL);
	return Insert_Pos(plist, 0, val);
}
 
//尾插
bool Push_Back(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode newnode = BuyNode();
	newnode->data = val;
	newnode->prev = plist->prev;
	newnode->next = plist;
	plist->prev->next = newnode;
	plist->prev = newnode;
	return true;
}
 
//按位置插
bool Insert_Pos(PDNode plist, int pos, Element val)
{
	assert(plist != NULL);
	if (pos < 0 || pos > GetSize(plist))
	{
		return false;
	}
	PDNode node = plist;
	for (int i = 0; i < pos; i++)
	{
		node = node->next;
	}
	PDNode newnode = BuyNode();
	newnode->data = val;
	newnode->next = node->next;
	newnode->prev = node;
	node->next->prev = newnode;
	node->next = newnode;
	return true;
}
 
//头删
bool Pop_Front(PDNode plist)
{
	assert(plist != NULL);
	return Erease_Pos(plist, 0);
}
 
//尾删
bool Pop_Back(PDNode plist)
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist->prev;
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}
 
//按位置删
bool Erease_Pos(PDNode plist, int pos)
{
	assert(plist != NULL);
	if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist;
	for (int i = 0; i <= pos; i++)
	{
		delnode = delnode->next;
	}
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}
 
//按值删
bool Erease_Val(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode delnode = Find(plist, val);
	if (delnode == NULL)
	{
		return false;
	}
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}
 
//查找  返回结点地址
PDNode Find(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode node = plist->next;
	while (node != plist && node->data != val)
	{
		node = node->next;
	}
	if (plist == node)
	{
		return NULL;
	}
	return node;
}
 
//判空
bool IsEmpty(PDNode plist)
{
	assert(plist != NULL);
	return (plist->next == plist->prev && plist->next == plist);
}
 
//获取元素个数
int GetSize(PDNode plist)
{
	assert(plist != NULL);
	PDNode node = plist->next;
	int count = 0;
	while (node != plist)
	{
		node = node->next;
		count++;
	}
	return count;
}
 
//打印链表
void Print(PDNode plist)
{
	assert(plist != NULL);
	PDNode node = plist->next;
	while (node != plist)
	{
		printf("%d ", node->data);
		node = node->next;
	}
	printf("\n");
}
 
//清空
void Clear(PDNode plist)
{
	assert(plist != NULL);
	while (!IsEmpty(plist))
	{
		Pop_Front(plist);
	}
}
 
//销毁
void Destroy(PDNode plist)
{
	Clear(plist);
	plist->next = plist->prev = NULL;
}

---

 

总结

以上为双向循环链表的实现和方法讲解，双向循环链表为比较常用的链表形式，学习并理解双向循环链表会方便以后的学习。