c - C 语言快速 union 实现中的段错误(核心转储)

Question

#include<stdio.h>
#include<stdlib.h>
int *id,N;

main()
{
    FILE* file=fopen("a.txt","r");
    int i,p,q,c;
    fscanf(file,"%d",&N);

    id=(int *)malloc(N*sizeof(int));

    for(i=0;i<N;i++)
        *(id+i)=i;

    while(!feof(file))
    {
        fscanf(file,"%d %d",&p,&q);
        if(!connected(p,q))
            unn(p,q);
    }
    fclose(file);
    c=1;

    while(c==1)
    {
        scanf("%d %d",&p,&q);
        printf("%d\nYes(1) or No(0)    ",connected(p,q));
        scanf("%d",&c);
    }
}

connected(int p,int q)
{
    return((root(p))==(root(q)));
}

unn(int p,int q)
{
    int j=root(q);
    int i=root(p);
    *(id+j)=i;
}

root(int i)
{
    while(i!=(*(id+i)))
        i=*(id+i);
    return(i);
}

编译时，不显示错误消息。但是，当我尝试执行该程序时，它显示“段错误(核心转储)。为什么会发生这种情况？正如您可能已经注意到的，这是实现快速 union 的尝试。

使用相同的文件“a.txt”轻松实现快速查找，只需对此代码进行一些调整。* Yes或No供用户查询。

Answer 1

我猜这就是问题所在

root(int i)
{
    int p;  
    while(p!=(*(id+p)))   <-- p uninitialised 
        p=*(id+p);
    return(p);
}

因为p未初始化，但您将其用作指针取消引用中的偏移量。即使这不是原因，它仍然是一个大问题。

您已编辑要离开的问题

root(int i)
{
    int i;  
    while(i!=(*(id+i)))  
        i=*(id+i);
    return(i);
}

其中您在本地重新声明 i 变量以及作为函数参数传递的 i 变量。