邓俊辉《数据结构》-列表学习笔记
2021/12/9 23:48:52
本文主要是介绍邓俊辉《数据结构》-列表学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2021.12.9
向量&列表的关系
向量结构中各数据项的物理存放位置与逻辑次序完全对应,可通过秩直接访问对应的元素,即”循秩访问“。好像可以通过一个人的家庭住址找到那个人。
本章的列表跟向量虽然相似,都是构成一个线性的逻辑次序,但和向量不同,列表的物理地址可以是任意的。
静态储存
数据结构支持的操作,无非静态和动态两类。第二章基于向量的例如size()、get()就是静态操作,所需的是常数时间,而insert()、remove()等动态操作就需要线性时间。
这是为什么?是因为向量的物理地址是连续排列的,即”静态储存“
静态储存:可以使静态操作效率提升,但是局部动态操作的时候,就需要大动干戈,引起大范围的移动调整。
动态储存
而动态储存-要求各元素按照一定的次序排列,但对物理地址没有要求。那么动态储存如何确定各元素的地址? —> 通过指针or引用,来确定地址。
链表 linked list
一种典型的动态存储结构。
列表 list
列表节点-ADT接口
其中:pred()-当前节点前驱节点位置 succ()-当前节点后继节点位置
insertAsPred(e)-插入前驱节点,存入引用对象e,并返回新节点位置
insertAsSucc(e)-后继...
列表对象-ADT接口
size() 节点总数
first() last() -返回首尾节点位置
insertAsFirst(e)/insertAsLast(e)-e当作节点插入首末
insertBefore(p,e)/insertAfter(p,e)-将e当作节点p的直接前驱、直接后继插入
哨兵节点&首末节点
1.头节点header和尾节点trailer始终存在,对外不可见;
2.外部可见数据的首末节点:first/last node
//初始化 void List<T> ::init(){ header=new ListNode<T>; //创建头哨兵节点 trailer=new ListNode<T>; //创建末哨兵节点 //其中: header -> succ = trailer; header -> pred = NULL; trailer -> pred = header; trailer -> succ = NULL; }
有序列表 sorted list
回忆《向量》内容
向量中,有 原方法->优化->再优化,当时我们引入了一个last ,想复习的时候请查看:邓俊辉《数据结构》-向量学习笔记_flashinggg的博客-CSDN博客
向量无序 ->O(n²) 有序 -> O(n)
列表无序 ->O(n²) 有序->O(n) 得益于列表已经有了顺序。
选择排序 selectionsort
与起泡排序相似,但起泡排序效率太低了。
这篇关于邓俊辉《数据结构》-列表学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现