带链接列表的快速排序

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个元素。