Как построить список смежности из матрицы смежности?

Я успешно построил матрицу смежности для входного файла с первой строкой ввода в качестве общего количества вершин, а следующие строки представляют собой ребра в произвольном порядке как пары вершин. например

файл.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);
}

Любая помощь приветствуется :)


c adjacency-list
person user2180691    schedule 18.03.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я думаю, что проблема в вашей сборке:

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.

person SeKa    schedule 18.03.2013

arrow_upward
0
arrow_downward

Я понимаю, что это был старый вопрос, но я сразу увидел проблему в том, как вы выполняете счетчики циклов. Так как это C++, элементами массива размера n являются arr[0], arr[1], ... arr[n-1]. Ваш код ссылается на arr[n], который находится за пределами массива и может привести к сбою.

Ваша логика цикла должна выглядеть следующим образом, чтобы она не включала i=n в итерации, используя ‹ вместо ‹= в тесте цикла for:

for (i = 0; i < n; i++)
    adjArray[i] = NULL;
person TWalder    schedule 05.03.2017