Sortieren in alphabetischer Reihenfolge eine Liste in c

Question

Hallo ich ein Programm schreibt, das eine Liste von Studenten verwalten, i eine Liste verwendet, wird jedes Element wie folgt beschrieben:

struct student 
{ 
    char lastname[50]; 
    char name[50]; 
    char date_of_birth[50]; 
    char height[50]; 
    struct student *next; 
}; 

struct student *root=0; //this is the root node 

Dies ist, wie ich Element hinzufügen zur Liste:

void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50]) 
{ 
    if(*root == 0) 
    { 
     *root = malloc(sizeof(struct student)); 
     strcpy((*root)->lastname,lastname); 
     strcpy((*root)->name,name); 
     strcpy((*root)->date_of_birth,date_of_birth); 
     strcpy((*root)->height,height); 

     (*root)->next = 0; 
    } 
    else 
    { 
     add_element(&(*root)->next,lastname,name,date_of_birth,height); 
    } 
} 

ich schrieb auch 2 Funktion, ist eine aus einer Datei zum Lesen, die andere ist die Datei zu schreiben, enthält die Datei, die alle Studenten, alles funktioniert, aber ich brauche eine Funktion alle zu sortieren Das Element in alphabetischer Reihenfolge nach Nachnamen, ich habe versucht, einen zu schreiben, aber es funktioniert nicht, es stürzt ständig ab.

habe ich versucht, eine Menge Dinge, und sie hat nicht funktioniert, dies ein Versuch ist, und es funktioniert nicht :-(

mir bitte

void sort(struct student *head) 
{ 
    struct student **current; 
    struct student *tmp; 

    for(current = &head ; *current !=NULL ; current = (*current)->next) 
    { 
     if((*current)->next == NULL) 
     { 
      break; 
     } 
     switch(strcmp((*current)->lastname,(*current)->next->lastname)) 
     { 
      case 0: 
      { 
       printf("user not valid"); 
       break; 
      } 

      case 1: 
      { 
       tmp = *current; 
       *current = (*current)->next; 
       (*current)->next = tmp; 
       break; 
      } 
     } 
    } 
} 

Answer 1

Nach einschließlich Bemerkungen von Kommentaren helfen Um den vorgeschlagenen Quellcode zu korrigieren, fehlen beim Algorithmus zum Sortieren der verketteten Liste einige Schritte.Um zumindest eine verknüpfte Liste zu sortieren, ist es notwendig, zwei Schleifen zu haben.Die Wahl, die für einen struct student **current Zugriff verwendet wird, ist für a komplex zwei verschachtelte Schleifen

Hier ist ein weiterer Powder Sortierfunktion mit der optimierten qsort() Funktion.

Schritt 1 - vor dem Anzeigen der Funktion, um eine Liste zu sortieren, soll der Zeiger root geändert werden.

ersten Verfahren verwendet für die add_element() durch die Adresse des der Zeiger sendet.

void sort(struct student **root) 
{ 
... 
} 

Zweite Methode, um das modifizierte root zurückzukehren.

struct student *sort(struct student *root) 
{ 
... 
    return (root); 
} 

Schritt 2 - Die Funktion sort() Verwendung qsort() quicksort Funktion.

Die Methode weist ein temporäres Array von Zeigern zu, damit ein Element fester Größe sortiert werden kann.

1. Die erste Schleife ist notwendig, um die Anzahl der zu sortierenden Zeiger zu kennen (wenn weniger als 2, ist keine Sortierung erforderlich);
2. Nachdem Sie das Array struct student * zugewiesen haben, füllen Sie das Array, indem Sie für jedes Element der verknüpften Liste eine Schleife verwenden;
3. Rufen Sie die qsort() Funktion auf, indem Sie die angepasste Vergleichsfunktion node_compare() verwenden (siehe nächster Schritt);
4. Stellen Sie die verknüpfte Liste mit den sortierten Zeigern wieder her, indem Sie den Wert struct student *next erzwingen (der erste ist *root und der letzte zeigt auf NULL).
5. das temporäre Array von struct student * freigeben;

Das ist alles.

// 
void sort(struct student **root) 
{ 
    struct student *tmp; 
    struct student **array; 
    int i,icount; 

    // number of nodes to be sorted 
    for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++); 
    if (icount<2) { 
     // no sort needed 
     return; 
    } 

    // allocate an array of pointers 
    array = (struct student **)malloc(icount*sizeof(struct student *)); 
    // push linked-list into array of pointers 
    for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++) { 
     array[icount]=tmp; 
    } 

    // quicksort using node_compare() customized function 
    qsort(array, icount, sizeof(struct student *), node_compare); 

    // pop linked-list from array of pointers 
    *root = array[0]; 
    (*root)->next = NULL; 
    for(tmp = *root,i = 1;i<icount;i++) { 
     tmp->next = array[i]; 
     array[i]->next = NULL; 
     tmp = tmp->next; 
    } 
    // free the allocated array of pointer 
    free(array); 
} 
// 

Schritt 3 - die Vergleichsfunktion node_compare() zu qsort() benötigt.

Die Funktion soll einen vorzeichenbehafteten Vergleich zurückgeben wie strcmp().

int node_compare(const void * a, const void * b) 
{ 
    // restore node pointers 
    struct student *node_a = *((struct student **)a); 
    struct student *node_b = *((struct student **)b); 

    if (node_b==NULL) return (-1); // force 'node_a' 
    if (node_a==NULL) return (+1); // force 'node_b' 
    // use the strcmp() function 
    return (strcmp(node_a->lastname,node_b->lastname)); 
} 

Enhancement - weil die add_element() ist einen rekursive Aufruf nicht kompatibel mit einer langen verketteten Liste verwendet wird, ist hier ein ganz einfacher nicht-rekursive Algorithmus.

Wenn der rekursive Algorithmus, um die Größe zu wenige Jahrhunderte von Elemente begrenzt, mit 100.000 Elementen (40Mb verketteten Liste), zufallsgeneriert und sortiert getestet das vorgeschlagene einer wurde.

void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50]) 
{ 
    struct student **current; 

    for(current = root; *current !=NULL ; current = &((*current)->next)); 
    *current = (struct student *)malloc(sizeof(struct student)); 
    strcpy((*current)->lastname,lastname); 
    strcpy((*current)->name,name); 
    strcpy((*current)->date_of_birth,date_of_birth); 
    strcpy((*current)->height,height); 

    (*current)->next = NULL; 
}