知识卡片
循环插移保持单节点自环
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 条
还没有人提交反馈。
在整书笔记中的位置
- · 循环插移保持单节点自环
- · clist_ins_next
- · clist_rem_next
- · 问与答
原书出处 · 4 处
- · 查看原书依据
将元素插入由list指定的循环链表中element之后。当插入空链表中时,element可能指向任何位置,为了避免混淆,element此时应该设置为NULL。新的元素包含一个指向data的指针,因此只要该元素仍在链表中时,data所引用的内存空间就应该保持合法。由调用者负责管理data所引用的存储空
- · 查看原书依据
将所插入元素的next指针设置为指向它自己。这就允许循环遍历只有一个元素的链表。这也确保了之后元素的插入操作能够按照恰当的方式进行。 clist_ins_next的运行时复杂度为O(1),因为插入操作中的所有步骤都能够在恒定的时间内完成。
- · 查看原书依据
从单向循环链表中移除元素的过程同非循环的单链表类似。 clist_rem_next的运行时复杂度为O(1),因为移除操作中的所有步骤都能够在恒定的时间内完成。
- · 查看原书依据
将新结点插入尾部元素之后。记住,在循环链表中,尾部结点的next指针又指回了头结点。