知识卡片

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

链表查询宏只读现有状态

理解等级:中级

list_size、list_head和list_tail读取容器里保存的数量及端点,list_data与list_next读取节点数据与后继;它们不必重新遍历链表。查询的正确性依赖更新操作已经同步维护这些字段。

头尾判断要以真实宏定义为准。02712中list_is_head(list,element)比较element与list->head,list_is_tail(element)检查element->next是否NULL,结果都是1或0;前面的接口表把参数数目和失败返回写错,不能照抄-1。尾判断也只是局部next检测,不独立证明节点属于给定表;节点参数必须有效。

56把这些操作概括为访问/检测字段。list_size返回已维护size,未遍历;list_is_tail仅测next为NULL,list_is_head比较head。公开宏使调用方依赖字段表示,不能把它们当语言强制隐藏实现细节的屏障。

59至60的实际dlist.h中dlist_is_head(element)测prev==NULL,dlist_is_tail(element)测next==NULL,均返回1/0,接口表尾判断写0/-1不符。dlist_prev与dlist_next分别读前后链接;size/head/tail/data也只是字段访问,不额外证明节点属于哪张表。

66完整代码维持size,宏仅读取它;端点判断在dlist.h已确定1/0。全文代码的存在也揭示前插缺next赋值,因而不能从字段查询简单推断结构一定正确。

68的clist_size/head/data/next只读保存字段。循环结构没有tail查询宏,并非任何节点的next为NULL就能表示末尾;按实际环结构使用next,不照搬list_is_tail。

74的02751-02752代码没有额外的尾部检测,size由成功插入/移除维护。遍历次数、回到起点等停止条件属于调用方任务,不由clist_next自动决定;宏O(1)不代表一次完整环遍历也O(1)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 6 处

    • · 查看原书依据

      这是一个宏,用来计算由参数list指定的链表中元素的个数。 复杂度 O(1) list_head 返回值 指向链表中头元素的指针。 描述 这是一个宏,返回由参数list指定的链表中头元素的指针。 复杂度 O(1) list_tail 返回值 指向链表中尾元素的指针。 描述 这是一个宏,返回由参数li

    • · 查看原书依据

      List和ListElmt结构体中成员的能力。 这些操作的运行时复杂度都是O(1),因为访问和检测结构体的成员都可以在恒定的时间内完成。

    • · 查看原书依据

      dlist_is_tail 返回值 如果由参数element所指定的元素是链表尾元素则返回0;否则返回-1。 描述 这是一个宏,用来判断由参数element所指定的元素是否为链表尾元素。 复杂度 O(1) dlist_data 返回值 返回由element所指定的链表元素的数据域。 描述 这是一个宏

    • · 查看原书依据

      访问和测试数据结构DList以及DListElmt的成员的接口。 本节中所有的宏的运行时复杂度都为O(1),因为访问和检测数据结构中的成员是一个简单的操作,它们都能够在恒定的时间内完成。 示例5-5:双向链表抽象数据类型的实现

    • · 查看原书依据

      clist_size 返回值 链表中的元素个数。 描述 这是一个宏,用来计算由参数list所指定的链表中的元素个数。 复杂度 O(1) clist_head 返回值 返回链表头的元素。 描述 这是一个宏,用来返回由参数list所指定的循环链表中的头元素。 复杂度 O(1) clist_data 返回

    • · 查看原书依据

      CList和CListElmt中的成员的接口。 以上这些宏的运行时复杂度都为O(1),因为访问和检测数据结构的成员是一种简单的操作,而且它们都能在恒定的时间内完成。 示例5-7:循环链表抽象数据类型的实现

    参考来源

    - 位置:《算法精解:C语言描述》第5章《单链表接口的定义》(spine1206;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1173.html;u050-ch05-007)。 - 结论依据:50全部查询说明与02704-02710原型已读,并与51的02712实际#define核对,修正list_is_head参数及真假返回;保留O(1)字段读的用途。 - 原始内容:这是一个宏,用来计算由参数list指定的链表中元素的个数。 复杂度 O(1) list_head 返回值 指向链表中头元素的指针。 描述 这是一个宏,返回由参数list指定的链表中头元素的指针。 复杂度 O(1) list_tail 返回值 指向链表中尾元素的指针。 描述 这是一个宏,返回由参数li - 位置:《算法精解:C语言描述》第5章《list_size、list_head、list_tail、list_is_tail、list_data以及list_next》(spine1211;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1178.html;u056-ch05-007)。 - 结论依据:56把这些操作概括为访问/检测字段。list_size返回已维护size,未遍历;list_is_tail仅测next为NULL,list_is_head比较head。公开宏使调用方依赖字段表示,不能把它们当语言强制隐藏实现细节的屏障。 - 原始内容:List和ListElmt结构体中成员的能力。 这些操作的运行时复杂度都是O(1),因为访问和检测结构体的成员都可以在恒定的时间内完成。 - 位置:《算法精解:C语言描述》第5章《双向链表接口的定义》(spine1214;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1181.html;u059-ch05-007)。 - 结论依据:59至60的实际dlist.h中dlist_is_head(element)测prev==NULL,dlist_is_tail(element)测next==NULL,均返回1/0,接口表尾判断写0/-1不符。dlist_prev与dlist_next分别读前后链接;size/head/tail/data也只是字段访问,不额外证明节点属于哪张表。 - 原始内容:dlist_is_tail 返回值 如果由参数element所指定的元素是链表尾元素则返回0;否则返回-1。 描述 这是一个宏,用来判断由参数element所指定的元素是否为链表尾元素。 复杂度 O(1) dlist_data 返回值 返回由element所指定的链表元素的数据域。 描述 这是一个宏 - 位置:《算法精解: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-007)。 - 结论依据:66完整代码维持size,宏仅读取它;端点判断在dlist.h已确定1/0。全文代码的存在也揭示前插缺next赋值,因而不能从字段查询简单推断结构一定正确。 - 原始内容:访问和测试数据结构DList以及DListElmt的成员的接口。 本节中所有的宏的运行时复杂度都为O(1),因为访问和检测数据结构中的成员是一个简单的操作,它们都能够在恒定的时间内完成。 示例5-5:双向链表抽象数据类型的实现 - 位置:《算法精解:C语言描述》第5章《循环链表接口的定义》(spine1222;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1189.html;u068-ch05-007)。 - 结论依据:68的clist_size/head/data/next只读保存字段。循环结构没有tail查询宏,并非任何节点的next为NULL就能表示末尾;按实际环结构使用next,不照搬list_is_tail。 - 原始内容:clist_size 返回值 链表中的元素个数。 描述 这是一个宏,用来计算由参数list所指定的链表中的元素个数。 复杂度 O(1) clist_head 返回值 返回链表头的元素。 描述 这是一个宏,用来返回由参数list所指定的循环链表中的头元素。 复杂度 O(1) clist_data 返回 - 位置:《算法精解:C语言描述》第5章《clist_size、clist_head、clist_data以及clist_next》(spine1227;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1194.html;u074-ch05-007)。 - 结论依据:74的02751-02752代码没有额外的尾部检测,size由成功插入/移除维护。遍历次数、回到起点等停止条件属于调用方任务,不由clist_next自动决定;宏O(1)不代表一次完整环遍历也O(1)。 - 原始内容:CList和CListElmt中的成员的接口。 以上这些宏的运行时复杂度都为O(1),因为访问和检测数据结构的成员是一种简单的操作,而且它们都能在恒定的时间内完成。 示例5-7:循环链表抽象数据类型的实现