сортировка связанного списка с использованием другого списка

Question

Так что я пытаюсь сортировать связанный список целых чисел, но, похоже, не выясняет, как правильно это сделать, моя идея состояла в том, чтобы взять неупорядоченный список, найти наибольшее значение из него , и поместить его в другой список. Поскольку я не верю, что смог удалить узел из исходного списка, не будучи дважды связанным, я планировал дать узлу из списка 1 нулевое значение, тем самым удалив его статус как наибольшее значение. Из-за этого я намеревался запустить его определенное количество раз, каждый раз, когда вы находите следующее наибольшее значение, пока список 1 не будет равен 0, а список 2 - упорядоченная версия того, что было в списке 1. Я создал функцию для этого, но, похоже, она не работает, хотя я не могу найти проблему.

Функции

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

struct num_node *create(struct num_node *list, int x){ 
    struct num_node *current; 

    if (list == NULL){ 
     list = (struct num_node*)malloc(sizeof(struct num_node)); 
     list->num = x; 
     list->next = NULL; 
     return(list); 
    } 
    else{ 
     current = (struct num_node *)malloc(sizeof(struct num_node)); 
     current->num = x; 
     current->next = list; 
     return(current); 
    } 
} 

void print_nums(struct num_node *list) { 

    struct num_node *current; 
    for (current = list; current != NULL; current = current->next) 
     printf("%d\t", current->num); 

} 

struct num_node *sort_nums(struct num_node *list1, struct num_node *list2){ 
    struct num_node *current; 
    struct num_node *large = list1; 

    for (int i = 0; i < 25; i++){ 
     for (current = list1; current != NULL; current = current->next){ 
      if (current->num > large->num){ 
       large = current; 
      } 
     } 
     create(list2, large->num); 
     large->num = 0; 
     return(list2); 
    } 
} 

int sum(struct num_node *list){ 
    int total = 0; 
    struct num_node *current; 
    for (current = list; current != NULL; current = current->next){ 
     total = total + current->num; 
    } 

    return total; 
} 

float average(struct num_node *list){ 
    float total = 0; 
    float count = 0; 
    struct num_node *current; 
    for (current = list; current != NULL; current = current->next){ 
     total = total + current->num; 
     count++; 
    } 
    return total/count; 
} 

MAIN

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#include "functions.h" 

int main(){ 
    struct num_node *head = NULL; 
    struct num_node *new_head = NULL; 

    srand(time(NULL)); 

     for (int i = 1; i <= 25; i++){ 
      int x = rand() % 100; 
      head = create(head, x); 
     } 

     print_nums(head); 

     sort_nums(head, new_head); 

     printf("\n"); 
     printf("\n"); 
     print_nums(new_head); 

     printf("\n"); 
     printf("\n"); 
     printf("The total of all numbers is: "); 
     printf("\t%d\n", sum(new_head)); 

     printf("The average of the numbers is: "); 
     printf("\t%.3f\n", average(new_head)); 


} 

Answer 1

Вы возвращаетесь преждевременно sort_nums:

struct num_node *sort_nums(struct num_node *list1, struct num_node *list2){ 
    struct num_node *current; 
    struct num_node *large = list1; 

    for (int i = 0; i < 25; i++){ 
     for (current = list1; current != NULL; current = current->next){ 
      if (current->num > large->num){ 
       large = current; 
      } 
     } 
     create(list2, large->num); 
     large->num = 0; 
     return(list2); // This just adds the largest item to list2 
    } 
} 

Вам нужно:

struct num_node *sort_nums(struct num_node *list1, struct num_node *list2){ 
    struct num_node *current; 
    struct num_node *large = list1; 

    for (int i = 0; i < 25; i++){ 
     for (current = list1; current != NULL; current = current->next){ 
      if (current->num > large->num){ 
       large = current; 
      } 
     } 
     list2 = create(list2, large->num); 
     large->num = 0; 
    } 
    return(list2); 
} 

Кроме того, вы не используете возвращаемое значение sort_nums в основном. У вас есть:

sort_nums(head, new_head); 

Понадобится:

new_head = sort_nums(head, new_head); 

Simplify create

Поскольку вы предваряя элементы в списке в create, он может быть упрощена:

struct num_node *create(struct num_node *list, int x){ 
    struct num_node *current = malloc(sizeof(struct num_node)); 
    current->num = x; 
    current->next = list; 
    return(current); 
} 

Упрощение sort_nums

Вы также можете упростить sort_nums. Вам не нужен второй аргумент. Вы можете использовать:

struct num_node *sort_nums(struct num_node *list1){ 
    struct num_node *list2 = NULL; 
    struct num_node *current; 
    struct num_node *large = list1; 
    int i; 

    for (i = 0; i < 25; i++){ 
     for (current = list1; current != NULL; current = current->next){ 
     if (current->num > large->num){ 
      large = current; 
     } 
     } 
     list2 = create(list2, large->num); 
     large->num = 0; 
    } 
    return(list2); 
} 

Конечно, вам придется изменить способ использования в основном.

new_head = sort_nums(head); 

Answer 2

Возвращаясь к первоначальной идее, пример кода для сортировки связанного списка путем нахождения наибольшего узла, а затем удалить его из исходного списка (то, что осталось от первоначального списка) и вставить этот узел в передней части новый список. Обратите внимание, что алгоритм, ориентированный на слияние, будет намного быстрее.

NODE * SortList(NODE * pList) 
{ 
NODE * pNew = NULL;      /* sorted list */ 
NODE **ppNode;       /* ptr to ptr to node */ 
NODE **ppLargest;      /* ptr to ptr to largest node */ 
NODE * pLargest;      /* ptr to largest node */ 
    while(pList != NULL){    /* while list not empty */ 
     ppLargest = &pList;    /* find largest node */ 
     ppNode = &((*ppLargest)->next); 
     while(NULL != *ppNode){ 
      if((*ppNode)->data > (*ppLargest)->data) 
       ppLargest = ppNode; 
      ppNode = &((*ppNode)->next); 
     } 
     pLargest = *ppLargest;   /* move node to new */ 
     *ppLargest = pLargest->next; 
     pLargest->next = pNew; 
     pNew = pLargest; 
    }  
    return(pNew); 
}