知识卡片

结构图卡 · 5654.d.1.b.4.o · 生成模型:未记录

循环链接需要另定遍历终点

理解等级:中级

循环链表把最后节点的next连回头节点,因而可反复沿链接访问,不用在NULL处停下;双向循环形式还可让头节点prev连回尾部,支持两个方向绕行。

这改变的是终点约定,不表示容器不能保存一个head作为入口。若要只走一圈,需要识别回到起点、计数或按任务定义停止条件;照搬非循环链表“遇NULL结束”的遍历会出问题。

本书后续实现为单向循环表,不保存tail字段;这一具体选择不等于所有循环链表都没有可识别的逻辑尾节点。

69的02750完整头文件给出真实类型:

结构图:

classDiagram
class CList {
 int size
 match : 比较回调
 destroy : 数据清理回调
 CListElmt* head
}
class CListElmt {
 void* data
 CListElmt_* next
}
class API["循环公开函数组(非类型)"] {
 clist_init(CList* list, destroy) void
 clist_destroy(CList* list) void
 clist_ins_next(CList* list, CListElmt* element, const void* data) int
 clist_rem_next(CList* list, CListElmt* element, void** data) int
}
CList --> CListElmt : head是入口
CListElmt --> CListElmt : next闭合为环
API ..> CList : 操作容器与节点

图中C函数组不是C类型或成员方法。实际标签为CList_/CListElmt_,别名去掉下划线;match为int(const void,const void),destroy为void(void*)。容器没有tail字段,是否形成有效环仍由操作维持,不是指针类型本身的保证。

77补充双向循环能正反绕行;67已给头prev与尾next闭合关系,本书实际代码仍只有单向CList,不把延伸主题当已实现DList环版本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      最后一个元素的next指针又指回头元素而不是设置为NULL。在双向循环链表中,头元素的prev指针则指向最后一个元素,这使得循环链表中的每个元素既可以看做头元素也可以看做尾元素。 和单向循环链表和双向循环链表不同,在遍历循环链表元素的时候不需要担心到达链表尾部而无法继续遍历下去了。相反,遍历过程会继

    • · 查看原书依据

      不包含tail成员。 示例5-6:循环链表抽象数据类型的头文件

    • · 查看原书依据

      双向循环链表 本章介绍的各种循环链表是单向的。双向循环链表允许正向和反向循环遍历结点。 链表数组 多维数组的一种动态表示方式。每个元素都包含额外的指针和位置信息来保证数组之间能够正确链接并能够访问。 广义表 广义表是一种为元素之间提供更灵活的链接关系的数据结构。例如,可能会在一组元素中用到多个指针来

    参考来源

    - 位置:《算法精解:C语言描述》第5章《循环链表介绍》(spine1221;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1188.html;u067-ch05-016)。 - 结论依据:67全文和02741尾接头示意图,区分无NULL终点与仍保留入口;双向回链是正文明确对照,未虚构其C实现。 - 原始内容:最后一个元素的next指针又指回头元素而不是设置为NULL。在双向循环链表中,头元素的prev指针则指向最后一个元素,这使得循环链表中的每个元素既可以看做头元素也可以看做尾元素。 和单向循环链表和双向循环链表不同,在遍历循环链表元素的时候不需要担心到达链表尾部而无法继续遍历下去了。相反,遍历过程会继 - 位置:《算法精解:C语言描述》第5章《循环链表的实现与分析》(spine1223;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1190.html;u069-ch05-016)。 - 结论依据:69的02750完整头文件给出真实类型: **结构图**: ```mermaid classDiagram class CList { int size match : 比较回调 destroy : 数据清理回调 CListElmt* head } class CListElmt { void* data CListElmt_* next } class API["循环公开函数组(非类型)"] { clist_init(CList* list, destroy) void clist_destroy(CList* list) void clist_ins_next(CList* list, CListElmt* element, const void* data) int clist_rem_next(CList* list, CListElmt* element, void** data) int } CList --> CListElmt : head是入口 CListElmt --> CListElmt : next闭合为环 API ..> CList : 操作容器与节点 ``` 图中C函数组不是C类型或成员方法。实际标签为CList_/CListElmt_,别名去掉下划线;match为int(const void*,const void*),destroy为void(void*)。容器没有tail字段,是否形成有效环仍由操作维持,不是指针类型本身的保证。 - 原始内容:不包含tail成员。 示例5-6:循环链表抽象数据类型的头文件 - 位置:《算法精解:C语言描述》第5章《相关主题》(spine1230;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1197.html;u077-ch05-016)。 - 结论依据:77补充双向循环能正反绕行;67已给头prev与尾next闭合关系,本书实际代码仍只有单向CList,不把延伸主题当已实现DList环版本。 - 原始内容:双向循环链表 本章介绍的各种循环链表是单向的。双向循环链表允许正向和反向循环遍历结点。 链表数组 多维数组的一种动态表示方式。每个元素都包含额外的指针和位置信息来保证数组之间能够正确链接并能够访问。 广义表 广义表是一种为元素之间提供更灵活的链接关系的数据结构。例如,可能会在一组元素中用到多个指针来