数据结构——双向循环链表的结构与实现(C语言)

╰半橙微兮° 2023-01-05 12:25 81阅读 0赞

### C语言实现带头双向循环链表 ###

*  一、双向链表的结构与实现
 *   *  1.1 带头双向循环链表
     *  1.2 带头双向循环链表的实现
 *  二、双向链表的接口实现
 *   *  2.1 创建双向链表
     *  2.2 双向链表销毁
     *  2.3 双向链表在pos的前面进行插入
     *  2.4 双向链表删除pos位置的节点
     *  2.5 双向链表打印
     *  2.5 双向链表尾插
     *  2.6 双向链表尾删
     *  2.7 双向链表头插
     *  2.8 双向链表头删
     *  2.9 双向链表查找
 *  三、代码清单
 *   *  3.1 List.h
     *  3.2 List.c
     *  3.3 test.c
 *  四、测试结果

# 一、双向链表的结构与实现 #

## 1.1 带头双向循环链表 ##

> **结构最复杂**，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

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

## 1.2 带头双向循环链表的实现 ##

// 带头+双向+循环链表增删查改实现
    typedef int LTDataType;
    typedef struct ListNode
    {
        
    	LTDataType _data;			
    	struct ListNode* _next;	
    	struct ListNode* _prev;
    }ListNode;

# 二、双向链表的接口实现 #

## 2.1 创建双向链表 ##

创建头节点，申请空间，newNode->\_next = newNode->\_prev = newNode;  
![在这里插入图片描述][20210112092618361.png]

ListNode* BuyNode(LTDataType x)
    {
        
    	ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
    	newNode->_data = x;
    	newNode->_next = newNode->_prev = NULL;
    	return newNode;
    
    }
    
    // 创建返回链表的头结点.
    ListNode* ListCreate()
    {
        
    	ListNode* Head = BuyNode(0);
    	Head->_next = Head->_prev = Head;
    	return Head;
    }

## 2.2 双向链表销毁 ##

//双向链表的清除，保留头节点
    void ListClear(ListNode* pHead)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->_next;
    	//遍历每个节点并释放
    	while (cur != pHead)
    	{
        
    		ListNode* next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	pHead->_next = pHead->_prev = pHead;
    }
    
    // 双向链表销毁
    void ListDestory(ListNode** ppHead)
    {
        
    	assert(*ppHead);
    	ListClear(*ppHead);
    	free(*ppHead);
    	*ppHead = NULL;
    }

## 2.3 双向链表在pos的前面进行插入 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

// 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
        
    	assert(pos);
    
    	ListNode* prev = pos->_prev;	//pos的前一个结点
    	ListNode* newNode = BuyNode(x);
    	newNode->_prev = prev;	//1.
    	prev->_next = newNode;	//2.
    	pos->_prev = newNode;	//3.
    	newNode->_next = pos;	//4.
    
    
    }

## 2.4 双向链表删除pos位置的节点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]

// 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
        
    	assert(pos);
    
    	ListNode* prev = pos->_prev;	//pos的前一个结点
    	ListNode* next = pos->_next;	//pos的后一个节点
    	
    	free(pos);
    	prev->_next = next;	//1.
    	next->_prev = prev;	//2.
    
    }

## 2.5 双向链表打印 ##

// 双向链表打印
    void ListPrint(ListNode* pHead)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->_next;
    	
    	遍历每个节点并打印
    	while (cur != pHead)
    	{
        
    		ListNode* next = cur->_next;	//next指向下一个节点
    		printf("%d ", cur->_data);	//打印当前节点
    		cur = next;		//cur指向下一个节点
    	}
    	printf("\n");
    
    }

## 2.5 双向链表尾插 ##

![在这里插入图片描述][20210112094934251.png]  
**尾插其实就是在头节点的前面插入节点**，因此直接调用前面写好的接口，也可以自己逐步实现

// 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListInsert(pHead, x);
    
    	//ListNode* tail = pHead->_prev;	//找到尾节点
    	//ListNode* newNode = BuyNode(x);	//创建一个新节点
    	//tail->_next = newNode;	//1.
    	//newNode->_prev = tail;	//2.
    	//newNode->_next = pHead;	//3.
    	//pHead->_prev = newNode;	//4.
    }

## 2.6 双向链表尾删 ##

尾删就是删除双向链表的最后一个结点，删除的位置也就是头节点的前一个结点

// 双向链表尾删
    void ListPopBack(ListNode* pHead)
    {
        
    	assert(pHead);
    
    	ListErase(pHead->_prev);
    
    	//ListNode* tail = pHead->_prev;	//找到尾节点
    	//if (tail == pHead)	//只有头节点说明双向链表为空，直接返回
    	//{
        
    	//	return;
    	//}
    	//ListNode* prev = tail->_prev;	//尾节点的前一个节点，即新的尾节点
    	//free(tail);		//释放尾节点
    	//prev->_next = pHead;	//1.新的尾节点next指向head
    	//pHead->_prev = prev;	//2.head的prev指向新的尾节点
    }

## 2.7 双向链表头插 ##

头插是在头节点的后面插入

// 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListInsert(pHead->_next, x);
    
    
    }

## 2.8 双向链表头删 ##

头删是删除头结点后面的元素

// 双向链表头删
    void ListPopFront(ListNode* pHead)
    {
        
    	assert(pHead);
    	
    	ListErase(pHead->_next);
    
    
    }

## 2.9 双向链表查找 ##

// 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->_next;
    	while (cur != pHead)
    	{
        
    		ListNode* next = cur->_next;
    		if (cur->_data == x)
    		{
        
    			return cur;
    		}
    		cur = next;
    	}
    	return NULL;
    }

# 三、代码清单 #

## 3.1 List.h ##

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<windows.h>
    
    // 带头+双向+循环链表增删查改实现
    typedef int LTDataType;
    typedef struct ListNode
    {
        
    	LTDataType _data;			
    	struct ListNode* _next;	
    	struct ListNode* _prev;
    }ListNode;
    
    // 创建返回链表的头结点.
    ListNode* ListCreate();
    // 双向链表销毁
    void ListClear(ListNode* pHead);
    void ListDestory(ListNode** ppHead);
    // 双向链表打印
    void ListPrint(ListNode* pHead);
    // 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x);
    // 双向链表尾删
    void ListPopBack(ListNode* pHead);
    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x);
    // 双向链表头删
    void ListPopFront(ListNode* pHead);
    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x);
    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x);
    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos);

## 3.2 List.c ##

#include "List.h"
    
    
    ListNode* BuyNode(LTDataType x)
    {
        
    	ListNode* newNode = (ListNode *)malloc(sizeof(ListNode));
    	newNode->_data = x;
    	newNode->_next = newNode->_prev = NULL;
    	return newNode;
    
    }
    
    // 创建返回链表的头结点.
    ListNode* ListCreate()
    {
        
    	ListNode* Head = BuyNode(0);
    	Head->_next = Head->_prev = Head;
    	return Head;
    }
    
    
    //双向链表的清除，保留头节点
    void ListClear(ListNode* pHead)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->_next;
    	//遍历每个节点并释放
    	while (cur != pHead)
    	{
        
    		ListNode* next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	pHead->_next = pHead->_prev = pHead;
    }
    
    // 双向链表销毁
    void ListDestory(ListNode** ppHead)
    {
        
    	assert(*ppHead);
    	ListClear(*ppHead);
    	free(*ppHead);
    	*ppHead = NULL;
    }
    
    // 双向链表打印
    void ListPrint(ListNode* pHead)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->_next;
    	
    	遍历每个节点并打印
    	while (cur != pHead)
    	{
        
    		ListNode* next = cur->_next;	//next指向下一个节点
    		printf("%d ", cur->_data);	//打印当前节点
    		cur = next;		//cur指向下一个节点
    	}
    	printf("\n");
    
    }
    // 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListInsert(pHead, x);
    
    	//ListNode* tail = pHead->_prev;	//找到尾节点
    	//ListNode* newNode = BuyNode(x);	//创建一个新节点
    	//tail->_next = newNode;	//1.
    	//newNode->_prev = tail;	//2.
    	//newNode->_next = pHead;	//3.
    	//pHead->_prev = newNode;	//4.
    }
    // 双向链表尾删
    void ListPopBack(ListNode* pHead)
    {
        
    	assert(pHead);
    
    	ListErase(pHead->_prev);
    
    	//ListNode* tail = pHead->_prev;	//找到尾节点
    	//if (tail == pHead)	//只有头节点说明双向链表为空，直接返回
    	//{
        
    	//	return;
    	//}
    	//ListNode* prev = tail->_prev;	//尾节点的前一个节点，即新的尾节点
    	//free(tail);		//释放尾节点
    	//prev->_next = pHead;	//1.新的尾节点next指向head
    	//pHead->_prev = prev;	//2.head的prev指向新的尾节点
    }
    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListInsert(pHead->_next, x);
    
    
    }
    // 双向链表头删
    void ListPopFront(ListNode* pHead)
    {
        
    	assert(pHead);
    	
    	ListErase(pHead->_next);
    
    
    }
    
    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
        
    	assert(pHead);
    
    	ListNode* cur = pHead->_next;
    	while (cur != pHead)
    	{
        
    		ListNode* next = cur->_next;
    		if (cur->_data == x)
    		{
        
    			return cur;
    		}
    		cur = next;
    	}
    	return NULL;
    }
    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
        
    	assert(pos);
    
    	ListNode* prev = pos->_prev;	//pos的前一个结点
    	ListNode* newNode = BuyNode(x);
    	newNode->_prev = prev;	//1.
    	prev->_next = newNode;	//2.
    	pos->_prev = newNode;	//3.
    	newNode->_next = pos;	//4.
    
    
    }
    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos)
    {
        
    	assert(pos);
    
    	ListNode* prev = pos->_prev;	//pos的前一个结点
    	ListNode* next = pos->_next;	//pos的后一个节点
    	
    	free(pos);
    	prev->_next = next;	//1.
    	next->_prev = prev;	//2.
    
    }

## 3.3 test.c ##

#include"List.h"
    
    void TestList()
    {
        
    	ListNode *p;
    	p = ListCreate();
    	ListPushFront(p, 5);
    	ListPushFront(p, 4);
    	ListPushFront(p, 3);
    	ListPushFront(p, 2);
    	ListPushFront(p, 1);
    	ListPrint(p);
    
    	ListPopFront(p);
    	ListPopFront(p);
    	ListPopFront(p);
    	ListPopFront(p);
    	ListPopFront(p);
    	ListPrint(p);
    
    	ListPushBack(p, 1);
    	ListPushBack(p, 2);
    	ListPushBack(p, 3);
    	ListPushBack(p, 4);
    	ListPushBack(p, 5);
    	ListPrint(p);
    
    	ListPopBack(p);
    	ListPopBack(p);
    	ListPopBack(p);
    	ListPopBack(p);
    	ListPopBack(p);
    	ListPrint(p);
    
    
    	//ListDestory(&p);
    
    	ListPushFront(p, 5);
    	ListPushFront(p, 4);
    	ListPushFront(p, 3);
    	ListPushFront(p, 2);
    	ListPushFront(p, 1);
    	ListPrint(p);
    
    	ListNode* pos = ListFind(p, 3);
    	pos->_data = 30;
    	ListPrint(p);
    
    	ListInsert(pos, 33);
    	ListPrint(p);
    	ListErase(pos);
    	ListPrint(p);
    
    	ListDestory(&p);
    }
    
    int main()
    {
        
    	TestList();
    	system("pause");
    	return 0;
    }

# 四、测试结果 #

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

[2021011209131052.png]: /images/20221119/cca44174c1ac44b791a1d0f8092ab02d.png
[20210112092618361.png]: https://img-blog.csdnimg.cn/20210112092618361.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210112142853149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210112143546527.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy,size_16,color_FFFFFF,t_70
[20210112094934251.png]: https://img-blog.csdnimg.cn/20210112094934251.png
[20210112144154735.png]: https://img-blog.csdnimg.cn/20210112144154735.png