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
与起泡排序相似,但起泡排序效率太低了。