Сортировка связанного списка по алфавиту в C

Question

Я написал следующую программу для хранения ввода из файла в формате адреса и сортировки связанного списка в алфавитном порядке по имени города, хранящегося в узле. Входной образец будет выглядеть следующим образом:

Titus \n 
Kollman \n 
1522 Foggy Grove Loop \n 
Wildcat NC 27507 \n 
(252) 644-5477 \n 

... и т.д.

Мой код в настоящее время составляет несортированный связанный список всех записей корректно, и я написал функцию сортировки для сортировки списка в алфавитном порядке. Когда я пытаюсь сортировать список, мой код просто непрерывно работает без вывода (застревает), и я не могу найти ничего плохого в моем алгоритме сортировки.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
/* make node structure to store the data in */ 
struct entry { 
    char fname[64]; 
    char lname[64]; 
    char city[64]; 
    char address[64]; 
    char cityandstate[64]; 
    char numb[64]; 
    struct entry* next; 
}; 

/* function to add entry that will be used in sort*/ 
void addEntryForSort(struct entry* list, struct entry* x){ 
    struct entry* newNode = (struct entry*) malloc(sizeof(struct entry)); 
    memcpy(newNode,x,sizeof(struct entry)); 
    newNode->next = NULL; 
    while (list->next != NULL){ 
     list = list->next; 
    } 
    list->next = newNode; 
} 
/*function to find the minimum (alpha)of a linked list */ 
struct entry* findMin(struct entry* begin){ 
    struct entry* curr = begin; 
    struct entry* min = curr; 
    curr = curr->next; 
    while (curr != NULL){ 
     if (strcmp(curr->city,min->city) < 0){ 
      min = curr; 
     } 
     else if (strcmp(curr->city,min->city)) 
      curr = curr->next; 
    } 
    return min; 
} 

/*sort function (attempt)*/ 
struct entry* sort(struct entry* top){ 
    struct entry* sorted = (struct entry*) malloc(sizeof(struct entry)); 
    struct entry* min = findMin(top); 
    struct entry* curr = top; 
    while (curr->next != NULL){ 
     if (top == min){ 
      addEntryForSort(sorted,min); 
      top = top->next; 
      min = findMin(top); 
      curr = top; 
     } 
     if (curr->next == min){ 
      addEntryForSort(sorted,min); 
      curr->next = curr->next->next; 
      min = findMin(top); 
      curr = top; 
     } 
     else { 
      curr = curr->next; 
     } 
    } 
    addEntryForSort(sorted,top); 
    addEntryForSort(sorted,curr); 
    return sorted; 
} 


int main() { 

    struct entry* head = (struct entry*) malloc(sizeof(struct entry)); 
    char x[64]; 

    fgets(x,64,stdin); 
    strcpy(head->fname,x); 
    strtok(head->fname,"\n"); 

    fgets(x,64,stdin); 
    strcpy(head->lname,x); 
    strtok(head->lname,"\n"); 

    fgets(x,64,stdin); 
    strcpy(head->address,x); 
    strtok(head->address,"\n"); 

    fgets(x,64,stdin); 
    strcpy(head->cityandstate,x); 
    strtok(head->cityandstate,"\n"); 
    strncpy(head->city,head->cityandstate,strlen(head->cityandstate)-10); 

    fgets(x,64,stdin); 
    strcpy(head->numb,x); 
    strtok(head->numb,"\n"); 
    fgets(x,64,stdin); 

    int line = 7; 

    struct entry* curr = (struct entry*) malloc(sizeof(struct entry)); 
    struct entry* prev = head; 
    head->next = curr; 

    while (fgets(x,64,stdin) != NULL) { 
     switch (line % 6){ 
      case 1: 
       strcpy(curr->fname,x); 
       strtok(curr->fname,"\n"); 
       break; 
      case 2: 
       strcpy(curr->lname,x); 
       strtok(curr->lname,"\n"); 
       break; 
      case 3: 
       strcpy(curr->address,x); 
       strtok(curr->address,"\n"); 
       break; 
      case 4: 
       strcpy(curr->cityandstate,x); 
       strtok(curr->cityandstate,"\n"); 
       strncpy(curr->city,curr->cityandstate,strlen(curr->cityandstate)-10); 
       if (strcmp(curr->city,"Old Roach MO 6") == 0){ 
        strcpy(curr->city,"Old Roach"); 
       } 
       break; 
      case 5: 
       strcpy(curr->numb,x); 
       strtok(curr->numb,"\n"); 
       break; 
      case 0: 
       curr->next = (struct entry*) malloc(sizeof(struct entry)); 
       prev = curr; 
       curr = curr->next; 
       break;    
     } 
     line++; 
    } 

    curr=sort(head); 
    while (curr!= NULL){ 
     printf("%s %s %s\n",curr->fname,curr->lname,curr->city); 
     curr = curr->next; 
    } 
} 

Answer 1

В этом коде есть много проблем.

Во-первых, вы никогда не инициализируете свои структуры, и malloc также не должен делать это, поэтому член next может быть недействительным, что приведет к сбою всего следующего кода. Вы должны написать:

struct entry* head = (struct entry*) malloc(sizeof(struct entry)); 
head->next = NULL; /* ensure next is correctly initialized */ 

и следующий:

struct entry* curr = (struct entry*) malloc(sizeof(struct entry)); 
curr->next = NULL; /* ensure next is correctly initialized */ 

используется strncpy для инициализации city поля. Но strncpy не добавляет завершающий нуль, оставляя ваше поле незавершенным. Вы должны написать:

strncpy(curr->city,curr->cityandstate,strlen(curr->cityandstate)-10); 
curr->city[strlen(curr->cityandstate)-10] = '\0'; 

(то же самое с head для первой записи).

В findMin, если две записи сравниваются, вы останетесь там, потому что вы не звоните curr = curr->next. Это должно быть действительно:

/*function to find the maximum (alpha)of a linked list */ 
struct entry* findMax(struct entry* curr){ 
    struct entry* min = curr; 
    while (curr != NULL){ 
     if (strcmp(curr->city,min->city) > 0){ 
      min = curr; 
     } 
     curr = curr->next; 
    } 
    return min; 
} 

я получаю максимум вместо минимума, так как для сортировки по отдельности связанный список с простой пузырьковой сортировки, самый простой способ для сортировки на месте, принимая наибольший элемент из список и поставить его на первое место в результирующем списке. Более того, это позволяет не выделять новые структуры, потому что, если вы не хотите утечки памяти, вы должны должны освободить каждый выделенный блок.sort функция может стать:

/*sort function (attempt)*/ 
struct entry* sort(struct entry* top){ 
    struct entry* sorted = NULL; 
    while (top != NULL) { 
     struct entry* max = findMax(top); 
     if (max == top) { /* if max is first, simply increment top */ 
      top = top->next; 
     } 
     else { /* else make prev->next = max->next to remove max from the list */ 
      struct entry *curr = top; 
      while (curr->next != min) curr = curr->next; 
      curr->next = min->next; 
     } 
     /* and put current max in first place of the sorted list */ 
     max->next = sorted; 
     sorted = max; 
    } 
    return sorted; 
} 

Наконец, вы должны освободить все выделенные блоки памяти, добавив, что в конце основной:

/* free all elements of the linked list */ 
while(head != NULL) { 
    curr = head->next; 
    free(head); 
    head = curr; 
} 
return 0; /* never return random value to environment */ 

Но если вы хотите сделать серьезное программирование, вы должны также :

• проверить все входные функции, здесь fgets не должны возвращать NULL и буфер должен иметь \n в качестве последнего символа
• управляет форматом полей ввода (номер телефона, города и почтовый индекс) - в частности, опираясь на несколько позиций, начиная с конца строки, не удастся, если у вас нет надлежащего количества пробелов в конце линия
• поместить код для чтения записи в функции, потому что вы используете его в два раза, и вы должны научиться следовать DRY (не повторяться) наилучшей практикой использования

Answer 2

Я не уверен, что об этой проблеме еще (не проверял свой код), но рассмотреть этот кусок кода:

while (curr != NULL){ 
    if (strcmp(curr->city,min->city) < 0){ 
     min = curr; 
     /* curr gets stuck here and doesn't move */ 
    } 
    else if (strcmp(curr->city,min->city)) 
     /* curr gets stuck if curr->city is equal to min->city */ 
     curr = curr->next; 
} 

изменить его ниже и сообщить, если вы все еще сталкиваются с вашей проблемой.

while (curr != NULL) { 
    if (strcmp(curr->city, min->city) < 0) min = curr; 
    curr = curr->next; }