数据结构——链表详解

链表

文章目录

  • 链表
    • 前言
    • 认识链表
        • 单链表结构图
        • 带头单循环链表结构图
        • 双向循环链表结构图
        • 带头双向循环链表结构图
      • 链表特点
    • 链表实现(带头双向循环链表实现)
        • 链表结构体
        • (1) 新建头节点
        • (2) 建立新节点
        • (3)尾部插入节点
        • (4)删除节点
        • (5)头部插入节点
        • (6) 头删节点
        • (7) 寻找节点
        • (8) pos位置插入节点
        • (9) 删除pos位置节点
        • (10) 打印链表
        • 测试用例

前言

new一个奶黄包:没关系,这条路我陪你走到底

在这里插入图片描述

认识链表

单链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CAU6jKY6-1692328909256)(https://flowus.cn/preview/624afaec-e422-4877-8061-cb639a1325b7)]

带头单循环链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4euIvGQg-1692328833369)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image.png)]

双向循环链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1uetT2ky-1692328833370)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 1.png)]

带头双向循环链表结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ITJxFGxY-1692328833370)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 2.png)]

链表特点

  • 单链表在内存中,并不是连续存储的(逻辑上连续)。

  • 不支持随机访问

  • 插入时只需要改变指针指向

  • 没有容量的概念

  • 可以高效的在任意位置插入&&删除

  • 缓存利用率低

链表实现(带头双向循环链表实现)

链表结构体

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

(1) 新建头节点

LTNode* ListInit()//建立头节点
{LTNode* phead = buyListNode(-1); //建立一个带头节点phead->next = phead;      phead->prev = phead;return phead;
}

(2) 建立新节点

LTNode* buyListNode(LTDataType x)//创建内存初始化数据  
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //if (newnode == NULL){perror("malloc fail");exit(-1);}// 初始化:注意所对的结构来初始化newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;
}

(3)尾部插入节点

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uzvehYMH-1692328833370)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 3.png)]

(4)删除节点

void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;  //记录上一个节点LTNode* tailmove =tail->prev;  //记录上一个节点的上一个节点tailmove->next = phead;    phead->prev = tailmove;free(tail);
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hCUDDN9I-1692328833371)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 4.png)]

(5)头部插入节点

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = buyListNode(x); LTNode* first = phead->next;newnode->next = first;first->prev = newnode;first->next = phead;phead->prev = first;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vx0P45G2-1692328833371)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 5.png)]

(6) 头删节点

void LTPopFront(LTNode* phead)
{assert(phead);  //判断是否有头节点assert(phead->next != NULL);  //判断第一个节点是否存在LTNode* tail = phead->next;LTNode* tailmove = tail->next;tailmove->prev = phead;phead->next = tailmove;tailmove->next = phead;phead->prev = tailmove;free(tail);
}

在这里插入图片描述

(7) 寻找节点

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){//printf("找到了");return cur;//返回指针}cur=cur->next; //每次都走到下一个节点直到phead}//printf("找不到");return NULL;
}

(8) pos位置插入节点

void LTInsert(LTNode* pos, LTDataType x)//头插尾插都可以调用这个函数 
{assert(pos);LTNode* newnode = buyListNode(x); //新建一个节点LTNode* prev = pos->prev;   //记录pos位置的前一个节点newnode->next = pos;   //新节点的下一个节点就是pospos->prev = newnode;   //pos位置节点prve就链接后面newnode->prev = prev;prev->next = newnode;
}

在这里插入图片描述

(9) 删除pos位置节点

void LTErase(LTNode* pos)  //删除节点
{assert(pos);LTNode* prve = pos->prev;LTNode* next = pos->next;prve->next = next;next->prev = prve;free(pos);
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1IWfpl22-1692328833371)(链表+2506bbec-fbf0-438b-8319-a4e748b4a543/image 7.png)]

(10) 打印链表

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

测试用例

void test1()
{LTNode* ptail = ListInit();LTPushBack(ptail, 1);LTPushBack(ptail, 3);LTPushBack(ptail, 2);LTPushBack(ptail, 4);LTPushBack(ptail, 5);LTPopBack(ptail);LTPrint(ptail);
}

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

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

相关文章

C语言之feof与fgetc应用实例(八十一)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…

常见的Web安全漏洞有哪些,Web安全漏洞常用测试方法介绍

Web安全漏洞是指在Web应用程序中存在的可能被攻击者利用的漏洞,正确认识和了解这些漏洞对于Web应用程序的开发和测试至关重要。 一、常见的Web安全漏洞类型: 1、跨站脚本攻击(Cross-Site Scripting,XSS):攻击者通过向Web页面注入…

雷布斯才是我爱的那斯

在知乎看到一个提问,说谁是程序员的天花板,我想了下,雷布斯可能真的是我辈楷模。 不过讲真,雷布斯我们可能是超越不了的了,不管是作为程序员还是作为老板,雷布斯都比普通人牛逼一大截。 还有,创…

解决hbase节点已下线,但在status中显示为dead问题

工作中需要下线4台hbase小节点,下线完成后使用status 命令查看,有一台为dead状态: 使用status detailed 查看,发现“hd-03"这台节点是dead。 检查各节点配置文件无误,并使用 /opt/hbase/bin/hbase-daemon.sh restart master 重启两个…

数据生成 | MATLAB实现WGAN生成对抗网络数据生成

数据生成 | MATLAB实现WGAN生成对抗网络数据生成 目录 数据生成 | MATLAB实现WGAN生成对抗网络数据生成生成效果基本描述程序设计参考资料 生成效果 基本描述 1.WGAN生成对抗网络,数据生成,样本生成程序,MATLAB程序; 2.适用于MATL…

一篇文章了解Java spring中bean的生命周期!

一.介绍在Java spring中bean的生命周期 1.什么是 Bean? 我们来看下 Spring Framework 的官方文档: In Spring, the objects that form the backbone of your application and that are managed by the Spring IoC container are called beans. A bean …

【第二阶段】kotlin函数引用

针对上篇传入函数参数我们也可以重新定义一个函数,然后在main中调用时传入函数对象 lambda属于函数类型的对象,需要把普通函数变成函数类型的对象(函数引用),使用“::” /*** You can edit, ru…

新能源电动车充电桩控制主板安全特点

新能源电动车充电桩控制主板安全特点 你是否曾经担心过充电桩的安全问题?充电桩主板又是什么样的呢?今天我们就来聊聊这个话题。 充电桩主板采用双重安全防护系统,包括防水、防护、防尘等,确保充电桩安全、可靠。不仅如此,充电桩主板采用先…

前端技术Vue学习笔记--004

Vue学习 文章目录 Vue学习一、scoped解决样式冲突二、data必须是一个函数三、组件通信3.1、组件关系3.2、组件通信解决方案3.3、父传子通信3.4、子传父通信3.5、组件通信案例 四、prop语法4.1、prop语法基础语法4.2、 <font color blue>prop校验4.3、prop&data、单向…

rabbitMQ服务自动停止(已解决

1、 在rabbitmq的sbin目录下操作 rabbitmq-plugins enable rabbitmq_management 2、 自己去rabbitmq_server-3.7.5文件夹下创建一个data&#xff0c;再执行这个命令&#xff08;用自己的目录哈 set RABBITMQ_BASED:\RabbitTools\RabbitMQ\rabbitmq_server-3.7.5\data 然后去配…

SOLIDWORKS有限元分析

SOLIDWORKS是一款广泛使用的三维计算机辅助设计软件&#xff0c;同时它还具有强大的有限元分析功能。有限元分析是一种工程分析方法&#xff0c;它将复杂的实体分解成许多小的有限元素&#xff0c;以便对其进行数学建模和分析。SOLIDWORKS的有限元分析功能可以帮助工程师预测和…

vue3和vue2 语法差异之v-model详细说明

文章目录 0.前言1.参考文档2.详细说明介绍2.x 语法使用 v-bind.sync 3.x 语法v-model 参数v-model 修饰符 迁移策略 3.总结 0.前言 在 Vue 3 中&#xff0c;v-model 的使用方式与 Vue 2 有一些差异。下面是 Vue 3 中 v-model 的一些主要变化&#xff1a; 组件上的默认绑定&…

【卷积神经网络】卷积,池化,全连接

随着计算机硬件的升级与性能的提高&#xff0c;运算量已不再是阻碍深度学习发展的难题。卷积神经网络&#xff08;Convolution Neural Network&#xff0c;CNN&#xff09;是深度学习中一项代表性的工作&#xff0c;CNN 是受人脑对图像的理解过程启发而提出的模型&#xff0c;其…

从零基础到精通IT:探索高效学习路径与成功案例

文章目录 导语&#xff1a;第一步&#xff1a;明确学习目标与方向选择适合的IT方向设定具体的学习目标咨询和调研 第二步&#xff1a;系统学习基础知识选择适合的编程语言学习数据结构和算法掌握操作系统和计算机网络基础 第三步&#xff1a;实践项目锻炼技能选择合适的项目编写…

-Webkit-Box 在 Safari 中出现的兼容性问题

一、问题背景&#xff1a; UI要求要实现这样的效果&#xff0c;使用 display:-webket-box在chrome浏览器下完美解决 但是马上啪啪打脸&#xff0c;在safari浏览器下显示空白 &#xff0c;不能不说浏览器之间的兼容性简直就是天坑 二、解决办法 通过浏览器调试发现原本float的…

探索性测试及基本用例

1 测试决策5要素 测试目标&#xff1a;所有的重要任务都完成了&#xff0c;而剩下没做的事情是比较次要的&#xff0c;我们做到这一点就可以尽早尽可能地降低发布风险。 测试方法&#xff1a;测试是一个不断抉择的过程&#xff0c;测试人员必须理解运行测试用例时和分析现有信…

Java算法_ 二叉树的最大深度(LeetCode_Hot100)

题目描述&#xff1a;给定一个二叉树 &#xff0c;返回其最大深度。root 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 获得更多&#xff1f;算法思路:代码文档&#xff0c;算法解析的私得。 运行效果 完整代码 /*** 2 * Author: LJJ* 3 * Date: 2023/…

去年校招面试中Hadoop高频都问些什么?秋招在即,快收藏!

1 总述 校招是远不同于社招的&#xff0c;企业对学生的要求更多的是一些概念性的东西&#xff0c;即所谓的八股文。但有些场景类的题目也是会涉及到&#xff0c;尤其是在一些中大厂的面试题中。场景题固然是能不能中大厂中必不可少的部分&#xff0c;但是基础牢不牢才是能不能…

idea如何建立web项目???

我们需要用到tomcat&#xff0c;没有下在着小伙伴&#xff0c;可以借鉴这篇博客&#xff1a; 如何正确下载tomcat&#xff1f;&#xff1f;&#xff1f;_明天更新的博客-CSDN博客 1.建立普通的Java项目。 2.简单编写index.jsp文件 3.添加tomcat 4.运行服务器 5.构建Servlet 最后…

如何优雅做好项目管理?

导言 项目本身无好坏之分&#xff0c;项目管理有做好与做坏之别。在互联网大厂的体制下&#xff0c;想要做坏一个项目很难&#xff08;可以通过换人、追加资源等方式消除风险&#xff09;&#xff0c;想要做好一个项目不容易&#xff0c;需要团队及PM付出大量心血和精力。在这…