知识卡片

操作参考卡 · 5654.d.1.f.3.n · 生成模型:未记录

图中顶点与边分开变更

理解等级:中级

graph_ins_vertex(Graph,const void)保存顶点地址;graph_ins_edge(Graph,const void,const void*)要求两个端点已存在,再把第二端点地址加入第一端点的邻接集合。两者0为新加入、1为已存在、-1为失败,重复不等于内部错误。

graph_rem_vertex(Graph*,void)只允许移除没有入边/出边的顶点,成功交回顶点数据地址;graph_rem_edge(Graph,void,void)只移除指定方向的邻接记录,成功交回该记录保存的地址。它们成功0、失败-1,读入键与输出对象地址共用参数,不能忽略输入输出职责。

移除边并不移除目标顶点,交回地址也不表示调用方可释放仍由顶点记录或其他边使用的数据。新增边保存的是传入data2地址,应用必须保证它代表正确且仍有效的顶点对象,不能用一个暂时等价的局部查找键替代长期引用。

192及02935 graph_ins_vertex重复return1,malloc AdjList失败-1,设vertex=data、set_init(adjacent,graph->match,NULL),尾插成功才vcount++。若记录malloc成功而list_ins_next分配链节点失败,原代码直接return retval而未free记录,失败清理遗漏;用户数据尚未加入,不应被随意回调销毁。

193及02935–02936 graph_ins_edge先线性找data2,再找data1,接着set_insert源adjacent。返回1表示边已存在、-1为失败,原文统称错误需按状态区分;只有retval=0才ecount++。查找确认等价目标存在,但保存的仍是实参data2,未替换为canonical vertex地址。

195及02937 graph_rem_edge源不存在或set_remove未命中返回-1;成功ecount–返回0。*data2替换为边记录原地址,仍可能被顶点记录和其他边借用,不能因本次移边输出就free对象。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      graph_ins_vertex 返回值 如果插入顶点成功,返回0;如果顶点已经存在,返回1;否则返回-1。 描述 将顶点插入由参数graph所指定的图中。新顶点包含一个指向data的指针,因此只要顶点还在图中,data所引用的内存就必须保持有效。由调用者负责管理data所引用的存储空间。 复杂度

    • · 查看原书依据

      AdjList结构体插入邻接表链表结构中,并将AdjList结构体中的vertex成员指向由调用者传入的数据。首先,要确保该顶点不存在于列表中。之后,通过调用list_ins_next将AdjList结构体插入链表的尾部。最后,将图数据结构的vcount成员加1以更新图中的顶点个数。 graph_i

    • · 查看原书依据

      set_insert会返回一个错误。最后,将图数据结构的ecount成员加1,以更新图中边的个数。 graph_ins_edge的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为搜索邻接表结构链表以及对set_insert的调用都是O(V)的操作。

    • · 查看原书依据

      set_remove来将data2所指定的顶点从data1所指定的顶点的邻接表中移除,从而实现移除这条边的功能。如果data2不在data1的邻接表中,则set_remove将返回一个错误。最后,通过递减图数据结构的ecount成员来更新图中边的个数。 graph_rem_dege的时间复杂度为O(

    参考来源

    - 位置:《算法精解:C语言描述》第11章《图的接口定义》(spine1322;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1289.html;u188-ch11-015)。 - 结论依据:188四变更接口全文和02922–02925原型、02935–02937对应实际实现实读;明确边输出不转移顶点所有权,返回1保留为已存在状态。 - 原始内容:graph_ins_vertex 返回值 如果插入顶点成功,返回0;如果顶点已经存在,返回1;否则返回-1。 描述 将顶点插入由参数graph所指定的图中。新顶点包含一个指向data的指针,因此只要顶点还在图中,data所引用的内存就必须保持有效。由调用者负责管理data所引用的存储空间。 复杂度 - 位置:《算法精解:C语言描述》第11章《graph_ins_vertex》(spine1325;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1292.html;u192-ch11-015)。 - 结论依据:192及02935 graph_ins_vertex重复return1,malloc AdjList失败-1,设vertex=data、set_init(adjacent,graph->match,NULL),尾插成功才vcount++。若记录malloc成功而list_ins_next分配链节点失败,原代码直接return retval而未free记录,失败清理遗漏;用户数据尚未加入,不应被随意回调销毁。 - 原始内容:AdjList结构体插入邻接表链表结构中,并将AdjList结构体中的vertex成员指向由调用者传入的数据。首先,要确保该顶点不存在于列表中。之后,通过调用list_ins_next将AdjList结构体插入链表的尾部。最后,将图数据结构的vcount成员加1以更新图中的顶点个数。 graph_i - 位置:《算法精解:C语言描述》第11章《graph_ins_edge》(spine1326;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1293.html;u193-ch11-015)。 - 结论依据:193及02935–02936 graph_ins_edge先线性找data2,再找data1,接着set_insert源adjacent。返回1表示边已存在、-1为失败,原文统称错误需按状态区分;只有retval=0才ecount++。查找确认等价目标存在,但保存的仍是实参data2,未替换为canonical vertex地址。 - 原始内容:set_insert会返回一个错误。最后,将图数据结构的ecount成员加1,以更新图中边的个数。 graph_ins_edge的时间复杂度为O(V),这里V代表图中顶点的个数。这是因为搜索邻接表结构链表以及对set_insert的调用都是O(V)的操作。 - 位置:《算法精解:C语言描述》第11章《graph_rem_edge》(spine1328;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1295.html;u195-ch11-015)。 - 结论依据:195及02937 graph_rem_edge源不存在或set_remove未命中返回-1;成功ecount--返回0。*data2替换为边记录原地址,仍可能被顶点记录和其他边借用,不能因本次移边输出就free对象。 - 原始内容:set_remove来将data2所指定的顶点从data1所指定的顶点的邻接表中移除,从而实现移除这条边的功能。如果data2不在data1的邻接表中,则set_remove将返回一个错误。最后,通过递减图数据结构的ecount成员来更新图中边的个数。 graph_rem_dege的时间复杂度为O(