差别

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

--- dsa:notes:dahua_ds:3_linearlist [2017/03/24 23:30] – [6.4.单链表的插入] haregy
+++ dsa:notes:dahua_ds:3_linearlist [2017/03/24 23:48] – [6.4.单链表的插入] haregy
@@ 行 174: / 行 174: @@
 \\
 \\
-{{:dsa:notes:dahua_ds:insert.jpg?600|}}
+{{ :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''。

What & How & Why