創建鄰接表

Question

我有問題以正確的順序創建相鄰列表。我認爲CreateAdjList（void）方法存在一些問題。我用完了想法。請給我一些提示。基本上我有圖形和創建連接邊緣上的鄰接列表。

#include <stdio.h> 
#include <stdlib.h> 
#define maxV 100        
typedef struct graphnode{       
    int vertex; 
    struct graphnode *next; 
}Node; 
Node **node;        
Node **nodeT; 

FILE *fp; 

void initial(int nv);        
void AdjList(void);        
void PrintAdjList(int nv);       


int main() 
{ 
    int nv; 

    fp= fopen("input.txt","r"); 
    fscanf(fp,"%d",&nv); 
    initial(nv); 
    CreateAdjList(); 
    PrintAdjList(nv); 

    return 0; 
} 



void initial(int nv) 
{ 
    int i; 
    node = new Node *[maxV]; 

    for(i=1;i<=nv;i++){ 
     node[i] = (Node *)malloc(sizeof(Node)); 
     node[i]->next=NULL; 


    } 

} 


//CREATE ADJACENCY LIST - 
void CreateAdjList(void) 
{ 
    int v1,v2; 
    Node *ptr; 

while(fscanf(fp,"%d%d",&v1,&v2)!=EOF){ 

     ptr = (Node *)malloc(sizeof(Node)); 
     ptr->vertex = v2; 
     ptr->next = node[v1]->next; //Problem could be here 
     node[v1]->next = ptr; 

    } 

    fclose(fp); 
} 




//PRINT LIST 
void PrintAdjList(int nv) 
{ 
    int i; 
    Node *ptr; 

    for(i=1; i<=nv; i++){ 
     ptr = node[i]->next; 
     printf(" node[%2d] ",i); 
     while(ptr != NULL){ 
      printf(" -->%2d", ptr->vertex); 
      ptr=ptr->next; 
     } 
     printf("\n"); 
    } 
    printf("\n"); 

} 

實際程序輸出 - 錯誤的順序。我附上輸出列表 打印在崇敬的方式。

輸入：

8 
1 2 
2 3 
2 5 
2 6 
3 4 
3 7 
4 3 
4 8 
5 1 
5 6 
6 7 
7 6 
7 8 
8 8 
0 0 

Expected Output: 
Adjacency list represenation: 
1: 2 
2: 3 5 6 
3: 4 7 
4: 3 8 
5: 1 6 
6: 7 
7: 6 8 
8: 8 

我的實際輸出顯示錯誤的命令。如果你看一下節點的正確順序應該是 2 - > 3-> 6-> 5

node[ 1] --> 2 
node[ 2] --> 6 --> 5 --> 3 
node[ 3] --> 7 --> 4 
node[ 4] --> 8 --> 3 
node[ 5] --> 6 --> 1 
node[ 6] --> 7 
node[ 7] --> 8 --> 6 
node[ 8] --> 8 

Answer 1

曾在此裂紋，因爲它已經有一段時間，因爲我做了C :)

你所追求的是更多沿着下面的線 - 注意，有幾個錯誤，我不明白它會如何工作。在文件末尾加上'0 0'，以及在循環中使用1-> nv的事實，從來不會有節點[0]元素，因此總是失敗。

在我的例子中，我保持數組稀疏（只分配實際存在的節點），同時滿足其他條件。我也不在乎他們進來的順序，所以輸入文件可能是無序的。還要注意，如果文件數據有稀疏的數據（例如，第一個數字爲10，並且它缺少像'9 x'之類的東西），則可能需要更新打印方法。

void initial(int nv) 
{ 
    node = (Node **)malloc(maxV * sizeof(Node *)); 
} 

//CREATE ADJACENCY LIST - 
void CreateAdjList(void) 
{ 
    int v1,v2; 
    Node *ptr; 

    while(fscanf(fp,"%d %d",&v1,&v2)!=EOF){ 

     ptr = (Node *)malloc(sizeof(Node)); 
     ptr->vertex = v2; 

     if (node[v1]==NULL) { 
      node[v1] = (Node *)malloc(sizeof(Node)); 
      node[v1]->vertex = v1; 
      node[v1]->next = NULL; 
     } 

     Node *next = node[v1]; 
     while (next->next!=NULL) 
      next = next->next; 

     next->next = ptr; 

     //ptr->next = &(*(node[v1])->next); //Problem could be here 
     //node[v1]->next = ptr; 
    } 

    fclose(fp); 
}