知识卡片

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

循环插移保持单节点自环

理解等级:中级

clist_ins_next(list,element,data)在给定节点后插入;空表时不依赖element而创建自环,按约定传NULL以免混淆。非空表需有效前驱,代码不会把NULL自动解释为头插。clist_rem_next(list,element,&out)移除其后继,成功0、失败-1,并交回数据地址。

最后一项移除后head为NULL;多项表移走原head时,要把head移到后继,保持剩余环。已知有效前驱时是固定步骤更新,寻找尾部或前驱仍可能需要遍历;数据释放仍按调用方约定。

72与02751-02752实际空分支new.next=new、head=new;非空分支new.next=element.next后element.next=new,最后size++。malloc失败在接入前返回-1;非空分支没有NULL检查,调用方必须给出有效表内位置,不误称无效位置都会返回失败。

73与02752实际代码先拒绝空表,再写出element.next.data。若element.next==element则清head,否则绕过后继并在目标是head时更新入口;free目标节点后size–。它不释放数据对象,也不检查非空element归属,不能把任意失效地址当可失败返回的普通输入。

76的循环表“头前插”通过已知尾后插在环中达到邻接目的,但实现并不会因此自动改head到新节点;若找尾还需另计遍历。双向表则可直接dlist_ins_prev(head,…),不把单链NULL头插规则套到所有类型。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      将元素插入由list指定的循环链表中element之后。当插入空链表中时,element可能指向任何位置,为了避免混淆,element此时应该设置为NULL。新的元素包含一个指向data的指针,因此只要该元素仍在链表中时,data所引用的内存空间就应该保持合法。由调用者负责管理data所引用的存储空

    • · 查看原书依据

      将所插入元素的next指针设置为指向它自己。这就允许循环遍历只有一个元素的链表。这也确保了之后元素的插入操作能够按照恰当的方式进行。 clist_ins_next的运行时复杂度为O(1),因为插入操作中的所有步骤都能够在恒定的时间内完成。

    • · 查看原书依据

      从单向循环链表中移除元素的过程同非循环的单链表类似。 clist_rem_next的运行时复杂度为O(1),因为移除操作中的所有步骤都能够在恒定的时间内完成。

    • · 查看原书依据

      将新结点插入尾部元素之后。记住,在循环链表中,尾部结点的next指针又指回了头结点。

    参考来源

    - 位置:《算法精解:C语言描述》第5章《循环链表接口的定义》(spine1222;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1189.html;u068-ch05-017)。 - 结论依据:68四项生命周期/插移接口与02742-02745原型已读,并对照74的02751-02752实现确认空表自环、非空element前提及状态返回。 - 原始内容:将元素插入由list指定的循环链表中element之后。当插入空链表中时,element可能指向任何位置,为了避免混淆,element此时应该设置为NULL。新的元素包含一个指向data的指针,因此只要该元素仍在链表中时,data所引用的内存空间就应该保持合法。由调用者负责管理data所引用的存储空 - 位置:《算法精解:C语言描述》第5章《clist_ins_next》(spine1225;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1192.html;u072-ch05-017)。 - 结论依据:72与02751-02752实际空分支new.next=new、head=new;非空分支new.next=element.next后element.next=new,最后size++。malloc失败在接入前返回-1;非空分支没有NULL检查,调用方必须给出有效表内位置,不误称无效位置都会返回失败。 - 原始内容:将所插入元素的next指针设置为指向它自己。这就允许循环遍历只有一个元素的链表。这也确保了之后元素的插入操作能够按照恰当的方式进行。 clist_ins_next的运行时复杂度为O(1),因为插入操作中的所有步骤都能够在恒定的时间内完成。 - 位置:《算法精解:C语言描述》第5章《clist_rem_next》(spine1226;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1193.html;u073-ch05-017)。 - 结论依据:73与02752实际代码先拒绝空表,再写出element.next.data。若element.next==element则清head,否则绕过后继并在目标是head时更新入口;free目标节点后size--。它不释放数据对象,也不检查非空element归属,不能把任意失效地址当可失败返回的普通输入。 - 原始内容:从单向循环链表中移除元素的过程同非循环的单链表类似。 clist_rem_next的运行时复杂度为O(1),因为移除操作中的所有步骤都能够在恒定的时间内完成。 - 位置:《算法精解:C语言描述》第5章《问与答》(spine1229;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1196.html;u076-ch05-017)。 - 结论依据:76的循环表“头前插”通过已知尾后插在环中达到邻接目的,但实现并不会因此自动改head到新节点;若找尾还需另计遍历。双向表则可直接dlist_ins_prev(head,...),不把单链NULL头插规则套到所有类型。 - 原始内容:将新结点插入尾部元素之后。记住,在循环链表中,尾部结点的next指针又指回了头结点。