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

向右看齐 2023-10-01 08:58 14阅读 0赞

## 2021.12.9 ##

### 向量&列表的关系 ###

向量结构中各数据项的物理存放位置与逻辑次序完全对应，可通过秩直接访问对应的元素，即”循秩访问“。好像可以通过一个人的家庭住址找到那个人。

本章的**列表**跟向量虽然相似，都是构成一个线性的逻辑次序，但和向量不同，列表的物理地址可以是任意的。

#### 静态储存 ####

数据结构支持的操作，无非静态和动态两类。第二章基于向量的例如size()、get()就是静态操作，所需的是常数时间，而insert()、remove()等动态操作就需要线性时间。

这是为什么？是因为向量的物理地址是连续排列的，即”**静态储存**“

**静态储存：**可以使静态操作效率提升，但是局部动态操作的时候，就需要大动干戈，引起大范围的移动调整。

#### 动态储存 ####

而**动态储存**\-要求各元素按照一定的次序排列，但对物理地址没有要求。那么**动态储存如何确定各元素的地址？** —> 通过指针或者引用，来确定地址。

### 链表 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博客][-_flashinggg_-CSDN]

向量无序 ->O(n²) 有序 -> O(n)

列表无序 ->O(n²) 有序->O(n) 得益于列表已经有了顺序。

### 选择排序 selectionsort ###

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

##  ##

[-_flashinggg_-CSDN]: https://blog.csdn.net/qq_41835314/article/details/121774867

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

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

2021.12.9 向量&列表的关系向量结构中各数据项的物理存放位置与逻辑次序完全对应，可通过秩直接访问对应的元素，即”循秩访问“。好像可以通过一个人的家庭住址找

向右看齐/ 2023年10月01日 08:58/ 0 赞/ 15 阅读

相关邓俊辉《数据结构》-向量学习笔记

目录 2021.12.7 星期二向量数组与向量简单理解什么是泛化？理解什么是接口？向量的ADT操作接口有序向量唯一化-去重有序向量的二分查找

今天药忘吃喽~/ 2023年10月01日 08:43/ 0 赞/ 19 阅读

相关邓俊辉《数据结构》-复杂度/递归学习笔记

目录 2021.12.4 星期六冒泡排序 bubblesort swap()函数迭代与递归 2021.12.6 星期一 1<<2 分而治之 fib()

ゝ一世哀愁。/ 2023年10月01日 08:23/ 0 赞/ 22 阅读

相关数据结构学习笔记 - 散列表(Hash表)

散列表(Hash表) 简介散列表依赖的是数组支持按下标随机访问数据的特性所以散列表是数组的一种扩展, 由数组演化而来, 如果没有数组就没有散列表时间复

冷不防/ 2022年12月27日 02:26/ 0 赞/ 174 阅读

相关清华邓俊辉教授数据结构&算法课程内容

![70][] [70]: /images/20220508/2a19ef4d4e7d49808f5f62e7246a827c.png

叁歲伎倆/ 2022年05月08日 10:22/ 0 赞/ 234 阅读

相关数据结构学习笔记

这两天还没有接到一个面试，感觉一点希望都没有。做笔试时感觉自己数据结构很差，什么都不太懂，回来看有个知乎涛吴，讲的关于数据结构，Java，c++的形象比喻，让我豁然开朗。也让我

红太狼/ 2022年04月24日 02:10/ 0 赞/ 344 阅读

相关数据结构学习笔记

一、链表 1、基本特征：内存节点是不连续的，节点之间通过指针彼此关联。 2、基本操作：追加、插入、删除、遍历、伪随机访问！ 3、实现要点 1）追加：

梦里梦外;/ 2021年11月29日 06:00/ 0 赞/ 483 阅读

相关 Python文档学习笔记（5）--数据结构 --列表(1)

列表数据类型还有更多的方法。这里是列表对象方法的清单： `list.``append`(x) 添加一个元素到列表的末尾。相当于 `a[len(a):] = [x]`. `

左手的ㄟ右手/ 2021年11月11日 11:54/ 0 赞/ 412 阅读

相关 Python学习笔记--杨辉三角

这两天在LeetCode遇到了杨辉三角这个题记录一下杨辉三角的迭代算法杨辉三角创建一个二维的列表 num = [[1]] 由输入

╰半夏微凉°/ 2021年09月28日 21:58/ 0 赞/ 402 阅读

相关数据结构学习笔记

复杂度时间复杂度(time complexity)：估算程序指令的执行次数（执行时间）大O表示法（Big O）一般用大O表示法来描述复杂度，它表示的是数据规

た入场券/ 2021年08月29日 14:36/ 0 赞/ 587 阅读