程序员经验分享-hwhale

一步一步写算法（之单向链表）

2023-10-26

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】


    有的时候，处于内存中的数据并不是连续的。那么这时候，我们就需要在数据结构中添加一个属性，这个属性会记录下面一个数据的地址。有了这个地址之后，所有的数据就像一条链子一样串起来了，那么这个地址属性就起到了穿线连结的作用。

    相比较普通的线性结构，链表结构的优势是什么呢？我们可以总结一下：

    （1）单个节点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小

    （2）节点的删除非常方便，不需要像线性结构那样移动剩下的数据

    （3）节点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

    那么在实际应用中，链表是怎么设计的呢？我们可以以int数据类型作为基础，设计一个简单的int链表：

    （1）设计链表的数据结构

  1. typedef struct _LINK_NODE  
  2. {  
  3.     int data;  
  4.     struct _LINK_NODE* next;  
  5. }LINK_NODE;  

     （2）创建链表
  1. LINK_NODE* alloca_node(int value)  
  2. {  
  3.     LINK_NODE* pLinkNode = NULL;  
  4.     pLinkNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));  
  5.       
  6.     pLinkNode->data = value;  
  7.     pLinkNode->next = NULL;  
  8.     return pLinkNode;  
  9. }  

    （3）删除链表

  1. void delete_node(LINK_NODE** pNode)  
  2. {  
  3.     LINK_NODE** pNext;  
  4.     if(NULL == pNode || NULL == *pNode)  
  5.         return ;  
  6.           
  7.     pNext = &(*pNode)->next;  
  8.     free(*pNode);  
  9.     delete_node(pNext);   
  10. }  
     （4）链表插入数据
  1. STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)  
  2. {  
  3.     if(NULL == *pNode){  
  4.         *pNode = pDataNode;  
  5.         return TRUE;  
  6.     }  
  7.       
  8.     return _add_data(&(*pNode)->next, pDataNode);  
  9. }  
  10.   
  11. STATUS add_data(const LINK_NODE** pNode, int value)  
  12. {  
  13.     LINK_NODE* pDataNode;  
  14.     if(NULL == *pNode)  
  15.         return FALSE;  
  16.           
  17.     pDataNode = alloca_node(value);  
  18.     assert(NULL != pDataNode);  
  19.     return _add_data((LINK_NODE**)pNode, pDataNode);  
  20. }  
     （5）删除数据
  1. STATUS _delete_data(LINK_NODE** pNode, int value)  
  2. {  
  3.     LINK_NODE* pLinkNode;  
  4.     if(NULL == (*pNode)->next)  
  5.         return FALSE;  
  6.       
  7.     pLinkNode = (*pNode)->next;  
  8.     if(value == pLinkNode->data){  
  9.         (*pNode)->next = pLinkNode->next;  
  10.         free(pLinkNode);  
  11.         return TRUE;  
  12.     }else{  
  13.         return _delete_data(&(*pNode)->next, value);  
  14.     }  
  15. }  
  16.   
  17. STATUS delete_data(LINK_NODE** pNode, int value)  
  18. {  
  19.     LINK_NODE* pLinkNode;  
  20.     if(NULL == pNode || NULL == *pNode)  
  21.         return FALSE;  
  22.   
  23.     if(value == (*pNode)->data){  
  24.         pLinkNode = *pNode;  
  25.         *pNode = pLinkNode->next;  
  26.         free(pLinkNode);  
  27.         return TRUE;  
  28.     }         
  29.       
  30.     return _delete_data(pNode, value);  
  31. }  
     （6）查找数据
  1. LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)  
  2. {  
  3.     if(NULL == pLinkNode)  
  4.         return NULL;  
  5.       
  6.     if(value == pLinkNode->data)  
  7.         return (LINK_NODE*)pLinkNode;  
  8.       
  9.     return find_data(pLinkNode->next, value);  
  10. }  
     （7）打印数据
  1. void print_node(const LINK_NODE* pLinkNode)  
  2. {  
  3.     if(pLinkNode){  
  4.         printf("%d\n", pLinkNode->data);  
  5.         print_node(pLinkNode->next);  
  6.     }  
  7. }  
     （8）统计数据
  1. int count_node(const LINK_NODE* pLinkNode)  
  2. {  
  3.     if(NULL == pLinkNode)  
  4.         return 0;  
  5.           
  6.     return 1 + count_node(pLinkNode->next);  
  7. }  


【预告： 下一篇博客介绍双向链表】



FROM:  http://blog.csdn.net/feixiaoxing/article/details/6848077

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

编程常用算法

一步一步写算法（之单向链表） 的相关文章

  • fread函数解析

    fread函数解析 1 size t fread void buffer size t elementsize size t count FILE stream return fread s buffer SIZE MAX elements

  • 微信小程序纯css实现一个弹出的菜单

    1 实现效果 2 实现原理 animation动画 transform属性 rotateZ translate 3 实现代码

  • 必读：学习C语言编程的路线图

    学习C语言编程 可以丰富编程思维的训练和经验 以下是一些学习C语言编程的路线图 设置开发环境 在计算机上安装C编译器 GNU编译器集合 GCC 是一个流行的选择 适用于Windows macOS和Linux等各种操作系统 安装IDE编程环境

  • 数据清洗方法

    来源 我是码农 转载请保留出处和链接 本文链接 http www 54manong com id 1220 1 数据错误 脏数据或错误数据 比如 温度 2003 数据不正确 0 代表真实的0还是代表缺失 数据不一致 2 删除重复值 删除重复

  • Shell脚本——条件语句

    shell脚本 编程条件语句 条件测试 if语句 case分支语句 一 条件测试 1 1 Test命令 1 2 文件测试 1 3整数值比较 1 4字符串比较 1 5逻辑测试 二 if语句 2 1 单分支结构 2 2双分支结构 2 3多分支结

  • Eclipse 语言包下载

    1 登陆http www eclipse org babel downloads php 选择你的eclipse版本 2 找到IDE中文补丁包 INDIGO的地址如下 http download eclipse org technology

  • Maven(六) eclipse 使用Maven deploy命令部署构建到Nexus

    转载于 http blog csdn net jun55xiu article details 43051627 1 应用场景 SYS UTIL 系统工具 项目部署 构建成JAR包 SYS UTIL XXX jar 存储到Nexus私服上

  • spring boot 使用application.properties 进行外部配置

    application properties大家都不陌生 我们在开发的时候 经常使用它来配置一些可以手动修改而且不用编译的变量 这样的作用在于 打成war包或者jar用于生产环境时 我们可以手动修改环境变量而不用再重新编译 spring b

  • python里的pypi是干什么用的_【python工具篇】pip和pypi

    PyPI the Python Package Index The Python Package Index is a repository of software for the Python programming language T

  • HTTP中GET，POST和PUT的区别

    一 HTTP中定义了以下几种请求方法 1 GET 2 POST 3 PUT 4 DELETE 5 HEAD 6 TRACE 7 OPTIONS 二 各个方法介绍 1 GET方法 对这个资源的查操作 2 DELETE方法 对这个资源的删操作

  • 电脑检测不到第二个显示器的解决方法

    一般是因为显示适配器被失效了 右击开始菜单 选择 设备管理器 再选择 显示适配器 这时图标上一般会带上感叹号 右击后选择禁用 再选择启用就能检测到第二个显示器

  • 第一个跑马灯实验

    如何新建一个工程 1 打开工程模板 删除其他不重要的库文件 把main 函数里的内容删除 不用的外设固件库文件可以删掉 节省编译时间 rcc 时钟使能 usart 串口 复用映射 setbits 设置高电平 resetbits 低电平 2

  • 「PAT甲级真题解析」Advanced Level 1006 Sign In and Sign Out

    PAT Advanced Level Practice 1006 Sign In and Sign Out 如果对你有帮助 要点个赞让我知道喔 文章目录 问题分析 完整描述步骤 伪代码描述 完整提交代码 问题分析 题目给出一组学生进入机房的

  • 计量经济学及Stata应用 陈强 第八章自相关习题8.3

    8 3使用数据集gasoline dta估计美国1953 2004年的汽油需求函数 考虑如下回归 其中 被解释变量lgasq为人均汽油消费量的对数 解释变量lincome为人均收入的对数 lgasp为汽油价格指数的对数 lpnc为新车价格指

  • ROS建模仿真(1)-创建机器人模型

    ROS建模仿真 1 创建机器人模型 创建catkin creat pkg功能包 创建机器人描述文件 创建launch文件 创建catkin creat pkg功能包 创建机器人描述文件 创建launch文件 创建catkin creat p

  • Mac OS上使用ffmpeg的“血泪”总结

    标题真不是夸张 这几天在整理视频相关的处理流程 为了获得一些性能数据 打算在自己的MacBook Pro 上面装ffmepg 这一折腾4 5天就过去了 有些问题 在解决之后就豁然开朗了 没有解决之前 真的是百思不得其解 中间就好像隔着一层纱

  • AF_INET和AF_PACKET区别

    http blog csdn net kzm2008 article details 5372834 man 7 ip man 7 packet Packet sockets are used to receive or send raw

  • 单片机蓝桥杯——定时中断实现数码管显示、按键判断

    1 1ms定时中断T0 控制数码管显示 1 关于中断 关于定时中断的初始化函数可直接在STC ISP软件上生成 如下图所示 注意 初始化函数中并没有打开EA和ET0 需要自己加上 2 关于数码管显示 数码管段码 segCode 0 segC

随机推荐

  • Flutter提供者模式说明

    在本文中 我们将介绍Flutter中的Provider模式 Google的工作小组建议使用提供程序模式 他们还在Flutter的Pragmatic State Management中的 Google I O 2019上进行了介绍 其他一些模

  • Nginx的Gzip压缩

    Nginx的Gzip压缩 Nginx开启Gzip压缩功能 可以使网站的css js xml html 文件在传输时进行压缩 提高访问速度 进而优化Nginx性能 在Nginx配置文件中可以配置Gzip的使用 相关指令可以在http区域 se

  • Java流程控制--分支结构

    Java流程控制 分支结构 if 单分支 结构 if 条件表达式 这个表达式的结果是布尔值 要么是false 要么是true 如果上面 中的表达式返回结果是true 那么执行 中代码 如果上面 中的表达式返回结果是false 那么不执行 中

  • Unity的Audio组件命令有哪些

    Unity 的 Audio 组件命令有以下几种 Play 播放音频 Pause 暂停音频 UnPause 取消暂停音频 Stop 停止播放音频 SetScheduledStartTime 设置音频开始播放的时间 SetScheduledEn

  • SpringBoot使用Redisson做延迟队列案列(超详细)

    背景 有些场景下 需要延迟触发一些任务 比如 延迟几秒钟发送短信或者邮件 某些业务系统回调 需要延时几秒钟后回调 当然 实现延时触发的方式有很多 我这里采用 redisson 的 RDelayedQueue 一是因为接入简单 二是没有分布式

  • post使用form-data和x-www-form-urlencoded的本质区别

    一是数据包格式的区别 二是数据包中非ANSCII字符怎么编码 是百分号转码发送还是直接发送 一 application x www form urlencoded 1 它是post的默认格式 使用js中URLencode转码方法 包括将na

  • 修改onnx模型输出示例

    前言 如图是netron github链接 软件中打开的onnx模型 可以看到右边模型的最终输出结果是分类值predict 0而非概率值 那么如何获取中间过程的概率值 或者说怎么把右边的图砍掉一截变成左边的图呢 代码 读入模型 import

  • keras_cv进行数据增强

    使用keras cv来做分类数据增强 以下直接上流程 具体的原理和代码上github查看源码及配合tensorflow官网及keras官网来做处理 当前 2022 10 8 这些文档还不是很全 import os import numpy

  • Shell 运行shell脚本的多种方法

    详情地址 运行shell脚本的多种方法 小步教程 Shell 运行shell脚本的多种方法 运行shell脚本文件可通过两类方法 方法1 bash执行 语法 sh 文件 文件可使用相对路径或绝对路径 示例 sh 01hello sh 等价写

  • 游戏出现GetThreadContext failed报错 Unity开发

    解决方案 1 检查是否有360 有的情况 1 简单方案 卸载360 2 专业方案 将游戏exe添加到360信任名单中 解释 360会将一些模拟按键视为木马 然后游戏运行一般直接闪退 2 检查防火墙 专业方案 将游戏exe加入防火墙允许应用的

  • 多端技术栈uniapp开发优势是什么？适合哪种类型产品开发？

    uniapp是一种基于Vue js的跨平台开发框架 它可以支持以单一代码库编写多个平台的应用程序 包括iOS Android Web等 以下是uniapp开发的优势和适用类型的介绍 1 跨平台开发 相比于传统的原生开发 uniapp可以基于

  • tar 打包、压缩和备份

    如何理解 首先讲两个概念 打包 将一大堆文件或目录变成一个总的文件 压缩 将一个大的文件通过压缩算法变成一个小文件 这两种场景一定要区分开 网络上有的技术文章 将tar命令解释为压缩命令 是不完全正确的 关于此点 本文不再拓展 感兴趣的可以

  • 黄页是什么意思

    黄页 起源于北美洲 1880年世界上第一本黄页电话号簿在美国问世 至今已有100多年的历史 黄页是国际通用按企业性质和产品类别编排的工商电话号码薄 相当于一个城市或地区的工商企业的户口本 国际惯例用黄色纸张印制 故称黄页 目前我们常说的黄页

  • Python 类型提示和静态类型检查

    介绍 在本文中 将了解 Python 类型检查 Type Checking 在本教程中 将了解以下内容 类型注释和类型提示 将静态类型添加到代码中 包括你的代码和其他人的代码 运行静态类型检查器 在运行时强制类型 视频介绍如下 Python

  • 树莓派软键盘乱码

    树莓派软键盘乱码的快速处理 matchbox keyboard的显示 处理办法 matchbox keyboard的显示 正常的Matchbox keyboard安装完成后应该出现如下的界面 但是 在初次安装时 发现部分用户的界面出现乱码情

  • react，useEffect一直重复执行

    import useState useEffect from react useEffect callback arr useEffect接受两个参数 callback 回调函数 第一次会默认执行一次 内部可以return一个回调函数 当卸

  • 客户端和服务端端口的建立与连接

    socket 建立通信的端口 并返回引用该端口的文件描述符 man sockst https man7 org linux man pages man2 socket 2 html 头文件 include

  • nacos服务中断导致项目无法连接，就算nacos服务恢复也不会自动注册,springboot要如何配置nacos自动重连?...

    您可以在配置文件中 例如 application properties 或 application yml 中添加如下配置来启用 Nacos 自动重连 spring cloud nacos discovery retry enabled t

  • [网络安全提高篇] 一〇九.津门杯CTF的Web Write-Up万字详解（SSRF、文件上传、SQL注入、代码审计、中国蚁剑）

    这是作者网络安全自学教程系列 主要是关于安全工具和实践操作的在线笔记 特分享出来与博友们学习 希望您喜欢 一起进步 这篇文章主要介绍5月9日参加津门杯CTF题目知识 包括power cut hate php Go0SS HploadHub和

  • 一步一步写算法（之单向链表）

    声明 版权所有 欢迎转载 请勿用于商业用途 联系信箱 feixiaoxing 163 com 有的时候 处于内存中的数据并不是连续的 那么这时候 我们就需要在数据结构中添加一个属性 这个属性会记录下面一个数据的地址 有了这个地址之后 所有的

热门标签