快速排序功能不起作用（在c）

Question

我無法讓我的代碼工作！我正試圖用鏈表實現快速排序算法。我不斷收到內存泄漏問題，無法解決它們。

#include <stdio.h> 
#include "linked_list.h" 
#include <stdlib.h> 
#include "memcheck.h" 
#include <string.h> 
#include <assert.h> 

node *quicksort(node *list); 
int ListLength (node *list); 

int main(int argc, char *argv[]) { 
    node *list; 
    node *sorted_list; 
    int i; 
    int intArg = 0; /* number of integer arguments */ 
    int print = 1; 
    /* if -q is found anywhere then we are going 
    * to change the behavior of the program */ 
    if (argc == 1) { 
    fprintf(stderr, "usage: %s [-q] number1 number2 ... \ 
    (must enter at least one argument)\n", argv[0]); 
    exit(1); } 
    for (i = 1 ; i < argc; i++) { 
    if (strcmp(argv[i], "-q") == 0) { 
     print = 0; } 
    else { 
     list = create_node(atoi(argv[i]), list); /* memory allocation is taken care of */ 
     intArg++; } } 
    if (intArg == 0) { 
    fprintf(stderr, "usage: %s [-q] number1 number2 ...\ 
    (at least one of the input arguments must be an integer)\n", argv[0]); 
    exit(1); } 
    sorted_list = quicksort(list); 
    free_list(list); 
    list = sorted_list; 
    if (print == 1) { 
    print_list(list); } 
    print_memory_leaks(); 
    return 0; } 

node *quicksort(node *list) { 
    node *less=NULL, *more=NULL, *next, *temp=NULL, *end, *listCopy; 
    node *pivot = list; 
    listCopy = copy_list(list); 
    if (ListLength(list) <= 1) { 
    return listCopy; } 
    else { 
    next = listCopy->next; 
    listCopy = next; 
    /* split into two */ 
    temp = listCopy; 
    while(temp != NULL) { 
     next = temp->next; 
     if (temp->data < pivot->data) { 
     temp->next = less; 
     less = temp; } 
     else { 
     temp->next = more; 
     more = temp; } 
     temp = next; } 
    less = quicksort(less); 
    more = quicksort(more); } 

    /* appending the results */ 
    if (less != NULL) { 
      end = less; 
      while (end->next != NULL) { 
        end = end->next; } 
      pivot->next = more; 
      end->next = pivot; 
      return less; } 
    else { 
      pivot->next = more; 
      return pivot; } } 

int ListLength (node *list) { 
    node *temp = list; 
    int i=0; 
    while(temp!=NULL) { 
    i++; 
    temp=temp->next; } 
    return i; } 


/*Code from the libraries */ 


node * 
create_node(int data, node *n) { 
    node *result = (node *)malloc(sizeof(node)); 
    if (result == NULL) { 
     fprintf(stderr, "Fatal error: out of memory. " 
       "Terminating program.\n"); 
     exit(1); } 
    result->data = data; /* Fill in the new node with the given value. */ 
    result->next = n; 
    return result; } 

void 
free_list(node *list) { 
    node *n;  /* a single node of the list */ 
    while (list != NULL) { 
     n = list; 
     list = list->next; 
    /* 
    * 'n' now points to the first element of the list, while 
    * 'list' now points to everything but the first element. 
    * Since nothing points to 'n', it can be freed. 
    */ 

     free(n); } } 

node * 
copy_list(node *list) { 
    if (list == NULL) { 
     return list; } 
    else { 
     node *new_list; 
     new_list = (node *)malloc(sizeof(node)); 
     if (new_list == NULL) { 
      fprintf(stderr, "Fatal error: out of memory. " 
        "Terminating program.\n"); 
      exit(1); } 
     new_list->data = list->data; 
     new_list->next = copy_list(list->next); 
     return new_list; } } 

/* other available methods are append_lists, reverse_list */ 

Answer 1

作爲在所有這些情況下爲您服務的一般答案：您說您不斷收到內存泄漏但無法解決它們。您是否嘗試過使用工具嘗試捕捉內存錯誤？例如，Valgrind將會捕獲大多數的故障來釋放內存，在發生免費錯誤後使用等。這是值得學習如何使用它的。

（順便說一句，你說，你知道你會得到內存泄漏，但你不解釋你如何知道你得到他們。）

Answer 2

一個問題是它使用未初始化的變量list。在第一次調用create_node之前，它需要分配NULL。

編輯我在想quicksort在某些情況下泄漏了輸入列表......現在我對此不太確定;它在做什麼並不完全清楚。我將不得不通過一個調試器來跟蹤它。我相當肯定它應該而不是被稱爲copy_list。沒有理由重複輸入列表。它應該分成兩組，然後重新組合這兩部分，然後返回重新排序的原始列表。