c：找到兩個簡單列表之間的連接（公共節點）

Question

我正在C中練習，在那裏我必須找出兩個列表（指針在同一節點）之間是否存在連接。

我想有兩個for循環來做到這一點，比較指針（或我是這麼認爲的......）：

• newList()：創建一個簡單的連接列表。
• findsize()：返回節點數量。
• synthesi()：打印控制公共節點的位置並返回節點上的指針（如果存在）。

而且編譯器「抱怨」關於tmp = tmp->next偶爾因爲最後next指針list這爲空（因爲它應該是一個簡單的列表）的約cur = cur->next。

struct list{ 
    int num; 
    struct list *next; 
}; 

struct list* synthesi(struct list*, struct list*); 
int findSize(struct list*); 
struct list* newList(); 

void main() 
{ 
    struct list *hd1, *hd2, *syn; 
    int sizeofhd1, sizeofhd2; 

    hd1 = newList(); 
    hd2 = newList(); 

    /*do{         test 
     printf("list1: %d\n", hd1->num); 
     printf("list1: %d\n", hd2->num); 
     hd1 = hd1->next; 
     hd2 = hd2->next; 
    } while (hd2!=NULL); 
    */ 
    sizeofhd1 = findSize(hd1); 
    sizeofhd2 = findSize(hd2); 

    //printf("list1: %d\n", sizeofhd1);  test 
    //printf("list2: %d\n", sizeofhd2); 

    syn = (struct list*)malloc(sizeof(struct list)); 
    syn = synthesi(hd1, hd2); 

    printf("synthesi: %d\n", syn->num); 
} 

int findSize(struct list *head) 
{ 
    struct list *cur; 
    int flag = 0; 

    cur = (struct list*)malloc(sizeof(struct list)); 
    cur = head; 
    do 
    { 
     flag++; 
     cur = cur->next; 
    }while (cur!=NULL); 
    free(cur); 
    return flag; 
} 

struct list* synthesi(struct list *head1, struct list *head2) 
{ 
    int i,j, pos, sizeofhd1, sizeofhd2; 
    struct list *tmp; 
    tmp = (struct list*)malloc(sizeof(struct list)); 

    sizeofhd1=findSize(head1); 
    sizeofhd2 = findSize(head1); 

    for (i = 0; i < sizeofhd1; i++) 
    { 
     for (j = 0; j < sizeofhd2; j++) 
     { 
      if (head1->next == tmp) 
      { 
       pos = i + i; 
       break; 
      } 
      tmp = tmp->next; 
     } 
     head1 = head1->next; 
     tmp = head2; 

    } 
    if (pos == 0) 
    { 
     puts("no connection!\n"); 
     return (struct list*)NULL; 
    } 
    else{ 
     puts("found at position: "); 
     printf("%d\n", pos); 
     return head1->next; 
    } 
} 

struct list* newList() 
{ 
    struct list *mylist, *hd; 
    int i; 
    hd = (struct list*)malloc(sizeof(struct list)); 
    mylist = (struct list*)malloc(sizeof(struct list)); 

    mylist->num = 7; 
    mylist->next = (struct list*)malloc(sizeof(struct list)); 
    hd = mylist; 
    for (i = 0; i < 10; i++) 
    { 
     mylist->next = (struct list*)malloc(sizeof(struct list)); 
     mylist->next->num = i + 1; 
     mylist = mylist->next; 
     mylist->next = (struct list*)NULL; 
    } 
    return hd; 
} 

Answer 1

我懷疑這是編譯器'偶爾'抱怨。我打賭一旦編譯和鏈接的程序並不總是工作：

findsize似乎有一些錯誤。首先你分配一個新的列表，然後覆蓋新分配的列表，然後在例程結束時釋放它，釋放你試圖找到大小的列表。試試這個：

int findSize(struct list *node) 
{ 
    int num = 0; 
    for (; node ; node=node->next) 
     num++; 
    return num; 
} 

在synthesi您再次分配列表項並沒有任何特別的理由。你所需要做的就是遍歷一個列表，然後逐步遍歷其中的另一個列表。如果這個想法是找到兩個列表中的項目（即其中num是一樣的），這樣的：

struct list * 
findcommonnumber (struct list *lista, struct list *listb) 
{ 
    struct list *a; 
    struct list *b; 
    for (a=lista; a; a=a->next) 
    { 
     for (b=listb; b; b=b->next) 
     { 
      if (a->num == b->num) 
      { 
       printf ("Found %d at %p and %p\n", a->num, a, b); 
       return a; 
      } 
     } 
    } 
    return NULL; 
} 

這是假設你實際上是試圖找到與這兩個列表相同數量的項目，因爲相同的實際項目不應該在兩個列表中（想一想）。

此外，您的list結構似乎是一個列表項結構，可能應該這樣稱呼。