邓俊辉《数据结构》-列表学习笔记

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

与起泡排序相似,但起泡排序效率太低了。

上一篇:Source Insight 4奔溃并跳出dmp文件解决


下一篇:使用PHPExcel实现Excel文件的导入和导出(模板导出) (转载自用)