知识卡片
链表销毁按数据回调清理
list_init(List *list, void (*destroy)(void *data))建立空表并记下应用数据清理规则;list_destroy(List *list)移除所有节点,若destroy非NULL,再对每个移出的数据调用一次。生命周期结束后需重新初始化才能继续按接口使用。
节点由链表实现管理,数据对象按调用方提供的规则管理。数据若来自独立malloc,可按约定用free;若内部还有动态成员,应由适当回调一起清理;借用数据则可用NULL避免误释放。回调只是一种约定,不自动证明没有共享引用或重复释放。
52的02713实际list_init仅写size、destroy、head、tail,不分配节点,也未初始化match。其固定赋值步骤可按O(1)理解;不能泛化成所有结构初始化都常数。
53正文把每次移除调用写成list_destroy,是笔误;02714实际调用list->destroy(data),不是递归调用自身。list_rem_next释放节点,destroy回调处理数据,最后memset清容器。O(n)是每次移除与回调成本固定时的模型;实际数据析构成本还要另计。memset清零不是重初始化的替代,也不自动使所有外部节点引用有效。
59的dlist_init(DList,destroy)与dlist_destroy(DList)沿用节点移除加应用destroy回调的分工;destroy为NULL表示不由该回调释放数据。正文将初始化复杂度写O(n),与61及实际常数赋值实现不符,应按O(1)字段建立理解;销毁成本还包含每个回调的工作。
61明确O(1),02737实际设置size=0、destroy、head/tail=NULL,不遍历也不初始化match。59接口表的O(n)不作为运行结论;没有重用旧表时自动清理原内容的逻辑,不能用再次init代替destroy。
02737-02738中循环对dlist_tail(list)调用dlist_remove,成功且destroy非NULL才调用list->destroy(data),最后清容器。destroy回调在初始化时保存,并非dlist_destroy额外收到一个destroy参数。总成本是逐个移除加回调成本,接口有效且不变量成立是循环进展的前提。
68的clist_init保存destroy,clist_destroy移除所有节点并按非空回调释放数据。与非循环表一致的是两层清理责任,不是内部删除顺序必然相同。
70与02751的clist_init只设size、destroy和head,不分配节点、不设match。空表与单节点环是不同状态,不能在init结束时就假设head->next可访问。
71正文写每移除调用clist_init是笔误;02751实际调用list->destroy(data),移除函数是clist_rem_next(list,list->head,&data)。多节点时先移head的后继,head会保留到最后,因此不能假定销毁顺序等于从head依次向前的数据顺序;接口没有承诺回调次序。
80生命周期接口与81头文件把stack_init/destroy映射到list_init/destroy;清理应用数据调用保存的destroy回调,而非每移一项递归调用stack_destroy。表中销毁复杂度写O(1)与83的O(n)不符;逐项节点清理加应用回调仍要计费。
83明确stack_destroy与list_destroy同为O(n),纠正80表中的O(1);若应用destroy成本不固定,总成本还需累计那些工作。栈别名并不改变节点和应用数据的分层清理。
88队列初始化保存destroy规则,销毁借list_destroy逐节点清理并调用非空数据回调。不是“释放destroy不为空的成员”这种逐字段自动反射;释放哪些内容由提供的回调决定,总成本也含回调。
91明确queue_destroy与list_destroy同为逐项O(n)模型;固定元素成本下随数量增长,并非别名使销毁变成常数。
103集合set_init接收match和destroy;销毁仍按每个节点调用非空destroy。销毁后要重新使用须再次set_init,描述中的“再次调用它”不能理解为再次destroy即可恢复对象。
106及02791 set_destroy为list_destroy宏别名,逐节点成本模型O(n),借用结果的NULL回调与拥有数据的非空回调仍要区分。
126和02815实际chtbl_destroy逐桶list_destroy,再free(table),最后memset结构。若m桶共n成员,固定回调成本模型为O(m+n),而非一般输入下只计O(m);只有α=n/m受常数界控制,才可简记O(m)。正文该段把函数名写为chtbl_init是笔误,实际讨论destroy。结构清零不等于重新分配了可用桶,复用须初始化。
137及02833 ohtbl_destroy先判断destroy是否非空;若非空遍历全部槽,只有非NULL且非vacated才回调,之后free(table)、memset结构。固定回调成本下带回调O(m);若回调为空,实际跳过扫描,按本书分配器模型仅固定步骤,但free真实耗时并非C语言保证。正文把函数名写为chtbl_init是笔误。
147二叉树生命周期同样保存destroy,销毁/移除意图对每个节点调用非空数据回调,之后重新使用需bitree_init。它不是按结构字段自动深层释放;实际NULL移除缺陷在153明确。
150及02856 bitree_destroy调用bitree_rem_left(tree,NULL)再memset结构,不会每移除一个节点就重新调用bitree_init。原文回调表述按153实际destroy(data)理解;移除实现NULL分支缺陷使非空树这条销毁路径有问题,153专卡明确。
175及02899 destroy非空才遍历tree[i]回调,之后free(tree)、memset容器;固定数据清理成本时O(n),回调为空时跳过循环,按本书分配器模型仅固定清理步骤。文字“destroy将指向此函数”应理解为调用所保存的数据回调,而非递归指向heap_destroy自身。
188销毁表描述“针对顶点和边都回调”过宽。191/02934实际每个邻接Set以NULL回调只释放边记录节点,graph->destroy仅对AdjList.vertex调用一次;否则共享端点会被重复释放。
191及02934 graph_destroy在每次list_rem_next后set_destroy(adjacent),可选destroy(vertex),free(adjlist);邻接Set的NULL回调不释放目标对象,避免同顶点因多入边重复销毁。全部V个记录与E条邻接节点给出O(V+E)固定清理模型,再清空外链和Graph。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 链表销毁按数据回调清理
- · list_init
- · list_destroy
- · 双向链表接口的定义
- · dlist_init
- · dlist_destroy
- · 循环链表接口的定义
- · clist_init
- · clist_destroy
- · 栈的接口定义
- · stack_destroy
- · 队列的接口定义
- · queue_destroy
- · 集合接口的定义
- · set_destroy
- · chtbl_destroy
- · ohtbl_destroy
- · 二叉树的接口定义
- · bitree_destroy
- · heap_destroy
- · 图的接口定义
- · graph_destroy
原书出处 · 22 处
- · 查看原书依据
destroy参数提供了一种释放动态分配的数据的方法。例如,如果链表包含采用malloc动态分配的数据,当链表被销毁时,destroy应该设置为free用来释放数据。对于包含好几个动态分配成员的结构化数据,destroy应该设置为一个用户自定义的析构函数,通过对每一个动态分配的成员以及对结构体自身调
- · 查看原书依据
把链表的size成员设置为0,把函数指针成员destroy设置为定义的析构函数,head和tail指针全设置为NULL即可。 list_init的复杂度为O(1),因为初始化过程中的所有步骤都能在一段恒定的时间内完成。 示例5-2:链表抽象数据类型的实现
- · 查看原书依据
当每个元素被移除时都将调用list_destroy一次。 list_destroy的运行时复杂度为O(n),n代表链表中的元素个数,这是因为list_rem_next的复杂度为O(1),而移除每个元素时都将调用list_rem_next一次。
- · 查看原书依据
dlist_init 返回值 无 描述 初始化由参数list所指定的双向链表。该函数必须在双向链表做其他任何操作之前调用。当调用dlist_destroy时,这里传入的destroy参数提供了一种释放动态分配空间的方法。它的工作方式同前面叙述的list_destroy。对于双向链表,如果其中包含不需
- · 查看原书依据
dlist_init的运行时复杂度为O(1),因为初始化过程中的所有步骤都能在恒定的时间内完成。
- · 查看原书依据
dlist_destroy dlist_destroy操作用来销毁一个双向链表(见示例5-5)。总的来说,该操作意味着将链表中的所有元素都移除。当传递给该函数的destroy参数不为NULL时每当一个元素被移除时都将调用dlist_remove。 dlist_destroy的运行时复杂度为O(n),
- · 查看原书依据
clist_destroy被调用时,这里传入的destroy参数提供了一种释放动态分配空间的方法。它的工作方式同前文叙述的list_destroy相似。对于循环链表,如果其中包含不需要手动释放空间的数据,则destroy参数应该设置为NULL。 复杂度 O(1) clist_destroy 返回值
- · 查看原书依据
循环链表没有tail成员而已。 clist_init的运行时复杂度为O(1),因为初始化过程中的所有步骤都能在恒定的时间内完成。
- · 查看原书依据
每移除一个元素时都将调用clist_init一次。 clist_destroy的运行时复杂度为O(n),这里n代表链表中的元素个数。这是因为对于每个元素的移除操作都需要调用一次复杂度为O(1)的clist_rem_next函数。
- · 查看原书依据
stack_destroy来释放动态分配的内存空间。例如:如果一个栈包含用malloc动态分配内存的数据,那么当此栈销毁时,destroy会调用free来释放内存空间。当一个结构化数据包含若干动态分配内存的数据成员时,destroy应该指向一个用户自定义的函数来释放每个动态分配的数据成员和结构本身的
- · 查看原书依据
都是O(n),n为栈包含元素的个数。
- · 查看原书依据
queue_destroy来释放动态分配的内存空间。它的工作原理与stack_destroy相似。如果队列中的数据不需要释放,那么destroy应该指向NULL。 复杂度 O(1) queue_destroy 返回值 无 描述 销毁由queue指定的队列。在调用queue_destroy之后队列不允
- · 查看原书依据
都是O(n),n为队列包含元素的个数。 示例6-3:队列抽象数据类型的头文件
- · 查看原书依据
set_destroy时,destroy参数提供了一种释放动态分配空间的方法。例如,如果集合的成员包含使用malloc动态分配的数据空间,则当销毁集合时,destroy应该设置为free来释放数据占用的空间。对于结构化数据,其中包含了多个动态分配的成员,destroy应该设置为一个由用户自定义的析构
- · 查看原书依据
定义为list_destroy即可。 set_destroy的时间复杂度同list_destroy一样,都是O(n)级的,这里n代表集合中的成员个数。
- · 查看原书依据
删除每个“桶”中的元素,然后释放由chtbl_init分配的内存空间。如果传递给函数chtbl_init的参数destroy不为NULL的话,每当一个元素被移除时都要调用一次由destroy所指向的析构函数。 chtbl_init的时间复杂度为O(m),其中m是表中“桶”的个数。这是由于list_d
- · 查看原书依据
ohtbl_destroy 开地址哈希表由ohtbl_destroy进行销毁(见示例8-7)。该函数的主要功能是释放由ohtbl_init分配的内存空间。如果传递给函数ohtbl_init的参数destroy不为NULL的话,每当移除一个元素时,都要调用一次由destroy所指向的析构函数。 cht
- · 查看原书依据
bitree_destroy时,destroy参数所指定的函数提供了一种释放动态分配数据空间的方法。例如,如果该树包含采用malloc动态分配的数据,当销毁二叉树时,destroy应该设置为free用来释放数据空间。对于包含多个动态分配成员的结构化数据,destroy参数应该设置为一个用户自定义的析
- · 查看原书依据
简单调用复杂度为O(n)的bitree_rem_left。
- · 查看原书依据
heap_destroy 堆由heap_destroy进行销毁(见示例10-2)。该函数主要用于移除堆中的所有结点。当在heap_init中destroy指针不为NULL时,destroy将指向此函数以便在移除每个结点时调用。 heap_destroy的时间复杂度为O(n),其中n为堆中结点的个数。
- · 查看原书依据
graph_destroy 返回值 无 描述 销毁由参数graph所指定的图。该函数调用后,任何其他的图操作都不允许再执行,除非用户再次调用graph_init。graph_destroy操作将图中所有的顶点和边都移除,如果destroy参数不为NULL的话,则调用由destroy参数所指定的析构函
- · 查看原书依据
释放分配给vertex成员的内存空间。 graph_destroy的时间复杂度为O(V+E),这里V代表图中顶点的个数,而E代表边的个数。这是因为需要调用复杂度为O(1)的list_rem_next操作V次,而所有针对set_destroy的调用的总运行时间是O(E)。