单词的链式基数排序.doc

设有 n 个单词 S1, S2, ?, Sn, 其长度分别为: l1, l2, , ln, l ? m a x( l , l , … , l ) 为所有单词的最大长 度, 为简单起见( 一般字典中亦如此) , 字母大小写不加 区分( 大写作为小写对待) 。采用线性链表作为存储结 构。设置 lmax 个队列, 队首、队尾指针分别为 lenf[i]、lene [i], 第 i 个队列中保存长度为 i 的单词; 设置 RADIX( 字 符集个数) 个队列, 队首、队尾指针分别为 f[i]、e[i]( i=0,.., RADIX- 1) , 用以存放某次分配时对应位置上的字母为 i(字母字母在字母表 a、b、c、 、y、z 中的序号)的单词; 设置队列 r 用以依次收集分配后的单词。 2 实现步骤 王镇西 ( 湖南城建职业技术学院 信息工程系, 湖南 湘潭 411101) 摘 要:本文针对英语字典中单词排列的特点和基数排序的思想, 将基数排序应用于英语单词排序中, 得到了单词的链式基 数排序法。 关键词:基数排序; 分配; 收集 中图分类号:TP399 文献标识码:B 文章编号: 1672- 6251( 2007) 05- 0178- 03 Linked r adix sor t to wor ds WANG Zhen- xi (Hunan Urban Construction College, Xiangtan 411101,China) Abstr act: This paper applies the radix sort to the sorting of english words,according to the characteristics of the sorting in english dictionary and the principle of radix sort is found. Key wor ds: Radix sort; Assignment;Collection 方法描述 将基数排序[1]的思想应用于字符串类型数据, 即可 得到对单词进行排序的方法( 字典方式) 。由于单词的 长度不等, 为了进行比较, 可以用一个特殊的符号( 比 如“空格”) 填补到每个单词的右端, 使所有单词串的长 度和最大串长相等[2]。但是, 在实际问题中各单词的长 度上下相差悬殊, 这种填补的方法将大大降低算法的 效率。本文提出一种变形的基数排序算法, 这种方法与 原基数排序列的最大区别在于, 并不是每趟都对所有 单词进行分配和收集, 而只是按单词的长度递减的方 式对部分单词进行分配和收集。方法详细描述如下: lmax 个队列 lenf[1]~lenf[lmax]中, 第 i 个队列中保存长度为 i 的单词(某些队列可能为空); i 从 0 到 lmax- 1, 重复以下两步 lmax 次: 1 第二步: 将队列 f[0], f[1], , f[RADIX]置空, 依次将 队列 lenf [lmax- i]、r 中单词按第 lmax- i 个字母分配到相应 队列 f[i]中( 即对长度不小于 lmax- i 的单词进行分配) ; 第三步: 顺序将队列 f[0], f[1], 接, 连接成队列 r; , f[RADIX]首尾相 3 用 C 语言描述的链式基数排序算法 /* 单词的链式基数排序法 */ #define MAXD 20 /* 关键字位数—单词的最大 长度 */ #define RADIX 26 /* 基数大小—字母个数 */ #define MAX_SPACE 40 /* 数据个数上限 */ #include stdlib.h #include stdio.h #include time.h #include string.h /* 关键字类型 */ 结点类型 */ typedef char KeysType; typedef struct node /* { KeysType *elem; struct node *next; { int i,j,k; link *p; lmax=0; r.next=NULL; randomize(); for(i=1;i=MAX_SPACE;i++) { p=(link *)malloc(sizeof(link)); p=lenf[i]; while (p) { j=p- elem[i- 1]- a ; if (! f[j]) f[j]=e[j]=p; else { e[j]- next=p; e[j]=p; } p=p- next; e[j]- next=NULL; } p=r.next; r.next=N