数据结构+基数排序算法

一、问题描述

实现英文单词按字典序排列的基数排序算法 编写一个程序，采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成，最长的单词有 MaxLen 个 字母，用相关数据进行测试并输出各趟的排序结果。 用例：R[] = {“ while”, “if”, “if else”, “for”, “do while”, “ switch”} 排序结果： “do while”, “for”, “if”, “if else”, “ while”, “ switch”

二、问题解决

#include <stdio.h> 
#include <malloc.h> #include <string.h> 
#define MAX_LEN 10 // 单词的最大长度 
#define RADIX 27 // 基数 rd 为 27,分
别对应' ','a',...,'z' typedef char String[MAX_LEN + 1]; // 定义 String 为字
符数组类型 
typedef struct node 
{ String word; struct node *next; 
}link_node; // 单链表结点类型 //输出单词 void disp_word(String R[], int n) 
{ int i; printf(" "); for(i = 0; i < n; i++) { printf(" %s ", R[i]); } printf("\n"); 
} //对单词进行预处理,用空格填充尾部至 MAX_LEN 长 void pre_process(String R[], int n) 
{ int i, j; for(i = 0; i < n; i++) { if(strlen(R[i]) < MAX_LEN) { for(j = strlen(R[i]); j < MAX_LEN; j++) { R[i][j] = ' '; } R[i][j] = '\0'; }  } 
} //恢复处理,删除预处理时填充的尾部空格 void end_process(String R[], int n) 
{ int i, j; for(i = 0; i < n; i++) { for(j = MAX_LEN - 1; R[i][j] == ' '; j--) R[i][j + 1] = '\0'; } 
} //按关键字的第 j 个分量进行分配，进入此过程时各队列一定为空 void distribute(String R[], link_node *head[], link_node *tail[], 
int j, int n) 
{ int i; // 循环变量 int k; // 队列编号 link_node *p; for(i = 0; i < n; i++) // 依次扫描
R[i],将其入队 { if(R[i][j] == ' ') // 空格时放入 0
号队列中,'a'放入 1 号队列中 k = 0; else k = R[i][j] - 'a' + 1; p = (link_node *)malloc(sizeof(link_node)); // 创建新结点 strcpy(p->word, R[i]); p->next = NULL; if(head[k] == NULL) { head[k] = p; tail[k] = p; } else  { tail[k]->next = p; tail[k] = p; } } 
} //依次将各非空队列中的结点收集起来，并释放各非空队列中的所有结点 void collect(String R[], link_node *head[]) 
{ int i; int k = 0; link_node *pre, *p; for(i = 0; i < RADIX; i++) { if(head[i] != NULL) { pre = head[i]; p = pre->next; while(p != NULL) { strcpy(R[k++], pre->word); free(pre); pre = p; p = p->next; } strcpy(R[k++], pre->word); free(pre); } } 
} //对 R[0...n-1]进行基数排序 void radix_sort(String R[], int n) 
{ int i, j; link_node *head[RADIX], *tail[RADIX]; for(i = MAX_LEN - 1; i >= 0; i--) // 从低位到
高位做 MAX_LEN 趟基数排序  { for(j = 0; j < RADIX; j++) head[j] = tail[j] = NULL; distribute(R, head, tail, i, n); // 第 i 趟分
配 collect(R, head); // 第 i 趟收
集 } 
} int main() 
{ int n = 6; String R[] = {"while", "if", "if else", "for", "do while", 
"switch"}; printf("排序前："); disp_word(R, n); pre_process(R, n); radix_sort(R, n); end_process(R, n); printf("排序后:"); disp_word(R, n); return 0; 
} 

三、代码分析

在对这组英文字母排序之前，要使它们的长度保持一致（即用空格填充）， 在排序完成之后再将填充的空格删去。这里运用的排序方法时基数排序， 基 数排序是一种非比较排序算法，它根据元素的每个位上的值进行排序。 函数 radix_sort 接受一个字符串数组 R 和数组的长度 n 作为参数。它使 用了两个辅助数组 head 和 tail，用于存储链表的头节点和尾节点。 首先，代码中使用两个循环嵌套来进行基数排序。外层循环从最高位开始，逐 渐向低位移动，共进行 MAX_LEN 趟排序。内层循环用于初始化 head 和 tail 数 组，将它们全部置为 NULL。 每一趟排序中，代码调用了两个函数：distribute 和 collect。这两个函 数分别用于分配和收集元素。函数 distribute 接受参数 R、head、tail、i 和 n，其中 R 是待排序的字符串数组，head 和 tail 是链表的头节点和尾节点数 组，i 表示当前进行排序的位数，n 表示数组的长度。该函数根据第 i 位上的 值将元素分配到不同的链表中。函数 collect 接受参数 R 和 head，其中 R 是 待排序的字符串数组，head 是链表的头节点数组。 该函数将链表中的元素按顺序收集到数组 R 中，完成一趟排序。通过循环 嵌套的方式，代码依次进行每一趟排序，直到最低位排序完成。最终，数组 R 中的元素就按照每个位上的值进行了排序。