知识卡片

操作参考卡 · 5654.d.1.b.4.e · 生成模型:未记录

单链插移接口围绕前驱

理解等级:中级

list_ins_next(list,element,data)在element之后插入,element为NULL时插到头部;list_rem_next(list,element,&out)移除element之后的节点,NULL时移除头部,并通过真正void*输出变量out交还数据地址。二者成功返回0,失败返回-1。

这组接口操作的是“某节点之后”,不是把element自身删掉。已有正确前驱时,链接更新可按常数步骤完成;寻找前驱或目标的遍历不包含在这个O(1)承诺里。调用方仍要提供属于该表的有效位置,插入的数据在节点存在期间须保持合法。

76讨论把后继数据拷贝进当前节点再删后继的技巧:它改变节点与数据的对应关系,让外部保存的引用语义发生变化,也不能普遍用于没有后继的尾节点。不能只凭O(1)宣称与精确删除当前对象等价;_rem_next和_remove分别表达目标。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      element设置为NULL,则新元素插入链表头部。新元素包含一个指向data的指针,因此只要该元素还在链表中,data所引用的内存空间就应该保持合法。管理data所引用的存储空间是调用者的责任。 复杂度 O(1) list_rem_next 返回值 如果移除元素成功则返回0,否则返回-1。 描述

    • · 查看原书依据

      后继结点的数据拷贝到指定元素中,然后移除后继结点。这貌似良好的O(1)方法导致危险的负面影响:使指向链表的指针失效。对于维护指向该元素的一个指针的开发人员来说,在认为该元素需要删除之后,他会大吃一惊。该方法的缺点是它与双向链表实现的dlist_remove操作不一致。不管如何,都需要由命名约定来修饰

    参考来源

    - 位置:《算法精解:C语言描述》第5章《单链表接口的定义》(spine1206;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1173.html;u050-ch05-006)。 - 结论依据:50插入/移除两节与02702-02703原型,返回值、NULL特殊含义、数据存活及调用方责任完整核对;输出适配沿第2章已纠正的void**规则。 - 原始内容:element设置为NULL,则新元素插入链表头部。新元素包含一个指向data的指针,因此只要该元素还在链表中,data所引用的内存空间就应该保持合法。管理data所引用的存储空间是调用者的责任。 复杂度 O(1) list_rem_next 返回值 如果移除元素成功则返回0,否则返回-1。 描述 - 位置:《算法精解:C语言描述》第5章《问与答》(spine1229;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1196.html;u076-ch05-006)。 - 结论依据:76讨论把后继数据拷贝进当前节点再删后继的技巧:它改变节点与数据的对应关系,让外部保存的引用语义发生变化,也不能普遍用于没有后继的尾节点。不能只凭O(1)宣称与精确删除当前对象等价;_rem_next和_remove分别表达目标。 - 原始内容:后继结点的数据拷贝到指定元素中,然后移除后继结点。这貌似良好的O(1)方法导致危险的负面影响:使指向链表的指针失效。对于维护指向该元素的一个指针的开发人员来说,在认为该元素需要删除之后,他会大吃一惊。该方法的缺点是它与双向链表实现的dlist_remove操作不一致。不管如何,都需要由命名约定来修饰