1

以下代码对单词数组进行排序，处理小数组，并对大数组进行分段（> 400000 个单词，尽管我没有找到限制）。它被一个程序调用，该程序将一个单词数组（从文件中读取）传递给它以进行排序并测试其是否成功：

#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];
    }
  }
}
4

2 回答 2

2

如果您的代码没有错误，那么问题可能是您如何存储数据。您是使用malloc()分配数组来存储数据还是声明一个足够大的数组？

对于大型数据集，您必须使用malloc()，它将在 HEAP 而不是堆栈上分配空间。堆栈空间有限。这可以解释为什么您的程序使用较小的数据可以工作，而使用较大的数据集会崩溃。

还有一个非常重要的一点是您正在使用递归：merge() 调用 merge()。太多的递归调用可能导致堆栈溢出（segfault）。

于 2011-04-21T17:16:14.550 回答
0

看起来像堆栈溢出，您在每次调用中分配数千个 if 项的自动数组，然后递归。

这些行，具体来说：

char* left[lcount];

和

char* right[rcount];

对于您评论中的值，其中 count == 7157，就堆栈空间而言，这将非常昂贵。

考虑使用malloc()这些，或者想办法在不需要新内存的情况下表示子数组。

于 2011-04-27T11:05:13.403 回答