c-如何对包含多个字符串的结构应用基数排序(使用计数排序)

Question

我想用基数排序按字母顺序对结构字符串进行排序，但我很难应用基数排序来检查字符串的每个数字。我查看了其他帖子，但找不到与我类似的结构。问题是，我的代码检查结构的每个ENTRY，而不是该条目中字符串的每个数字。(我指的是条目；table[0]、table[1]等(所以基本上它对每个条目的字符串本身进行排序。我无法建立逻辑，有人能帮我吗？

EDIT：字符串的长度与不同

这是我的代码：

typedef struct FUNCTIONS_STRUCT
{
    char *fncName;
    void (*fnc)(char *);
    char *description;
} FUNCTIONS_STRUCT_t;
FUNCTIONS_STRUCT_t FUNC_TABLE[] =
{
        { "ABCD", ABCD, "" },
        { "abcD", abcD, "" },
        { "EaBB", EaBB ,""}
        //it goes on ..
};
// Function to find the Largest Number
int getMax(int array[], int n) {
  int max = array[0];
  int i;
  for (i = 1; i < n; i++)
    if (array[i] > max)
      max = array[i];
  return max;
}
// Function for Count sort
void countSort(int array[], int n, int dig) {
  int output[n];
  int i, count[10] = {0};
  for (i = 0; i < n; i++)
    count[(array[i] / dig) % 10]++;
  for (i = 1; i < 10; i++)
    count[i] += count[i - 1];
  for (i = n - 1; i >= 0; i--){
    output[count[(array[i] / dig) % 10] - 1] = array[i];
    count[(array[i] / dig) % 10]--;
  }
  for (i = 0; i < n; i++)
    array[i] = output[i];
}
void radixsort(int array[], int n) {
  //Get the largest number to know the maximum number of digits
  int m = getMax(array, n);
  int dig;
  //Counting sort is performed for every digit
  for (dig = 1; m / dig > 0; dig *= 10)
    countSort(array, n, dig);
}
int main()
{
    int functionTableUnitSize = sizeof(FUNC_TABLE) / sizeof(FUNC_TABLE[0]);
    radixsort(&FUNC_TABLE, functionTableUnitSize);
    return 0;
}

Answer 1

我假设问题中的函数名称具有4个字母数字字符的统一长度。在C中，标识符可以使用来自以下组的63个不同的字母数字字符：

• 小写(abcdefghijklmnopqrstuvxyz(
• 大写字母(EFGHIJKLMNOPQRSTUVWXYZ(
• 数字(0123456789(
• 和下划线(_(

不同的编码有不同的顺序(例如，EBCDIC小写字母在大写字母之前排序，而ASCII则相反(。因此，对于可移植的C程序，我们可以定义自己的词汇排序顺序。

例如，我们可以在一个名为build_lexical_sorting_index的函数中执行此操作。

详细信息

• 我已经根据您在问题中提供的代码对命名进行了最低限度的调整
• 函数必须使用FUNCTION数组，而不能使用int数组
• radix_sort首先创建词汇排序索引
• 然后，必须为函数名的4个字母数字字符中的每一个调用count_sort
• 单词通常从最左边的字符开始排序，这就是我们这样做的原因
• 然后为4个字符中的每一个调用count_sort
• 这将根据函数名中相应字符的词法排序索引确定索引
• 然后应用问题中显示的计数排序算法
• 最后打印结果

如果根据上面提到的几点稍微修改你的代码，它看起来是这样的：

#include <stdio.h>
#define UNIFORM_FUNCNAME_LENGTH 4
typedef struct {
    char *fnc_name;
    void (*fnc)(char *);
    char *description;
} FUNCTION;

void ABCD(char *a) {};
void abcD(char *a) {};
void EaBB(char *a) {};
void A012(char *a) {};
void _ABC(char *a) {};
FUNCTION func_table[] = {
        {"ABCD", ABCD, ""},
        {"abcD", abcD, ""},
        {"EaBB", EaBB, ""},
        {"A012", A012, ""},
        {"_ABC", _ABC, ""}
        //it goes on ..
};
int lexical_sorting_index[256] = {0};
int lexical_index(int ch) {
    return lexical_sorting_index[ch];
}
void count_sort(FUNCTION *array, int n, int char_position) {
    FUNCTION output[n];
    int count[256] = {0};
    for (int i = 0; i < n; i++) {
        int ch = array[i].fnc_name[char_position];
        int index = lexical_index(ch);
        count[index]++;
    }
    for (int i = 1; i < 256; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        int ch = array[i].fnc_name[char_position];
        int index = lexical_index(ch);
        output[count[index] - 1] = array[i];
        count[index]--;
    }
    for (int i = 0; i < n; i++)
        array[i] = output[i];
}
void build_lexical_sorting_index() {
    int nr = 0;
    for (int i = 'a'; i <= 'z'; i++)
        lexical_sorting_index[i] = nr++;
    for (int i = 'A'; i <= 'Z'; i++)
        lexical_sorting_index[i] = nr++;
    for (int i = '0'; i <= '9'; i++)
        lexical_sorting_index[i] = nr++;
    lexical_sorting_index['_'] = nr;
}
void radix_sort(FUNCTION *array, int n) {
    build_lexical_sorting_index();
    for(int char_position = UNIFORM_FUNCNAME_LENGTH - 1; char_position >= 0; char_position--)
        count_sort(array, n, char_position);
}
int main() {
    int table_size = sizeof(func_table) / sizeof(func_table[0]);
    radix_sort(func_table, table_size);
    for (int i = 0; i < table_size; i++)
        printf("%s ", func_table[i].fnc_name);
    return 0;
}

执行程序时，调试控制台中会显示以下内容：

abcD ABCD A012 EaBB _ABC