c - 如何从邻接矩阵构建邻接表？

Question

我已经成功地为一个输入文件构建了一个邻接矩阵，其中输入的第一行是顶点总数，接下来的几行是任意顺序的边作为顶点对。例如

文件.txt

7
1 2
4 6
4 3
5 2

但是，当我运行这个程序时，邻接矩阵构建成功，但是当我尝试创建一个邻接列表作为结构树数组时，程序 Seg 出错(核心转储)。关于为什么程序失败的任何线索？有问题的功能是:

tree * buildAdjList(int a[][100], int n)
{       int i, j, k;
    tree *node;
    tree * adjArray[n];
    for(i=0; i<=n; i++)
            adjArray[i] = NULL;
    for(j=0; j<=n; j++)
            for(k=0; k<=n; k++)
                    if(a[j][k] == 1){
                            node = (tree *)malloc(sizeof(tree));
                            node->val = k;
                            node->next = adjArray[j];
                            adjArray[j] = node;
                    }
    return adjArray[0];
}

和程序的其余部分:

#include <stdio.h>
#include <stdlib.h>
struct tree{
    int val;
    struct tree *next;
};

typedef struct tree tree;

void printArray(int a[][100],int n);
void adjacencyMatrix(int a[][100], int n, int p1, int p2, FILE * inputF);
tree * buildAdjList(int a[][100], int n);
void printAdjArray(tree * adjArr[], int n);

int main(int argc, char ** argv)
{

int a[100][100];
int n,*q;
FILE * inputFile;
int entries, i;
inputFile = fopen(argv[1], "r");
int p1, p2 =0;
if(inputFile==NULL){
    printf("File failed to open.");
    exit(EXIT_FAILURE);
}
fscanf(inputFile, "%d", &entries);
tree * adjarray[entries];
q = (int *)malloc(sizeof(int)*n);
adjacencyMatrix(a,entries,p1,p2,inputFile);
adjarray[0] = buildAdjList(a, entries);
printAdjArray(adjarray, entries);
return 0;
}

void adjacencyMatrix(int a[][100], int n, int p1, int p2, FILE * inputF){
int i,j;
do{
    for(i = 0;i <= n; i++)
    {
        for(j = 0;j <=n; j++)
        {   if(i==p1 && j == p2){
                 a[i][j] = 1;
                 a[j][i] = 1;
            }
        }
        a[i][i] = 0;
    }
}while(fscanf(inputF, "%d %d", &p1, &p2) !=EOF);
    printArray(a,n);
}

非常感谢任何帮助:)

Answer 1

我认为问题出在您的构建中:

tree * buildAdjList(int a[][100], int n)
{       int i, j, k;
    tree *node;
    tree * adjArray[n];
    // work
    return adjArray[0];
}

您正在尝试从局部变量(失去作用域)返回内存。在上面的代码中，tree * adjArray[n] 创建了一个局部变量 数组(在局部地址空间中)。返回指向该数组头部的指针在函数离开后将无效。

通常，当你想创建一个列表或节点时，你需要 malloc 以便内存将存在于堆中(因此将比创建函数本身更有效)。像这样的东西:

tree * buildAdjList(int a[][100], int n)
{
    tree *newtree = malloc(n * sizeof(tree *));
    // work
    return newtree;
}

请注意，您分配的是 tree * 的连续内存块(读取:数组)，而不是完整的 trees。