c-使用qsort()和strcmp的后缀数组

Question

我有以下代码来创建排序后缀数组，但根本没有输出。我运行程序，它会暂停1-2秒，然后退出。

该代码基于以下网站上的c++答案：https://www.geeksforgeeks.org/suffix-array-set-1-introduction/

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
struct suffix
{
int index; 
char *suff;
};
int cmp(const void *a, const void *b)
{
const struct suffix *a1 = a;
const struct suffix *b1 = b;  
return strcmp(a1->suff, b1->suff) < 0? 1 : 0;
}
int *buildSuffixArray(char *txt, int n)
{
struct suffix suffixes[n];
for (int i = 0; i < n; i++)
{
suffixes[i].index = i;
suffixes[i].suff = (txt+i);
}
qsort(suffixes, n, sizeof(int), cmp);
int *suffixArr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
{
suffixArr[i] = suffixes[i].index;
}
return suffixArr;
}
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("n");
}
int main()
{
char txt[] = "banana";
int n = strlen(txt);
int *suffixArr = buildSuffixArray(txt, n);
printf("following is suffix array for %sn", txt);
printArr(suffixArr, n);
return 0;
}

由于没有输出，我认为问题在"buildSuffixArray"函数中，特别是在qsort中。我试过把它修好，但没有成功。如有任何帮助，我们将不胜感激。

Answer 1

总结Weather Vane和Jonathan Leffler对问题的评论：

1. OP将错误的元素大小传递给qsort()。qsort(suffixes, n, sizeof(int), cmp);应该是qsort(suffixes, n, sizeof suffixes[0], cmp);。(风向标(
2. 如果第一个参数在第二个参数之前排序，则cmp函数必须返回负值；如果它们排序相等，则返回零；如果第一个变量在第二次参数之后排序，则返回正值。如果第一个参数小于第二个参数，则OP的cmp函数返回1，否则返回0。这将破坏qsort()的任何排序。(Jonathan Leffler(

OP编写的cmp函数似乎是基于后缀数组|集1(简介(中的C++代码。特别地，OP的return strcmp(a1->suff, b1->suff) < 0? 1 : 0;是基于C++代码中类似的return strcmp(a.suff, b.suff) < 0? 1 : 0;。问题是C++代码使用std::sort()，而不是qsort()，并且比较函数的返回值规则不同。

正如Jonathan Leffler所指出的，OP的cmp函数直接返回strcmp()的值就足够了：

return strcmp(a->suff, b->suff);

OP的printArr()函数打印数组中的整数，每个数字之间没有分隔。修正是微不足道的。