Liste liés Tri avec des chaînes en C

Question

J'ai un struct, avec un nom et un seul nœud appelé nextName

Il est une liste chaînée, et ma tâche est de créer la liste, en fonction de l'ordre alphabétique des cordes .

Alors ssi j'entre Joe Zolt et Arthur que je devrais obtenir ma liste structurée comme

Joe

Than

Joe Zolt

Than

Arthur Joe Zolt

J'ai des problèmes pour implémenter le c orrect Algorithm, qui placerait les pointeurs dans le bon ordre.

C'est ce que j'ai à partir de maintenant. Temp serait le nom que l'utilisateur vient d'entrer et tente de mettre dans la liste, namebox est juste une copie de ma racine, étant toute la liste

if(temp != NULL) 
     { 
       struct node* namebox = root; 
       while (namebox!=NULL && (strcmp((namebox)->name,temp->name) <= 0)) 
       { 
         namebox = namebox->nextName; 
         printf("here"); 
       } 
       temp->nextName = namebox; 
    namebox = temp; 
    root = namebox; 

This Works en ce moment, si j'entrer des noms tels que CCC BBB que AAA

I Get Back AAA BBB CCC quand j'imprimer

Mais si je mets AAA BBB CCC, lorsque j'imprime je reçois seulement CCC, il coupe l'arrêt précédent.

Edit:

que quelqu'un peut me montrer ce que le code ressemblerait, je ne peux pas le faire descendre.

Answer 1

Lorsque vous entrez AAA, BBB puis CCC namebox est toujours NULL lorsque la boucle est terminée.

Et vous faites:

// namebox is null 
temp->nextName = namebox; 
// namebox = CCC 
namebox = temp; 
// root = CCC 
root = namebox; 

Voilà pourquoi vous obtenez seulement CCC.

Maintenant, ce que vous devez faire dans ces cas est de vous assurer que CCC est ajouté à la fin de la liste et ne change pas de racine.

Answer 2

Ce que vous décrivez est Insertion Sort.

Lorsque vous entrez AAA, BBB, CCC et enfin, namebox est NULL lorsque la boucle while est fait.

Ensuite, lorsque vous faites temp->nextName = namebox, namebox est NULL. Après cela, vous définissez namebox à temp (qui contient CCC). Enfin, vous définissez root à namebox qui le définit également à CCC. C'est pourquoi vous obtenez CCC.

Dans votre algorithme, vous devez gérer le cas où vous ajoutez quelque chose à la fin ou au milieu de la liste et ne pas modifier la racine dans ces cas. En fait, cela devrait être le cas général.Ajout de choses à l'avant et à la fin devraient être vos cas particuliers.

Answer 3

if(temp != NULL) 
{ 
    struct node* namebox = root; 
    while (namebox!=NULL) 
    { 
     if(strcmp(namebox->Name,temp->Name) > 0) // if temp comes before this 
     { 
      temp->nextName = namebox->nextName; 
      namebox->nextName = temp; 
      //printf("here"); I'm guessing this is debugging stuff? 
     } 
     namebox = namebox->nextName; 
    } 
} 

c'est pour l'insertion générale, mais vous devez faire des cas particuliers lorsque vous ajoutez le premier nom et ajouter au début de la liste