Tri d'une liste liée dans C
Je suis en train de trier une liste liée par trouver la plus grande valeur, la suppression de son poste, et ensuite de l'insérer dans le haut de la liste.
La difficulté, je suis en cours d'exécution dans est la la suppression et l'insertion dans la partie supérieure. Le problème semble être dans la condition if dans la boucle while contenues dans le sortList fonction, mais je ne suis pas sûr de savoir comment le résoudre.
Toute aide serait appréciée.
#include <stdio.h>
#include <stdlib.h>
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 un certain nombre de questions sur le tri des listes chaînées en C; beaucoup d'entre eux sont répertoriés comme des questions sur le membre de droite de la page. Avez-vous regardez n'importe quel d'entre eux pour voir si elles sont pertinentes à votre problème?
OriginalL'auteur maxmouse | 2012-08-05
Vous devez vous connecter pour publier un commentaire.
Il y a des problèmes dans la
sortList
fonction.Cette fonction seulement mis quelques gros nœuds dans le début de la liste. Il n'est pas soting tous la liste. vous pouvez vous un algorithme de tri pour trier le fichier : quicksort/bubblesort/...
j'ai mis un code qui font un tri, à la fin de cette réponse.
voici un code en faisant le tri de la liste :
//c'est le remplacement plus grand nœud avec d'abord un, puis faire la même opération avec la sous-liste (liste-premier élément)
ty, c'est fait. plus lisible le code serait d'utiliser une fonction qui recherche le plus grand élément et une fonction qui permet de basculer les nœuds.
Cet algorithme ne fonctionne pas lorsque vous avez une liste comme ceci: 524361
OriginalL'auteur Hicham from CppDepend Team
Ici est une tentative de ma part pour trier une seule liste liée utilisant l'algorithme QuickSort. Si vous connaissez n puis exécuter en temps O(n log n). Vérifier si cela aide.
OriginalL'auteur user1596193
Cette devrait vraiment vous aider. C'est un très joli post.
Leçon apprise. Va faire.
OriginalL'auteur Prasanth
Par écrit à
largest->next
vous écrasaitcurr->next
. Donc, vous vous retrouvez de redémarrer à partir du haut de tous les temps.Assurez-vous que:
Mais dans l'ensemble, votre code semble être fortement cassé, je crois qu'il pourrait être une couple d'autres erreurs dans votre logique de tri.
OriginalL'auteur Anony-Mousse
Les éléments suivants sont quelques-uns des problèmes qui existent dans votre logique de tri:
Le code modifié comme ci-dessous (Juste un pointeur, vous devez vérifier pour d'autres questions vous-même):
OriginalL'auteur Jay
OriginalL'auteur Sagar Damle