быстрая сортировка со связанными списками - PullRequest
Новая
       26

быстрая сортировка со связанными списками

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

Я записал следующую программу, которая использует алгоритм быстрой сортировки, чтобы отсортировать сколько угодно чисел в командной строке, используя связанные списки. Я не только получаю ошибку 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; }

Ответы [ 2 ]

1 голос
/ 08 сентября 2012

Ну, вы не опубликовали код для 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 элемент.

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

В main вы освобождаете один узел, первоначальный заголовок списка: 

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

Но вы никогда не освобождаете никакие другие узлы, хотя копируете узлы. Таким образом, все исходные узлы списка, сохраненные с первого раза, плавают в недоступной памяти. Либо free при копировании, но затем не free в main, либо вообще не копируйте (и освободите все узлы в main, но только после того, как они вам больше не нужны).

...