? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?带头结点的双向循环链表

我之前对链表进行操作时一直是用头指针的方式，今天所说的链表是用头结点的方式。它们二者其实区别不是很大。共同点都是指向链表的第一个结点。不同点是：头结点的存储数据的内存里面可以存储链表信息，也可以什么都不存。而头指针只能用于指向链表第一个结点，它不能存储其它数据，因为它只有存储指针的内存。2.就是二者数据类型不同。头结点数据类型就是链表结点数据类型，而头指针数据类型是再次自定义的类型。

前面一直是对单链表进行操作。单链表有一个不足就是不能通过一个链表的结点来找到它的前一个结点。对此可以访问前一个结点的双向链表就此诞生。但还有一个问题就是如果查找最后一个结点时，时间复杂度将和单链表一样高都是O(n)，因此双向循环链表出生。

双向循环链表的出现使得以前单链表的尾插，尾删时间复杂度由O(n)变成了O(1)。

对比与单链表区别：

优点：1.通过任意一个结点可以访问到任意一个结点

? ? ? ? ? ?2.访问较后面结点时间复杂度降低

不足：由于双向循环所以增加了用于指向前一个的指针。在进行增加、删除结点操作时更加容易造成结点的丢失。（诱导人为原因）

OK，代码如下：

#include"BothwayHeadLinkList.h"

//1.初始化
void InitBCHLinkList(BCHLinkList* BCHptr)
{
	BCHptr->data = 0;
	BCHptr->prve = BCHptr;
	BCHptr->next = BCHptr;
}

//2.创建新结点
BCHLinkList* CreateBCHLinkList(DataType data)
{
	BCHLinkList* NewNode = (BCHLinkList*)malloc(sizeof(BCHLinkList));
	NewNode->data = data;
	NewNode->prve = NULL;
	NewNode->next = NULL;
	return NewNode;
}

//3.查找data
BCHLinkList* FindBCHLinkList(BCHLinkList* BCHptr, DataType data)
{
	assert(BCHptr);
	BCHLinkList* ptr = BCHptr->next;
	while (ptr != BCHptr)
	{
		if (ptr->data == data)
		{
			return ptr;
		}
		else
		{
			ptr = ptr->next;
		}
	}
	return NULL;
}

//4.插入结点
//4.1头插
void HeadAddBCHLinkList(BCHLinkList* BCHptr, DataType data)
{
	assert(BCHptr);
	BCHLinkList* NewNode = CreateBCHLinkList(data);
	NewNode->next = BCHptr->next;
	NewNode->prve = BCHptr;
	BCHptr->next->prve = NewNode;
	BCHptr->next = NewNode;
}

//4.2尾插
void WeiAddBCHLinkList(BCHLinkList* BCHptr, DataType data)
{
	assert(BCHptr);
	BCHLinkList* NewNode = CreateBCHLinkList(data);
	NewNode->next = BCHptr;
	NewNode->prve = BCHptr->prve;
	BCHptr->prve->next = NewNode;
	BCHptr->prve = NewNode;
}

//4.3任意结点前插入数据
void RenYiAddBCHLinkList(BCHLinkList* BCHptr, BCHLinkList* pos, DataType data)
{
	assert(BCHptr);
	BCHLinkList* NewNode = CreateBCHLinkList(data);
	NewNode->next = pos;
	NewNode->prve = pos->prve;
	pos->prve->next = NewNode;
	pos->prve = NewNode;
}

//5.删除结点
//5.1头删
void HeadDelBCHLinkList(BCHLinkList* BCHptr)
{
	assert(BCHptr);
	BCHLinkList*ptr = BCHptr->next;
	BCHptr->next = ptr->next;
	ptr->next->prve = BCHptr;
	free(ptr);
	ptr = NULL;
}

//5.2尾删
void WeiDelBCHLinkList(BCHLinkList* BCHptr)
{
	assert(BCHptr);
	BCHLinkList* ptr = BCHptr->prve;
	BCHptr->prve = ptr->prve;
	ptr->prve->next = BCHptr;
	free(ptr);
	ptr = NULL;
}

//5.3任意结点删除
void RenYiDelBCHLinkList(BCHLinkList* BCHptr, DataType data)
{
	assert(BCHptr);
	BCHLinkList* ptr = FindBCHLinkList(BCHptr, data);
	ptr->prve->next = ptr->next;
	ptr->next->prve = ptr->prve;
	free(ptr);
	ptr = NULL;
}

//6.修改结点数据
//data1源数据，data要保存的数据
void RenYiXiuGaiBCHLinkList(BCHLinkList* BCHptr, DataType data1, DataType data)
{
	assert(BCHptr);
	BCHLinkList* ptr = FindBCHLinkList(BCHptr, data1);
	ptr->data = data;
}

//7.打印双向循环链表
void PrintBCHLinkList(BCHLinkList* BCHptr)
{
	assert(BCHptr);
	BCHLinkList* ptr=BCHptr->next;
	if (ptr->next == BCHptr)
	{
		printf("空链表\n");
		return;
	}
	else
	{
		while (ptr != BCHptr)
		{
			printf("-> %d <-", ptr->data);
			ptr = ptr->next;
		}
		printf("\n");
	}
}

//8.销毁链表
void DestoryBCHLinkList(BCHLinkList* BCHptr)
{
	assert(BCHptr);
	while (BCHptr->next != BCHptr)
	{
		HeadDelBCHLinkList(BCHptr);
	}
}

#pragma once

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


//双向循环带头结点链表

//定义链表数据类型
#define DataType int

//定义链表结点
typedef struct BCHLinkList
{
	DataType data;
	struct BCHLinkList* prve;
	struct BCHLinkList* next;
}BCHLinkList;

//1.初始化
void InitBCHLinkList(BCHLinkList* BCHptr);

//2.创建新结点
BCHLinkList* CreateBCHLinkList(DataType data);

//3.查找data
BCHLinkList* FindBCHLinkList(BCHLinkList* BCHptr, DataType data);

//4.插入结点
//4.1头插
void HeadAddBCHLinkList(BCHLinkList* BCHptr, DataType data);

//4.2尾插
void WeiAddBCHLinkList(BCHLinkList* BCHptr, DataType data);

//4.3任意结点后插入数据
void RenYiAddBCHLinkList(BCHLinkList* BCHptr, BCHLinkList* pos, DataType data);

//5.删除结点
//5.1头删
void HeadDelBCHLinkList(BCHLinkList* BCHptr);

//5.2尾删
void WeiDelBCHLinkList(BCHLinkList* BCHptr);

//5.3任意结点删除
void RenYiDelBCHLinkList(BCHLinkList* BCHptr, DataType data);

//6.修改结点数据
void RenYiXiuGaiBCHLinkList(BCHLinkList* BCHptr, DataType data1, DataType data);

//7.打印双向循环链表
void PrintBCHLinkList(BCHLinkList* BCHptr);

//8.销毁链表
void DestoryBCHLinkList(BCHLinkList* BCHptr);

#include"BothwayHeadLinkList.h"

void Test()
{
	BCHLinkList* Head = (BCHLinkList*)malloc(sizeof(BCHLinkList));
	InitBCHLinkList(Head);
	//头插
	HeadAddBCHLinkList(Head, 8);
	HeadAddBCHLinkList(Head, 7);
	HeadAddBCHLinkList(Head, 6);
	HeadAddBCHLinkList(Head, 5);
	PrintBCHLinkList(Head);

	//尾插
	WeiAddBCHLinkList(Head, 10);
	WeiAddBCHLinkList(Head, 11);
	PrintBCHLinkList(Head);

	//在中间插入
	BCHLinkList* pos = FindBCHLinkList(Head, 5);
	RenYiAddBCHLinkList(Head, pos, 2);
	PrintBCHLinkList(Head);

	//头删
	HeadDelBCHLinkList(Head);
	PrintBCHLinkList(Head);

	//尾删
	WeiDelBCHLinkList(Head);
	PrintBCHLinkList(Head);

	//删除任意结点
	RenYiDelBCHLinkList(Head, 10);
	PrintBCHLinkList(Head);

	//修改结点数据
	RenYiXiuGaiBCHLinkList(Head, 5, 1);
	PrintBCHLinkList(Head);

	//销毁链表
	DestoryBCHLinkList(Head);
	PrintBCHLinkList(Head);
}

int main()
{
	Test();
	system("pause");
	return 0;
}

结果显示：?

-> 5 <--> 6 <--> 7 <--> 8 <-
-> 5 <--> 6 <--> 7 <--> 8 <--> 10 <--> 11 <-
-> 2 <--> 5 <--> 6 <--> 7 <--> 8 <--> 10 <--> 11 <-
-> 5 <--> 6 <--> 7 <--> 8 <--> 10 <--> 11 <-
-> 5 <--> 6 <--> 7 <--> 8 <--> 10 <-
-> 5 <--> 6 <--> 7 <--> 8 <-
-> 1 <--> 6 <--> 7 <--> 8 <-
空链表
请按任意键继续. . .

最后再说一下链表和顺序表的区别：

顺序表：

? ? ? ? ? 优点：1.支持随机访问，并且存储空间是连续的

? ? ? ? ? 不足：1.在对顺序表前面进行增加，删除时，时间复杂度相对较大为O(n)

? ? ? ? ? ? ? ? ? ? ?2.如果为动态顺表时，扩容代价比较大

链表：

? ? ? ? ? 优点：1.任意位置插入，删除的时间复杂度都为O(1)

? ? ? ? ? ? ? ? ? ? ?2.没有扩容问题（搬移数据的问题）

? ? ? ? ? 不足：1.以节点为单位进行存储

? ? ? ? ? ? ? ? ? ? ?2.不支持随机访问

特别注意：双向（循环）链表虽然可以通过一个结点可以访问链表任意一个结点，但它和顺序表访问方式不同。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码