使用QSORT引起分割故障

Question

嗯，作为学习 C++ 的一部分，我的项目对此有一个限制。除了 等基本库和一些其他必需品之外，我不允许使用任何库。

该项目应该从一个文件中获取输入，该文件是“n”个字符串列，并且能够根据任何选定列的字典顺序对输出进行排序。例如，给定输入，

Cartwright   Wendy    93
Williamson   Mark     81
Thompson     Mark     100
Anderson     John     76
Turner       Dennis   56

它应该按列对它们进行排序。我在 StackOverflow 上的搜索返回了其他人的结果，几年前他也必须做完全相同的项目哈哈哈 基于 C 字符串中的列进行 Qsort？

但就我而言，我只是为该列使用全局变量并继续生活。当我实现 qsort 的比较函数时，我的问题出现了。

在我的主要方法中，我调用

qsort (data, i, sizeof(char*), compare);

其中 data 是 char * data[] ，而 i 是要进​​行排序的行数。比较。 （在本例中为 5）

下面是我的比较方法的代码，

int compare (const void * a, const void * b){
    char* line1 = new char[1000]; char* line2 = new char[1000];
    strcpy(line1, *((const char**) a));
    strcpy(line2, *((const char**) b));
    char* left = &(strtok(line1, " \t"))[column-1];
    char* right = &(strtok(line2, " \t"))[column-1];
    return strcmp(left, right);
}

1000 是因为我只是概括（并故意进行了错误的编码）以过度概括，没有行会超过 1000 个字符。

让我困惑的是，当我在 Eclipse 中使用调试器时，我可以看到第一次比较成功，然后在第二轮尝试比较它们时出现分段错误。

我还尝试更改将左和右分配给下面的代码，但这也没有帮助

char* left = new char[100];
strcpy(left, &(strtok(line1, " \t"))[column-1]);
char* right = new char[100];
strcpy(right, &(strtok(line2, " \t"))[column-1]);

请帮助我了解导致此分段错误的原因。第一次比较两者时，左=“Williamson”，右=“Thompson”。第二次比较（并尝试崩溃）左=“Cartwright”和右=“Thompson”

Answer 1

char* line1 = new char[1000]; char* line2 = new char[1000];

这一点都不好。您永远不会释放此功能，因此每次调用比较功能时，您都会泄漏2000个字节。最终，这将导致较低的内存条件，新将投掷。 （或在Linux上，您的过程可能会被OOM杀手杀死）。当您只能说char line1 [1000]时，这也不是很有效的，这是超级问题，因为它只是从堆栈指针中减去而不是潜在地浏览免费列表或要求内核提供更多信息记忆。

但是实际上，您可以在不修改或复制字符串的情况下进行比较。例如：

static int
is_end_of_token(char ch)
{
    // If the string has the terminating NUL character we consider it the end.
    // If it has the ' ' or '\t' character we also consider it the end.  This
    // accomplishes the same thing as your strtok call, but WITHOUT modifying
    // the source buffer.
    return (!ch || ch == ' ' || ch == '\t');
}

int
compare(const void *a, const void *b)
{
   const char *strA = *(const char**)a;
   const char *strB = *(const char**)b;

   // Loop while there is data left to compare...
   while (!is_end_of_token(*strA) && !is_end_of_token(*strB))
   {
      if (*strA < *strB)
         return -1;      // String on left is smaller
      else if (*strA > *strB)
         return 1;       // String on right is smaller
      ++strA;
      ++strB;
   }

   if (is_end_of_token(*strA) && is_end_of_token(*strB))
      return 0;    // both strings are finished, so they are equal.
   else if (is_end_of_token(*strA))
      return -1;   // left string has ended, but right string still has chars
   else
      return 1;    // right string has ended, but left string still has chars
}

但是最后...您正在使用std :: String您说的？好吧，如果是这样，则假设将内存传递给QSort与“ const char **”兼容有点奇怪，我希望它会崩溃。从这个意义上讲，也许您应该做类似的事情：

int compare(const void *a, const void *b)
{
    const char *strA = ((const std::string*)a)->c_str();
    const char *strB = ((const std::string*)b)->c_str();

    // ...
}

但是，实际上，如果您使用的是C ++而不是C，则应使用std :: Sort。