带头+双向+循环链表的实现

2024-06-14 21:52
文章标签 实现 链表 双向 循环 带头

本文主要是介绍带头+双向+循环链表的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 1. 链表
    • 1.1 带头双向循环链表
  • 2. 链表的实现
    • 2.1 结构体
    • 2.2 初始化
    • 2.3 打印
    • 2.4 判断空不能删
    • 2.5 尾插
    • 2.6 头插
    • 2.7 尾删
    • 2.8 头删
    • 2.9 查找
    • 2.10 在pos之前插入
    • 2.11 删除pos位置的值
    • 2. 12 销毁
    • 2.13 创建节点
  • 3. test主函数
  • 4. List.c文件
  • 5. List.h文件

1. 链表

1.1 带头双向循环链表

在这里插入图片描述
双向带头循环链表（Doubly Linked Circular List）是一种特殊的链表结构，其中每个节点都包含两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。与普通双向链表不同，双向带头循环链表的第一个节点（通常称为头节点）的 prev 指针指向链表的最后一个节点，而最后一个节点的 next 指针则指向头节点，形成一个闭环。头节点不存储数据，只用于方便操作。

以下是双向带头循环链表的一些主要特点：

  • 循环性：链表的最后一个节点的 next 指针指向头节点，头节点的 prev 指针指向最后一个节点，形成一个闭环。
  • 带头节点：链表包含一个不存储数据的头节点，其 prev 指针指向最后一个节点，next 指针指向第一个数据节点。头节点的存在可以简化一些操作，如插入和删除节点。
  • 双向性：每个节点都有两个指针，一个指向前一个节点，另一个指向后一个节点。这使得在链表中向前和向后遍历都非常容易。

双向带头循环链表的基本操作包括：

  • 初始化：创建一个头节点，并设置其 prev 和 next 指针都指向自己。
  • 插入节点：在指定位置插入新节点，并更新相邻节点的指针。
  • 删除节点：删除指定节点，并更新相邻节点的指针。
  • 遍历：从头节点开始，可以向前或向后遍历整个链表。
    这种链表结构常用于需要频繁在链表中进行插入和删除操作的场景，因为双向结构使得查找和更新节点的前后指针都非常高效。而循环性则避免了处理边界条件的复杂性。头节点的存在进一步简化了这些操作。

2. 链表的实现

2.1 结构体

首先要先把结构体定义出来，因为是带头双向循环链表，所以要有两个指针域一个指向头，一个指向尾，还要有一个数据域。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//头指针struct ListNode* next;//尾指针LTDataType data;//数据域
}LTNode;

2.2 初始化

初始化链表，防止都是随机值。

//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

2.3 打印

这个就得注意点了，只能是cur != phead不能是cur->next != phead，这样的话链表的最后一个就不能打印出来，少了一个。

//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

2.4 判断空不能删

当只有头节点的时候再删就出问题了。

//判断空不能删
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2.5 尾插

只有找到phead->prev就是尾，所以实现起来也比较简单，只要改变4个指针的指向就可以了。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = newnode;*/LTInsert(phead->prev, x);
}

测试代码：

//尾插测试
void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.6 头插

因为是带哨兵位的，要找到phead->next这就是我们要头插的位置。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = tail;tail->prev = newnode;*/LTInsert(phead->next, x);
}

测试代码：

//头插测试
void TestList2()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.7 尾删

跟尾插是一样的，改4个指针的指向，再free掉。

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* cur = phead->prev;LTNode* tail = cur->prev;free(cur);tail->next = phead;phead->prev = tail;*/LTErase(phead->next);
}

测试代码：

//尾删测试
void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.8 头删

哨兵位的next就是当前的头，改指针的指向。

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* next = phead->next;LTNode* tail = next->next;free(next);phead->next = tail;tail->prev = phead;*/LTErase(phead->prev);
}

测试代码：

//头删测试
void TestList4()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.9 查找

尽量不要动头指针，最好是用一个指针记录下来，不然找不到头指针，再去遍历。

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.10 在pos之前插入

//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

3之前插入40测试代码：

void TestList8()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2.11 删除pos位置的值

//删除pos位置的值		
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

删除3位置测试代码：

void TestList9()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}

效果展示：
在这里插入图片描述

2. 12 销毁

//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

2.13 创建节点

写一个函数创建节点，不然每次要创建节点的时候都得写一个，现在直接调用就可以。

//创建节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}

3. test主函数

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//尾插测试
void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}//头插测试
void TestList2()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTDestroy(plist);plist = NULL;
}//尾删测试
void TestList3()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}//头删测试
void TestList4()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}void TestList8()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}void TestList9()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTErase(pos);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{TestList9();return 0;
}

4. List.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//声明
LTNode* BuyLTNode(LTDataType x);//初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}//判断空不能删
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//创建节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("BuyLTNode");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = newnode;*/LTInsert(phead, x);
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* tail = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = tail;tail->prev = newnode;*/LTInsert(phead->next, x);
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* cur = phead->prev;LTNode* tail = cur->prev;free(cur);tail->next = phead;phead->prev = tail;*/LTErase(phead->next);
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));/*LTNode* next = phead->next;LTNode* tail = next->next;free(next);phead->next = tail;tail->prev = phead;*/LTErase(phead->prev);
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置的值		
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

5. List.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;//初始化
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);//判断空不能删
bool LTEmpty(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的值		
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

这篇关于带头+双向+循环链表的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1061607。

相关文章

C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
OpenCV实现实时颜色检测的示例

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间
阅读更多...
Python实现精准提取 PDF中的文本,表格与图片

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容：获取整页文本与指定区域内容获取页面上的所有文本内容获取
阅读更多...
基于Python实现一个Windows Tree命令工具

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一：创建批处理文件并添加到PATH1
阅读更多...
Java使用HttpClient实现图片下载与本地保存功能

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.
阅读更多...
canal实现mysql数据同步的详细过程

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》：本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal
阅读更多...
Nexus安装和启动的实现教程

Nexus安装和启动的实现教程

《Nexus安装和启动的实现教程》：本文主要介绍Nexus安装和启动的实现教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Nexus下载二、Nexus安装和启动三、关闭Nexus总结一、Nexus下载官方下载链接：DownloadWindows系统根
阅读更多...
MySQL存储过程之循环遍历查询的结果集详解

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》：本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题：在生产上导入的数据发现
阅读更多...
SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

《SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程》LiteFlow是一款专注于逻辑驱动流程编排的轻量级框架,它以组件化方式快速构建和执行业务流程,有效解耦复杂业务逻辑,下面给大... 目录一、基础概念1.1 组件（Component）1.2 规则（Rule）1.3 上下文（Conte
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2