C：僅適用於大文件的合併排序上的段錯誤

下面的代碼對大數組（大於400000個字，儘管我沒有發現有限制）進行排序的單詞數組進行排序。它被通過它傳遞的話數組（從文件中讀取）進行排序，並測試其成功的一個項目叫做：C：僅適用於大文件的合併排序上的段錯誤

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

#include "csort.h" 
#include "sort.h" 

// array points to array of pointers to strings, count is number of entries in array 

void sortC(char** array, unsigned int count){ 
    array = merge_sort(array, count); 
    // testing: 
    /*for (int i = 0; i < count; i++){ 
    printf("%s ", array[i]); 
    }*/ 
} 

char** merge_sort(char** array, int count){ 
    if (count <= 1) return array; 
    else { 
    int lcount = 0; 
    int rcount = 0; 
    int middle = count/2; 
    lcount = middle; 
    char* left[lcount]; 
    subArray(array, left, 0, middle); 
    rcount = count-middle; 
    char* right[rcount]; 
    subArray(array, right, middle, count); 
    return merge(merge_sort(left, lcount), merge_sort(right, rcount), array, 0, lcount, rcount); 
    } 
} 

void subArray(char** array, char** subarray, int start, int end){ 
    int ai; // index in original array 
    int si; // index in subarray 
    for (ai = start, si = 0; ai < end; ai++, si++){ 
    subarray[si] = array[ai]; 
    } 
} 

char** merge(char** left, char** right, char** output, int oi, int lcount, int rcount){ 
    if (lcount > 0 && rcount > 0){ 
    int lmin = findMinimum(left, lcount); 
    int rmin = findMinimum(right, rcount); 
    if (strcmp(left[lmin], right[rmin]) < 0){ 
     output[oi] = left[lmin]; 
     removeFromArray(left, lmin, lcount); 
     lcount--; 
    } 
    else { 
     output[oi] = right[rmin]; 
     removeFromArray(right, rmin, rcount); 
     rcount--; 
    } 
    } 
    else if (lcount == 0) { 
    if (rcount == 1) { 
     output[oi] = right[0]; 
     return output; 
    } else { 
     int rmin = findMinimum(right, rcount); 
     output[oi] = right[rmin]; 
     removeFromArray(right, rmin, rcount); 
     rcount--; 
    } 
    } 
    else if (rcount == 0) { 
    if (lcount == 1) { 
     output[oi] = left[0]; 
     return output; 
    } else { 
     int lmin = findMinimum(left, lcount); 
     output[oi] = left[lmin]; 
     removeFromArray(left, lmin, lcount); 
     lcount--; 
    } 
    } 
    return merge(left, right, output, ++oi, lcount, rcount); 
} 

int findMinimum(char** array, int count){ 
    char* minvalue = array[0]; 
    char* currentvalue = minvalue; 
    int minindex = 0; 
    for (int i = 1; i < count; i++){ 
    currentvalue = array[i]; 
    if (strcmp(currentvalue, minvalue) < 0){ 
     minvalue = currentvalue; 
     minindex = i; 
    } 
    } 
    return minindex; 
} 

void removeFromArray(char** array, int index, int count){ 
    // removes specified index from an array 
    for (int i = index; i < count; i++){ 
    if (i+1 == count){ 
     array[i] = 0; // this entry will be gone when count decrements 
    } else { 
     array[i] = array[i+1]; 
    } 
    } 
}

來源

2011-04-21 Elijah

這裏有一個具體問題嗎？你有沒有在調試器中運行它以查看它在哪裏進行分割？ – 2011-04-21 17:11:42

（gdb）運行輸入文件名：kjvbible.txt 790691單詞被讀取。編程接收到的信號SIGSEGV，分段故障。 0x08048a1d在合併中（左= 0xff518910，右= 0xff5006e0，輸出= 0xff530bd0，oi = 35226，lcount = 7036，rcount = 7157）at csort.c：48 /home/elijah_houle/cs261/sort/csort.c:48 ：1185：乞求：0x8048a1d – Elijah 2011-04-21 17:14:03

爲什麼它會出現故障？回溯沒有幫助，因爲它只顯示「merge（）」被稱爲數千次。 – Elijah 2011-04-21 17:15:26

如果有你的代碼中沒有錯誤，那麼問題可能是你如何存儲數據。你使用malloc()來分配數組來存儲你的數據還是你聲明一個數組是足夠大？

對於大數據集，您必須使用malloc()，這將在HEAP而不是堆棧上分配空間。 堆棧空間有限。這可以解釋爲什麼使用較小的數據，程序可以正常工作，而數據集越大，它就會崩潰。

另外一個非常重要的問題是您正在使用遞歸：merge（）調用merge（）。遞歸調用過多會導致堆棧溢出（段錯誤）。

來源

2011-04-21 17:16:14 karlphillip

如果是這樣的話，你會認爲他會得到一個'Stack Overflow'錯誤。（雖然他可能是，並且由於這個問題在細節上相當短暫，所以不會告訴我們）。 – 2011-04-21 17:26:06

另外不要忘記檢查malloc的錯誤代碼。 – 2011-04-21 17:31:20

已更新的答案。 – karlphillip 2011-04-21 17:35:51

看起來像堆棧溢出，如果每次調用中的項目都分配了數千個自動數組，然後遞歸。

這些線路，具體而言：

char* left[lcount];

和

char* right[rcount];

對於您的評論的值，其中數== 7157，這將是在棧空間方面相當昂貴的。

考慮使用malloc()這些，或找出一種方法來表示一個子陣列，而不需要新的內存。

來源

2011-04-27 11:05:13 unwind

C：僅適用於大文件的合併排序上的段錯誤

回答

相關問題