帶鏈接列表的快速排序

Question

我寫下了下面的程序，該程序使用quicksort算法來排序使用鏈接列表將多少個整數放入命令行的方式。我不僅得到關於混合聲明的ISO C90錯誤，而且我的代碼中存在內存泄漏，我不知道如何解決它。任何幫助，將不勝感激！

#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[]) { 
    if (argc == 1) { 
    fprintf(stderr, "usage: %s [-q] number1 number2 ... \ 
    (must enter at least one argument)\n", argv[0]); 
    exit(1); 
    } 
    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 so that 
    * it still sorts but does not print the result */ 
    for (i = 1 ; i < argc; i++) { 
     if (strcmp(argv[i], "-q") == 0) { 
      print = 0; 
     } 
     else { 
      list = create_node(atoi(argv[i]), list); /* memory allocation in the   create_node function */ 
      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; } 

/* This function sorts a linked list using the quicksort 
* algorithm */ 
node *quicksort(node *list) { 
node *less=NULL, *more=NULL, *next, *temp=NULL, *end; 
node *pivot = list; 
if (ListLength(list) <= 1) { 
    node *listCopy; 
    listCopy = copy_list(list); 
    return listCopy; } 
else { 
    next = list->next; 
    list = next; 
    /* split into two */ 
    temp = list; 
    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; } 

Answer 1

在main，你自由一個節點，列表的原廠頭：

sorted_list = quicksort(list); 
free_list(list); 

但你永遠不會釋放任何其他節點，儘管你複製的節點。因此，從第一個節點保存的所有原始列表節點都將浮動在不可訪問的內存中。要麼複製free，要麼複製freemain，要麼完全不復制（並釋放main中的所有節點，但只在不再需要它們之後）。

Answer 2

好了，你有沒有張貼free_list()或create_node()這些都是潛在的內存泄漏總理候選人的代碼，但我相信你的quicksort()代碼有內存泄漏的位置：

less = quicksort(less); 
    more = quicksort(more); } 

如果任一列表中只有一個元素，那麼這個代碼：

if (ListLength(list) <= 1) { 
    node *listCopy; 
    listCopy = copy_list(list); 
    return listCopy; } 

返回一個元素的副本。通過在這裏設置less和more指針，您可能會丟失單個節點。

考慮名單：2 1 3

的代碼將增加1到less列表，3到more列表。然後它會在這兩個單元素列表上執行quicksort()，返回列表的副本，並丟失指向原始less和more列表的指針，導致兩個節點的內存泄漏。

巧合的是，這將是更好，以取代上述與if語句的檢查：

if (list == NULL || list->next == NULL) { 

這避免了遍歷一個潛在的一長串只是爲了檢查是否只包含0或1個元素。