Tri d’une liste chaînée en C

J’essaie de sortinger une liste chaînée en recherchant la plus grande valeur, en la supprimant de sa position, puis en l’insérant en haut de la liste.

La difficulté que je rencontre est la suppression et l’insertion en haut. Le problème semble être dans la condition if de la boucle while contenue dans la fonction sortList, mais je ne sais pas comment le résoudre.

Toute aide serait appréciée.

#include  #include  typedef struct node{ int num; struct node *next; } Node, *NodePtr; void printList(NodePtr np); NodePtr makeList(void); NodePtr makeNode(int n); NodePtr sortList(NodePtr list); int main(void) { NodePtr list; printf("Enter numbers for the list (0 to end)\n"); list = makeList(); printList(list); list = sortList(list); printList(list); return 0; } NodePtr makeList(void) { NodePtr makeNode(int), np, top, last; int n; top = NULL; if(scanf("%d", &n) != 1)n = 0; while(n != 0) { np = makeNode(n); if(top == NULL)top = np; else last->next = np; last = np; if(scanf("%d", &n)!=1)n=0; } return top; } void printList(NodePtr np) { while(np != NULL) { printf("%d\n", np->num); np = np->next; } } NodePtr makeNode(int n) { NodePtr np = (NodePtr)malloc(sizeof(Node)); np->num = n; np->next = NULL; return np; } NodePtr sortList(NodePtr list) { NodePtr top = list; NodePtr curr = NULL; NodePtr largest; NodePtr prev; prev = NULL; curr = top; largest = top; while(curr != NULL) { prev = curr; if(curr->num > largest->num) { largest = curr; prev->next = curr->next; largest->next = top; } curr = curr->next; } if(prev == NULL) { largest->next = top; return largest; } return largest; } 

Il y a des problèmes dans la fonction sortList .

Cette fonction ne place que quelques gros nœuds au début de la liste. Il ne cite pas toute la liste. vous pouvez utiliser un algorithme de sorting pour sortinger le fichier: quicksort / bubblesort / … je mets un code faisant un sorting à la fin de cette réponse.

voici un code faisant le genre de la liste:

// remplace le plus grand noeud par le premier puis effectue la même opération avec sublist (list-first element)

 NodePtr sortList(NodePtr list) { // if(list == null || list->next == null) return list; // the list is sorted. //replace largest node with the first : //1- find largest node : NodePtr curr, largest,largestPrev; curr = list; largest = list; prev = list; largestPrev = list; while(curr != NULL) { if(curr->num > largest->num) { largestPrev = prev; largest = curr; } prev = curr; curr = curr->next; } //largest node is in largest. //2- switching firt node and largest node : NodePtr tmp; if(largest != list) { largestPrev->next = list; tmp = list->next; list->next = largest->next; largest->next = tmp; } // now largest is the first node of the list. // calling the function again with the sub list : // list minus its first node : largest->next = sortList(largest->next); return largest; } 

Voici ma tentative de sortinger une liste liée individuellement en utilisant l’algorithme QuickSort. Si vous connaissez n, le temps d’exécution sera O (n log n). Vérifiez si cela aide.

 #include "malloc.h" typedef struct node { struct node *next; int val; } node; bool insert_node(struct node **head, int val) { struct node *elem; elem = (struct node *)malloc(sizeof(struct node)); if (!elem) return false; elem->val = val; elem->next = *head; *head = elem; return true; } int get_lval(struct node *head, int l) { while(head && l) { head = head->next; l--; } if (head != NULL) return head->val; else return -1; } void swap(struct node *head, int i, int j) { struct node *tmp = head; int tmpival; int tmpjval; int ti = i; while(tmp && i) { i--; tmp = tmp->next; } tmpival = tmp->val; tmp = head; while(tmp && j) { j--; tmp = tmp->next; } tmpjval = tmp->val; tmp->val = tmpival; tmp = head; i = ti; while(tmp && i) { i--; tmp = tmp->next; } tmp->val = tmpjval; } struct node *Quick_Sort_List(struct node *head, int l, int r) { int i, j; int jval; int pivot; i = l + 1; if (l + 1 < r) { pivot = get_lval(head, l); printf("Pivot = %d\n", pivot); for (j = l + 1; j <= r; j++) { jval = get_lval(head, j); if (jval < pivot && jval != -1) { swap(head, i, j); i++; } } swap(head, i - 1, l); Quick_Sort_List(head, l, i); Quick_Sort_List(head, i, r); } return head; } struct node *Sort_linkedlist(struct node *head) { struct node *tmp = head; // Using Quick sort. int n = 0; while (tmp) { n++; tmp = tmp->next; } printf("n = %d\n", n); head = Quick_Sort_List(head, 0, n); return head; } void print_list(struct node *head) { while(head) { printf("%d->", head->val); head = head->next; } printf("\n"); } int _tmain(int argc, _TCHAR* argv[]) { struct node *head = NULL; struct node *shead = NULL; insert_node(&head, 10); insert_node(&head, 12); insert_node(&head, 9); insert_node(&head, 11); insert_node(&head, 7); insert_node(&head, 1); insert_node(&head, 3); insert_node(&head, 8); insert_node(&head, 5); insert_node(&head, 2); insert_node(&head, 4); insert_node(&head, 6); print_list(head); shead = Sort_linkedlist(head); print_list(shead); return 0; } 

Cela devrait vraiment vous aider. C’est un très bon post.

En écrivant au plus largest->next vous avez écrasé curr->next . Donc, vous finissez par redémarrer depuis le début tout le temps.

Sois sûr que:

  1. la liste rest cohérente
  2. votre iterator de liste rest cohérent

Mais dans l’ensemble, votre code semble gravement endommagé. Je pense qu’il pourrait y avoir quelques autres erreurs dans votre logique de sorting.

Vous trouverez ci-dessous certains des problèmes rencontrés dans votre logique de sorting:

  1. Vous définissez le pointeur prev sur curr au début de la boucle elle-même, ce qui est incorrect. En faisant cela, vous rendez le pointeur actuel et le pointeur précédent, ce qui rend impossible la suppression du noeud.
  2. Vous devez également affecter le pointeur le plus grand au sumt, ce qui facilite la possibilité de définir le nœud le plus grand-> suivant le nœud supérieur réel.

Le code peut être modifié comme ci-dessous (juste un pointeur, vous devez vérifier vous-même les autres problèmes):

 while(curr != NULL) { if(curr->num > largest->num) { largest = curr; prev->next = curr->next; largest->next = top; top = largest; } prev = curr; curr = curr->next; } 
 // Program to sort a single linked list in ascending order // (without exchanging data in the nodes) /************************************************************************** There are two methods of sorting presented here(At a time,we can use any of these two functions to sort our single linked list.) - 1. Function 'void Sort()' - This function uses selection sort method(I think). In this function,a node whose data is the smallest in the list is made as 'head' node(ie starting node of the list) by scanning the whole list once.Then from the remaining list,again a node with the smallest data is found out whose address is kept in the 'next' field of previous node(head node).This process continues to sort the whole list. 2. Function 'void Sort_method2()' - This function uses insertion sort method(I think). In this function,starting from second node in the list, all previous node data(starting from 'head' node) are compared with current reference node (which is initially second node in the list).If 'data' field of current reference node is smaller than that of any of its previous nodes,then suitable changes in the 'next' field of corresponding nodes are made.If data in the current reference node is smaller than that in the 'head' node, then the current reference node is made as 'head' node. *********************************************************************/ #include #include #include #include struct node { int data; struct node *next; }; struct node *head,*head1; void Create_node(int data); void display(); void Sort(); void Sort_method2(); void main() { int choice,d; clrscr(); while(1) { printf("\n 1.Create new node"); printf("\n 2.Sort in ascending order"); printf("\n 3.Exit"); printf("\nEnter your choice : "); scanf("%d",&choice); switch(choice) { case 1: printf("\nEnter data :"); scanf("%d",&d); Create_node(d); break; case 2: Sort(); // At a time,we can use any of these two //Sort_method2(); // functions to sort our single linked list. break; case 3: exit(0); default:exit(0); } } // end of while(1) } // end of main() //-------------------------------------------- void Create_node(int d) { struct node *newnode,*temp; newnode = (struct node *)malloc(sizeof(struct node)); newnode -> data = d; newnode -> next = NULL; if(head == NULL) head = newnode; else { temp = head; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } // end of 'else' } // end of 'Create_node(int d)' //--------------------------------------------- void display() // Print linked list contents { struct node *temp; printf("\nList contents are :\n"); temp = head; while(temp != NULL) { printf(" Data = %d Address = %u\n",temp->data,temp); temp = temp->next; } printf("\n"); } //-------------------------------------------- void Sort() { struct node *t,*t1,*t2,*t3; t1 = head; head1 = head; if(head == NULL) printf("\nThe linked list is empty!"); else { while( (t2 = t1 -> next) != NULL) { while(t2 != NULL) { t3 = t2 -> next; if( t1 -> data > t2 -> data) { t2 -> next = t1; for(t = t1; t -> next != t2;t = t -> next); t -> next = t3; t1 = t2; // t1 = Node with smaller data t2 = t3; // t2 = Node to be compared with t1 } // end of 'if' else { // t1 = t1; // That is,no change in t1. t2 = t3; } } // end of ' while(t2 != NULL)' if(head == head1) // We want this action only for first pass of { // outer while() loop.Only initially, head = head1. head = t1; head1 = t1 -> next; } // end of 'if(head == head1)' else { for(t = head;t -> next != head1; t = t -> next); t -> next = t1; head1 = t1 -> next; } // end of 'else' t1 = t1 -> next; } // end of 'while( (t2 = t1 -> next) != NULL)' display(); // Display the list. } // end of 'else' of 'if(head == NULL)' } // end of 'Sort()' //-------------------------------------------- void Sort_method2() { struct node *t,*t1,*t2,*tt; if(head == NULL) printf("\nThe linked list is empty!"); else { t1 = head -> next; while(t1 != NULL) // This is i-loop(outer loop). { t2 = t1 -> next; for(t = head; t != t1; t = t -> next) // This is j-loop(inner loop). { if(t1->data < t->data) { t1 -> next = t; for(tt=head; tt->next != t1; tt=tt->next); //end of for loop in 'if' tt -> next = t2; if(t == head) head = t1; // There is only one statement in this 'if'. else // ie,'if(t != head)' { for(tt=head; tt->next != t; tt=tt->next); tt -> next = t1; } break; } // end of 'if' } // end of outer 'for' loop t1 = t2; } // end of 'while' display(); // Display the list. } // end of 'else' of 'if(head == NULL)' } // end of 'Sort_method2()'