双向循环链表的实现

本文实现语言：c语言

上篇文章回顾

上几篇博客我们已经实现静态顺序表和动态顺序表的基本功能，在顺序表中存取表元素非常简单，但是插入和删除需要移动大量的数据（时间复杂度O(n) ）非常麻烦；因此今天我们来实现插入和删除都非常方便的链表。

其实链表分为好几类，如下；其中以不带头节点，不循环的单链表和带头节点，循环的双链表最为重要。

本文主要实现带头节点的双向循环链表的增，删，插，改等功能。

在实现代码前，有一个重要的问题需要讨论，就是传参问题，什么情况下我们需要传二级指针？

如果我们的形参是普通变量，在传递的时候，如果我们打算对普通变量进行修改，那么我们就需要传递变量的地址；如果我们不打算修改普通变量（比如只是查看一下内容），那么我们的形参传递数值就可以（此时形参是实参的一份临时copy）。

同样的，如果我们的形参是指针变量，如果我们打算修改这个指针变量，那么我们传递的时候就需要二级指针；否则传递一级指针就OK。

这个理论放到链表实现里就是说：我们在设计链表的时候会设计一个头指针pNode，这个头指针pNode会指向头结点（或者指向第一个有效结点），所以头指针里面存的就是头结点的地址。如果我们要修改头结点里面所保存的地址（比如初始化链表时，让头指针指向NULL；再比如头插的时候，头指针保存的地址会发生变化，变成新插入节点的地址）时，在设计函数的时候就需要传递二级指针；如果我们只是查看头指针指向的内容，这样并不会改变头指针本身保存的地址，此时传递一级指针就可以。

所以，一般销毁，初始化，头插等需要用到二级指针；查找，遍历等传递一级指针就OK。

代码：

#define _CRT_SECURE_NO_WARNINGS 1

//--------------------DoubleList.h---------------
//  #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int DataType;
typedef struct DListNode
{
	struct DListNode *next;
	struct DListNode *prev;
	DataType data;
}DListNode, *pDListNode, **ppDListNode;

void DListInit(ppDListNode pphead);//初始化
pDListNode CreatDListNode(DataType x);//创造一个节点
void DListPushFront(ppDListNode pphead, DataType data);//头插
void DListPushBack(ppDListNode pphead, DataType data);//尾插
void DListInsert(ppDListNode pphead, pDListNode pos, DataType data);//任意位置插入
void DListPopFront(ppDListNode pphead);//头删
void DListPopBack(ppDListNode pphead);//尾删
void DListErase(ppDListNode pphead, pDListNode pos);//任意位置删除
void DListRemove(ppDListNode pphead, DataType x);//删除遇到的第一个数
void DListRemoveAll(ppDListNode pphead, DataType x);//删除遇到的所有的数字
pDListNode DListFind(pDListNode phead, DataType x);//查x所在的节点位置
int DListSize(pDListNode phead);//算节点数
int DListEmpty(pDListNode phead);//判断是否为空
void DListClear(ppDListNode pphead);//清空
void DListDestory(ppDListNode pphead);//销毁
void DListPrint(const pDListNode phead);//打印

//-------------------DoubleList.c------------

//创造一个节点
pDListNode CreatDListNode(DataType x)
{
	pDListNode newNode = (pDListNode)malloc(sizeof(DListNode));
	assert(newNode);
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

//初始化
void DListInit(ppDListNode pphead)
{
	assert(pphead);
	int num = 0;
	*pphead = CreatDListNode(num);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
	return;
}

//头插
void DListPushFront(ppDListNode pphead, DataType data)
{
	assert(pphead);
	pDListNode newNode = CreatDListNode(data);
	pDListNode first = (*pphead)->next;

	(*pphead)->next = newNode;
	newNode->prev = *pphead;
	newNode->next = first;
	first->prev = newNode;
	return;
}

//尾插
void DListPushBack(ppDListNode pphead, DataType data)
{
	assert(pphead);
	pDListNode newNode = CreatDListNode(data);
	pDListNode end = (*pphead)->prev;

	end->next = newNode;
	newNode->prev = end;
	newNode->next = (*pphead);
	(*pphead)->prev = newNode;
}

//任意位置插入：1.创建一个以data为值的新节点newNode 2.在双链表上找到插入位置的前一个节点cur 3.newNode的next指向pos 4.newNode的prev指向cur 5.将pos的prev指向newNode 6.cur的next指向newNode
void DListInsert(ppDListNode pphead, pDListNode pos, DataType data)
{
	assert(pphead);
	assert(pos);

	pDListNode newNode = CreatDListNode(data);
	pDListNode cur = pos->prev;

	newNode->next = pos;
	newNode->prev = cur;
	pos->prev = newNode;
	cur->next = newNode;
}

//头删
void DListPopFront(ppDListNode pphead)
{
	assert(pphead);
	if (NULL == (*pphead)->next)
	{
		printf("链表为空，不可以删除\n");
		return;
	}

	pDListNode first = (*pphead)->next;
	pDListNode second = first->next;
	(*pphead)->next = second;
	second->prev = (*pphead);
	free(first);
	first = NULL;
}

//尾删
void DListPopBack(ppDListNode pphead)
{
	assert(pphead);
	if (NULL == (*pphead)->next)
	{
		printf("链表为空，不可以删除\n");
		return;
	}

	pDListNode end = (*pphead)->prev;
	pDListNode penultimate = end->prev;

	penultimate->next = (*pphead);
	(*pphead)->prev = penultimate;
	free(end);
	end = NULL;
}

//任意位置删除
void DListErase(ppDListNode pphead, pDListNode pos)
{
	assert(pphead);
	assert(pos);
	assert(pos != (*pphead));
	if (NULL == (*pphead)->next)
	{
		printf("链表为空，不可以删除\n");
		return;
	}

	pDListNode tmp1 = (pos)->prev;
	pDListNode tmp2 = pos->next;

	tmp1->next = tmp2;
	tmp2->prev = tmp1;

	free(pos);
	pos = NULL;

}

//查x所在的节点位置
pDListNode DListFind(pDListNode phead, DataType x)
{
	assert(phead);
	pDListNode cur = phead->next;

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

//删除遇到的第一个数
void DListRemove(ppDListNode pphead, DataType x)
{
	assert(pphead);
	pDListNode node = DListFind(*pphead, x);
	if ((NULL != node) && (node != *pphead))
	{
		DListErase(pphead, node);
	}
	else {
		printf("没有这个数字，无法删除\n");
	}
}

//删除遇到的所有的数字
void DListRemoveAll(ppDListNode pphead, DataType x)
{
	assert(pphead);
	pDListNode pos;
	
	while ((NULL != (pos = DListFind(*pphead, x))) && (pos != *pphead))
	{
	
		DListErase(pphead, pos);
		
	}
}

//算节点数
int DListSize(pDListNode phead)
{
	assert(phead);
	pDListNode node = phead->next;
	size_t num = 0;
	while (node != phead)
	{
		num++;
		node = node->next;
	}
	return num;//不算头结点
}

//判断是否为空
int DListEmpty(pDListNode phead)
{
	return phead->next == phead ? 0 : 1;
}

//清空
void DListClear(ppDListNode pphead)
{
	assert(pphead);
	pDListNode first = (*pphead)->next;
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);

	pDListNode cur = first;
	while (first != (*pphead))
	{		
		first = first->next;
		free(cur);
		cur = NULL;
	}
}

//销毁
void DListDestory(ppDListNode pphead)
{
	assert(pphead);
	DListClear(pphead);
	free(*pphead);
	*pphead = NULL;
}
//打印
void DListPrint(const pDListNode phead)
{
	assert(phead);
	pDListNode cur = phead->next;
	printf("链表内容为：%2d->", phead->data);
	while (cur != phead)
	{
		printf("%2d->", cur->data);
		cur = cur->next;
	}
	printf("%2d\n", phead->data);
}

//---------------------------test.c---------------------------
void Test()
{
	DListNode *list = NULL;
	DListInit(&list);
	DListPushFront(&list, 1);//头插
	DListPushFront(&list, 2);//头插
	DListPushFront(&list, 3);//头插
	DListPushFront(&list, 4);//头插
	DListPrint(list);
	DListPushBack(&list, 101);//尾插
	DListPushBack(&list, 102);//尾插
	DListPushBack(&list, 103);//尾插
	DListPushBack(&list, 104);//尾插
	DListPrint(list);
	DListInsert(&list, list->next, 100);//任意位置插
	DListPrint(list);
	DListErase(&list, list->next);//任意位置删

	DListPrint(list);
	int ret = DListSize(list);//算节点数
	printf("节点数%d\n", ret);
	int cur = DListEmpty(list);//判断是否为空
	if (cur == 0)
		printf("链表为空\n");
	else
		printf("链表不为空\n");
	DListInsert(&list, list->next->next, 1);//任意位置插
	DListPrint(list);
	DListInsert(&list, list->next->next->next->next, 1);//任意位置插
	DListPrint(list);
	DListPushBack(&list, 1);//尾插
	DListPushFront(&list, 1);//头插
	DListPrint(list);

	DListRemove(&list, 1);//删除x
	DListPrint(list);
	printf("hehe1\n");
	DListRemoveAll(&list, 1);//删除x
	printf("hehe2\n");
	DListPrint(list);

	DListClear(&list);//清空
	DListPrint(list);
	DListDestory(&list);//销毁
}


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

结果：