функция быстрой сортировки не работает (в c) - PullRequest
Новая
       24

функция быстрой сортировки не работает (в c)

1 голос
/ 25 февраля 2012

Я не могу заставить мой код работать! Я пытаюсь реализовать алгоритм быстрой сортировки со связанными списками. У меня постоянно возникают проблемы с утечкой памяти, и я не могу их решить. 

#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 */

Ответы [ 2 ]

1 голос
/ 25 февраля 2012

В качестве общего ответа, чтобы служить вам при всех таких обстоятельствах: вы говорите, что продолжаете получать утечки памяти, но не можете их устранить. Вы пытались использовать инструмент, чтобы попытаться поймать ошибки памяти, хотя? Например, Valgrind будет отлавливать большинство сбоев при освобождении памяти, использовании после ошибок и т. Д. Стоит изучить, как ее использовать.

(Кроме того, вы говорите, что знаете, что у вас возникают утечки памяти, но вы не объясняете, откуда вы это знаете.)

1 голос
/ 25 февраля 2012

Одна проблема заключается в том, что он использует неинициализированную переменную list.Ему нужно присвоить NULL до первого вызова create_node.

Редактировать Я думал, что quicksort пропускает список ввода в некоторых случаях ... и сейчасменее уверен в этом;не совсем понятно, что он делает.Я должен был пройти через это с отладчиком, чтобы следовать за этим.Я совершенно уверен, что он должен не звонить copy_list.Нет причин для дублирования списка ввода.Он должен быть разделен на две группы, а затем повторно собран две части и просто вернуть переупорядоченный исходный список.

...