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：仅适用于大文件的合并排序上的段错误

回答

相关问题