链表之双向链表的实现
铁汁们大家好,我们上一篇博客学习了单链表,这节课让我们继续往深学习,学习一下双线链表,话不多说,我们开始吧!
目录
1.双向链表
2.顺序表和链表的优缺点
3.双向链表的实现
1.双向链表
1.我们要实现的双线链表是带头双向循环链表,它的结构最复杂,一般用在单独的存储数据。我们实际中使用的链表数据结构都是带头双向循环链表。
2.它虽然结构复杂,但是在我们用代码实现过程中,它比单链表简单。
3.相信很多铁汁不清楚双向链表的结构是什么,如下图:
2.顺序表和链表的优缺点
我们在这里总结一下这两种线性表,方便之后的学习。
顺序表:
优点:空间连续,支持随机访问
缺点:中间或前面部分的插入和删除,时间复杂度是O(n);
增容很不方便,代价较大。
链表:
优点:任意位置的插入删除,时间复杂度为O(1);
没有增容销耗,按需申请节点空间,不用了直接释放。
缺点:以节点为单位存储,不支持随机访问
3.双向链表的实现
经过上面的铺垫,我们来实现一个带头双向循环链表
List.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int ADataType;
typedef struct ListNode
{ADataType data;struct ListNode* prev;//双线链表前驱指针struct ListNode* next;//后继指针
}LN;//双向链表初始化
LN* ListInit();
//为节点开辟空间
LN* BuyListCapacity(ADataType x);
//链表的销毁
void ListDestory(LN* phead);
//头插
void ListPushFront(LN* phead, ADataType x);
//尾插
void ListPushBack(LN* phead, ADataType x);
//打印
void ListPrint(LN* phead);
//头删
void ListPopFront(LN* phead);
//尾删
void ListPopBack(LN* phead);
//查找链表中的数据
LN* ListSearch(LN* phead, ADataType x);
//修改找到的数据
void ListModify( LN* pos, ADataType y);
//在这个位置后插入数据
void ListInsert(LN* pos, ADataType x);
//删除这个位置之后的数据
void ListErase(LN* pos);
//判断链表是否为空
bool ListEmpty(LN* phead);
List.c文件
#include"List.h"//为节点开辟空间
LN* BuyListCapacity(ADataType x)
{LN* newnode = (LN*)malloc(sizeof(LN));if (newnode == NULL){perror("malloc is false!\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}//双向链表初始化
LN* ListInit()
{//开辟空间LN* phead = BuyListCapacity(0);//让头节点的前驱和后继都指向自己,是一个循环phead->next = phead;phead->prev = phead;return phead;
}//链表的销毁
void ListDestory(LN* phead)
{assert(phead);LN* tail = phead->next;while (tail != phead)//链表的头尾相连,当尾等于头时,说明链表空了{LN* next = tail->next;free(tail);tail = next;}free(phead);phead = NULL;
}
//头插
void ListPushFront(LN* phead, ADataType x)
{assert(phead);LN* newnode = BuyListCapacity(x);//若这里不使用新的变量来存储原来第一个节点的值,就先链接后,在链接前newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}
//尾插
void ListPushBack(LN* phead, ADataType x)
{assert(phead);LN* newnode = BuyListCapacity(x);//找到尾,进行插入节点LN* tail = phead->prev;tail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;
}
//打印
void ListPrint(LN* phead)
{assert(phead);LN* tail = phead->next;while (tail != phead){printf(" %d ", tail->data);tail = tail->next;}printf("\n");
}
//头删
void ListPopFront(LN* phead)
{assert(phead);//判断链表是否为空,为空则删不了if (phead->next == phead){printf("List is NULL!\n");return;}//先记录下后一个节点LN* first = phead->next;LN* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}
//尾删
void ListPopBack(LN* phead)
{assert(phead);//判断链表是否为空if (phead->prev == phead){printf("List is NULL!\n");return;}LN* tail = phead->prev;LN* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;
}
//查找链表中的数据
LN* ListSearch(LN* phead, ADataType x)
{assert(phead);LN* cur = phead->next;while (cur->data != x){cur = cur->next;}if (cur->data == x){return cur;}return NULL;
}
//修改找到的数据
void ListModify( LN* pos, ADataType y)
{assert(pos);pos->data = y;
}
//在这个位置后插入数据
void ListInsert(LN* pos, ADataType x)
{assert(pos);LN* newnode = BuyListCapacity(x);LN* next = pos->next;pos->next = newnode;newnode->prev = pos;newnode->next = next;next->prev = newnode;
}
//删除这个位置之后的数据
void ListErase(LN* pos)
{assert(pos);LN* cur = pos->next;LN* next = cur->next;pos->next = next;next->prev = pos;free(cur);cur = NULL;
}
//判断链表是否为空
bool ListEmpty(LN* phead)
{assert(phead);if (phead->prev == phead || phead->next == phead){return true;}return false;
}
Test.c文件
#include"List.h"
//带头双向循环链表的实现void Test1()
{LN* head = ListInit();ListPushFront(head, 33);ListPushFront(head, 22);ListPushFront(head, 11);ListPushBack(head, 4);ListPushBack(head, 5);ListPushBack(head, 6);ListPushBack(head, 7);ListPushBack(head, 8);ListPushBack(head, 9);ListPushBack(head, 10);printf("ListNode:> ");ListPrint(head);ListPopFront(head);ListPopBack(head);printf("ListNode:> ");ListPrint(head);LN* pos = ListSearch(head, 7);if (pos == NULL){printf("Not Find!\n");}else{printf("the number is %d\n", pos->data);ListModify(pos, 77);printf("ListNode:> ");ListPrint(head);ListInsert(pos, 13);ListInsert(pos, 14);ListInsert(pos, 15);printf("ListNode:> ");ListPrint(head);ListErase(pos);printf("ListNode:> ");ListPrint(head);}if (ListEmpty(head)){printf("List is NULL!\n");}else{printf("List is Notnull!\n");}ListDestory(head);printf("List is disory!\n");
}int main()
{Test1();return 0;
}
结果:结果就是这样的,大家可以自己尝试一下!
这就是双向链表的实现,大家还是要自己敲一遍代码,帮助自己更好的掌握知识点。
谢谢铁汁们的支持,咱们下期再见!!!
相关文章:
链表之双向链表的实现
铁汁们大家好,我们上一篇博客学习了单链表,这节课让我们继续往深学习,学习一下双线链表,话不多说,我们开始吧! 目录 1.双向链表 2.顺序表和链表的优缺点 3.双向链表的实现 1.双向链表 1.我们要实现的双线…...
小白学大模型:什么是生成式人工智能?
什么是生成式人工智能? 在过去几年中,机器学习领域取得了迅猛进步,创造了人工智能的一个新的子领域:生成式人工智能。这些程序通过分析大量的数字化材料产生新颖的文本、图像、音乐和软件,我将这些程序简称为“GAIs”…...
并发编程01-深入理解Java并发/线程等待/通知机制
为什么我们要学习并发编程? 最直白的原因,因为面试需要,我们来看看美团和阿里对 Java 岗位的 JD: 从上面两大互联网公司的招聘需求可以看到, 大厂的 Java 岗的并发编程能力属于标配。 而在非大厂的公司, 并…...
3.类与对象(中篇)介绍了类的6个默认构造函数,列举了相关案例,实现了一个日期类
1.类的6个默认成员函数 如果一个类中什么成员都没有,简称为空类。 空类中真的什么都没有吗?并不是,任何类在什么都不写时,编译器会自动生成以下6个默认成员函数。 默认成员函数:用户没有显式实现,编译器会…...
Vue实现手机APP页面的切换,如何使用Vue Router进行路由管理呢?
在Vue中,实现手机APP页面的切换,通常会使用Vue Router进行路由管理。Vue Router是Vue.js官方的路由管理器,它和Vue.js深度集成,使构建单页面应用变得易如反掌。 以下是一个简单的步骤说明,展示如何使用Vue Router实现…...
软考--软件设计师(软件工程总结2)
目录 1.测试方法 2.软件项目管理 3.软件容错技术 4.软件复杂性度量 5.结构化分析方法(一种面向数据流的开发方法) 6.数据流图 1.测试方法 软件测试:静态测试(被测程序采用人工检测,计算机辅助静态分析的手段&…...
渗透测试之SSRF漏洞
一、SSRF介绍 SSRF(Cross-site Scripting,简称XSS)是一种安全漏洞,它允许攻击者通过构造特定的请求,使服务器发起对外网无法访问的内部系统请求。这种漏洞通常发生在服务端提供了从其他服务器应用获取数据的功能&#…...
【C++】1957. 求三个数的平均数
问题:1957. 求三个数的平均数 类型:基本运算、小数运算 题目描述: 小雅刚刚考完语文、数学、英语的三门期中考试,她想请你编个程序来帮她算算她的平均分。 要求输入三个正整数,分别表示三科考试的分数,输…...
GPU部署ChatGLM3
首先,检查一下自己的电脑有没有CUDA环境,没有的话,去安装一个。我的电脑是4060显卡,买回来就自带这些环境了。没有显卡的话,也不要紧,这个懒人安装包支持CPU运行,会自动识别没有GPU,…...
Windows远程执行
Windows远程执行 前言 1、在办公环境中,利用系统本身的远程服务进行远程代码执行甚至内网穿透横向移动的安全事件是非常可怕的,因此系统本身的一些远程服务在没有必要的情况下建议关闭,防止意外发生; 2、作为安全人员࿰…...
AJAX —— 学习(一)
目录 一、原生 AJAX (一)AJAX 介绍 1.理解 2.作用 3.最大的优势 4.应用例子 (二)XML 介绍 1.理解 2.作用 (三)AJAX 的特点 1.优点 2.缺点 二、HTTP 协议 (一)HTTP 介…...
Activity——idea(2020以后)配置actiBPM
文章目录 前言jar下载idea 安装本地扩展插件 前言 2020及之后版本的idea中,未维护对应的actiBPM扩展插件。如果需要安装该插件,则需要使用本地导入 jar的方式。 jar下载 访问官方网站,搜索对应的actiBPM扩展插件。 https://plugins.jetbra…...
MyBatis——配置优化和分页插件
MyBatis配置优化 MyBatis配置文件的元素结构如下: configuration(配置) properties(属性) settings(设置) typeAliases(类型别名) plugins(插件)…...
[蓝桥杯 2013 省 B] 翻硬币
[蓝桥杯 2013 省 B] 翻硬币 题目背景 小明正在玩一个“翻硬币”的游戏。 题目描述 桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零),比如可能情形是 **oo***oooo,如果…...
[BT]BUUCTF刷题第13天(4.1)
第13天 Upload-Labs-Linux (Basic) Pass-01 根据题目提示,该题为绕过js验证。 一句话木马: <?php eval(system($_POST["cmd"]));?> // 符号 表示后面的语句即使执行错误,也不报错。 // eval() 把括号内的字符串全部…...
特别详细的Spring Cloud 系列教程1:服务注册中心Eureka的启动
Eureka已经被Spring Cloud继承在其子项目spring-cloud-netflix中,搭建Eureka Server的方式还是非常简单的。只需要通过一个独立的maven工程即可搭建Eureka Server。 我们引入spring cloud的依赖和eureka的依赖。 <dependencyManagement><!-- spring clo…...
Day108:代码审计-PHP模型开发篇MVC层动态调试未授权脆弱鉴权未引用错误逻辑
目录 案例1-Xhcms-动态调试-脆弱的鉴权逻辑 案例2-Cwcms-动态调试-未引用鉴权逻辑 案例3-Bosscms-动态调试-不严谨的鉴权逻辑 知识点: 1、PHP审计-动态调试-未授权安全 2、PHP审计-文件对比-未授权安全 3、PHP审计-未授权访问-三种形态 动态调试优点: 环境配置&…...
重读Java设计模式: 桥接模式详解
引言 在软件开发中,经常会遇到需要在抽象与实现之间建立连接的情况。当系统需要支持多个维度的变化时,使用传统的继承方式往往会导致类爆炸和耦合度增加的问题。为了解决这一问题,我们可以使用桥接模式。桥接模式是一种结构型设计模式&#…...
新规解读 | 被网信办豁免数据出境申报义务的企业,还需要做什么?
为了促进数据依法有序自由流动,激发数据要素价值,扩大高水平对外开放,《促进和规范数据跨境流动规定》(以下简称《规定》)对数据出境安全评估、个人信息出境标准合同、个人信息保护认证等数据出境制度作出优化调整。 …...
fakebook-攻防世界
题目 先目录扫描一下 dirseach 打开flag.php是空白的 访问robots.txt,访问user.php.bak <?php class UserInfo { public $name ""; public $age 0; public $blog ""; public function __construct($name, $age, $blog) { …...
mynet开源库
1.介绍 个人实现的c开源网络库. 2.软件架构 1.结构图 2.基于event的自动分发机制 3.多优先级分发队列,延迟分发队列 内部event服务于通知机制的优先级为0,外部event优先级为1. 当集中处理分发的event_callback时,…...
深度挖掘商品信息,jd.item_get API助您呈现商品全面规格参数
深度挖掘商品信息,特别是在电商平台上,对于商家、开发者和用户来说都至关重要。jd.item_get API作为京东开放平台提供的一个强大工具,能够帮助用户轻松获取商品的全面规格参数,进而为商品分析、推荐、比较等提供有力的数据支撑。 …...
A Random Walk Based Anonymous Peer-to-Peer
一、 背景 匿名性一直是P2P系统等自组织环境中最具挑战性的问题之一。在本文中,我们提出了一个匿名协议,称为基于随机漫步的匿名协议(RWAP),在分散的P2P系统。我们通过全面的轨迹驱动模拟来评估RWAP。结果表明,与现有方法相比,RWAP显著降低了流量成本和加密开销。 二、 …...
php代码执行计划任务dos实现方式和宝塔面板实现方式
dos php 计划任务 echo off :loop echo 这是一个死循环 echo This is an infinite loop. php think gpt php think ai timeout /t 2 goto loop 宝塔面板 php 计划任务 #!/bin/bash PATH/bin:/sbin:/usr/bin:/usr/sbin:/usr/local/bin:/usr/local/sbin:~/bin export PATH ste…...
千万不要错过这6款能让你快速写作成长的宝藏软件…… #学习方法#AI写作
国外ChatGPT爆火,AI写作在国内也引起不小的瞩目,目前国内的AI写作工具少说也有几十上百个,要在这么多AI写作中找出适合自己的工具,一个一个尝试是不太现实的,所以今天就给大家推荐一些款AI写作工具。帮助你少走弯路&am…...
TypeScript系列之-理解TypeScript类型系统画图讲解
TypeScript的输入输出 如果我们把 Typescript 编译器看成一个黑盒的话。其输入则是使用 TypeScript 语法书写的文本或者文本集合。 输出是编译之后的 JS 文件 和 .d.ts 的声明文件 其中 JS 是将来需要运行的文件(里面是没有ts语法,有一个类型擦除的操作)࿰…...
制造业智能化一体式I/O模块的集成与应用案例分享
在现代制造业中,智能化一体式I/O模块的应用已经成为提升生产效率、优化工艺流程的关键技术之一。这种一体化I/O模块的主要功能在于作为PLC(可编程逻辑控制器)系统的扩展接口,以满足多样化的输入输出需求。本文将通过一个实际案例&…...
《云原生安全攻防》-- 云原生应用风险分析
为了满足每位朋友的学习需求,并且支持课程的持续更新,本系列课程提供了免费版和付费视频版两种方式来提供课程内容。我们会持续更新课程内容,以确保内容的度和实用性。 在本节课程中,我们将一起探讨云原生应用在新的架构模式下可能…...
抖音-引流私域转化模式1.0现场视频,从抖音源源不断把人加到私域,
抖音-引流私域转化模式1.0现场视频,从抖音源源不断把人加到私域,让加到私域的粉丝买单 抖音-引流私域转化模式1.0现场视频,从抖音源源不断把人加到私域 - 百创网-源码交易平台_网站源码_商城源码_小程序源码 课程内容: 01.第一…...
外包干了6天,技术明显进步
先说一下自己的情况,本科生,2019年我通过校招踏入了南京一家软件公司,开始了我的职业生涯。那时的我,满怀热血和憧憬,期待着在这个行业中闯出一片天地。然而,随着时间的推移,我发现自己逐渐陷入…...
室内设计和平面设计区别/郑州seo哪家专业
敏捷演示会这篇文章可帮助您将产品演示用作有效的敏捷市场研究工具:收集相关反馈以验证您的想法并改进产品。 如果您使用演示来签署用户故事,那么本文将向您展示如何从中获得更多收益。 在像Scrum这样的敏捷方法中,最新的产品增量将在sprint…...
私人订制网站建设/微信群二维码推广平台
#1014 : Trie树 时间限制:10000ms单点时限:1000ms内存限制:256MB描述 省略 输入 输入的第一行为一个正整数n,表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦),…...
西城做网站/百度网络优化
php实现不对称加密的方法:首先创建一个PHP示例文件;然后使用openssl实现非对称加密;最后通过“$rsa new Rsa(ssl-key);”进行测试即可。推荐:《PHP视频教程》PHP实现非对称加密至于什么是非对称加密,这里就不说啦&…...
seo推广的作用/seo优化咨询
使用DAX中的某些函数特别类似Calculate这种函数创建计算列时很容易出现一种错误,叫做检测到循环依赖关系,即:A circular dependency was detected。对于刚接触Dax语言的人来说,这个错误看着有点摸不到头脑,整个公式使用…...
凡总创业网站/在哪里打广告效果最好
我的应用场景是获取给整个页面的LinearLayout设置背景,当页面没有数据的时候,就给页面加一个背景图,setBackground()设置页面背景图片: 看代码吧!!! //获取项目中的静态资源文件Resources resources getCo…...
门户网站模板免费下载/深圳经济最新新闻
这是我在拓朴上配置的单闭路由,可是老是分配不了IP 地址,请你们帮我看下 这是在交换机上的配置 Switch>en Switch# Switch#conf t Enter configuration commands, one per line. End with CNTL/Z. Switch(config)#vlan 2 Switch(config-vlan)#ex Swi…...