quicksort函数不起作用(在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。它没有理由重复输入列表。它应该划分为两个组，然后重新组合这两个部分，只返回重新排序的原始列表。