接上节:C/C++编程笔记:如何使用C++实现单链表?单链表第一部分。
单链表上的基本运算实现
(四) 求表长
由与我们的代码中已经定义过一个叫做 curLength 的变量用来记录我们的表长
所以我们可以直接返回,我们在定义中已经实现了,也就是这句:
int size()const {return curLength;}//返回单链表的当前实际长度
但是如果我们没有这样一个变量,我们想要实现这样的功能又是什么样的方法呢?
(五) 遍历单链表
我们需要从头到尾访问单链表中的每一个节点,并且输出其中数据域的信息。
(六) 按照位序 i 寻找其元素对应内存地址
设置一个移动工作指针,和一个计数器 count,初始时p指向头结点,每当指针p移向下一个结点的时候,计数器count + 1 ,直到 p指向位序为 i的节点为止。返回 p。
(七) 按值查询节点位序
设置一个移动工作指针,和一个计数器 count,从单链表的第一个节点开始,开始于给定的值进行比对,如果相等则查找成功,返回节点的位序,否则继续查询知道单链表结束,查询失败返回 -1。
(八) 插入节点
在位序为 i 出插入值为value 的新节点q,我们需要做的就是找到位序为i – 1 的节点p,让q指针域指向原来p的后继,然后修改p的后继为q即可,说白了也就是修改插入元素位置前后的元素指向关系就可以了。
(九) 删除节点
能看懂添加节点的方法,理解删除节点也是手到擒来。
单链表整表的创建
回顾我们前面认识的顺序表,它其实可以理解为一个数组,我们声明一个类型,同时给定值,初始化其大小,但是单链表就不一样了,它是一种动态组织,它不需要像顺序表一样元素集中,它可以随着实际的情况来动态生成节点,所以也不需要预先分配空间大小和位置。
(一) 头插法创建单链表
头插法的意思就是说,每次新增节点全部插在头结点之后,首元结点之前,你可以这样理解,我先来排队,但是后面来了人,他就会排到我的前面去,我们来借助图看一下:
我们一次插入元素 123 但实际上输出的是按照321的顺序存储的,也就是说和我们的逻辑顺序是相反的。
我们来看一看怎么实现它:
内置单链表
我们知道单链表中元素顺序与读入的顺序是相反的,我们可以通过逆置单链表的算法,帮助我们重新恢复我们的惯有思维顺序。
(二) 尾插法创建单链表
看完了头插法,但是感觉这样的顺序与我们一贯的思维总是有一点别扭,而尾插法则是一种,逻辑顺序与我们一致的创建方法。
还是看一下图:
合并单链表
要求:假设我们给出两个仍然是递增的单链表la和lb,我们将其合并为lc 仍保证递增,利用原表空间,但是我们仍在下面将表C称作新表。
因为我们的要求是递增的,所以使用尾插法是非常合适的,我们设计三个工作指针,分别指向两个表的首元结点,然后将第三个指针指向新表的头结点,比较前两个指针指向的值,小的就放到新表的表尾,然后后移动两表中较小的那一个的指针,以此类推,直到其中一个表尾空,将剩余的节点全部链接到新表的末尾。
总结
单链表,采取了链式存储结构,用一组任意的存储单元存放线性表的元素,尤其对于需要频繁的插入和删除数据的时候更加适用,如果需要进行频繁的查找还是推荐使用顺序表,例如对于一个学生成绩管理系统的制作,学生更多的时候是查看自己的成绩,而录入的老师,也只有在考试后录入一次,所以应该使用顺序表,而例如考勤打卡系统,更多的是打卡信息的记录,所以还是选择使用链表,当然例子可能不是很恰当,同时正常的开发中还会有更多复杂的问题需要考虑,举例子只为了利于理解。
自学C/C++编程难度很大,不妨和一些志同道合的小伙伴一起学习成长!
C语言C++编程学习交流圈子,关注+私信【C/C++编程】微信公众号:C语言编程学习基地
有一些源码和资料分享,欢迎转行也学习编程的伙伴,和大家一起交流成长会比自己琢磨更快哦!
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/86388.html