C++实现Kruskal最小生成树时,从根重初始化的指针仍为null问题
你看到iterate莫名变成NULL,本质是代码里的指针操作逻辑出了连锁问题,和你“每次循环开头重置iterate”的写法没有直接关系,具体漏洞点如下:
1. 空指针解引用直接触发未定义行为
你在make_spanning_tree开头申请的sets是forest类型对象,类构造函数里明确把vertices初始化为NULL。
但你第一次进循环的判断条件写的是if (iterate->vertices->data == 0)——这时候iterate指向的sets节点的vertices是NULL,你直接对空指针解引用读data字段,这是完全的非法内存访问。
这种情况下程序的行为不受控制:轻则读到内存里的随机值触发分支判断,重则直接篡改栈上的变量值(包括sets、iterate这些指针本身),你看到的“第三次循环指针莫名变NULL”,有很大概率是非法内存访问把指针值给覆盖了。
正确的初始化判断逻辑应该是直接判断vertices本身是否为空,比如改成if (iterate->vertices == NULL),完全不需要依赖vertices->data == 0这种脆弱的判断条件。
2. 遍历集合链表的时候把主游标给冲掉了
你在else分支里写内层集合遍历逻辑的时候,直接拿iterate当遍历游标用:
for (int j = 0; j < set_no; j++) { r_count[j] = 0; c_count[j] = 0; move = iterate->vertices; // 遍历当前集合的邻接链 while (move != NULL) { ... } iterate = iterate->next; // 每遍历完一个集合,把iterate往后推 }
要知道你一开始的集合链表只有sets这一个头节点,它的next永远是NULL(你从来没给链表追加过新的集合节点)。也就是说内层循环跑完最后一轮,iterate直接从sets的地址变成了NULL。
哪怕你外层循环开头写了iterate = sets,但因为前面的空指针解引用已经把栈上的sets指针本身给篡改了,重置操作根本拿不到原来的有效地址。
正确的写法是单独建一个临时遍历游标,绝对不能用主指针去遍历:
// 外层循环开头正常重置主指针 iterate = sets; // 内层遍历用单独的临时游标 forest* set_cursor = sets; for (int j = 0; j < set_no; j++) { move = set_cursor->vertices; // 遍历邻接链 while (move != NULL) { ... } set_cursor = set_cursor->next; // 只动临时游标,不碰iterate }
3. 核心逻辑残缺导致链表永远不扩容
你在else分支里定义了r_count、c_count、new_r、new_c这些变量用来判断两个端点属于哪个集合,但算完结果之后没有任何后续处理:既没有判断两个端点是不是在同一个集合(避免成环),也没有在跨集合的时候合并集合,更没有在两个端点都不属于现有集合的时候,给sets的链表追加新的forest节点。
这直接导致你的不相交集合链表从头到尾只有一个头节点,set_no变量也从来没被更新过,一直停在初始值1,根本没法支撑Kruskal算法的多集合合并逻辑。
4. 其他容易踩的内存漏洞
priority_dq函数里开头新建的que* required = new que;马上就被required = move;覆盖了,不仅内存泄漏,还完全冗余,直接删掉就行。forest类的析构函数里直接输出vertices->data,没加空判断,一旦遇到vertices为NULL的情况,程序直接崩。- 函数开头申请的全局
node* move = new node;从来没被正确使用,纯属多余的内存申请。
内容的提问来源于stack exchange,提问作者Amna_shawty

