Блог

Главная - Вопросы по программированию - Как реализовать массив суффиксов на C без использования qsort?

Как реализовать массив суффиксов на C без использования qsort?

#c #suffix-array

#c #суффикс-массив

Вопрос:

Я искал реализацию массива суффиксов на C, но все программы, которые я видел, были на C , которые использовали сортировку. Я не уверен, как я могу использовать встроенную функцию C, qsort() вместо функции sort() C. Можем ли мы реализовать массивы суффиксов без использования 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.

Комментарии:

1. Что вам мешает использовать qsort ?

2. Вы используете qsort() тот же способ, что и в любом другом контексте, чем отличаются массивы суффиксов?

3. Похоже, вы просто не уверены, как использовать qsort() для сортировки массива структур.

4. Итак, не могли бы вы рассказать мне, как использовать qsort

5. Начните с чтения справочной страницы . Здесь описано, как это работает, и приведен пример, так что это должно помочь вам начать.

Ответ №1:

Объявление qsort функции выглядит следующим образом:

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

Вы заметите, что функция сравнения, которую она принимает, должна быть определена так, чтобы принимать a const void * для каждого из двух своих параметров, но вместо этого вы передаете a 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; 
}