知识卡片
集合增删先按判等寻找成员
本章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 条
还没有人提交反馈。
在整书笔记中的位置
- · 集合增删先按判等寻找成员
- · set_init
- · set_insert
原书出处 · 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