知识卡片

操作参考卡 · 3725.b.1.l · 生成模型:未记录

集合谓词返回成员关系结果

理解等级:中级

本章实现的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抽象数据类型的实现

    参考来源

    - 位置:《算法精解:C语言描述》第7章《集合接口的定义》(spine1251;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1218.html;u103-ch07-013)。 - 结论依据:103查询接口表与02787–02790原型全部实读,112–115正文、02795–02796代码明确false返回0及size字段读取,保留文字差异。 - 原始内容:set_is_member 返回值 如果找到成员返回1;否则返回。 描述 判断由data所指定成员是否存在于set所指定的集合中。 复杂度 O(n),这里n代表集合中的元素个数。 set_is_subset 返回值 如果set1是set2的子集返回1;否则返回-1。 描述 判断由参数set1所指定集 - 位置:《算法精解:C语言描述》第7章《set_is_member》(spine1259;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1226.html;u112-ch07-013)。 - 结论依据:112及02795 set_is_member在match成立时return1,循环结束return0。最坏O(n)以每次判等为常数为前提,回调较昂贵时需把其成本计入。它不修改集合,也不返回匹配数据的地址。 - 原始内容:直到找到与参数data相吻合的成员或者遍历完整个集合。 set_is_member的时间复杂度为O(n),这里n为集合中的成员个数。这是因为在最坏的情况下,整个集合中的成员都需要遍历一次以此来确定要查找的成员。 - 位置:《算法精解:C语言描述》第7章《set_size》(spine1262;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1229.html;u115-ch07-013)。 - 结论依据:115与02791头文件:set_size(set)为((set)->size),O(1)来自维护好的字段,而不是临时遍历计数。02792–02796全文件已读,所有谓词均以0/1表示结果。 - 原始内容:直接通过访问数据结构Set中的size成员得到。 因此set_size的时间复杂度为O(1),因为访问结构体中的成员可以在恒定的时间内完成。 示例7-2:Set抽象数据类型的实现