知识卡片
移除成员会交还实际数据地址
set_remove的void **data不是只输出参数。调用前*data指向用于匹配的查找键;函数遍历时以match(*data,member_data)找目标,同时记住其前驱prev。找到后把prev传给list_rem_next,释放节点并将*data改为该节点原本保存的数据地址。
因此等价的查找键对象与返回的数据对象不必是同一个地址。调用方可以用独立的void *变量承载键/结果,再作适当的类型赋值;不要把void当成任何T都可安全强转的通用接口。找不到时返回-1且没有进入底层移除,调用方不能按成功释放返回对象。
查询最坏扫描n个成员,定位之后的链接更新是常数步;只有局部删除常数步不等于整个按值移除为O(1)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
prev指针刚好指向需要移除成员的前一个元素,因为这是调用list_rem_next所需要的参数。list_rem_next将参数data指向已移除成员的数据域。 set_remove的时间复杂度为O(n)级的,这里n代表集合中的成员个数。这是因为在最坏的情况下,整个集合的成员都需要遍历一次,以此才
参考来源
- 位置:《算法精解:C语言描述》第7章《set_remove》(spine1255;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1222.html;u108-ch07-014)。
- 结论依据:108完整说明与02792–02793 set_remove全部代码实读,确认match读*data、前驱更新、未找到return-1、成功委托list_rem_next;指针适配承接第2章已核验规则。
- 原始内容:prev指针刚好指向需要移除成员的前一个元素,因为这是调用list_rem_next所需要的参数。list_rem_next将参数data指向已移除成员的数据域。 set_remove的时间复杂度为O(n)级的,这里n代表集合中的成员个数。这是因为在最坏的情况下,整个集合的成员都需要遍历一次,以此才