如何对包含多个字符串的结构应用基数排序（使用计数排序）

Question

我想使用基数排序按字母顺序对结构字符串进行排序，但是我正在努力应用基数排序来检查字符串的每个数字。我检查了其他帖子，但找不到与我的类似的结构。问题是我的代码检查结构的每个条目，而不是该条目中字符串的每个数字。（我的意思是条目；table[0]、table[1] 等）所以基本上它对每个条目本身的字符串进行排序。我无法构建逻辑，有人可以帮助我吗？

编辑：字符串的长度不一样

这是我的代码：

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 个不同的字母数字字符：

小写 (abcdefghijklmnopqrstuvwxyz)
大写字母 (ABCDEFGHIJKLMNOPQRSTUVWXYZ)
位数 (0123456789)
和下划线 (_)

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

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

详情

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

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

#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

如何对包含多个字符串的结构应用基数排序（使用计数排序）

How to apply radix sort (uses counting sort) with struct containing multiple strings

c

struct

radix-sort

counting-sort