快速排序与链表 [英] quicksort with linked lists
问题描述
我写下来，它使用快速排序算法进行排序怎么过许多整数投入使用链表命令行下面的程序。不仅我会收到有关混合声明的ISO C90错误，但有内存泄漏的地方在我的code和我不知道如何解决它。任何帮助将是AP preciated！
的#include＆LT;＆stdio.h中GT;
＃包括linked_list.h
＃包括LT＆;＆stdlib.h中GT;
＃包括memcheck.h
＃包括LT＆;＆string.h中GT;
＃包括LT＆;＆ASSERT.H GT;节点*快速排序（节点*名单）;
INT ListLength（节点*名单）;INT主（INT ARGC，CHAR *的argv []）{
如果（的argc == 1）{
fprintf中（标准错误，用法：％s的[-q] NUMBER1号码2 ... \\
（至少必须输入一个参数）\\ n，argv的[0]）;
出口（1）;
}
节点*名单;
节点* sorted_list;
INT I;
INT intArg = 0; / *整数参数的数目* /
INT打印= 1;
/ *如果-q发现的任何地方，然后我们会
*改变程序，这样的行为
*它仍然排序，但不打印结果* /
对于（i = 1; I＆LT; ARGC，我++）{
如果（的strcmp（argv的[I]中，-q）== 0）{
打印= 0;
}
其他{
清单= create_node（与atoi（argv的[I]），清单）; / *在create_node功能的内存分配* /
intArg ++; }
} 如果（intArg == 0）{
fprintf中（标准错误，用法：％s的[-q] NUMBER1号码2 ... \\
（的输入参数的至少一个必须是一个整数）\\ N，argv的[0]）;
出口（1）; }
sorted_list =快速排序（表）;
free_list（名单）;
名单= sorted_list;
如果（印刷== 1）{
print_list（名单）; }
print_memory_leaks（）;
返回0; }/ *此功能使用排序快速排序的链表
*算法* /
节点*快速排序（节点*名单）{
节点*少= NULL，*更多= NULL，*接下来，* TEMP = NULL，*结束;
节点*支点=清单;
如果（ListLength（名单）＆LT; = 1）{
节点* listCopy;
listCopy = copy_list（名单）;
返回listCopy; }
其他{
接下来=列表 - ＆gt;接下来，
名单=下一个;
/ *分裂成两个* /
TEMP =清单;
而（温度！= NULL）{
接下来= TEMP-＆gt;接下来，
如果（TEMP-GT＆;数据和LT; pivot-＆GT;数据）{
TEMP-＆gt;接着=少;
少=温度;
}
其他{
TEMP-＆gt;接下来=多;
更多=温度;
}
TEMP =下一个;
}
少=快速排序（少）;
更快速排序=（更多）; }
/ *将结果追加* /
如果（少！= NULL）{
最终=少;
而（端值＆GT;！下次= NULL）{
结束=端值＆gt;接下来，
}
pivot-＆gt;接下来=多;
端值＆gt;接下来=支点;
返回少; }
其他{
pivot-＆gt;接下来=多;
返回支点; }}
INT ListLength（节点*名单）{
节点* TEMP =清单;
INT I = 0;
而（温度！= NULL）{
我++;
TEMP = TEMP-＆gt;接下来， }
返回我; }
在主，你自由的一个节点，列表的原厂头：
sorted_list =快速排序（表）;
free_list（名单）;
但是你从来没有免费的任何其他节点，虽然你复制的节点。因此，所有的原始列表节点从第一个在不可访问内存浮动保存。无论是免费上的复制，但不要免费在主，或根本不复制（并释放所有节点主，但只有当你不再需要它们）。
I have written down the following program that uses the quicksort algorithm to sort how ever many ints are put into the command line using linked lists. Not only am I getting an ISO C90 error about mixed declarations but there is a memory leak somewhere in my code and I am not sure how to fix it. Any help would be appreciated!
#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; }
In main, you free one node, the original head of the list:
sorted_list = quicksort(list);
free_list(list);
But you never free any other node, although you copy the nodes. So all the original list nodes save from the first are floating in unreachable memory. Either free on copy, but then don't free in main, or don't copy at all (and free all nodes in main, but only after you no longer need them).
这篇关于快速排序与链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
