What & How & Why

您在这里: start » dsa » notes » dahua_ds » 3_linearlist

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
dsa:notes:dahua_ds:3_linearlist [2017/03/24 23:29] – [6.4.单链表的删除] haregydsa:notes:dahua_ds:3_linearlist [2021/11/11 08:07] (当前版本) – codinghare
行 1: 行 1:
-====线性表====+======线性表======
 大话数据结构 笔记 第三章\\ 大话数据结构 笔记 第三章\\
 <wrap em>我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！</wrap> <wrap em>我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！</wrap>
-===== ===== +---- 
-====1.线性表的定义====+====线性表的定义====
 线性表（List）是指的<wrap em>零个或者多个数据元素组成的有限序列</wrap>。它的特点体现在<wrap em>有序</wrap>和<wrap em>有限</wrap>上。用数学描述则有： 线性表（List）是指的<wrap em>零个或者多个数据元素组成的有限序列</wrap>。它的特点体现在<wrap em>有序</wrap>和<wrap em>有限</wrap>上。用数学描述则有：
 \\ \\
行 15: 行 15:
   * 线性表中的元素可以是一个元素，也可以是多个元素的合集。   * 线性表中的元素可以是一个元素，也可以是多个元素的合集。
   * 线性表中的所有元素必须是相同的类型。   * 线性表中的所有元素必须是相同的类型。
-====2.线性表的抽象数据类型====+====线性表的抽象数据类型====
 我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 //ADT// 呢？设想我们有一个队列，首先我们需要排队的人，其次我们需要指挥排队的人加入，离开，统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 //ADT// 格式来定义线性表就是： 我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 //ADT// 呢？设想我们有一个队列，首先我们需要排队的人，其次我们需要指挥排队的人加入，离开，统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 //ADT// 格式来定义线性表就是：
 <code> <code>
行 33: 行 33:
 </code> </code>
 上述基本是最基本的操作，我们可由这些基本操作组合衍生出一系列复杂的运算。 上述基本是最基本的操作，我们可由这些基本操作组合衍生出一系列复杂的运算。
-====3.线性表的顺序存储结构====+====线性表的顺序存储结构====
 线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性： 线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性：
   * 起始内存位置。   * 起始内存位置。
行 39: 行 39:
   * 当前 //List// 长度。   * 当前 //List// 长度。
 容量和长度是两个概念。容量指 //List// 最多能容纳元素，既占用的内存空间；而长度是指现阶段元素的个数，很可能会增长或者减少。我们可以看出来，长度在任意时间都是小于等于容量的。 容量和长度是两个概念。容量指 //List// 最多能容纳元素，既占用的内存空间；而长度是指现阶段元素的个数，很可能会增长或者减少。我们可以看出来，长度在任意时间都是小于等于容量的。
-===3.1.地址计算方法===+===地址计算方法===
 线性表的起始元素下标为 '0' 。每个元素对应的存储单元都有自己的起始地址；因此我们可以通过这样计算出第 i 个元素的地址： 线性表的起始元素下标为 '0' 。每个元素对应的存储单元都有自己的起始地址；因此我们可以通过这样计算出第 i 个元素的地址：
 <code> <code>
行 47: 行 47:
 </code> </code>
 我们可以看到无论存取哪个元素，只需要在常数时间内完成。我们通常把有这种特点的存储结构成为**随机存储结构**。 我们可以看到无论存取哪个元素，只需要在常数时间内完成。我们通常把有这种特点的存储结构成为**随机存储结构**。
-====4.顺序存储结构的插入与删除==== +====顺序存储结构的插入与删除==== 
-===4.1.获取元素===+===获取元素===
 要实现获取元的方法很简单，直接访问下标 ''i-1'' 即可。这个函数可以分两步骤设计： 要实现获取元的方法很简单，直接访问下标 ''i-1'' 即可。这个函数可以分两步骤设计：
   - 验证下标是否在有效范围以内。   - 验证下标是否在有效范围以内。
   - 如果在范围内，返回结果。   - 如果在范围内，返回结果。
-<code:cpp linenums:1>+<code cpp linenums:1>
 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];
 </code> </code>
-===4.2.插入操作===+===插入操作===
 有个很形象的词可以用来形容线性表的插入操作：**加塞**。想一想如果你加塞，那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数： 有个很形象的词可以用来形容线性表的插入操作：**加塞**。想一想如果你加塞，那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数：
   - 有效性验证：如果插入位置不合法，跑出异常。   - 有效性验证：如果插入位置不合法，跑出异常。
行 64: 行 64:
   - 从最后一个元素开始，往前遍历到第 ''i'' 个元素，把这些元素分别往后移动一位。   - 从最后一个元素开始，往前遍历到第 ''i'' 个元素，把这些元素分别往后移动一位。
   - 在 ''i'' 的位置插入新元素。   - 在 ''i'' 的位置插入新元素。
-<code:cpp linenums:1>+<code cpp linenums:1>
 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
 </code> </code>
-===4.2.删除操作===+===删除操作===
 还是刚才的例子。试想一下如果那个加塞的人被人赶出去了，那么所有的人都会往前站一位。\\ 还是刚才的例子。试想一下如果那个加塞的人被人赶出去了，那么所有的人都会往前站一位。\\
 \\ \\
行 84: 行 84:
   * 从被删除的元素开始遍历到表尾，分别把这区域的元素都往前移动一位。   * 从被删除的元素开始遍历到表尾，分别把这区域的元素都往前移动一位。
   * 表长减去1。   * 表长减去1。
-<code:cpp linenums:1>+<code cpp linenums:1>
 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;
 </code> </code>
-===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 语言中这个信息被称为指针。所以链式存储中，我们的元素实际上分成了两部分：**数据部分**和**指针部分**。我们把每一个这样的元素称为一个节点（//node//）, 而所有这些节点串起来，就形成了一个链式的线性表，简称链表（//linked_list//)： 相比起物理结构为线性的 //List//, 链式存储结构则采用了类似于上下线的关系来处理 //List// 的物理结构，也就是逻辑上连续，物理上不连续。为了表示 $a_i$ 和 $a_{i+1}$ 的关系，我们必须需要一个数据使得我们可以从 $a_i$ 找到 $a_{i+1}$ 。在 C 语言中这个信息被称为指针。所以链式存储中，我们的元素实际上分成了两部分：**数据部分**和**指针部分**。我们把每一个这样的元素称为一个节点（//node//）, 而所有这些节点串起来，就形成了一个链式的线性表，简称链表（//linked_list//)：
 \\ \\
行 119: 行 119:
 \\ \\
 实际操作中为了方便，我们会定义一个不带任何数据的头结点，只包含指针的信息（或者附带链表的长度信息等等）。 实际操作中为了方便，我们会定义一个不带任何数据的头结点，只包含指针的信息（或者附带链表的长度信息等等）。
-====6.链表的实现==== +====链表的实现==== 
-===6.1.链表的数据===+===链表的数据===
 根据上面的描述，我们需要先定义链表的 Data 模型：具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构： 根据上面的描述，我们需要先定义链表的 Data 模型：具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构：
-<code:cpp linenums:1>+<code cpp linenums:1>
 struct Node { struct Node {
     int data;      int data; 
行 128: 行 128:
 } }
 </code> </code>
-===6.2.链表的创建===+===链表的创建===
 从我们先前对链表的理解来看，它的存储结构很松散；而我们也注意到对链表的插入/删除并不会对其他节点造成内存地址上的改动。这些特性让我们可以对链表进行动态的数据分配，即可以以很小的代价对表进行扩大，缩小，而内存的分配也会按照需要的大小来添加删除。 从我们先前对链表的理解来看，它的存储结构很松散；而我们也注意到对链表的插入/删除并不会对其他节点造成内存地址上的改动。这些特性让我们可以对链表进行动态的数据分配，即可以以很小的代价对表进行扩大，缩小，而内存的分配也会按照需要的大小来添加删除。
 \\ \\
行 138: 行 138:
   * 如果链表为空，建立初始节点（头节点）   * 如果链表为空，建立初始节点（头节点）
   * 如果链表非空，建立新节点，并用前一个节点指向新节点。   * 如果链表非空，建立新节点，并用前一个节点指向新节点。
-<code:cpp linenums:1>+<code cpp linenums:1>
 Linklist p, r; Linklist p, r;
 *L = （LinkList）malloc( sizeof(Node)); //apply memory for LinkList *L = （LinkList）malloc( sizeof(Node)); //apply memory for LinkList
行 157: 行 157:
   - 如果到了链表的尾部, ''p''的数据部分为空，那证明没有找到第 ''i'' 个元素。   - 如果到了链表的尾部, ''p''的数据部分为空，那证明没有找到第 ''i'' 个元素。
   - 否则的话，''i'' 的元素应该存到了 ''p'' 里面，这时我们返回 ''p''的值就可以。   - 否则的话，''i'' 的元素应该存到了 ''p'' 里面，这时我们返回 ''p''的值就可以。
-<code:cpp linenums>+<code cpp linenums>
 LinkList p; LinkList p;
 p = (*L).next(); p = (*L).next();
行 173: 行 173:
 相比起链表的读取和存储，单链表的插入和删除操作都显得简单了许多： 相比起链表的读取和存储，单链表的插入和删除操作都显得简单了许多：
 \\ \\
-\\{{:dsa:notes:dahua_ds:insert.jpg|}}+\\ 
 +{{ :dsa:notes:dahua_ds:insert.jpg?600 |}} 
 +\\ 
 +\\ 
 +大致的顺序是： 
 +  - 先将新节点指向目标节点。 
 +  - 再将前驱结点指向新节点。 
 +用代码可以表示为： 
 +<code cpp linenums:1> 
 +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 
 +</code> 
 +注意，这里**不能交换操作的顺序**。试想一下如果我们先让前驱结点指向新节点，那么指向 ''rear'' 的指针信息会被新节点的信息覆盖，从而造成链表断链。 
 +\\ 
 +\\ 
 +实现链表插入第 $i$ 个数据的的流程如下： 
 +  - 初始化：建立一个节点 ''p'' 并指向链表的第一个节点。 
 +  - 声明自变量 ''j'', 当 ''j < i'' （未达到插入位置）的时候， 让 ''p'' 的指针向后移动，并累加 ''j''。 
 +  - 如果找到链表末尾 ''p'' 依然为空，证明该链表没有第 ''i'' 个元素，返回错误。 
 +  - 如果查找成功，则建立一个空节点 ''s''。 
 +  - 将值赋予空节点 ''s''。 
 +  - 对 ''s'' 进行插入操作（详见上述代码）。 
 +  - 程序成功执行，返回 ''0''。 
 +===6.5.单链表的删除=== 
 +单链表的删除则更简单了，只需要把要删除的节点的前驱结点直接指向要删除节点的后置节点就可以： 
 +\\ 
 +\\ 
 +{{ :dsa:notes:dahua_ds:delete.jpg?600 |}} 
 +\\ 
 +\\ 
 +用代码可以表示为： 
 +<code cpp linenums:1> 
 +front -> next = new -> next; 
 +</code> 
 +注意：<wrap em>被删除的节点必须要释放内存。</wrap> 
 +实现链表删除第 $i$ 个数据的的流程如下： 
 +  - 初始化：创建节点 ''p'' 指向链表第一个节点，初始化 ''j'' 从 ''1'' 开始。 
 +  - 当 ''j < i'' 时就遍历链表，让 ''p'' 的指针往后移动，不断指向下一个节点， ''j'' 自加。 
 +  - 如果到链表末尾 ''p'' 为空，证明第 ''i'' 个元素不存在。 
 +  - 否则查找成功，删除节点。 
 +  - 释放被删除节点的内存。 
 +  - 返回成功。 
 +===链表清空（销毁）=== 
 +链表的删除和创建一样也需要遍历，同时也需要挨个的释放节点的内存。算法思路大概如下： 
 +  - 声明节点 ''p'' 和 节点 ''q''，''p'' 在这里总是代表当前需要释放的节点， ''q'' 则代表了下一个节点。 
 +  - 用 ''p'' 指向第一个节点。 
 +  - 循环： 
 +    - 用''q'' 指向 ''p'' 指向的节点的下一个节点。 
 +    - 释放 ''p'' 指向的节点。 
 +    - 将 ''q'' 指向的节点给 ''p''，使该节点在下一轮循环中被释放。 
 +====总结==== 
 +学习完了线性表和链表，我们可以明确几个注意点： 
 +  - 需要频繁查找的时候，使用线性表；而需要频繁插入删除的时候，使用单链表。 
 +  - 如果不知道元素有多少，那么用单链表。如果事先知道长度，那么用线性表。 
  • 最后更改: 2018/09/24 15:30
  • ©2022 YGwiki.com