WordPress代码改silder,义乌网站建设优化案例,怎么创建图片网站,网站规范建设情况一、问题描述
实现英文单词按字典序排列的基数排序算法 编写一个程序#xff0c;采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成#xff0c;最长的单词有 MaxLen 个 字母#xff0c;用相关数据进行测试并输出各趟的排序结果。 用例#…一、问题描述
实现英文单词按字典序排列的基数排序算法 编写一个程序采用基数排序方法将一组英文单词按字典顺序排 列。假设单词均由小写字母或空格构成最长的单词有 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 中的元素就按照每个位上的值进行了排序。
