C - 使用链表快速排序

Question

我写下了以下程序，该程序使用快速排序算法对使用链表将多少个整数放入命令行进行排序。我不仅收到有关混合声明的 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复制，但不要free main，要么根本不复制(并释放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 个元素而遍历可能很长的列表。