初阶数据结构之带头+双向+循环链表增删查实现（三）

迈不过友情╰ 2023-10-09 23:51 1阅读 0赞

--------------------

### 文章目录  @\[TOC\](文章目录)  前言  一、带头双向循环链表的初始化  1.1带头双向循环链表的结构体定义  1.2初始化代码的实现  二、带头+双向+循环链表的增功能实现  2.1头插代码的实现  2.2尾插代码的实现  三、带头+双向+循环链表的打印功能实现  3.1打印代码的实现  四、带头+双向+循环链表删功能实现  4.1头删功能的实现  4.2尾删功能的实现  五、带头+双向+循环链表查功能实现  5.1查功能代码实现  六、最后的代码全过程实现  总结 ###

## 前言 ##

> 这篇文章主要讲的就是带头+双向+循环链表增删查改的实现

--------------------

## 一、带头双向循环链表的初始化 ##

### 1.1带头双向循环链表的结构体定义 ###

> 我们应该知道为什么他叫双向循环链表，因为他有两个指针，一个指向自己的next（也就是下一个），一个是prev（也就是自己的上一个），这样是不是就很方便了呢？对比单链表，单链表的删除就需要定义两个指针来删除，还得从头来删除，而带头双向循环链表就不用那么的麻烦啦。下面是结构体的代码描述

typedef int LTDatatype;
    typedef struct ListNode
    {
        
    	struct ListNode* next;
    	struct ListNode* prev;
    	LTDatatype data;
    }LNode;

### 1.2初始化代码的实现 ###

> 首先带头双向循环链表的初始化首先是有一个next，一个prev,这是什么呢？这是一个头指针，一个尾指针，初始化的话可以都先指向自己，如下图所示这就是初始化代码的由来啦。

![在这里插入图片描述][2bd81538ae694d7e807f3de689fef0e4.png]

LNode* LTInit()
    {
        
    	LNode* phead = BuyLTNode(-1);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }

> 我们会发现这里有一个BuyLTNode函数，这个函数是用来干什么的呢？这个函数是用来开辟一个新的节点的，那么具体是怎么实现的呢？这里我们用到了malloc函数用来动态开辟一个节点。

LNode* BuyLTNode(LTDatatype x)
    {
        
    	LNode* newnode = (LNode*)malloc(sizeof(LNode));
    	if (newnode == NULL)
    	{
        
    		perror("malloc fail");
    		return NULL;
    	}
    	newnode->data = x;
    	newnode->next = NULL;
    	newnode->prev = NULL;
    	return newnode;
    }

## 二、带头+双向+循环链表的增功能实现 ##

### 2.1头插代码的实现 ###

void LTPustFront(LNode* phead, LTDatatype x)
    {
        
    	assert(phead);
    	LNode* newnode = BuyLTNode(x);
    	LNode* first = phead->next;
    	phead->next = newnode;
    	newnode->prev = phead;
    	newnode->next = first;
    	first->prev = newnode;
    }

> 我们要进行带头双向循环链表的头插，那么我们应该怎么样头插呢？很多人会认为是在phead那一个指针进行头插，实则并不然，应该是在phead与p之间才是对的，那么我们应该怎么操作才能把我们newnode的节点头插进去呢？首先我们应该找到first，也就是phead->next,我们为什么要找到这一个节点呢？因为我们要在phead和p之间头插所以first这个节点我们必须得是知道的，而且找到这个节点也是有好处的，有什么好处呢？找到这个节点我们就能知道这个节点的位置，之后的操作也会方便很多。

![在这里插入图片描述][4b6a40392cbd4100a54103a988198b0a.png]![在这里插入图片描述][2ded5ce8e1414e1395e2eca300f74290.png]

> 先将cur定义出来，也就是LNode\* cur = phead->next;,其次在链接就行啦，phead->next = newnode,newnode->prev = phead,newnode->next = cur,cur->next = newnode;这里的p指针要根据图来链接哦！

### 2.2尾插代码的实现 ###

void LTPustBack(LNode* phead, LTDatatype x)
    {
        
    	assert(phead);
    	LNode* tail = phead->prev;
    	LNode* newnode = BuyLTNode(x);
    
    	tail->next = newnode;
    	newnode->prev = tail;
    	newnode->next = phead;
    	phead->prev = newnode;
    }

> 尾插：顾名思义就是在尾部插入，那么双向带头循环链表有啥优势呢？我们可以直接从头就可以找到尾，就不像单链表需要从头开始找了。如下图所示

这是未插入之前：  
![在这里插入图片描述][ea7364d0fa5f41a698dd9c672df3b9e6.png]  
这是插入之后：  
![在这里插入图片描述][914fcf1b73594eca97d91189ab2729ca.png]

> 该图把尾指针的next链接到newnode上，再把头指针的链接链到新开的newnode的节点上。这里我们还需要找到未插入之前的尾节点，那么我们应该怎么找到尾节点呢？LNode\* tail = phead->prev;这样我们是不是就能找到尾节点了呢？

## 三、带头+双向+循环链表的打印功能实现 ##

### 3.1打印代码的实现 ###

void LTPrint(LNode* phead)
    {
        
    	assert(phead);
    	LNode* cur = phead->next;
    	printf("phead<==>");
    	while (cur != phead)
    	{
        
    		printf("%d<==>", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }

> 因为我们是带有双向循环链表，我们的最后一个节点，会重新指向头结点，我们只需要把遍历的继续条件设为cur!=phead时就行啦。

## 四、带头+双向+循环链表删功能实现 ##

### 4.1头删功能的实现 ###

> 首先，我们应该怎么样进行头删呢？既然遇到解决不了的事情，我们选择画图来进行理解吧

![在这里插入图片描述][22722f531896417a9c77c5faac16bdef.png]

void LTPopFront(LNode* phead)
    {
        
    	assert(phead);
    	LNode* first = phead->next;
    	LNode* second = first->next;
    	phead->next = second;
    	second->prev = phead;
    	free(first);
    }

### 4.2尾删功能的实现 ###

![在这里插入图片描述][8656724e35f646d791dc02dbfb7c05eb.png]

void LTPopBack(LNode* phead)
    {
        
    	assert(phead);
    	LNode* tail = phead->prev;
    	LNode* tailprev = tail->prev;
    	free(tail);
    	phead->prev = tailprev;
    	tailprev->next = phead;
    }

## 五、带头+双向+循环链表查功能实现 ##

### 5.1查功能代码实现 ###

> 其实查找功能也就是遍历一遍所有的节点，找到我们想要的值，然后返回就行啦。

LNode* LTFind(LNode* phead, LTDatatype x)
    {
        
    	assert(phead);
    	LNode* cur = phead->next;
    	while (cur != phead)
    	{
        
    		if (cur->data == x)
    		{
        
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }

## 六、最后的代码全过程实现 ##

test.c

#define _CRT_SECURE_NO_WARNINGS 1
    #include "List.h"
    
    void TestList1()
    {
        
    	LNode* plist = LTInit();
    	LTPustBack(plist, 1);
    	LTPustBack(plist, 2);
    	LTPustBack(plist, 3);
    	LTPustBack(plist, 4);
    	LTPrint(plist);
    	
    	LTPopBack(plist);
    	LTPrint(plist);
    }
    
    void TestList2()
    {
        
    	LNode* plist = LTInit();
    	LTPustFront(plist, 1);
    	LTPustFront(plist, 2);
    	LTPustFront(plist, 3);
    	LTPustFront(plist, 4);
    	LTPrint(plist);
    
    	LTPopFront(plist);
    	LTPrint(plist);
    	LNode* pos = LTFind(plist, 3);
    	//LTInsert(pos, 4);
    	LTErase(pos);
    	LTPrint(plist);
    }
    
    int main()
    {
        
    	TestList2();
    	return 0;
    }

list.h

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    typedef int LTDatatype;
    typedef struct ListNode
    {
        
    	struct ListNode* next;
    	struct ListNode* prev;
    	LTDatatype data;
    }LNode;
    
    
    LNode* LTInit();
    void LTPustBack(LNode* phead, LTDatatype x);
    void LTPustFront(LNode* phead, LTDatatype x);
    void LTPopBack(LNode* phead);
    void LTPopFront(LNode* phead);
    void LTPrint(LNode* phead);
    
    void LTInsert(LNode* pos, LTDatatype x);
    LNode* LTFind(LNode* phead, LTDatatype x);
    void LTErase(LNode* pos);

list.c

#define _CRT_SECURE_NO_WARNINGS 1
    #include "List.h"
    
    LNode* BuyLTNode(LTDatatype x)
    {
        
    	LNode* newnode = (LNode*)malloc(sizeof(LNode));
    	if (newnode == NULL)
    	{
        
    		perror("malloc fail");
    		return NULL;
    	}
    	newnode->data = x;
    	newnode->next = NULL;
    	newnode->prev = NULL;
    	return newnode;
    }
    
    LNode* LTInit()
    {
        
    	LNode* phead = BuyLTNode(-1);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }
    
    void LTPustBack(LNode* phead, LTDatatype x)
    {
        
    	assert(phead);
    	LNode* tail = phead->prev;
    	LNode* newnode = BuyLTNode(x);
    
    	tail->next = newnode;
    	newnode->prev = tail;
    	newnode->next = phead;
    	phead->prev = newnode;
    }
    void LTPrint(LNode* phead)
    {
        
    	assert(phead);
    	LNode* cur = phead->next;
    	printf("phead<==>");
    	while (cur != phead)
    	{
        
    		printf("%d<==>", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    //void LTPustFront(LNode* phead, LTDatatype x)
    //{
        
    //	assert(phead);
    //	LNode* newnode = BuyLTNode(x);
    //	newnode->next = phead->next;
    //	phead->next->prev = newnode;
    //	phead->next = newnode;
    //	newnode->prev = phead;
    //
    //}
    void LTPustFront(LNode* phead, LTDatatype x)
    {
        
    	assert(phead);
    	LNode* newnode = BuyLTNode(x);
    	LNode* first = phead->next;
    	phead->next = newnode;
    	newnode->prev = phead;
    	newnode->next = first;
    	first->prev = newnode;
    }
    void LTPopBack(LNode* phead)
    {
        
    	assert(phead);
    	LNode* tail = phead->prev;
    	LNode* tailprev = tail->prev;
    	free(tail);
    	phead->prev = tailprev;
    	tailprev->next = phead;
    }
    
    void LTPopFront(LNode* phead)
    {
        
    	assert(phead);
    	LNode* first = phead->next;
    	LNode* second = first->next;
    	phead->next = second;
    	second->prev = phead;
    	free(first);
    }
    
    LNode* LTFind(LNode* phead, LTDatatype x)
    {
        
    	assert(phead);
    	LNode* cur = phead->next;
    	while (cur != phead)
    	{
        
    		if (cur->data == x)
    		{
        
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    void LTInsert(LNode* pos, LTDatatype x)
    {
        
    	assert(pos);
    	LNode* prev = pos->prev;
    	LNode* newnode = BuyLTNode(x);
    
    	prev->next = newnode;
    	newnode->prev = prev;
    	newnode->next = pos;
    	pos->prev = newnode;
    }
    
    void LTErase(LNode* pos)
    {
        
    	assert(pos);
    	LNode* tail = pos->next;
    	LNode* prev = pos->prev;
    	prev->next = tail;
    	tail->prev = prev;
    }

--------------------

## 总结 ##

> 今天带大家了解了数据结构的带头双向循环链表的增删查，其中该数据结构还有随机插入和随机删除我没讲解，大家有不懂的可以评论区留言啦！

[2bd81538ae694d7e807f3de689fef0e4.png]: https://img-blog.csdnimg.cn/2bd81538ae694d7e807f3de689fef0e4.png
[4b6a40392cbd4100a54103a988198b0a.png]: https://img-blog.csdnimg.cn/4b6a40392cbd4100a54103a988198b0a.png
[2ded5ce8e1414e1395e2eca300f74290.png]: https://img-blog.csdnimg.cn/2ded5ce8e1414e1395e2eca300f74290.png
[ea7364d0fa5f41a698dd9c672df3b9e6.png]: https://img-blog.csdnimg.cn/ea7364d0fa5f41a698dd9c672df3b9e6.png
[914fcf1b73594eca97d91189ab2729ca.png]: https://img-blog.csdnimg.cn/914fcf1b73594eca97d91189ab2729ca.png
[22722f531896417a9c77c5faac16bdef.png]: https://img-blog.csdnimg.cn/22722f531896417a9c77c5faac16bdef.png
[8656724e35f646d791dc02dbfb7c05eb.png]: https://img-blog.csdnimg.cn/8656724e35f646d791dc02dbfb7c05eb.png