常规实现带头双向循环链表

发布于：2022-11-10 ⋅ 阅读:(752) ⋅ 点赞:(0)

文章目录
        1.什么是带头双向循环链表

                a.结构

        2.各操作具体实现

                a.创建节点

                b.初始化

                c.打印

                d.销毁

                e.删除操作

                        (1).尾删

                        (2).头删

                        (3).删除指定pos位置的节点

                f.插入操作

                        (1).尾插

                        (2).头插

                        (3).在pos前插入

                g.查找

                h.判断空

                i.求链表长度

        3.总结           

1.什么是带头双向循环链表

        如图能够很清楚的表示这个结构，一个节点存储着一个数据元素，两个指针，一个为prev指针: 指向前一个节点，另一个为next指针: 指向下一个节点。带头就是头结点是个哨兵节点，一般不存储数据。双向就是头结点的prev指向尾结点，尾结点的next指向头结点。循环也容易理解，这里我就不一一阐述，看图容易看出来。

2.各操作具体实现

先创建一个头文件包含一下接口的声明和节点的定义  -  DList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once

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

typedef int LTDataType;//重命名数据类型，方便修改数据类型
typedef struct DoubleListNode
{
	struct DoubleListNode* next;
	LTDataType data;
	struct DoubleListNode* prev;
}LTNode;//重命名结构体

//初始化
LTNode* DListInit();

//打印
void DListPrint(LTNode* plist);

//销毁
void DListDestory(LTNode* plist);

//尾插
void DListPushBack(LTNode* plist, LTDataType x);

//尾删
void DListPopBack(LTNode* plist);

//头插
void DListPushFront(LTNode* plist, LTDataType x);

//头删
void DListPopFront(LTNode* plist);

//查找
LTNode* DListFind(LTNode* plist, LTDataType x);

//在pos的前面进行插入
void DListInsert(LTNode* pos, LTDataType x);

//删除pos位置的结点
void DListErase(LTNode* pos);

//判断空
bool DListEmpty(LTNode* plist);

//链表长度
size_t DListSize(LTNode* plist);

  a.创建节点

LTNode* BuyDListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);//退出程序
	}
	node->prev = NULL;
	node->data = x;
	node->next = NULL;

	return node;
}

  b.初始化

  先上代码，再解释说明

//初始化
LTNode* DListInit()
{
	LTNode* phead = BuyDListNode(-1);
	phead->next = phead;//指向自己
	phead->prev = phead;//指向自己-

	return phead;
}

那为什么是指向自己呢？而不是指向一个空呢？

那如果指向空的话，就失去了循环的意义，就变成了双向链表了。

 c.打印

这个停止的循环停止的条件为遍历的头结点时就停止，这个也好理解，因为只需打印到尾结点就行了，而尾结点的next指向头结点，头结点一般是不存储数据的。

//打印
void DListPrint(LTNode* plist)
{
	assert(plist);

	LTNode* cur = plist->next;

	while (cur != plist)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

d.销毁

这个也简单，每销毁一个节点前，先创建当前节点的下一个节点指针，再一个一个销毁

void DListDestory(LTNode* plist)
{
	assert(plist);

	LTNode* cur = plist->next;
	while (cur != plist)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

e.删除操作

(1).尾删

//尾删
void DListPopBack(LTNode* plist)
{
	assert(plist);
	assert(plist->next != plist);//只剩哨兵位时不能删

	LTNode* tail = plist->prev;//最后一个节点
	LTNode* tailPrev = tail->prev;//最后一个节点的前一个节点

	free(tail);
	//链接
	plist->prev = tailPrev;
	tailPrev->next = plist;
}

上图！也是蛮简单的~

 先定义两个指针，一个尾，一个尾的前一个 

1.先释放尾结点

2.再连接节点      a.头结点的prev指向尾的前一个   b.尾的next指向头结点  

这样尾的前一个就变成了新的尾结点。

 (2).头删

//头删
void DListPopFront(LTNode* plist)
{
	assert(plist);
	assert(plist->next != plist);//只剩哨兵位时不能删

	LTNode* first = plist->next;//哨兵后面的第一个节点
	LTNode* second = first->next;//哨兵后面的第二个节点

	free(first);
	
	//链接
	plist->next = second;
	second->prev = plist;
}

上图！也是蛮简单的~

 先定义两个指针，一个当前指针，一个当前的后一个

1.先释放当前结点

2.再连接节点      a.头结点的next指向当前的后一个   b.后一个的prev指向头结点

(3).删除指定pos位置的节点

//删除
void DListErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	free(pos);
	prev->next = next;
	next->prev = prev;
}

上图！也是蛮简单的~  

 先定义两个指针，一个pos的前一个指针，一个pos的后一个指针

1.先释放pos结点

2.再连接节点      a.头结点的next指向pos的后一个   b.后一个的prev指向头结点

当然这里头删和尾删也可以复用这操作，

头删：void DListPopFront(LTNode* plist->next)

尾删：void DListPopFront(LTNode* plist->prev)

f.插入操作

(1).尾插

//尾插
void DListPushBack(LTNode* plist, LTDataType x)
{
	assert(plist);
	LTNode* newNode = BuyDListNode(x);
	LTNode* tail = plist->prev;//最后一个节点

	//链接
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = plist;
	plist->prev = newNode;
}

  上图！也是蛮简单的~  

先创建一个新节点和一个尾结点指针

1.尾指针的next指向新节点

2.新节点的prev指向尾结点

3.新节点的next指向头结点

4.头结点next指向新节点

(2).头插

//头插
void DListPushFront(LTNode* plist, LTDataType x)
{
	assert(plist);

	LTNode* newnode = BuyDListNode(x);

	//链接
	newnode->next = plist->next;
	plist->next->prev = newnode;
	plist->next = newnode;
	newnode->prev = plist;
}

 上图！也是蛮简单的~  

 先创建一个新节点

1.新节点的next指向头结点的next，即指向d1节点

2.d1节点的prev指向新节点

3.头结点的next指向新节点

4.新节点prev指向头结点

(3).在pos前插入

//在pos的前面进行插入
void DListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = BuyDListNode(x);
	LTNode* prev = pos->prev;//pos的前一个

	//链接
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

上图！也是蛮简单的~  

       
先创建一个新节点和一个指向pos前一个的指针prev

1.prev的next指向新节点

2.新节点的prev指向prev

3.新节点的next指向pos

4.pos的prev指向新节点

当然这里头插和尾插也可以复用这操作

头插：void DListInsert(LTNode* pos->next, LTDataType x)

尾插：void DListInsert(LTNode* plist, LTDataType x)

g.查找

//查找
LTNode* DListFind(LTNode* plist, LTDataType x)
{
	assert(plist);

	LTNode* cur = plist->next;//当前节点
	//开始查找
	while(cur != plist)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

当然这里查找也可以进行修改的操作，即修改需查找的数据

h.判断空

//判空
bool DListEmpty(LTNode* plist)
{
	return plist->next == plist;
}

 i.求链表长度   

//长度
size_t DListSize(LTNode* plist)
{
	assert(plist);

	size_t size = 0;
	LTNode* cur = plist->next;
	while (cur != plist)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

DList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Dlist.h"

//打印
void DListPrint(LTNode* plist)
{
	assert(plist);

	LTNode* cur = plist->next;

	while (cur != plist)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//创建节点
LTNode* BuyDListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);//退出程序
	}
	node->prev = NULL;
	node->data = x;
	node->next = NULL;

	return node;
}

//初始化
LTNode* DListInit()
{
	LTNode* phead = BuyDListNode(-1);
	phead->next = phead;//指向自己
	phead->prev = phead;//指向自己-

	return phead;
}

//尾插
void DListPushBack(LTNode* plist, LTDataType x)
{
	assert(plist);
	LTNode* newNode = BuyDListNode(x);
	LTNode* tail = plist->prev;//最后一个节点

	//链接
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = plist;
	plist->prev = newNode;
}

//销毁
void DListDestory(LTNode* plist)
{
	assert(plist);

	LTNode* cur = plist->next;
	while (cur != plist)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

//尾删
void DListPopBack(LTNode* plist)
{
	assert(plist);
	assert(plist->next != plist);//只剩哨兵位时不能删

	LTNode* tail = plist->prev;//最后一个节点
	LTNode* tailPrev = tail->prev;//最后一个节点的前一个节点

	free(tail);
	//链接
	plist->prev = tailPrev;
	tailPrev->next = plist;
}

//头插
void DListPushFront(LTNode* plist, LTDataType x)
{
	assert(plist);

	LTNode* newnode = BuyDListNode(x);

	//链接
	newnode->next = plist->next;
	plist->next->prev = newnode;
	plist->next = newnode;
	newnode->prev = plist;

	//LTNode* first = plist->next;//哨兵后面的第一个节点
	//
	链接
	//plist->next = newnode;
	//newnode->prev = plist;
	//newnode->next = first;
	//first->prev = newnode;
}

//头删
void DListPopFront(LTNode* plist)
{
	assert(plist);
	assert(plist->next != plist);//只剩哨兵位时不能删

	LTNode* first = plist->next;//哨兵后面的第一个节点
	LTNode* second = first->next;//哨兵后面的第二个节点

	free(first);
	
	//链接
	plist->next = second;
	second->prev = plist;
}

//查找
LTNode* DListFind(LTNode* plist, LTDataType x)
{
	assert(plist);

	LTNode* cur = plist->next;//当前节点
	//开始查找
	while(cur != plist)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//在pos的前面进行插入
void DListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = BuyDListNode(x);
	LTNode* prev = pos->prev;//pos的前一个

	//链接
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

//删除
void DListErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	free(pos);
	prev->next = next;
	next->prev = prev;
}

//判空
bool DListEmpty(LTNode* plist)
{
	return plist->next == plist;
}

//长度
size_t DListSize(LTNode* plist)
{
	assert(plist);

	size_t size = 0;
	LTNode* cur = plist->next;
	while (cur != plist)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

test.c

void testPushBackAndPopBack()
{
	LTNode* phead = DListInit();
	DListPushBack(phead, 1);
	DListPrint(phead);
	DListPushBack(phead, 1);
	DListPrint(phead);
	DListPushBack(phead, 3);
	DListPrint(phead);
	DListPushBack(phead, 4);
	DListPrint(phead);
	DListPushBack(phead, 5);
	DListPrint(phead);

	printf("\n");

	DListPopBack(phead);
	DListPrint(phead);
	DListPopBack(phead);
	DListPrint(phead);
	DListPopBack(phead);
	DListPrint(phead);
	DListPopBack(phead);
	DListPrint(phead);
	DListPopBack(phead);
	DListPrint(phead);
	//DListPopBack(phead);
	//DListPrint(phead);
}

void testPushFrontAndPopFront()
{
	LTNode* phead = DListInit();
	DListPushFront(phead, 1);
	DListPushFront(phead, 2);
	DListPushFront(phead, 3);
	DListPushFront(phead, 4);
	DListPrint(phead);

	DListPopFront(phead);
	DListPopFront(phead);
	DListPopFront(phead);
	DListPopFront(phead);
	//DListPopFront(phead);
	DListPrint(phead);
}

void testFind()
{
	LTNode* phead = DListInit();
	DListPushFront(phead, 1);
	DListPushFront(phead, 2);
	DListPushFront(phead, 3);
	DListPushFront(phead, 4);
	DListPrint(phead);

	//修改找到的数据
	LTNode* pos = DListFind(phead, 2);
	if (pos)
		pos->data = 10;
	DListPrint(phead);
}

void testInsertAndErase()
{
	LTNode* phead = DListInit();
	DListPushFront(phead, 1);
	DListPushFront(phead, 2);
	DListPushFront(phead, 3);

	LTNode* pos = DListFind(phead, 2);

	//DListInsert(pos, 20);
	//DListPrint(phead);

	DListErase(pos);
	DListPrint(phead);
}

int main()
{
	//testPushBackAndPopBack();
	//testPushFrontAndPopFront();
	//testFind();
	testInsertAndErase();
}

3.总结   

都是蛮easy的~ 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布