数据结构------双向带头循环链表_双向有头循环链表

目录

1.什么是双向带头循环链表？模型。

2.1 创建结点函数

2.2初始化

3.尾插实现

3.1图示

 3.2尾插

4.打印函数实现

4.1打印函数

5.思考为啥是一级指针

6.头插实现

6.2实现代码

6.3特殊情况

7.头删

7.1图解

7.2代码

7.3多删

8.尾删 

8.1上图

8.2代码 

 9.在任意（pos）位置的插入删除。

9.1 插入

 9.2尾插·头插的复用

9.3思考

9.4pos位置的删除

9.6思考 

10销毁

11.SList.h代码

 12.SList.c代码

---

1.什么是双向带头循环链表？模型。

上次写的链表是单向的，就是只去不会，但是我想让他有来有回所以叫单向，带头是创建一个哨兵位头结点，但不影响实际写的链表。循环我就不解释了。

上模型：

2.初始化链表

2.1 创建结点函数

ListNode* BuyListNode(SLTDateType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));  //开辟一个结点
	if (node == NULL)
	{
		perror("malloc:fault");
		exit(-1);
	}
	node->date = x;      //把值给这个结点
	node->next = NULL;   //	全都赋值
	node->prev = NULL;    //全都赋值
	return  node;
}

2.2初始化

//初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(-1);  //创建哨兵位，不一定取-1，想取啥取啥
	phead->next = phead;
	phead->prev = phead;
	//既然是循环，那它的头指向自己，尾指向自己
	return phead;
}

刚开始就一个头结点，所以要首尾都指向自身。

3.尾插实现

3.1图示

 3.2尾插

//尾插
void ListPushBack(ListNode* phead, SLTDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->prev;
	tail->next = newnode;  //把newnode给tail
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

最灵性的的是tail=phead->prev，所以首尾相连了。

要实现尾插，无非四步d3结点和newnode相连，phead和newnode相连。

4.打印函数实现

4.1打印函数

//打印函数
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

注意不打印头结点所以cur是phead->next; 判断条件是！=phead,因为这是一个循环，最后一个跟phead连着呢，所以不等于。

4.2尾插实现

5.思考为啥是一级指针

单链表是二级指针实现尾插的，为啥这个是一级指针？为啥能用一级指针？

当我们写单链表时，要实现尾插首先我们要找到尾，咱们一般都是定义一个一级指针并改变这个指针来找尾，但是循环链表就不需要了。因为它的尾和phead紧密相连（设cur是尾），cur->next就是头，所以不需要一级指针的改变，所以一级指针就可以应付了。

6.头插实现

6.1图解

是插在d1前面不是head前面。

6.2实现代码

//头插
void ListPushFront(ListNode* phead, SLTDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* next = phead->next;   //来记录d1的地址放止一会找不到。
	
	//还是四步链接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next=next;
	next->prev=newnode;
}

 注意：其实不加这个next也可以，为啥还要加，就看上面这个代码，如果先连接phead和newnode那d1的地址咱就找不到了，所以就只能先连接后边的，但是加上next就不用看顺序来

了。

6.3特殊情况

就只有一个头结点进行头插，那next就是phead了。

再看咱这代码加图，照样可以。把d1换成phead,一样。

7.头删

7.1图解

注意啊兄弟们，不是删除第一个，第一个是哨兵节点，d1才是实际上的第一个。

7.2代码

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
 
}

 cur->next是d2，把d2的地址给phead，所以是cur->next->prev。

7.3多删

如果五个数据删六次呢？

所以代码：

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
 
}

8.尾删 

8.1上图

双链表对尾删最友好的地方是不用遍历找尾，phead->prev就是尾。

8.2代码 

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //前车之鉴
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

 

 9.在任意（pos）位置的插入删除。

9.1 插入

//pos位置插
void ListInsert(ListNode* pos, SLTDateType x)
{   
	assert(pos);
	ListNode* prev = pos->prev;   //pos前面的那个结点
	ListNode* newnode = BuyListNode(x);
 
	//四步走
	prev->next=newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

 9.2尾插·头插的复用

9.3思考

为啥尾插是参数phead？

 d3是尾，要在d3那插入可不是尾插，在phead前插入不就是尾插吗？因为phead->prev必须指向链表的尾部。

9.4pos位置的删除

 9.5复用

9.6思考 

为啥尾插是phead,而尾删是phead->prev？

首先我们要理解进行尾插时，就是在pos前插入，那要找到pos位置，并在它前边插入，pos就是phead。

而进行尾删时也要找到pos，并删除pos，这个是删除pos位。所以是phead->prev。

10销毁

//销毁
void ListDestory(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

11.SList.h代码

#pragma once
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
 
typedef int SLTDateType;
 
typedef struct ListNode
{
	struct ListNode* prev;     //头
	struct ListNode* next;     //尾
	SLTDateType  date;
}ListNode;
 
 //初始化
ListNode* ListInit();
 
//打印
void ListPrint(ListNode* phead);
 
//开辟节点
ListNode* BuyListNode(SLTDateType x);
 
//尾插
void ListPushBack(ListNode* phead, SLTDateType x);
 
//头插
void ListPushFront(ListNode* phead, SLTDateType x);
 
//头删
void ListPopFront(ListNode* phead);
 
//尾删
void ListPopBack(ListNode* phead);
 
//pos位置插
void ListInsert(ListNode* pos, SLTDateType x);
 
//pos位置删除
void ListErase(ListNode* pos);
 
//销毁
void ListDestory(ListNode* phead);

 12.SList.c代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
 
ListNode* BuyListNode(SLTDateType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));  //开辟一个结点
	if (node == NULL)
	{
		perror("malloc:fault");
		exit(-1);
	}
	node->date = x;      //把值给这个结点
	node->next = NULL;   //	全都赋值
	node->prev = NULL;    //全都赋值
	return  node;
}
//初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(-1);  //创建哨兵位，不一定取-1，想取啥取啥
	phead->next = phead;
	phead->prev = phead;
	//既然是循环，那它的头指向自己，尾指向自己
	return phead;
}
 
//打印函数
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}
 
 
//尾插
void ListPushBack(ListNode* phead, SLTDateType x)
{
	assert(phead);
	ListInsert(phead, x);
	//ListNode* newnode = BuyListNode(x);
	//ListNode* tail = phead->prev;
	//tail->next = newnode;  //把newnode给tail
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;
}
 
 
//头插
void ListPushFront(ListNode* phead, SLTDateType x)
{
	assert(phead);
	ListInsert(phead->next, x);
	//ListNode* newnode = BuyListNode(x);
	//ListNode* next = phead->next;   //来记录d1的地址放止一会找不到。
	//
	还是四步链接
	//phead->next = newnode;
	//newnode->prev = phead;
	//newnode->next=next;
	//next->prev=newnode;
}
 
//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->next);
 
	/*ListNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);*/
 
}
 
//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //前车之鉴
	ListErase(phead->prev);
 
	/*ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;*/
}
 
//pos位置插
void ListInsert(ListNode* pos, SLTDateType x)
{   
	assert(pos);
	ListNode* prev = pos->prev;   //pos前面的那个结点
	ListNode* newnode = BuyListNode(x);
 
	//四步走
	prev->next=newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
 
//pos位置删除
void ListErase(ListNode* pos)
{
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
 
//销毁
void ListDestory(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}