知识卡片
链表查询宏只读现有状态
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:循环链表抽象数据类型的实现