知识卡片
集合谓词返回成员关系结果
本章实现的set_is_member(const Set,const void)、set_is_subset(const Set,const Set)和set_is_equal(const Set,const Set)都返回1表示条件成立、0表示不成立。它们回答成员存在、包含或相等,不表示调用者应否继续后续流程。
接口文字对member的假值漏写,对subset/equal误写为-1;完整set.c均使用0/1,应按实际实现理解。set_size宏则返回已保存的成员数量,不是谓词。调用方不能把这些查询结果套用到插入操作0/1/-1的另一套约定。
112及02795 set_is_member在match成立时return1,循环结束return0。最坏O(n)以每次判等为常数为前提,回调较昂贵时需把其成本计入。它不修改集合,也不返回匹配数据的地址。
115与02791头文件:set_size(set)为((set)->size),O(1)来自维护好的字段,而不是临时遍历计数。02792–02796全文件已读,所有谓词均以0/1表示结果。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- · 查看原书依据
set_is_member 返回值 如果找到成员返回1;否则返回。 描述 判断由data所指定成员是否存在于set所指定的集合中。 复杂度 O(n),这里n代表集合中的元素个数。 set_is_subset 返回值 如果set1是set2的子集返回1;否则返回-1。 描述 判断由参数set1所指定集
- · 查看原书依据
直到找到与参数data相吻合的成员或者遍历完整个集合。 set_is_member的时间复杂度为O(n),这里n为集合中的成员个数。这是因为在最坏的情况下,整个集合中的成员都需要遍历一次以此来确定要查找的成员。
- · 查看原书依据
直接通过访问数据结构Set中的size成员得到。 因此set_size的时间复杂度为O(1),因为访问结构体中的成员可以在恒定的时间内完成。 示例7-2:Set抽象数据类型的实现