本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
dsa:notes:dahua_ds:3_linearlist [2017/03/24 04:36] – [5.1.3链表的读取] haregy | dsa:notes:dahua_ds:3_linearlist [2021/11/11 08:07] (当前版本) – codinghare | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ====线性表==== | + | ======线性表====== |
大话数据结构 笔记 第三章\\ | 大话数据结构 笔记 第三章\\ | ||
<wrap em> | <wrap em> | ||
- | ===== ===== | + | ---- |
- | ====1.线性表的定义==== | + | ====线性表的定义==== |
线性表(List)是指的< | 线性表(List)是指的< | ||
\\ | \\ | ||
行 15: | 行 15: | ||
* 线性表中的元素可以是一个元素,也可以是多个元素的合集。 | * 线性表中的元素可以是一个元素,也可以是多个元素的合集。 | ||
* 线性表中的所有元素必须是相同的类型。 | * 线性表中的所有元素必须是相同的类型。 | ||
- | ====2.线性表的抽象数据类型==== | + | ====线性表的抽象数据类型==== |
我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 //ADT// 呢?设想我们有一个队列,首先我们需要排队的人,其次我们需要指挥排队的人加入,离开,统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 //ADT// 格式来定义线性表就是: | 我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 //ADT// 呢?设想我们有一个队列,首先我们需要排队的人,其次我们需要指挥排队的人加入,离开,统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 //ADT// 格式来定义线性表就是: | ||
< | < | ||
行 33: | 行 33: | ||
</ | </ | ||
上述基本是最基本的操作,我们可由这些基本操作组合衍生出一系列复杂的运算。 | 上述基本是最基本的操作,我们可由这些基本操作组合衍生出一系列复杂的运算。 | ||
- | ====3.线性表的顺序存储结构==== | + | ====线性表的顺序存储结构==== |
线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性: | 线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性: | ||
* 起始内存位置。 | * 起始内存位置。 | ||
行 39: | 行 39: | ||
* 当前 //List// 长度。 | * 当前 //List// 长度。 | ||
容量和长度是两个概念。容量指 //List// 最多能容纳元素,既占用的内存空间;而长度是指现阶段元素的个数,很可能会增长或者减少。我们可以看出来,长度在任意时间都是小于等于容量的。 | 容量和长度是两个概念。容量指 //List// 最多能容纳元素,既占用的内存空间;而长度是指现阶段元素的个数,很可能会增长或者减少。我们可以看出来,长度在任意时间都是小于等于容量的。 | ||
- | ===3.1.地址计算方法=== | + | ===地址计算方法=== |
线性表的起始元素下标为 ' | 线性表的起始元素下标为 ' | ||
< | < | ||
行 47: | 行 47: | ||
</ | </ | ||
我们可以看到无论存取哪个元素,只需要在常数时间内完成。我们通常把有这种特点的存储结构成为**随机存储结构**。 | 我们可以看到无论存取哪个元素,只需要在常数时间内完成。我们通常把有这种特点的存储结构成为**随机存储结构**。 | ||
- | ====4.顺序存储结构的插入与删除==== | + | ====顺序存储结构的插入与删除==== |
- | ===4.1.获取元素=== | + | ===获取元素=== |
要实现获取元的方法很简单,直接访问下标 '' | 要实现获取元的方法很简单,直接访问下标 '' | ||
- 验证下标是否在有效范围以内。 | - 验证下标是否在有效范围以内。 | ||
- 如果在范围内,返回结果。 | - 如果在范围内,返回结果。 | ||
- | <code:cpp linenums: | + | <code cpp linenums: |
if (L.length == 0 || i < 1 || i > L.length) { | if (L.length == 0 || i < 1 || i > L.length) { | ||
return -1; | return -1; | ||
行 58: | 行 58: | ||
return L.data[i-1]; | return L.data[i-1]; | ||
</ | </ | ||
- | ===4.2.插入操作=== | + | ===插入操作=== |
有个很形象的词可以用来形容线性表的插入操作:**加塞**。想一想如果你加塞,那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数: | 有个很形象的词可以用来形容线性表的插入操作:**加塞**。想一想如果你加塞,那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数: | ||
- 有效性验证:如果插入位置不合法,跑出异常。 | - 有效性验证:如果插入位置不合法,跑出异常。 | ||
行 64: | 行 64: | ||
- 从最后一个元素开始,往前遍历到第 '' | - 从最后一个元素开始,往前遍历到第 '' | ||
- 在 '' | - 在 '' | ||
- | <code:cpp linenums: | + | <code cpp linenums: |
if(L.length == MAXSIZE) //check if list is full | if(L.length == MAXSIZE) //check if list is full | ||
return -1; | return -1; | ||
行 76: | 行 76: | ||
++L.length; // renew the length | ++L.length; // renew the length | ||
</ | </ | ||
- | ===4.2.删除操作=== | + | ===删除操作=== |
还是刚才的例子。试想一下如果那个加塞的人被人赶出去了,那么所有的人都会往前站一位。\\ | 还是刚才的例子。试想一下如果那个加塞的人被人赶出去了,那么所有的人都会往前站一位。\\ | ||
\\ | \\ | ||
行 84: | 行 84: | ||
* 从被删除的元素开始遍历到表尾,分别把这区域的元素都往前移动一位。 | * 从被删除的元素开始遍历到表尾,分别把这区域的元素都往前移动一位。 | ||
* 表长减去1。 | * 表长减去1。 | ||
- | <code:cpp linenums: | + | <code cpp linenums: |
if (i < 1 || i > L.length) //check if element is in range | if (i < 1 || i > L.length) //check if element is in range | ||
return -1; | return -1; | ||
行 93: | 行 93: | ||
return 0; | return 0; | ||
</ | </ | ||
- | ===4.3.List操作的时间复杂度=== | + | ===List操作的时间复杂度=== |
我们来看一看插入删除的各种情况: | 我们来看一看插入删除的各种情况: | ||
- 最好情况:插入删除的元素都在 //List// 的尾部,因此我们不需要挪动元素,算法复杂度为$O(1)$。 | - 最好情况:插入删除的元素都在 //List// 的尾部,因此我们不需要挪动元素,算法复杂度为$O(1)$。 | ||
行 108: | 行 108: | ||
* 插入删除开销非常大 | * 插入删除开销非常大 | ||
* 表长度变化较大时,存储空间容量不好确定,同时也容易造成存储空间的碎片。 | * 表长度变化较大时,存储空间容量不好确定,同时也容易造成存储空间的碎片。 | ||
- | ====5.线性空间的链式存储结构==== | + | ====线性空间的链式存储结构==== |
相比起物理结构为线性的 //List//, 链式存储结构则采用了类似于上下线的关系来处理 //List// 的物理结构,也就是逻辑上连续,物理上不连续。为了表示 $a_i$ 和 $a_{i+1}$ 的关系,我们必须需要一个数据使得我们可以从 $a_i$ 找到 $a_{i+1}$ 。在 C 语言中这个信息被称为指针。所以链式存储中,我们的元素实际上分成了两部分:**数据部分**和**指针部分**。我们把每一个这样的元素称为一个节点(// | 相比起物理结构为线性的 //List//, 链式存储结构则采用了类似于上下线的关系来处理 //List// 的物理结构,也就是逻辑上连续,物理上不连续。为了表示 $a_i$ 和 $a_{i+1}$ 的关系,我们必须需要一个数据使得我们可以从 $a_i$ 找到 $a_{i+1}$ 。在 C 语言中这个信息被称为指针。所以链式存储中,我们的元素实际上分成了两部分:**数据部分**和**指针部分**。我们把每一个这样的元素称为一个节点(// | ||
\\ | \\ | ||
行 119: | 行 119: | ||
\\ | \\ | ||
实际操作中为了方便,我们会定义一个不带任何数据的头结点,只包含指针的信息(或者附带链表的长度信息等等)。 | 实际操作中为了方便,我们会定义一个不带任何数据的头结点,只包含指针的信息(或者附带链表的长度信息等等)。 | ||
- | ===5.1.链表的实现=== | + | ====链表的实现==== |
- | ==5.1.1.链表的数据== | + | ===链表的数据=== |
根据上面的描述,我们需要先定义链表的 Data 模型:具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构: | 根据上面的描述,我们需要先定义链表的 Data 模型:具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构: | ||
- | <code:cpp linenums: | + | <code cpp linenums: |
struct Node { | struct Node { | ||
int data; | int data; | ||
行 128: | 行 128: | ||
} | } | ||
</ | </ | ||
- | ==5.1.2.链表的创建== | + | ===链表的创建=== |
从我们先前对链表的理解来看,它的存储结构很松散;而我们也注意到对链表的插入/ | 从我们先前对链表的理解来看,它的存储结构很松散;而我们也注意到对链表的插入/ | ||
\\ | \\ | ||
行 138: | 行 138: | ||
* 如果链表为空,建立初始节点(头节点) | * 如果链表为空,建立初始节点(头节点) | ||
* 如果链表非空,建立新节点,并用前一个节点指向新节点。 | * 如果链表非空,建立新节点,并用前一个节点指向新节点。 | ||
- | <code:cpp linenums: | + | <code cpp linenums: |
Linklist p, r; | Linklist p, r; | ||
*L = (LinkList)malloc( sizeof(Node)); | *L = (LinkList)malloc( sizeof(Node)); | ||
行 151: | 行 151: | ||
</ | </ | ||
r -> next = p 在这里是将表尾终端的指针指向新的节点p。 而 '' | r -> next = p 在这里是将表尾终端的指针指向新的节点p。 而 '' | ||
- | ==5.1.3链表的读取== | + | ===6.3.单链表的读取=== |
+ | 由于链表中的元素除了第一个元素,其他的元素都需要自己的前驱来确定自己的位置;因此**单链表的读取必须从头开始**,通过遍历来找到所需要的元素。我们的思路大概如下: | ||
+ | - 声明一个节点 '' | ||
+ | - 当目前元素还没有接近到目标元素(第 '' | ||
+ | - 如果到了链表的尾部, | ||
+ | - 否则的话,'' | ||
+ | <code cpp linenums> | ||
+ | LinkList p; | ||
+ | p = (*L).next(); | ||
+ | j = 1; | ||
+ | while(p && j < i) { | ||
+ | p = p.next(); | ||
+ | ++j; | ||
+ | if ( !p || j>i) { | ||
+ | | ||
+ | } | ||
+ | return p.data() // got element content from i | ||
+ | } | ||
+ | </ | ||
+ | ===6.4.单链表的插入=== | ||
+ | 相比起链表的读取和存储,单链表的插入和删除操作都显得简单了许多: | ||
+ | \\ | ||
+ | \\ | ||
+ | {{ : | ||
+ | \\ | ||
+ | \\ | ||
+ | 大致的顺序是: | ||
+ | - 先将新节点指向目标节点。 | ||
+ | - 再将前驱结点指向新节点。 | ||
+ | 用代码可以表示为: | ||
+ | <code cpp linenums: | ||
+ | new -> next = front -> next; // copy the pointer info from front node to new node, use the info point to the rear node | ||
+ | front -> next = new; // then let front point to the new node | ||
+ | </ | ||
+ | 注意,这里**不能交换操作的顺序**。试想一下如果我们先让前驱结点指向新节点,那么指向 '' | ||
+ | \\ | ||
+ | \\ | ||
+ | 实现链表插入第 $i$ 个数据的的流程如下: | ||
+ | - 初始化:建立一个节点 '' | ||
+ | - 声明自变量 '' | ||
+ | - 如果找到链表末尾 '' | ||
+ | - 如果查找成功,则建立一个空节点 '' | ||
+ | - 将值赋予空节点 '' | ||
+ | - 对 '' | ||
+ | - 程序成功执行,返回 '' | ||
+ | ===6.5.单链表的删除=== | ||
+ | 单链表的删除则更简单了,只需要把要删除的节点的前驱结点直接指向要删除节点的后置节点就可以: | ||
+ | \\ | ||
+ | \\ | ||
+ | {{ : | ||
+ | \\ | ||
+ | \\ | ||
+ | 用代码可以表示为: | ||
+ | <code cpp linenums: | ||
+ | front -> next = new -> next; | ||
+ | </ | ||
+ | 注意:< | ||
+ | 实现链表删除第 $i$ 个数据的的流程如下: | ||
+ | - 初始化:创建节点 '' | ||
+ | - 当 '' | ||
+ | - 如果到链表末尾 '' | ||
+ | - 否则查找成功,删除节点。 | ||
+ | - 释放被删除节点的内存。 | ||
+ | - 返回成功。 | ||
+ | ===链表清空(销毁)=== | ||
+ | 链表的删除和创建一样也需要遍历,同时也需要挨个的释放节点的内存。算法思路大概如下: | ||
+ | - 声明节点 '' | ||
+ | - 用 '' | ||
+ | - 循环: | ||
+ | - 用'' | ||
+ | - 释放 '' | ||
+ | - 将 '' | ||
+ | ====总结==== | ||
+ | 学习完了线性表和链表,我们可以明确几个注意点: | ||
+ | - 需要频繁查找的时候,使用线性表;而需要频繁插入删除的时候,使用单链表。 | ||
+ | - 如果不知道元素有多少,那么用单链表。如果事先知道长度,那么用线性表。 | ||