数据结构--单链表

一.单链表的设计

1.单链表的结构定义:

typedef struct Node{
int data;//数据域
struct Node* next;//后继指针
}Node,*List;

2.单链表的设计示意图:

image-20230602115022970.png


3.注意:

单链表的最后一个节点的next域为NULL;

4.为什么要有一个头节点?

简单方便,不用传二级指针;

二.单链表的实现

//初始化
}//考试重点
//删除第一个val的值
bool DelVal(List plist, int val)
{Node* p = GetPrio(plist, val);if (p == NULL)return false;Node* q = p->next;//删除qp->next = q->next;//p->next=p->next->next;//释放qfree(q);return true;
}//返回key的前驱地址,如果不存在返回NULL;
Node* GetPrio(List plist, int key)
{for (Node* p = plist; p->next != NULL; p = p->next){if (p->next->data == key)return p;}return NULL;
}//返回key的后继地址,如果不存在返回NULL;
Node* GetNext(List plist, int key)
{assert(plist != NULL);if (plist == NULL)return NULL;Node* p = Search(plist, key);if (p == NULL)return NULL;return p->next;
}//输出
void Show(List plist)
{//注意,头节点不能访问datafor (Node* p = plist->next; p != NULL; p = p->next){printf("%d ", p->data);}printf("\n");
}//清空数据
void Clear(List plist)
{Destroy(plist);
}void Destroy(List plist)
{//总是删除第一个数据节点Node* p;while (plist->next != NULL){p = plist->next;plist->next = p->next;free(p);//error//plist->next = plist->next->next;//free(plist->next);}
}

三.单链表的总结

1.单链表的特点:

头插,头删 时间复杂度是O(1)

尾插,尾删 时间复杂度是O(n)

2.P初始化成什么?

如果我们要修改表的结构(或者说依赖于前驱,比如插入,删除):遍历:

for(Node *p=plist;p->next!=NULL;p=p->next)

如果我们不修改表的结构(或者说不依赖于前驱, 比如求长度,打印,查找) :遍历:

for (Node* p = plist->next; p != NULL; p = p->next)
3.注意考点:

头插,尾插,按值删除;

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

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

相关文章

韩顺平 | 零基础快速学Python(9~11) 排序查找

排序和查找 排序 排序:将多个数据按顺序排列。有冒泡、选择、插入、希尔、归并、快速、堆、计数、捅、基数排序。 冒泡排序 冒泡排序 Bubble Sorting:重复地走访需要排序地元素列表,依次比较相邻的元素,如果顺序错误就交换位置…

SSH穿透ECS访问内网RDS数据库

处于安全考虑,RDS一般只会允许指定的IP进行访问,而我们开发环境的IP往往是动态的,每次IP变动都需要去修改RDS的白名单,为我们的工作带来很大的不便。 那么如何去解决这个问题? 假如我们有一台ESC服务器,E…

简介:基于Web的产品3D

基于 Web 的产品 3D 通过可视化界面获得各种选项来个性化他们的产品,例如颜色、材料、尺寸、文字、徽标、零件等。 在过去几年中,随着 3D 建模和渲染软件的出现,3D 渲染现在更常用于营销和促销目的。设计师、制造商和营销人员使用 3D 产品渲…

【Kafka】Kafka 架构深入

Kafka 工作流程及文件存储机制 Kafka 中消息是以 topic 进行分类的,生产者生产消息,消费者消费消息,都是面向 topic 的。 topic 是逻辑上的概念,而 partition 是物理上的概念,每个 partition 对应于一个 log 文件&am…

11111111

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话: 知不足而奋进,望远山而前行&am…

MT3020 任务分配

思路:利用二分找到某个时间是满足“k个人可以完成” ,并且时间最小。 因为尽量让后面的人做任务,所以从后往前排任务(倒着分配)。从后往前遍历任务,如果此人加上这个任务超出之前求得的时间,就…

逐步学习Go-sync.RWMutex(读写锁)-深入理解与实战

概述 在并发编程中,我们经常会遇到多个线程或协程访问共享资源的情况。为了保护这些资源不被同时修改,我们会用到"锁"的概念。 Go中提供了读写锁:sync.RWMutex。 sync.RWMutex是Go语言提供的一个基础同步原语,它是Rea…

Nikon | NEF格式图片批量转换为jpg格式

如何将nikon相机拍的NEF格式图片转换为jpg格式呢? 这里推荐一个在线转换的网址: https://picflow.com/convert/nef-to-jpg 添加图片后,可以批量选择图片,点击转换后即可进行下载

74HC595引脚图时序图工作原理

74HC595和74hc164一样是在单片机系统中常用的芯片之一他的作用就是把串行的信号转为并行的信号,常用在各种数码管以及点阵屏的驱动芯片, 使用74HC595可以节约单片机mcu的io口资源,用3个io就可以控制8个数码管的引脚,他还具有一定的…

[攻防世界]Reversing-x64Elf-100

1.查壳 无壳,ELF文件 2.用IDA64打开 找到关键部分 这里有坑,看清楚v3是长度为3数组,里面放三个字符串 3.脚本解密 v1"Dufhbmf" v2"pGimos" v3"ewUglpt" v4[v1,v2,v3] a1[0,0,0,0,0,0,0,0,0,0,0,0] for i …

乐趣Python——办公魔法:Word文件自动化

嘿,朋友们!在这个办公小课堂中,我将为大家揭开一个神奇的秘密:Word文件自动化处理! 通过这种魔法般的方式,我们可以大大提高办公效率,减少重复性工作。而Python作为我们的助手,将展现…

JavaSE-12笔记【集合1(+2024新)】

文章目录 1. 集合概述2.Collection2.1 Collection继承结构(基于Java21)2.2 Collection接口的常用方法2.3 Collection的遍历(集合的通用遍历方式)2.4 所有的有序集合都实现了SequencedCollection接口2.5 泛型2.5.1 如何判断是否可以…

防止狗上沙发,写一个浏览器实时识别目标检测功能

家里有一条狗🐶,很喜欢乘人不备睡沙发🛋️,恰好最近刚搬家 狗迎来了掉毛期 不想让沙发上很多毛。所以希望能识别到狗,然后播放“gun 下去”的音频📣。 需求分析 需要一个摄像头📷 利用 chrome…

Mapmost Alpha:开启三维城市场景创作新纪元

🤵‍♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞&#x1f4…

vue3中使用antv-S2表格(基础功能版)

先看展示效果: 可以调整行宽、列宽、自定义字段图标、表头图标、添加排序、显示总计、小计等 首先确保搭建一个vue3项目环境,从0开始的小伙伴着重看第一点: 一、搭建vue3项目环境 首先创建一个vue3vitets项目,可以查看下面相关…

头歌-机器学习实验 第8次实验 决策树

第1关:什么是决策树 任务描述 本关任务:根据本节课所学知识完成本关所设置的选择题。 相关知识 为了完成本关任务,你需要掌握决策树的相关基础知识。 引例 在炎热的夏天,没有什么比冰镇后的西瓜更能令人感到心旷神怡的了。现…

Spark-Scala语言实战(16)

在之前的文章中,我们学习了三道任务,运用之前学到的方法。想了解的朋友可以查看这篇文章。同时,希望我的文章能帮助到你,如果觉得我的文章写的不错,请留下你宝贵的点赞,谢谢。 Spark-Scala语言实战&#x…

使用doop识别近commons text漏洞的污点信息流

一、doop静态分析框架简介 1. doop静态分析框架简介 doop静态分析框架由希腊雅典大学plast-lab Yannis Smaragdakis团队设计开发,目前看是一款开源领域的比较先进的程序静态分析框架,一些程序静态分析论文的理论也有通过doop的规则实现后实验。 doop整…

c 解数独(通用方法,适用于9×9 数独)

折腾了一周时间,终于搞定99数独通用方法 思路:1.生成每行空位的值,也就是1-9中除去非0的数。 2.用行,列,宫判断每行中每个空位的最小取值范围后再重新生成每行。 3.随机提取生成的9行,判断每列之和是否等…

【数据结构与算法】:二叉树经典OJ

目录 1. 二叉树的前序遍历 (中,后序类似)2. 二叉树的最大深度3. 平衡二叉树4. 二叉树遍历 1. 二叉树的前序遍历 (中,后序类似) 这道题的意思是对二叉树进行前序遍历,把每个结点的值都存入一个数组中,并且返回这个数组。 思路&…