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; 

сортировать его по фамилии, а затем имя. Когда значения равно возвращает 0, если альфа должен быть перед бетой он возвращается -1, в противном случае 1:

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; 
} 

А вот алгоритм вставки в моем списке:

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перед тем сравнения current с узлом ptr->next:

 // 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 «s next указатель указывает на NULL.

5) Наконец вы установили new_head->prev в NULL, а это означает, что теперь current/new_head пункт NULL в обоих направлениях, но ваш цикл ждет list->head быть 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; 
     } 
    } 

6) Этот блок пытается сравнить current с new_head->next. Но new_head->next - NULL!