Insérer un numéro dans une liste chaînée, pourquoi le nombre est-il inséré à la deuxième position à chaque fois?

Je travaille sur un projet concernant la liste chaînée, je ne parviens pas à insérer un numéro dans une liste chaînée sortingée. Le numéro inséré à la deuxième position à chaque fois, je ne peux pas comprendre où est le problème. Voici mon code:

void insertSort(struct linkedList *n,int num,int *length){ //insert number to a sort linked list node *new = (node *) malloc(sizeof(node)); //create a new node new->next=NULL; new->data = num; while(n!=NULL&&n->data > new->data){ // find which position num should insert in sorted list n = n->next; } new->next = n->next; n->next= new; length += 1; } 

n est en tête de la liste chaînée. J’ai initialisé la tête pointe sur le premier noeud et n’a pas de valeur. Voici comment j’appelle cette fonction:

 insertSort(head->next,num,&length); 

Le numéro inséré à la deuxième position à chaque fois. Comme je veux insérer 45 dans la liste chaînée sortingée , après l’insertion, la liste serait . 45 inserts à la deuxième position pour une raison quelconque.

Le problème :

Le numéro inséré à la deuxième position à chaque fois …

se produit parce que dans cette partie du code:

 while(n!=NULL&&n->data > new->data){ // find which position num should insert in sorted list n = n->next; } new->next = n->next; n->next= new; 

vous insérez le nouveau noeud après le n->next .

Supposons que le premier nœud de votre liste liée contient les données 16 et que vous souhaitez maintenant insérer le nouveau nœud avec les données 45 dans la liste liée, la condition de boucle while échouera car 16 > 45 sera considéré comme false .

Et la déclaration after while loop new->next = n->next; définira le prochain du nouveau nœud sur le suivant du premier nœud et n->next= new; va insérer le nouveau noeud après le premier noeud. Par conséquent, le nouveau noeud inséré à la deuxième position à chaque fois.

Il y a peu de problèmes avec votre fonction insertSort() comme:

  • Il ne suit pas la head de la liste liée lors de l’insertion d’un nœud dans la liste liée et,
  • Que se passera-t-il si le nœud inséré est le premier nœud de la liste liée? Dans ce cas, n sera NULL et dans insertSort() après la boucle while, elle insertSort() next of nnew->next = n->next; .

En regardant l’exemple que vous avez donné – <16,32,72,81,97>, vous voulez insérer par ordre croissant. Tu peux faire:

 struct linkedList *insertSort(struct linkedList *n, int num, int *length) { struct linkedList *first_node = n; struct linkedList *new_node = malloc(sizeof(struct linkedList)); //create a new node new_node->next=NULL; new_node->data = num; if (first_node == NULL || first_node->data >= new_node->data) { new_node->next = first_node; first_node = new_node; } else { struct linkedList *temp = first_node; while (temp->next != NULL && temp->next->data < new_node->data) { temp = temp->next; } new_node->next = temp->next; temp->next = new_node; } *length += 1; return first_node; } 

Ici, vous pouvez voir que j’ai changé le type de retour void en struct linkedList * sorte qu’après l’insertion du nouveau noeud à l’emplacement approprié dans la liste liée, insertSort() renvoie la head de la liste liée. De cette façon, vous pouvez suivre la head de la liste liée après chaque insertion. Vous devez juste faire:

 head = insertSort(head, num, &length); 

d’où que vous insertSort() .

Alternativement, vous pouvez passer l’adresse du pointeur head dans insertSort() et en garder la trace, si vous ne voulez pas changer le type de retour de insertSort() , comme ceci:

 void insertSort(struct linkedList **head, int num, int *length) { struct linkedList *new_node = malloc(sizeof(struct linkedList)); //create a new node new_node->next=NULL; new_node->data = num; if (*head == NULL || (*head)->data >= new_node->data) { new_node->next = *head; *head = new_node; } else { struct linkedList *temp = *head; while (temp->next != NULL && temp->next->data < new_node->data) { temp = temp->next; } new_node->next = temp->next; temp->next = new_node; } *length += 1; } 

Vous pouvez appeler insertSort() comme ceci:

 insertSort(&head, 32, &length); 

J’espère que cela t’aides.

parce que vous ne testez jamais la position du noeud. votre code ne place que le nouveau noeud en 2ème position. il ne vérifie pas où il devrait être dans la liste sortingée essayer ci-dessous

  void sortedInsert(struct Node** head_ref, struct Node* new_node) { struct Node* current; /* Special case for the head end */ if(*head_ref == NULL || (*head_ref)->data >= new_node->data) { new_node->next = *head_ref; *head_ref = new_node; } else { /*Locate the node before the point of insertion */ current =*head_ref; while (current->next!=NULL && current->next->data < new_node->data) { current = current->next; } new_node->next =current->next; current->next = new_node; } }