差别

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

--- dsa:notes:dahua_ds:3_linearlist [2017/03/24 23:29] – [6.4.单链表的删除] haregy
+++ dsa:notes:dahua_ds:3_linearlist [2017/03/25 01:05] – [6.4.单链表的插入] haregy
@@ 行 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'' 个元素不存在。
+  - 否则查找成功，删除节点。
+  - 释放被删除节点的内存。
+  - 返回成功。
+===6.6.链表清空（销毁）===
+链表的删除和创建一样也需要遍历，同时也需要挨个的释放节点的内存。算法思路大概如下：
+  - 声明节点 ''p'' 和 节点 ''q''，''p'' 在这里总是代表当前需要释放的节点， ''q'' 则代表了下一个节点。
+  - 用 ''p'' 指向第一个节点。
+  - 循环：
+    - 用''q'' 指向 ''p'' 指向的节点的下一个节点。
+    - 释放 ''p'' 指向的节点。
+    - 将 ''q'' 指向的节点给 ''p''，使该节点在下一轮循环中被释放。
+===6.7.总结===
+学习完了线性表和链表，我们可以明确几个注意点：
+  - 需要频繁查找的时候，使用线性表；而需要频繁插入删除的时候，使用单链表。
+  - 如果不知道元素有多少，那么用单链表。如果事先知道长度，那么用线性表。

What & How & Why

[ About ]

[ My Links ]

[ Notice ]

页面工具

站点工具

用户工具

差别