У вас возникли проблемы с вставкой Sort для Linked List. Только печатает первое значение списка при попытке отсортировать список в порядке возрастания

Question

Я пишу программу для одного из моих классов и застрял в секции, которая запрашивает , чтобы отсортировать связанный список в порядке возрастания. Я попытался отсортировать список, но когда Я запустил функцию, она только печатает первое значение. Я знаю, что функция печати работает , потому что я могу запустить ее без Insert Sort, и она отлично печатается.

Мой код выглядит следующим образом:

#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; 

} 

И файл linkedList.h здесь:

#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 

И тестовый файл здесь (Хотя не должно быть никакой ошибки здесь поскольку это было предоставлено всем учащимся этого класса нашим инструктором):

#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 

} 

Кто-нибудь знает, в чем проблема? Ошибка находится где-то в спискеInsertionSort (struct Link * head), но я пробовал несколько разных комбинаций без успеха.

В настоящее время выход: LL Сортировка по модулю 0-9 4: 1 Когда это должно быть: LL Сортировка по модулю 0-9 4: 0 0 0 1 1 1 2 2 3 3

Answer 1

Я нашел решение для проблемы, которую я имел.

Вместо того, чтобы возвращать cur, я должен был вернуть голову. Я также изменил функцию подкачки, чтобы она не включала значения обмена ссылками в списке, потому что это было ненужно и выглядело беспорядочным.