Open AllofMortal opened 1 month ago
我试着修了一下,你可以试试这里的代码 https://github.com/krahets/hello-algo/pull/1381
这里应该是删除顶点函数removeVertex在遍历其它顶点的链表时(第一个for循环),进入了死循环,所以程序卡在了删除顶点函数那里。原函数在遍历其它顶点的链表时,是遍历的整个图,即所有的链表,包括已经删除的链表。但以待删除节点为顶点的链表在第一个while循环之后,其头节点和邻接节点都成为了悬空指针,因此不应该访问这个链表。所以加一个if语句,不要遍历以待删除节点为顶点的链表即可:
/* 删除顶点 */
void removeVertex(GraphAdjList *graph, Vertex *vet) {
AdjListNode *node = findNode(graph, vet);
assert(node != NULL);
// 在邻接表中删除顶点 vet 对应的链表
AdjListNode *cur = node, *pre = NULL;
while (cur) {
pre = cur;
cur = cur->next;
free(pre);
}
// 遍历其他顶点的链表,删除所有包含 vet 的边
for (int i = 0; i < graph->size; i++) {
cur = graph->heads[i];
pre = NULL;
// 修改的部分:在进入while循环遍历链表之前,添加条件语句确保不要遍历到先前已被释放的顶点所在的链表
if (cur != node) {
while (cur) {
pre = cur;
cur = cur->next;
if (cur && cur->vertex == vet) {
pre->next = cur->next;
free(cur);
break;
}
}
}
}
// 将该顶点之后的顶点向前移动,以填补空缺
...
}
整体看这段代码没有什么问题但是运行时无法输入内容,持续在运行