C雙鏈表插入排序內存故障

Question

我想在dl_list上實現插入排序，其中包含char*值，但運行程序（沒有警告，我使用gcc）後出現分段錯誤。

這是我的結構：

struct node; 

typedef struct node { 
    char *name; 
    char *surname; 
    char *birth_date; 
    char *email; 
    char *phone; 
    char *address; 

    struct node *next; 
    struct node *prev; 
} node; 

//doubly linked_list 
typedef struct dl_list { 
    node *head; 
    node *tail; 
} dl_list; 

我按姓氏排序呢，後來的名字。我的名單上

int compare(node *alpha, node *beta) { 
    int a_surn_len = strlen(alpha->surname); 
    int b_surn_len = strlen(beta->surname); 

    for (int i = 0; i < ((a_surn_len > b_surn_len) ? b_surn_len : a_surn_len); i += 1) { 
     if (alpha->surname[i] > beta->surname[i]) return 1; 
     if (alpha->surname[i] < beta->surname[i]) return -1; 
     //if (alpha->surname[i] == beta->surname[i]) continue; 
    } 
    if (a_surn_len != b_surn_len) return a_surn_len > b_surn_len ? 1 : -1; 

    int a_n_len = strlen(alpha->name); 
    int b_n_len = strlen(beta->name); 
    for (int j = 0; j < ((a_n_len > b_n_len) ? b_n_len : a_n_len); j += 1) { 
     if (alpha->name[j] > beta->name[j]) return 1; 
     if (alpha->name[j] < beta->name[j]) return -1; 
     //if (alpha->surname[i] == beta->surname[i]) continue; 
    } 
    if (a_n_len != b_n_len) return a_n_len > b_n_len ? 1 : -1; 
    return 0; 
} 

這裏插入算法：當值同它返回0，如果alpha應該是公測前返回-1，否則1

dl_list *list_sort(dl_list *list) { 
    // zero or one element in list 
    if (list->head == NULL || list->tail == NULL) 
     return list; 
    // new_head is the first element of resulting sorted list 
    node *new_head = NULL; 
    while (list->head != NULL) { 
     node *current = list->head; 
     list->head = list->head->next; 
     // insert the first element into an empty sorted list 
     if (new_head == NULL) { 
      current->next = new_head; 
      new_head = current; 
      new_head->prev = NULL; 
     // or as the head of the sorted list 
     } else 
     if (compare(current, new_head) == -1) { 
      current->next = new_head; 
      new_head->prev = current; 
      new_head = current; 
      new_head->prev = NULL; 
     } else { 
      // insert current element into proper position in non-empty sorted list 
      node *ptr = new_head; 
      while (ptr != NULL) { 
       // middle of the list 
       if (compare(current, ptr->next) == -1) { 
        current->next = ptr->next; 
        ptr->next->prev = current; 
        ptr->next = current; 
        current->prev = ptr; 
        break; //done 
       // last element of the sorted list 
       } else 
       if (ptr->next == NULL) { 
        current->next = ptr->next; 
        ptr->next = current; 
        current->prev = ptr; 
        break;//done     
       } 
       ptr = ptr->next; 
      } 
     } 
    } 
    list->head = new_head; 
    node *ptr2; 
    for (ptr2 = list->head; ptr2->next != NULL; ptr2 = ptr2->next); 
    list->tail = ptr2; 

    return list; 
} 

我試圖檢查這個代碼在紙上，它似乎工作正常，在一些4-5元素清單。

Answer 1

的問題是在插入循環：你必須檢查ptr->next不NULL之前，節點ptr->next比較current：

 // insert current element into proper position in non-empty sorted list 
     node *ptr = new_head; 
     while (ptr != NULL) { 
      if (ptr->next == NULL) { 
       current->next = ptr->next; 
       ptr->next = current; 
       current->prev = ptr; 
       break;    
      } else 
      if (compare(current, ptr->next) < 0) { 
       current->next = ptr->next; 
       ptr->next->prev = current; 
       ptr->next = current; 
       current->prev = ptr; 
       break; 
      } 
      ptr = ptr->next; 
     } 

你也可以用strcmp()簡化比較功能：

int compare(const node *alpha, const node *beta) { 
    int res; 

    if ((res = strcmp(alpha->surname, beta->surname)) != 0) 
     return res; 
    if ((res = strcmp(alpha->name, beta->name)) != 0) 
     return res; 
    return 0; 
} 

而你應該只比較返回值與0而不是顯式地-1或1。

這裏是一個簡化的版本：

dl_list *list_sort(dl_list *list) { 
    // zero or one element in list 
    if (list->head == NULL || list->tail == NULL) 
     return list; 
    // new_head is the first element of resulting sorted list 
    node *new_head = NULL; 
    while (list->head != NULL) { 
     node *current = list->head; 
     list->head = list->head->next; 
     if (new_head == NULL) { 
      // insert the first element into an empty sorted list 
      current->prev = current->next = NULL;     
      new_head = current; 
     } else 
     if (compare(current, new_head) < 0) { 
      // or as the head of the sorted list 
      current->next = new_head; 
      current->prev = NULL; 
      new_head->prev = current; 
      new_head = current; 
     } else { 
      // insert current element into proper position in non-empty sorted list 
      node *ptr = new_head; 
      while (ptr != NULL) { 
       if (ptr->next == NULL) { 
        current->next = NULL; 
        ptr->next = current; 
        current->prev = ptr; 
        break;    
       } else 
       if (compare(current, ptr->next) < 0) { 
        current->next = ptr->next; 
        ptr->next->prev = current; 
        ptr->next = current; 
        current->prev = ptr; 
        break; 
       } 
       ptr = ptr->next; 
      } 
     } 
    } 
    list->head = new_head; 
    node *ptr2; 
    for (ptr2 = list->head; ptr2->next != NULL; ptr2 = ptr2->next) 
     continue; 
    list->tail = ptr2; 

    return list; 
} 

Answer 2

你的代碼很長，如果沒有一個簡單的例子就很難調試。也許，你可以用-g標誌編譯並使用valgrind。該工具會給你的內存故障:)

只需使用的線：valgrind --track-origins=yes ./executable

Answer 3

你的問題是，您的插入循環並沒有真正意義：

node *new_head=NULL; 
    while(list->head != NULL){ 
     node *current=list->head; 
     list->head=list->head->next; 
     // insert the first element into an empty sorted list 
     if(new_head == NULL){ 
      current->next=new_head; 
      new_head=current; 
      new_head->prev=NULL; 

1）您可以設置new_head到是指向NULL

2）你把保持的head參考在current和使head = head->next

3）在你的第一個循環new_head仍然是NULL，所以你輸入if語句並設置current->next=new_head。但new_head指向NULL，所以這會導致問題！

4）現在，當你設置new_head=current，current/new_head的next指針指向NULL。

5）最後你設置new_head->prev到NULL，這意味着現在current/new_head點NULL在兩個方向，但你的循環正在等待list->head是NULL！這不會發生，所以一旦你做一個迭代，並嘗試着你最終移動在else塊

} else{ 
     // insert current element into proper position in non-empty sorted list 
     node *ptr=new_head; 
     while(ptr != NULL){ 
      // middle of the list 
      if(compare(current, ptr->next) == -1){ 
       current->next=ptr->next; 
       ptr->next->prev=current; 
       ptr->next=current; 
       current->prev=ptr; 
       break; //done 
      // last element of the sorted list 
      } else if(ptr->next == NULL){ 
       current->next=ptr->next; 
       ptr->next=current; 
       current->prev=ptr; 
       break;//done     
      } 
      ptr=ptr->next; 
     } 
    } 

6）此塊試圖比較current到new_head->next。但是new_head->next是NULL！