2015-12-18 第十六周项目4 - 英文单词的基数排序

本文主要是介绍2015-12-18 第十六周项目4 - 英文单词的基数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.问题及代码

#include <stdio.h>  
#include <malloc.h>  
#include <string.h>  
#define MaxLen 9                //单词的最大长度  
#define Radix  27               //基数rd为27,分别对应' ','a',…'z'  
typedef char String[MaxLen+1];  //定义String为字符数组类型  
typedef struct node  
{  String word;  struct node *next;  
} LinkNode;  
void DispWord(String R[],int n) //输出单词  
{  int i;  printf("  ");  for (i=0; i<n; i++)  printf("[%s] ",R[i]);  printf("\n");  
}  
void PreProcess(String R[],int n)  
//对单词进行预处理,用空格填充尾部至MaxLen长  
{  int i,j;  for (i=0; i<n; i++)  {  if (strlen(R[i])<MaxLen)  {  for (j=strlen(R[i]); j<MaxLen; j++)  R[i][j]=' ';  R[i][j]='\0';  }  }  
}  
void EndProcess(String R[],int n)  
//恢复处理,删除预处理时填充的尾部空格  
{  int i,j;  for (i=0; i<n; i++)  {  for (j=MaxLen-1; R[i][j]==' '; j--);  R[i][j+1]='\0';  }  
}  
void Distribute(String R[],LinkNode *head[],LinkNode *tail[],int j,int n)  
//按关键字的第j个分量进行分配,进入此过程时各队列一定为空  
{  int i,k;  LinkNode *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=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点  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[],LinkNode *head[])  
//依次将各非空队列中的记录收集起来  
{  int k=0,i;  LinkNode *p;  for (i=0; i<Radix; i++)  for (p=head[i]; p!=NULL; p=p->next)  strcpy(R[k++],p->word);  
}  
void RadixSort(String R[],int n)    //对R[0..n-1]进行基数排序  
{  LinkNode *head[Radix],*tail[Radix]; //定义Radix个队列  int i,j;  for (i=MaxLen-1; i>=0; i--)             //从低位到高位做d趟箱排序  {  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","do while","for","case"};  printf("排序前:\n");  DispWord(R,n);  PreProcess(R,n);  printf("预处理后:\n");  DispWord(R,n);  RadixSort(R,n);  printf("排序结果:\n");  DispWord(R,n);  EndProcess(R,n);  printf("最终结果:\n");  DispWord(R,n);  printf("\n");  return 0;  
}

2.运行结果