如何在不使用 qsort 的情况下在 C 中实现后缀数组？

Question

我搜索了后缀数组在C中的实现，但我看到的所有程序都是C++中使用排序的。我不确定如何使用 C 的内置函数 qsort() 代替 C 的 sort() 函数。我们可以在不使用 qsort() 的情况下实现后缀数组吗？要么 C中如何使用qsort()实现后缀数组？

这是我从 geeksforgeeks.com:

得到的代码

int cmp(struct suffix a, struct suffix b) 
{ 
return strcmp(a.suff, b.suff) < 0? 1 : 0; 
}

int *buildSuffixArray(char *txt, int n) 
{ 
// A structure to store suffixes and their indexes 
struct suffix suffixes[n]; 

// Store suffixes and their indexes in an array of structures. 
// The structure is needed to sort the suffixes alphabatically 
// and maintain their old indexes while sorting 
for (int i = 0; i < n; i++) 
{ 
    suffixes[i].index = i; 
    suffixes[i].suff = (txt+i); 
} 

// Sort the suffixes using the comparison function 
// defined above. 
sort(suffixes, suffixes+n, cmp); 

// Store indexes of all sorted suffixes in the suffix array 
int *suffixArr = new int[n]; 
for (int i = 0; i < n; i++) 
    suffixArr[i] = suffixes[i].index; 

// Return the suffix array 
return  suffixArr; 
}

cmp 函数正在比较结构数据类型，而我在使用 qsort() 时遇到错误，它说只允许 void 输入。

Answer 1

qsort函数的声明如下：

void qsort(void *base, size_t nmemb, size_t size,
       int (*compar)(const void *, const void *));

您会注意到，它接受的比较函数必须定义为对其两个参数中的每一个都采用 const void *，但您却为每个参数传递了一个 struct suffix。

您需要更改比较函数以使用 qsort 期望的参数类型。然后你可以将函数内部的那些参数转换为正确的指针类型并使用它们。

int cmp(const void *p1, const void *p2) 
{ 
    const struct suffix *a = p1;
    const struct suffix *b = p2;
    return strcmp(a->suff, b->suff) < 0? 1 : 0; 
}

如何在不使用 qsort 的情况下在 C 中实现后缀数组？

How to implement suffix array in C without using qsort?

c

suffix-array