Créer une liste chaînée triée

Question

Après presque 3 ans, j'ai commencé à réapprendre C.

J'ai créé un Linked list, et j'aimerais l'étendre à la création d'une liste chaînée triée. Voici mon code:

typedef struct node{ 
int data; 
struct node *ptr; 
}node; 

node* insert(node* head, int num){ 
node *temp,*prev,*next; 
temp = (node*)malloc(sizeof(node)); 
temp->data = num; 
temp->ptr = '\0'; 
if(head=='\0'){ 
    head=temp; 
}else{ 
    next = head; 
    prev = next; 
    while(next->data<=num){ 
     prev = next; 
     next = next->ptr; 
    } 
    if(next==NULL){ 
     prev->ptr = temp; 
    }else{ 
     temp->ptr = prev->ptr; 
     prev-> ptr = temp; 
    } 

} 
return head; 
} 

void main(){ 
int num; 
node *head, *p; 
head = '\0'; 
do{ 
    printf("Enter a number"); 
    scanf("%d",&num); 
    if(num!=0) 
     head = insert(head,num); 
}while(num!=0); 
p = head; 
printf("\nThe numbers are:\n"); 
while(p!='\0'){ 
    printf("%d ",p->data); 
    p = p->ptr; 
} 
} 

Ceci est mon idée. Je traverse la liste jusqu'à ce que je trouve un numéro >= l'entrée. Je stocke le nœud précédent dans prev et le nœud next contient la valeur actuelle. Si next est null, alors la liste est terminée et le numéro est le plus élevé parmi la liste, donc il doit être inséré à la dernière place, si le nombre est quelque part où au milieu, la partie d'adresse du noeud précédent est stockée dans les noeuds temporaires partie de l'adresse maintenant pointeur de noeud temp détient l'adresse du noeud suivant.

Modifier: Problème avec mon code si j'entre 1,2 J'obtiens un message d'erreur comme a.exe has stopped working. J'utilise MinGW pour la compilation. Je romps la boucle lorsque les entrées utilisateur 0.

Answer 1

Vous devez changer la ligne

while(next->data<=num) 

à

while(next!='\0' && next->data<=num) 

Lorsque vous insérez le deuxième élément next sera '\0' à la deuxième itération et essayer d'obtenir le champ data avec next->data conduira à une faute de segmentation.

Avec la condition modifiée dans le temps si next!='\0' sera fausse (donc next=='\0') le tout est avorté et à cause de courts-circuits de &&next->data n'est pas calculé.

---

EDIT

Vous avez plus de problèmes dans votre code.

Si vous regardez l'entrée 2 1 0 alors la sortie avec un programme fonctionnant correctement devrait être 1 2 mais c'est plutôt 2 1. Le problème est que dans votre fonction insert vous ne considérez pas le cas où vous insérez le plus petit élément actuel qui sera la nouvelle tête.

Un autre problème est que vous ne libérez pas la mémoire malloc ed à la fin, ce qui conduit à des fuites de mémoire.

j'ai changé votre code à se comporter correctement:

#include <stdio.h> 
#include <stdlib.h> 

typedef struct node{ 
    int data; 
    struct node *ptr; 
} node; 

node* insert(node* head, int num) { 
    node *temp, *prev, *next; 
    temp = (node*)malloc(sizeof(node)); 
    temp->data = num; 
    temp->ptr = NULL; 
    if(!head){ 
     head=temp; 
    } else{ 
     prev = NULL; 
     next = head; 
     while(next && next->data<=num){ 
      prev = next; 
      next = next->ptr; 
     } 
     if(!next){ 
      prev->ptr = temp; 
     } else{ 
      if(prev) { 
       temp->ptr = prev->ptr; 
       prev-> ptr = temp; 
      } else { 
       temp->ptr = head; 
       head = temp; 
      }    
     } 
    } 
    return head; 
} 

void free_list(node *head) { 
    node *prev = head; 
    node *cur = head; 
    while(cur) { 
     prev = cur; 
     cur = prev->ptr; 
     free(prev); 
    }  
} 

int main(){ 
    int num; 
    node *head, *p; 
    head = NULL; 
    do { 
     printf("Enter a number"); 
     scanf("%d",&num); 
     if(num) { 
      head = insert(head, num); 
     } 
    } while(num); 
    p = head; 
    printf("\nThe numbers are:\n"); 
    while(p) { 
     printf("%d ", p->data); 
     p = p->ptr; 
    } 
    free_list(head); 
    return 0; 
} 

Voir https://ideone.com/wT5iQ8 pour mon code sur un testinput en même temps que la sortie correcte.