What & How & Why

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版两侧同时换到之后的修订记录
dsa:notes:dahua_ds:3_linearlist [2017/03/24 23:48] – [6.4.单链表的插入] haregydsa:notes:dahua_ds:3_linearlist [2017/03/25 01:05] – [6.4.单链表的插入] haregy
行 196: 行 196:
   - 对 ''s'' 进行插入操作（详见上述代码）。   - 对 ''s'' 进行插入操作（详见上述代码）。
   - 程序成功执行，返回 ''0''。   - 程序成功执行，返回 ''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.总结===
 +学习完了线性表和链表，我们可以明确几个注意点：
 +  - 需要频繁查找的时候，使用线性表；而需要频繁插入删除的时候，使用单链表。
 +  - 如果不知道元素有多少，那么用单链表。如果事先知道长度，那么用线性表。
  
  • 最后更改: 2021/11/11 08:07
  • ©2022 YGwiki.com