insertion d'un nouvel élément dans la liste chaînée avec tri C

Question

J'ai un problème lors de l'insertion d'une chaîne dans la position correcte (insertion du tri) dans la liste chaînée. Quand j'ajoute quelques positions dans la liste liée et termine le programme en tapant '0', le programme me montre seulement la première position. Aussi j'ai des doutes sur "(strcmp (tmp-> ch, nouveau-> ch)> 0)" ça marche comme je suis en train de penser? (Comparez le nouvel élément avec le courant (je veux dire qu'il devrait être '>' ou ' < ')). Je serai vraiment reconnaissant pour tous les conseils;) est mon code .Il:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define MAX_L 30 

typedef struct elem{ 
    char ch[MAX_L]; 
    struct elem *next; 
    struct elem *prev; 
} list_elem; 

void add_to_list (list_elem *first, char ch[MAX_L]) 
{ 
    list_elem *new=(list_elem*)malloc(sizeof(list_elem)); 

    strcpy(new->ch, ch); 
    list_elem *tmp=first; 
    do 
    { 
     if(tmp->next==NULL) 
     { 
      tmp->next=new; 
      new->prev=tmp; 
      new->next=NULL; 
     } 
     if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element 
     { 
      new->prev=tmp->prev; 
      new->next=tmp; 
      tmp->prev=new; 
     } 
     else 
     tmp=tmp->next; 

    }while (tmp->next!=NULL); 

} 


void print_list(list_elem *first) 
{ 
    first=first->next; 
    if(first->ch==NULL) 
    printf("lista jest pusta!!\n"); 
    while(first->next!=NULL){ 
    printf("%s\n",first->ch); 
    first=first->next;} 
    printf("%s\n",first->ch); 
} 



int main() 
{ 
    list_elem *first=(list_elem*)calloc(1,sizeof(list_elem)); 
    first->next=NULL; 
    first->prev=NULL; 

    char a; 
    char ch[MAX_L]; 
    printf("write ' 0 ' to end program.\n"); 
    printf("write smth to add it to list: \n"); 
     while(ch[0]!='0'){ 
     scanf("%s",&ch); 
     add_to_list(first,ch);} 
    print_list(first); 
    return 0; 
} 

Answer 1

Il y a des problèmes dans la boucle add_to_list:

do { 
    if(tmp->next==NULL) 
    { 
     tmp->next=new; 
     new->prev=tmp; 
     new->next=NULL; 
     break; // you must exit here, you don't want to go the "if" below... 
    } 
    if (strcmp(tmp->ch,new->ch)>0) 
    { 
     if(tmp->prev != NULL) 
     { 
      tmp->prev->next = new; // link from previous to the new element 
     } 
     new->prev=tmp->prev; 
     new->next=tmp; 
     tmp->prev=new; 
     break; // you should exit here, work is done 
    } 
    else { 
     tmp=tmp->next; 
    } 
} while (1); // try again 

Un problème aussi ici:

scanf("%s",&ch); // should be scanf("%s",ch); 

Et pour votre question:

Aussi j'ai des doutes sur "(strcmp (tmp-> ch, nouveau-> ch)> 0)" il fonctionne comme je pense?

Si vous avez tord, vous trierez dans l'ordre inverse, donc ce sera facile à corriger.

Answer 2

On dirait que lorsque vous insérez avant tmp vous ne définissez pas tmp->prev->next-new

Pour plus de clarté:

if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element 
    { 
     new->prev=tmp->prev; 
     new->next=tmp; 
     tmp->prev=new; 
    } 

devrait être:

if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element 
    { 
     tmp->prev->next=new; 
     new->prev=tmp->prev; 
     new->next=tmp; 
     tmp->prev=new; 
    } 

Remarque: l'utilisation de new pour un nom de variable est généralement désapprouvée car elle n'est pas immédiatement reconnaissable en tant que variable car la plupart des programmeurs auront de l'expérience en Java/C#/C++, où new est un mot clé.

Remarque secondaire n ° 2: ne pas lancer malloc. Je l'ai fait jusqu'à récemment quand j'ai lu this fil de la pile. C'est une très bonne lecture.

Answer 3

1. list_elem *first=(list_elem*)calloc(1,sizeof(list_elem));

   Comment savez-vous si calloc ou non réussi?
   Vérifiez si first est NULL ou non, puis accédez uniquement à first->next.

---

2. while(ch[0]!='0')

   Jusqu'à ce point de réseau ch contient ordures. Alors, comment pouvez-vous comparer avec ch[0] avec '0'?

---

3. scanf("%s",&ch);

   %s attend un argument de char * de type alors que le type de &ch est char (*)[30].

   Vous pouvez également éviter le dépassement de tampon accidentel si l'utilisateur entre la chaîne avec la longueur>sizeof(ch). Spécifiez la largeur maximale du champ pour y remédier.

---

4. first=first->next; dans print_list()

   Ici vous venez sauté le premier élément.

---

5. if(first->ch==NULL)

   Qu'est-ce que vous voulez vraiment faire ici? Vous souhaitez probablement vérifier si la chaîne first->ch est vide ou non. Si oui, alors c'est pas le moyen de vérifier cela. Au lieu de vérifier first->ch[0] == '\0'

---

6. while(ch[0]!='0')

   Pour vérifier si l'utilisateur est entré 0 ou autre chaîne, c'est une façon incorrecte. Cela rejettera les chaînes à partir de 0 (par exemple "0bar")

   Manière correcte serait:

   while((ch[0]!='0') || (strlen(ch) > 1))

---

7. Pause sur la boucle une fois que vous avez inséré le nœud new dans la liste

   if (strcmp(tmp->ch,new->ch)>0) 
   { 
       new->prev=tmp->prev; 
       new->next=tmp; 
       tmp->prev=new; 
   } 
   

   Ici, après l'insertion du nœud new, l'expression ifstrcmp(tmp->ch,new->ch)>0 restera true dans toutes les itérations de boucle suivantes car nous n'avons pas modifié tmp et new. Donc, cela conduira à une boucle infinie. La seule exception à cette règle est .

   Solution:

   cassure de la boucle, dès que le noeud new est inséré dans la liste. Il suffit d'écrire break; comme la dernière déclaration ci-dessus strcmpif