Vous rencontrez des problèmes avec Insert Sort for Linked List. N'imprime que la première valeur de la liste lorsque j'essaie de trier la liste par ordre croissant

Question

Je suis en train d'écrire un programme pour l'un de mes cours et je suis coincé dans la section qui demande pour trier une liste chaînée par ordre croissant. J'ai essayé de trier la liste mais quand je cours la fonction il imprime seulement la première valeur. Je sais que la fonction d'impression fonctionne parce que je peux l'exécuter sans insérer le tri et il imprime bien.

Mon code est le suivant:

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


void swap(struct Link *first, struct Link *second){ 
    struct Link* temp = first; 
    temp->next = first->next; 
    temp->value = first->value; 
    first = second; 
    first->next = second->next; 
    first->value = second->value; 
    second = temp; 
    second->next = temp->next; 
    second->value = temp->value; 
} 

struct Link* listInsertionSort(struct Link* head) { 

    /* 
    * This function should perform an insertion sort on the list whose head is 
    * provided as the function's argument, so that the values in the list are 
    * sorted in ascending order, starting at the head. 
    * 
    * The sort should be done without allocating any new Link structs or any 
    * other auxiliary data structures. 
    * 
    * Return a pointer to the new head of the list. 
    */ 

struct Link* cur = head; 
cur->next = head->next; 
struct Link* count; 
for(;cur->next != NULL; cur = cur->next){ 
    for(count = cur->next; count != NULL; count = count->next){ 
     if(cur->value < count->value){ 
     swap(cur, count); 
     } 
    } 
} 


return cur; 

} 

Et le fichier linkedList.h est ici:

#ifndef __LINKEDLIST_H 
#define __LINKEDLIST_H 

#define TYPE int 

/* Single link structure */ 
struct Link { 
    TYPE value; 
    struct Link* next; 
}; 

struct Link* listInsertionSort(struct Link* head); 
struct Link* reverseList(struct Link* head); 
struct Link* reverseListRecursive(struct Link* head); 

#endif 

Et le fichier de test est ici (Bien qu'il ne devrait pas être une erreur ici puisque ceci a été fourni à tous les étudiants de la classe par notre instructeur):

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

#include "linkedList.h" 

struct Link* buildLink(int n, int rev, int mod) { 
    struct Link* head = (struct Link*)malloc(sizeof(struct Link)); 
    struct Link* cur = head; 

    for (int i = 0; i < n; i++) { 
    if (rev) 
     cur->value = n - i - 1; //If rev is 1, creates list from high value to low value 
    else 
     cur->value = i; //If rev is 0, creates list from low value to high value 

    if (mod) 
     cur->value = cur->value % mod; //Modifies list so that it increments up to value of mod 

    if (i + 1 < n) 
     cur->next = (struct Link*)malloc(sizeof(struct Link)); //Creates next link in the array 
    else 
     cur->next = 0; //If less than the cap it sets next character to NULL, ending the list 
    cur = cur->next; //Sets current link to next link to continue for loop 
    } 

    return head; 
} 

void printLL(struct Link* l,char* s) { 
    printf("LL %s: ",s); 
    while (l != 0) { 
    printf("%d ", l->value); 
    l = l->next; 
    } 
    printf("\n"); 
} 

int main() { 
    // We aren't practicing good memory management 
    // here.... 
    struct Link* l = buildLink(10, 0, 4); 
    struct Link* r = listInsertionSort(l); 
    printLL(r, "Sort 0-9 mod 4"); //This should print 0 0 0 1 1 1 2 2 3 3 

} 

Est-ce que quelqu'un a une idée du problème? L'erreur est quelque part dans listInsertionSort (struct Link * head) mais j'ai essayé plusieurs combinaisons différentes sans succès.

Le courant de sortie est: LL Trier 0-9 mod 4: 1 quand il doit être: LL Trier 0-9 mod 4: 0 0 0 1 1 1 2 2 3 3

Answer 1

je trouve la solution pour le problème que j'avais.

Au lieu de retourner cur, j'étais censé retourner la tête. J'ai également changé la fonction de swap afin qu'elle n'inclue pas les valeurs de permutation des liens dans la liste parce que c'était inutile et avait l'air désordonné.