知识卡片

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

集合增删先按判等寻找成员

理解等级:中级

本章Set以match(const void,const void)判断成员相同:相同返回1,不同返回0。这是相等谓词,不是负/零/正的大小比较器。match应稳定地表达所讨论的成员相等关系,集合使用期间不能任意改变这层含义。

set_insert(Set,const void)先查成员,未存在才保存地址:0表示新插入,1表示已有等价成员而未插入,-1表示失败。重复时没有转移新传入对象的存储责任;不能把所有非零都理解为同一业务失败。

set_remove(Set*,void**)既读入查找键,也在成功后交回实际移除成员的数据地址,0成功、-1未找到。移除节点并不自动销毁其数据对象,释放责任仍需由调用方履行。

105及02792 set_init先list_init(set,destroy),再set->match=match。list_init没有使用或初始化match,不能依赖一个仅做list_init的对象已经具备有效集合判等能力。固定字段初始化为O(1)。

107和02792实际代码:已存在return1,否则return list_ins_next(set,list_tail(set),data)。尾插的位置不成为集合次序语义。未改变成员时保持原有对象;若调用方为重复项新分配了数据,需自己处理该对象。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      set_insert 返回值 如果插入操作成功则返回0;如果插入的成员在集合中已经存在返回1;否则返回-1。 描述 在由参数set所指定的集合中插入一个成员。新成员包含一个指向data的指针,因此只要该成员还在集合中,则data所引用的内存空间就应该保持合法。由调用者负责管理data所关联的存储空间

    • · 查看原书依据

      手动初始化match成员,因为这个成员在链表中并没有得到使用,所以list_init不能初始化这个成员。 set_init的运行时复杂度同list_init一样,都是O(1)级的。

    • · 查看原书依据

      首先调用set_is_member以确保集合中不会已经包含了待插入的成员。只要集合中不存在待插入的成员,就调用list_ins_next将待插入的成员插入到集合中。 set_insert的时间复杂度为O(n)级的,因为set_is_member需要遍历整个集合,所以需要O(n)的时间复杂度,list

    参考来源

    - 位置:《算法精解:C语言描述》第7章《集合接口的定义》(spine1251;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1218.html;u103-ch07-011)。 - 结论依据:103全部接口表及02782/02783原型实读,与108说明和02792/02793实际实现相互定位;记录三态插入和输入输出参数,未运行。 - 原始内容:set_insert 返回值 如果插入操作成功则返回0;如果插入的成员在集合中已经存在返回1;否则返回-1。 描述 在由参数set所指定的集合中插入一个成员。新成员包含一个指向data的指针,因此只要该成员还在集合中,则data所引用的内存空间就应该保持合法。由调用者负责管理data所关联的存储空间 - 位置:《算法精解:C语言描述》第7章《set_init》(spine1252;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1219.html;u105-ch07-011)。 - 结论依据:105及02792 set_init先list_init(set,destroy),再set->match=match。list_init没有使用或初始化match,不能依赖一个仅做list_init的对象已经具备有效集合判等能力。固定字段初始化为O(1)。 - 原始内容:手动初始化match成员,因为这个成员在链表中并没有得到使用,所以list_init不能初始化这个成员。 set_init的运行时复杂度同list_init一样,都是O(1)级的。 - 位置:《算法精解:C语言描述》第7章《set_insert》(spine1254;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1221.html;u107-ch07-011)。 - 结论依据:107和02792实际代码:已存在return1,否则return list_ins_next(set,list_tail(set),data)。尾插的位置不成为集合次序语义。未改变成员时保持原有对象;若调用方为重复项新分配了数据,需自己处理该对象。 - 原始内容:首先调用set_is_member以确保集合中不会已经包含了待插入的成员。只要集合中不存在待插入的成员,就调用list_ins_next将待插入的成员插入到集合中。 set_insert的时间复杂度为O(n)级的,因为set_is_member需要遍历整个集合,所以需要O(n)的时间复杂度,list