时间戳

首页 > 解决方案 > 如何在不使用 qsort 的情况下在 C 中实现后缀数组？

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

问题描述

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

这是我从 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 输入。

标签： csuffix-array

解决方案

函数的声明qsort如下：

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

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

您需要更改比较函数以使用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; 
}

推荐阅读