链接列表在C快速排列

Question

好吧，在gdb和valgrind没有成功之后，我谦虚地向您提问。我们被要求在c中实现一个快速排序的版本，使用列表的第一个元素作为支点（以保持与我们在本学期早些时候做的简单的haskell实现的可比性）。提供了LIST实现（制作，打印和结构定义），其余部分由我们决定。我（惊喜，惊喜）收到了段错误，但valgrind发现了大量的错误以及堆栈溢出，所以也许有些新鲜的眼睛可以帮助我。

我的代码：

#include <stdio.h> 
#include <stdlib.h> 

typedef struct CELL *LIST; 
struct CELL { 
    int element; 
    LIST next; 
}; 


LIST MakeList(); 
void PrintList(LIST); 
LIST qSort(LIST); 
int listLength(LIST); 
LIST combine(LIST, LIST, LIST); 


int main(){ 
    LIST list; 
    printf ("enter a several numbers separated by spaces or returns and ended by Ctrl-D\n"); 
    list = MakeList(); 
    PrintList(qSort(list)); 
    return 0; 
} 

LIST qSort(LIST list){ 
    LIST current, pivot = list, temp = NULL;//use first element as pivot, start comparison at list->next 
    LIST little, big, littleHead, bigHead; 
    little = (LIST) malloc(sizeof(struct CELL)); 
    little->element = 0; 
    little->next = NULL; 
    littleHead = little; 
    big = (LIST) malloc(sizeof(struct CELL)); 
    big->element = 0; 
    big->next = NULL; 
    bigHead = big; 

    if(listLength(list) <= 1){//base case 
     return list; 
    } 
//remove pivot by setting current to list->next 
    current = list->next; 

    do{ 
     if(current->element <= pivot->element){ 
     little->element = current->element; 
     little->next = (LIST) malloc(sizeof(struct CELL)); 
     little = little->next; 
     little->next = NULL; 
     } 
     else{ 
     big->element = current->element; 
     big->next = (LIST) malloc(sizeof(struct CELL)); 
     big = big->next; 
     big->next = NULL; 
     } 

     current = current->next; 
    }while(current != NULL); 

    littleHead = qSort(littleHead); 
    bigHead = qSort(bigHead); 

    return combine(littleHead, bigHead, pivot); 
} 

int listLength(LIST list){ 
    int length = 0; 
    LIST current = list; 
    if(NULL==list){ 
     return length; 
    } 
    else{ 
     while(current != NULL){ 
     current = current->next; 
     length++; 
     } 
    } 
    return length; 
} 



LIST combine(LIST little, LIST big, LIST pivot){ 
    LIST temp = little; 
    while(temp->next != NULL){ 
     temp = temp->next; 
    } 
    temp->next = pivot; 
    pivot->next = big; 
    return little; 
} 

LIST MakeList() 
{ 
    int x; 
    LIST pNewCell; 

    if (scanf("\%d", &x) == EOF) return NULL; 
    else { 
     pNewCell = (LIST) malloc(sizeof(struct CELL)); 
     pNewCell->next = MakeList(); 
     pNewCell->element = x; 
     return pNewCell; 
    } 
} 

void PrintList(LIST list) 
{ 
    while (list != NULL) { 
     printf("\%d\n", list->element); 
     list = list->next; 
    } 
} 

而且Valgrind的输出

==20391== Conditional jump or move depends on uninitialised value(s) 
==20391== at 0x804855D: qSort (2100assignment4.c:45) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80484BD: main (2100assignment4.c:22) 
==20391== Uninitialised value was created by a heap allocation 
==20391== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) 
==20391== by 0x8048574: qSort (2100assignment4.c:47) 
==20391== by 0x80484BD: main (2100assignment4.c:22) 
==20391== 
==20391== Conditional jump or move depends on uninitialised value(s) 
==20391== at 0x804855D: qSort (2100assignment4.c:45) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80484BD: main (2100assignment4.c:22) 
==20391== Uninitialised value was created by a heap allocation 
==20391== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) 
==20391== by 0x8048574: qSort (2100assignment4.c:47) 
==20391== by 0x80484BD: main (2100assignment4.c:22) 
==20391== 
==20391== Conditional jump or move depends on uninitialised value(s) 
==20391== at 0x804855D: qSort (2100assignment4.c:45) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80484BD: main (2100assignment4.c:22) 
==20391== Uninitialised value was created by a heap allocation 
==20391== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) 
==20391== by 0x8048574: qSort (2100assignment4.c:47) 
==20391== by 0x80485E0: qSort (2100assignment4.c:61) 
==20391== by 0x80484BD: main (2100assignment4.c:22) 
==20391== 
==20391== Stack overflow in thread 1: can't grow stack to 0xbe297ff4 
==20391== 
==20391== Process terminating with default action of signal 11 (SIGSEGV) 
==20391== Access not within mapped region at address 0xBE297FF4 
==20391== at 0x402BE35: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) 
==20391== If you believe this happened as a result of a stack 
==20391== overflow in your program's main thread (unlikely but 
==20391== possible), you can try to increase the size of the 
==20391== main thread stack using the --main-stacksize= flag. 
==20391== The main thread stack size used in this run was 8388608. 
==20391== Stack overflow in thread 1: can't grow stack to 0xbe297fe4 
==20391== 
==20391== Process terminating with default action of signal 11 (SIGSEGV) 
==20391== Access not within mapped region at address 0xBE297FE4 
==20391== at 0x4025430: _vgnU_freeres (in /usr/lib/valgrind/vgpreload_core-x86-linux.so) 
==20391== If you believe this happened as a result of a stack 
==20391== overflow in your program's main thread (unlikely but 
==20391== possible), you can try to increase the size of the 
==20391== main thread stack using the --main-stacksize= flag. 
==20391== The main thread stack size used in this run was 8388608. 
==20391== 
==20391== HEAP SUMMARY: 
==20391==  in use at exit: 4,190,952 bytes in 523,869 blocks 
==20391== total heap usage: 523,869 allocs, 0 frees, 4,190,952 bytes allocated 
==20391== 
==20391== LEAK SUMMARY: 
==20391== definitely lost: 0 bytes in 0 blocks 
==20391== indirectly lost: 0 bytes in 0 blocks 
==20391==  possibly lost: 0 bytes in 0 blocks 
==20391== still reachable: 4,190,952 bytes in 523,869 blocks 
==20391==   suppressed: 0 bytes in 0 blocks 
==20391== Rerun with --leak-check=full to see details of leaked memory 
==20391== 
==20391== For counts of detected and suppressed errors, rerun with: -v 
==20391== ERROR SUMMARY: 261929 errors from 3 contexts (suppressed: 0 from 0) 

Answer 1

一些问题开始：

if (scanf("\%d", &x) == EOF) return NULL; 

是不需要的\。因为您希望得到一个值，所以检查！= 1可能会更容易。

这使您的MakeList无限递归（至少在我的机器上）。

在你的qsort函数，你的小和大名单总是在最后一个虚拟条目 - 通过这个代码做

little->next = (LIST) malloc(sizeof(struct CELL)); 
little = little->next; 
little->next = NULL; 

这意味着，当你拆你的列表，你最后总是比你更多的条目开始，所以它永远不会完成。还要注意，这些新条目没有设置元素值，这可能是您获取未初始化警告的位置。

您应该重新考虑如何存储子列表，也许将它们作为NULL开始以指示为空，尽管这会使添加新值变得更困难。

Answer 2

您可以编辑下面你makelist功能..

你会看到一些变化。

1. scanf是正确的去除\（参见黑暗的答案）
2. scanf读一段时间，这将确保读，如果你输入任何不兼容的输入像任何字母，而不是按Ctrl + D。
将停止

LIST MakeList() 
{ 
    int x; 
    LIST pNewCell; 

    while(scanf("%d", &x)) 
    { 
     pNewCell = (LIST) malloc(sizeof(struct CELL)); 
     pNewCell->next = MakeList(); 
     pNewCell->element = x; 
     return pNewCell; 
    } 
    return NULL; 
}