圖adjacenct矩陣和列表錯誤

Question

我做的圖表，圖表中的數據只與鄰接矩陣工作正常，它成爲越野車相鄰的列表，改變adjmtx[3][2]的價值，一個隨機數：

Graph* graph = createGraph(4); 
Graph* graph = createGraph(3); 

這些似乎工作，但這：

Graph* graph = createGraph(5); 

導致崩潰。我不明白的是當我調試好所有功能。它會是什麼？

#include <stdio.h> 
#include <stdlib.h> 

typedef struct Node{ 
    int num; 
    struct Node* next; 
}Node; 

typedef struct Graph{ 
    int nodes; 
    int** adjmtx; 
    Node** adjlist; 
}Graph; 

Node* createHead(){ 
    Node* head = malloc(sizeof(Node)); 
    head->next = NULL; 
    return head; 
} 

Node* createNode(int num){ 
    Node* node = malloc(sizeof(Node)); 
    node->num = num; 
    node->next = NULL; 
    return node; 
} 

void addAdjlist(Node* head, int num){ 
    Node* node = createNode(num); 
    while(head->next != NULL && head->next->num < node->num){ 
     head = head->next; 
    } 
    node->next = head->next; 
    head->next = node; 
} 

Node** createAdjlist(int** adjmtx, int nodes){ 
    Node** adjlist; 
    int i, j; 
    adjlist = malloc(sizeof(Node*)); 
    for(i=0 ; i<nodes ; i++){ 
     adjlist[i] = createHead(); 
     for(j=0 ; j<nodes ; j++){ 
       if(adjmtx[i][j] != 0) 
        addAdjlist(adjlist[i],j); 
     } 
    } 
    return adjlist; 
} 

int** createAdjmtx(int nodes){ 
    int** adjmtx, i, j; 
    adjmtx = malloc(sizeof(int*)); 
    for(i=0 ; i<nodes ; i++) 
     adjmtx[i] = malloc(sizeof(int)); 
    for(i=0 ; i<nodes ; i++){ 
     for(j=0 ; j<nodes ; j++) 
      adjmtx[i][j] = 0; 
    } 
    for(i=0 ; i<nodes ; i++){ 
     for(j=i ; j<nodes ; j++){ 
      if(i!=j){ 
       printf("[%d]-[%d]",i,j); 
       scanf("%d",&adjmtx[i][j]); 
       adjmtx[j][i] = adjmtx[i][j]; 
      } 
     } 
    } 
    return adjmtx; 
} 

Graph* createGraph(int nodes){ 
    Graph* graph = malloc(sizeof(Graph)); 
    graph->nodes = nodes; 
    graph->adjmtx = createAdjmtx(nodes); 
    graph->adjlist = createAdjlist(graph->adjmtx,nodes); 
    return graph; 
} 


void viewAdjmtx(int** adjmtx,int nodes){ 
    int i, j; 
    for(i=0 ; i<nodes ; i++){ 
     for(j=0 ; j<nodes ; j++){ 
      printf("%d\t",adjmtx[i][j]); 
     } 
     printf("\n"); 
    } 
} 

void viewAdjlist(Node** adjlist,int nodes){ 
    int i; 
    for(i=0 ; i<nodes ; i++){ 
     printf("[%d]:",i); 
     while(adjlist[i]->next != NULL){ 
      printf("%d -> ",adjlist[i]->next->num); 
      adjlist[i] = adjlist[i]->next; 
     } 
     printf("NULL\n"); 
    } 
} 
int main(){ 
    Graph* graph = createGraph(4); 
    viewAdjmtx(graph->adjmtx,graph->nodes); 
    viewAdjlist(graph->adjlist,graph->nodes); 
    return 0; 
} 

Answer 1

您沒有爲您的數據結構分配足夠的內存。

adjmtx = malloc(sizeof(int*)); 
for(i=0 ; i<nodes ; i++) 
    adjmtx[i] = malloc(sizeof(int)); 

.... 

adjlist = malloc(sizeof(Node*)); 

你只分配足夠的內存爲一個條目，而不是nodes條目，所以你寫你過去的分配內存的界限，導致不確定的行爲。

分配每個nodes條目：

adjmtx = malloc(nodes * sizeof(int*)); 
for(i=0 ; i<nodes ; i++) 
    adjmtx[i] = malloc(nodes * sizeof(int)); 

.... 

adjlist = malloc(nodes * sizeof(Node*)); 

而且，當你用它做一定要free你在main內存。