线性表之双向带头循环链表

准备工作：

创建结构体指针

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

1.创建一个新的节点

基本思路：malloc节点，判断节点是否创造成功。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态开辟节点
	if (newnode == NULL)//判断是否malloc成功
	{
		printf("malloc fail\n");
		exit(-1);//退出程序
	}
	newnode->data = x;//初始化
	newnode->next = NULL;//置空
	newnode->prev = NULL;//置空
	return newnode;
}

2.尾插

基本思路：1）创建一个新节点

2）找到尾节点，链接即可

画图：

代码：

void LTNodePushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	//创建一个新节点
	LTNode* newnode = BuyLTNode(x);
	//链接节点
	LTNode* tail = phead->prev;//找尾节点
	tail->next = newnode;
	newnode->prev = tail;
 
	newnode->next = phead;
	phead->prev = newnode;
}

3.头插

基本思路：1）创建一个新节点

2）找到第一个节点，链接节点

画图：

代码：

void LTNodePushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;//找到第一个节点
	//链接
	newnode->next = first;
	first->prev = newnode;
 
	phead->next = newnode;
	newnode->prev = phead;
}

3.打印链表

基本思路：1）断言

2）创立cur节点，指向第一个节点

3）当cur == phead时，一轮结束。

画图：

代码：

void LTNodePrint(LTNode* phead)
{
	LTNode* cur = phead->next;//一般情况下，不允许动头节点
	while (cur != phead)//当指向phead时，循环结束
	{
		printf("%d ", cur->data);
		cur = cur->next;//更新cur
	}
	printf("\n\n");
}

4.尾删

基本思路：1）断言

2）找到尾节点和倒数第二个节点，链接phead与tailPrev，free节点

画图：

代码：

void LTNPopBack(LTNode* phead)
{
	//断言
	assert(phead);
	//找到尾节点和第二个尾节点
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//释放尾节点
	free(tail);
	tail = NULL;
	//新的链接
	tailPrev->next = phead;
	phead->prev = tailPrev;
 
}

 

5.头删

基本思路：1）断言

2）找到第一个和第二个节点，链接phead和第二个节点，free第一个节点

画图：

代码：

void LTNPopFront(LTNode* phead)
{
	//断言
	assert(phead);
	//找到第一个节点和第二个节点
	LTNode* first = phead->next;
	LTNode* second = first->next;
	//释放内存
	free(first);
	first = NULL;
	//链接
	phead->next = second;
	second->prev = phead;
}

 

6.找到pos的值

基本思路：1）断言

2）遍历链表，找到就返回链表，找不到就返回NULL

代码：

LTNode* LTNFind(LTNode* phead, LTDataType x)
{
	//断言
	assert(phead);
	//创立一个节点
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			//找到返回节点
			return cur;
		}
		cur = cur->next;
	}
	//找不到，返回NULL
	return NULL;
}

7.在pos前插入新节点

基本思路：1）断言

2）创建一个新的节点，找到pos前的节点

3）链接newnode pos和pos的前一个

画图：

代码：

void LTNInsert(LTNode* pos, LTDataType x)
{
	//断言
	assert(pos);
	//找到pos的前一个节点
	LTNode* prev = pos->prev;
	//创建一个新节点
	LTNode* newnode = BuyLTNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;
 
	newnode->next = pos;
	pos->prev = newnode;
}

 

8.删除pos节点

基本思路：1）断言

2）创建pos前后两个节点，链接，free掉pos节点

画图：

代码：

void LTNErase(LTNode* pos)
{
	//断言
	assert(pos);
	//创建pos对应前后的节点
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//释放节点
	free(pos);
	pos = NULL;
	//链接
	prev->next = next;
	next->prev = prev;
}

9.销毁链表

基本思路：1）断言

2）创建cur指针记录

3）循环一次，一个节点一个节点释放。

4）phead最后释放，并置空。

代码：

void LTNDestroy(LTNode* phead)
{
	//断言
	assert(phead);
	//创建cur指针
	LTNode* cur = phead->prev;
	//循环
	while (cur != phead)
	{
		//记录下一个节点
		LTNode* next = cur->next;
		free(cur);
		//更新
		cur = next;
	}
	//释放并置空
	free(phead);
	phead = NULL;
}

头文件：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
 
//双向带头循环链表
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
//尾插
void LTNodePushBack(LTNode* phead, LTDataType x);
 
LTNode* BuyLTNode(LTDataType x);
void LTNodePrint(LTNode* phead);
 
LTNode* LTNodeInit();
//头插
void LTNodePushFront(LTNode* phead, LTDataType x);
 
//尾删
void LTNPopBack(LTNode* phead);
 
//头删
 
void LTNPopFront(LTNode* phead);
 
//查找
 
LTNode* LTNFind(LTNode* phead, LTDataType x);
//在pos前面插入
void LTNInsert(LTNode* pos, LTDataType x);
 
//删除pos位置对应的值
 
void LTNErase(LTNode* pos);
 
//销毁链表
void LTNDestroy(LTNode* phead);