2 yangmo2526 yangmo2526 于 2015.06.16 20:35 提问

数据结构基数排序c++语言

设计一个将一组英文单词按字典序排列的基数排序算法。设单词均由小写字母或空格构成,最长的单词有n个字母

3个回答

gamefinity
gamefinity   Rxr 2015.06.16 21:09

简单说下思路吧。先有26个指针数组,分别对应单词的第一位的a-z,这个指针指向另一个指针数组,对应单词的第二位字母(这层的数组最多可能有26个)。以此类推,直到最后直接指向单词。

lx624909677
lx624909677   Ds   Rxr 2015.06.16 22:01

/********************************************************
*函数名称:GetNumInPos
*参数说明:num 一个整形数据

  •      pos 表示要获得的整形的第pos位数据 
    

    说明: 找到num的从低到高的第pos位的数据
    *
    *******************************************************/

    int GetNumInPos(int num,int pos)

    {

    int temp = 1;

    for (int i = 0; i < pos - 1; i++)

    temp *= 10;

    return (num / temp) % 10;

    }

/********************************************************
*函数名称:RadixSort
*参数说明:pDataArray 无序数组;

  •      iDataNum为无序数据个数 
    

    说明: 基数排序
    *
    *******************************************************/

    #define RADIX_10 10 //整形排序

    #define KEYNUM_31 10 //关键字个数,这里为整形位数

    void RadixSort(int* pDataArray, int iDataNum)

    {

    int *radixArrays[RADIX_10]; //分别为0~9的序列空间

    for (int i = 0; i < 10; i++)

    {

    radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));

    radixArrays[i][0] = 0; //index为0处记录这组数据的个数

    }

    for (int pos = 1; pos <= KEYNUM_31; pos++) //从个位开始到31位

    {

    for (int i = 0; i < iDataNum; i++) //分配过程

    {

    int num = GetNumInPos(pDataArray[i], pos);

    int index = ++radixArrays[num][0];

    radixArrays[num][index] = pDataArray[i];

    }

    for (int i = 0, j =0; i < RADIX_10; i++)    //收集  
    {  
        for (int k = 1; k <= radixArrays[i][0]; k++)  
            pDataArray[j++] = radixArrays[i][k];  
        radixArrays[i][0] = 0;    //复位  
    }  
    

    }

    }

    直接调用就行了

cuiwei1026522829
cuiwei1026522829   Ds   Rxr 2015.06.16 23:21

26.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成,最长的单词有d个字母。提示:所有长度不足d个字母的单词都在尾处补足空格,排序时设置27个箱子,分别与空格,A,B...Z对应。
答:
 #define KeySize 10 //设关键字位数d=10
 #define Radix 27 //基数rd为27
 typedef RecType DataType;//将队列中结点数据类型改为RecType类型
 typedef struct node{
   char key[KeySize]; //关键字域
   OtherInfoType info; //其它信息域,
  }RecType; //记录结点类型
 typedef RecType seqlist[n+1];

 void RadixSort(seqlist R)
  {
   LinkQueue B[Radix];
   int i;
   for(i=0;i     InitQueue(&B[i]);
   for(i=KeySize-1;i>=0;i--){//从低位到高位做d趟箱排序
     Distribute(R,B,i);//第KeySize-i趟分配
     Collect(R,B);//第KeySize-i趟收集
    }
  }

 void Distribute(seqlist R,LinkQueue B[], int j)
  {//按关键字的第j个分量进行分配,初始时箱子为空
   int i;
   j=KeySize-j; // 确定关键字从低位起的位置
   for(i=0;i      if (R[i].key[j]-'A'>26)
       EnQueue(&B[0],R[i]);//将第j位关键字位空格的记录入第0个队列
     else EnQueue(&B[0],R[R[i].key[j]-'A'+1]);
  }

 void Collect(seqlist R,LinkQueue B[])
  {
   //依次将各非空箱子中的记录收集起来,本过程结束,各箱子都变空
   int i,j;
   for (j=0;j<Radix;j++)
    while(!QueueEmpty(&B[j]))
     R[i++]=DeQueue(&B[j]);//将出队记录依次输出到R[i]中
  }

Csdn user default icon
上传中...
上传图片
插入图片