知识卡片

问题卡 · 5654.d.1.b.4.n · 生成模型:未记录

双向前插须接好新节点后继

理解等级:中级

在非空双向链表中前插一个新节点,若只设置它的prev,却没有把next指向原element,正向遍历会从新节点读到未初始化的后继。前驱已经指向新节点,并不能弥补这一缺口。

02739的dlist_ins_prev非空分支正有这个遗漏:设new_element->prev=element->prev后更新head或前驱next,再改element->prev,但没有给new_element->next赋值。空表分支则同时设了两向NULL,不是同一问题。

修复方向是接入前先设置new_element->next=element,并保留/接好两侧引用;之后核对头插、中间前插的正反遍历与数量。此处是从已读代码推导的缺陷和验证计划,未修改原书或执行测试。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法精解:C语言描述》第5章《dlist_size、dlist_head、dlist_tail、dlist_is_head、dlist_is_tail、dlist_next以及dlist_prev》(spine1220;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1187.html;u066-ch05-015)。 - 结论依据:66完整02737-02740实际逐图读取;02739显示ins_prev非空分支缺next赋值,前后插两个分支对照支持根因。修复与验证是明确的读者推导,不冒充作者已运行结论。 - 原始内容:示例5-5:双向链表抽象数据类型的实现