如何從鄰接矩陣建立鄰接表？

我已經成功地爲輸入文件建立了一個鄰接矩陣，輸入的第一行是頂點的總數，下面幾行是以任意順序作爲頂點對的邊。例如如何從鄰接矩陣建立鄰接表？

file.txt的

然而，當我運行這個程序，鄰接矩陣構建成功，但是當我嘗試創建一個鄰接表的結構樹的陣列，程序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); 
}

任何及所有的幫助深表感謝:)

來源

2013-03-18 user2180691

我認爲這個問題是在您的構建：

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

您試圖從局部變量（它丟失範圍）返回內存。在上面的代碼中，tree * adjArray[n]創建了一個本地變量數組（在本地地址空間中）。函數離開後，返回指向該數組頭部的指針將無效。

通常，當你想創建一個列表或節點時，你需要malloc，使得內存將存在於堆中（因此將會使create函數本身生效）。喜歡的東西：

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

請注意，你的malloc-ING連續的內存塊（讀：數組）的tree *的，而不是完全trees。

來源

2013-03-18 02:17:43 SeKa

我意識到這是一個古老的問題，但我立即看到一個問題，你在做循環計數器的方式。由於這是C++，因此大小爲n的數組中的元素是arr [0]，arr [1]，... arr [n-1]。您的代碼引用超出數組邊界的arr [n]，並可能導致崩潰。

你的循環邏輯需要如下所示，使得它不包括i = N時的迭代中，通過使用<代替< =在for循環測試：

for (i = 0; i < n; i++) 
    adjArray[i] = NULL;

來源

2017-03-05 02:29:10 TWalder

如何從鄰接矩陣建立鄰接表？

回答

相關問題