鏈接列表在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; 
}