数据结构——带头双向循环链表

数据结构——带头双向循环链表

  • 一、带头双向循环链表的定义
  • 二、带头双向循环链表的实现
    • 2.1初始化创建带头双向循环链表的节点
    • 2.2申请新节点
    • 2.3节点的初始化
    • 2.4带头双向循环链表的尾插
    • 2.5带头双向循环链表的头插
    • 2.6判空函数
    • 2.7带头双向循环链表的打印函数
    • 2.8带头双向循环链表的尾删
    • 2.9带头双向循环链表的头删
    • 2.11带头双向循环链表的在pos之前插入
    • 2.12带头双向循环链表的在pos位置删除
    • 2.14带头双向循环链表的销毁
  • 三、完整代码
    • 3.1LIst.h
    • 3.2List.c
    • 3.3test.c

一、带头双向循环链表的定义

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势。
带头双向循环链表包括一个带有哨兵位的头节点，该节点既可以作为链表的第一个节点，也可以作为链表的最后一个节点.
这种链表的特点是每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点，这样就可以实现双向遍历。
同时，链表的最后一个节点的后继指针指向头节点，形成了循环的结构。这样，我们可以在任意一个节点上进行前后移动，插入和删除操作，而不需要像单链表那样遍历整个链表去找到前一个节点。
需要注意的是，带头双向循环链表为空并不意味着没有一个节点，而是只有一个带哨兵位的头节点，所以在使用之前需要对链表进行初始化。

二、带头双向循环链表的实现

2.1初始化创建带头双向循环链表的节点

typedef struct ListNode
{Listdatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;

带头双向循环链表示意图

在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针，目的在与存储前一个节点的地址，便于将整个链表连在一起。

2.2申请新节点

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

动态申请内存结点，函数返回的是一个指针类型，用malloc开辟一个LTNode大小的空间，并用node指向这个空间，再判断是否为空，如为空就perror，显示错误信息。反之则把需要存储的数据x存到newnode指向的空间里面，并且把newnode->next,newnode->prev置为空。

2.3节点的初始化

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

通过动态内存申请节点，申请了一个头节点。并且将它的phead->next ，phead->prev 都置为phead,得到如下图的头节点。
哨兵位的头节点

2.4带头双向循环链表的尾插

void LTPushBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

尾插节点的方法：首先通过内存申请一个节点， 然后改变四个指针的指向，便可以完成带头双向循环链表的尾插。
在这里插入图片描述
在这里插入图片描述

2.5带头双向循环链表的头插

void LTFrontBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

在这里插入图片描述
在这里插入图片描述

2.6判空函数

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2.7带头双向循环链表的打印函数

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

2.8带头双向循环链表的尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(! LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;//改变指针的指向free(tail);tailprev->next = phead;phead->prev = tailprev;
}

在这里插入图片描述

2.9带头双向循环链表的头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* firstnext = first->next;free(first);phead->next = firstnext;firstnext->prev = phead;
}

在这里插入图片描述

2.11带头双向循环链表的在pos之前插入

void LTInsert(LTNode* pos, Listdatatype x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* posprev = pos->prev;posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

在这里插入图片描述

2.12带头双向循环链表的在pos位置删除

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);
}

在这里插入图片描述

2.14带头双向循环链表的销毁

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

三、完整代码

3.1LIst.h

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

3.2List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
LTNode* BuyLTNode(Listdatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}
//尾插
void LTPushBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//头插
void LTFrontBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//打印
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;printf("guard<->");while (cur != phead){printf("%d<->", cur->data);cur = cur->next;}printf("\n");
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(! LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;//改变指针的指向free(tail);tailprev->next = phead;phead->prev = tailprev;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* firstnext = first->next;free(first);phead->next = firstnext;firstnext->prev = phead;
}//寻找
LTNode* LTFind(LTNode* phead, Listdatatype 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, Listdatatype x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* posprev = pos->prev;posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}在pos之前删除
//void LTErase(LTNode* pos)
//{
//	assert(pos);
//	LTNode* posprev = pos->prev;
//	free(posprev);
//	posprev->prev->next = pos;
//	pos->prev = posprev->prev;
//	
//}//在pos位置删除
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);
}//销毁
LTNode* LTDestory(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

3.3test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//void test1()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPrint(plist);
//	LTPopBack(plist);
//	LTPrint(plist);//}
void test2()
{LTNode* plist = LTInit();LTFrontBack(plist, 1);LTFrontBack(plist, 2);LTFrontBack(plist, 3);LTFrontBack(plist, 4);LTPrint(plist);LTErase(3);LTPrint(plist);
}
int main()
{//test1();test2();return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/129640.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

博客系统项目

博客系统项目

文章目录 数据库的增删改查草稿箱草稿箱自动保存分页查询后端前端 评论区后端前端 md5加盐加密 md5加盐对用户密码进行加密; 全服用户博客列表页,实现分页查询; 用户博客列表页; 写博客,发博客,改博客; 博客草稿箱,自动保存,定时发布; 博客访问量,博客评论区,博客点赞; 数据库…
阅读更多...
“JSR303和拦截器在Java Web开发中的应用与实践“

“JSR303和拦截器在Java Web开发中的应用与实践“

目录 引言JSR303什么是JSR303?为什么要使用JSR303?常用注解快速入门JSR303 拦截器什么是拦截器拦截器与过滤器应用场景快速入门拦截器 总结 引言 在Java Web开发过程中&#xff0c;我们经常会遇到需要对输入数据进行验证和处理&#xff0c;同时需要对请求进行拦截与控制的需…
阅读更多...
通过idea实现springboot集成mybatys

通过idea实现springboot集成mybatys

概述 使用springboot 集成 mybatys后&#xff0c;通过http请求接口&#xff0c;使得通过http请求可以直接直接操作数据库&#xff1b; 完成后端功能框架&#xff1b;前端是准备上小程序&#xff0c;调用https的请求接口用。简单实现后端框架&#xff1b; 详细 springboot 集…
阅读更多...
Scrum工作模式的角色和活动

Scrum工作模式的角色和活动

​Scrum工作模式是一种敏捷软件开发方法&#xff0c;其核心是团队合作和自我组织&#xff0c;旨在通过短周期的迭代开发&#xff0c;实现快速反馈和持续改进。 Scrum工作模式包括以下角色和活动&#xff1a; 1、产品负责人&#xff08;Product Owner&#xff09;&#xff1a;…
阅读更多...
laravel系列(二) Dcat admin框架开发工具使用

laravel系列(二) Dcat admin框架开发工具使用

开发工具可以非常好的帮助我们去快速的开发CURD等操作,但也是有部分框架有些不是太便捷操作,这篇博客主要为大家介绍Dcat admin的开发工具详细使用. 如何创建页面: 在联表我们首先要去.env文件中去找连接数据库方法: APP_NAMELaravel APP_ENVlocal APP_KEYbase64:thO0lOVlzj0…
阅读更多...
Allegro166版本如何在颜色管理器中实时显示层面操作指导

Allegro166版本如何在颜色管理器中实时显示层面操作指导

Allegro166版本如何在颜色管理器中实时显示层面操作指导 在用Allegro166进行PCB设计的时候，需要在颜色管理器中频繁的开关层面。但是166不像172一样在颜色管理器中可以实时的开关层面，如下图 需要打开Board Geometry/Soldermask_top层，首先需要勾选这个层面，再点击Apply即…
阅读更多...
论文简读 LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

论文简读 LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS

论文地址&#xff1a;https://arxiv.org/pdf/2106.09685.pdf 项目地址&#xff1a;https://github.com/microsoft/LoRA 全文翻译地址&#xff1a;https://zhuanlan.zhihu.com/p/611557340 本来想自行翻译的&#xff0c;但最近没有空 1、关键凝练 1.1 LORA是什么&#xff1f; …
阅读更多...
基于java SpringBoot和Vue uniapp的影楼摄影预约小程序

基于java SpringBoot和Vue uniapp的影楼摄影预约小程序

摘要 今天信息技术的发展很快&#xff0c;其足迹在我们的生活中随处可见。它影响着我们的衣食住行等各种需求。影响也在逐渐增加&#xff0c;逐渐渗透到各行各业&#xff0c;在这种背景下&#xff0c;经过实地考察后&#xff0c;为了让婚纱照管理更加高效方便&#xff0c;我决定…
阅读更多...
gitlab 点击Integrations出现500错误

gitlab 点击Integrations出现500错误

背景&#xff1a;在新服务器重新搭建了gitlab&#xff0c;并导入原来gitlab的备份&#xff0c;在项目中点击点击Integrations出现500错误。 解决方法&#xff1a;1.进入新服务器&#xff0c;将 /etc/gitlab/gitlab-secrets.json重命名为 /etc/gitlab/gitlab-secrets.json.bak …
阅读更多...
JavaScript的内置类

JavaScript的内置类

一、认识包装类型 1.原始类型的包装类 JavaScript的原始类型并非对象类型&#xff0c;所以从理论上来说&#xff0c;它们是没有办法获取属性或者调用方法的。 但是&#xff0c;在开发中会看到&#xff0c;我们会经常这样操作&#xff1a; var message "hello world&q…
阅读更多...
文件上传漏洞（CVE-2022-30887）

文件上传漏洞（CVE-2022-30887）

简介 多语言药房管理系统&#xff08;MPMS&#xff09;是用PHP和MySQL开发的&#xff0c;该软件的主要目的是在药房和客户之间提供一套接口&#xff0c;客户是该软件的主要用户。该软件有助于为药房业务创建一个综合数据库&#xff0c;并根据到期、产品等各种参数提供各种报告…
阅读更多...
python超详细安装

python超详细安装

目录 初始python获取python安装包python解释器安装pycharm编译器安装pycharm的简单使用&#xff08;第一个hello world&#xff09; 初始python Python 是一款易于学习且功能强大的编程语言。 它具有高效率的数据结构&#xff0c;能够简单又有效地实现面向对象编程。 Python简…
阅读更多...
uni-app(微信小程序)图片旋转放缩，文字绘制、海报绘制

uni-app(微信小程序)图片旋转放缩，文字绘制、海报绘制

总结一下&#xff1a; 要进行海报绘制离不开canvas&#xff0c;我们是先进行图片&#xff0c;文字的拖拽、旋转等操作 最后再对canvas进行绘制&#xff0c;完成海报绘制。 背景区域设置为 position: relative&#xff0c;方便图片在当前区域中拖动等处理。添加图片&#xff0…
阅读更多...
Python 图形化界面基础篇：添加标签（ Label ）到 Tkinter 窗口

Python 图形化界面基础篇：添加标签（ Label ）到 Tkinter 窗口

Python 图形化界面基础篇&#xff1a;添加标签&#xff08; Label &#xff09;到 Tkinter 窗口 引言什么是 Tkinter 标签&#xff08; Label &#xff09;&#xff1f;步骤1&#xff1a;导入 Tkinter 模块步骤2&#xff1a;创建 Tkinter 窗口步骤3&#xff1a;创建标签&#x…
阅读更多...
Mybatis---resultMap详解

Mybatis---resultMap详解

目录 一、resultMap介绍 二、自定义映射关系 一、resultMap介绍 该标签的作用是自定义映射关系。 Mybatis可以将数据库结果封装到对象中&#xff0c;是因为结果集和对象属性名相同&#xff08;也就是你写的pojo类型的参数名和数据库的字段名相同&#xff09; 但是如果当他们不…
阅读更多...
npm publish包报404，is not in the npm registry错误

npm publish包报404，is not in the npm registry错误

1. 指定发布目标2. 登录npm&#xff0c;使用登录名发布包&#xff0c;包名命名原则“登录名/包名”&#xff0c;或 “包名” 3. 删除某一个版本npm unpublish pvfhv/eslint-config-prettier1.0.1 --force 删除后的版本不能重复使用&#xff0c;正式解释&#xff1a; Unfortun…
阅读更多...
小米13Pro/13Ultra刷面具ROOT后激活LSPosed框架微X模块详细教程

小米13Pro/13Ultra刷面具ROOT后激活LSPosed框架微X模块详细教程

喜欢买小米手机&#xff0c;很多是因为小米手机的开放&#xff0c;支持root权限&#xff0c;而ROOT对普通用户来说更多的是刷入DIY模块功能&#xff0c;今天ROM乐园小编就教大家如何使用面具ROOT&#xff0c;实现大家日常情况下非常依赖的微X模块功能&#xff0c;体验微X模块的…
阅读更多...
makefile之链接静态库

makefile之链接静态库

make之链接静态库 (1)方法一: 指定静态库全路径和全名 APP_S_LIBS ./app_lib/libhost.a $(CC) $(CFLAGS) $(SRCOBJ) $(APP_S_LIBS) -o $(TARGET) APP_HEAD_DIR -I./include #APP_LIBS_DIR -L ./app_lib#APP_S_LIBS -lhost APP_S_LIBS ./app_lib/libhost.aCFLAGS $(APP_…
阅读更多...
企业密码安全：ADSelfService Plus 提升密码管理的千里之行

企业密码安全：ADSelfService Plus 提升密码管理的千里之行

在当今数字化时代&#xff0c;企业的密码安全变得至关重要。密码是保护企业敏感信息和数据的第一道防线&#xff0c;而有效的密码管理对于确保网络安全至关重要。ADSelfService Plus是一款强大的密码管理和自助服务解决方案&#xff0c;它在提供密码安全方面走在了前沿。 ADSel…
阅读更多...
Ajax + Promise复习简单小结simple

Ajax + Promise复习简单小结simple

axios使用 先看看老朋友 axios axios是基于Ajaxpromise封装的 看一下他的简单使用 安装&#xff1a;npm install axios --save 引入&#xff1a;import axios from axios GitHub地址 基本使用 axios({url: http://hmajax.itheima.net/api/province}).then(function (result…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023