基数排序

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <string.h>
  4. #define MAXE 20            /*线性表中最多元素个数*/
  5. #define MAXR 10            /*基数的最大取值*/
  6. #define MAXD 8            /*关键字位数的最大取值*/
  8. typedef struct node
  9. {    
  10.     char data[MAXD];    /*记录的关键字定义的字符串*/
  11.        struct node *next;
  12. } RecType;
  14. void RadixSort(RecType *&p,int r,int d) 
  15. /*p为待排序序列链表指针,r为基数,d为关键字位数*/
  16. {
  17.     RecType *head[MAXR],*tail[MAXR],*t;/*定义各链队的首尾指针*/
  18.     int i,j,k;
  19.     for (i=d-1;i>=0;i--)                   /*从低位到高位做d趟排序*/
  20.     {    for (j=0;j<r;j++)                 /*初始化各链队首、尾指针*/
  21.             head[j]=tail[j]=NULL;
  22.         while (p!=NULL)                  /*对于原链表中每个结点循环*/
  23.         {    k=p->data[i]-'0';           /*找第k个链队*/
  24.             if (head[k]==NULL)           /*进行分配,即采用尾插法建立单链表*/
  25.             {    
  26.                 head[k]=p;
  27.                 tail[k]=p;
  28.             }
  29.               else
  30.             {      
  31.                 tail[k]->next=p;
  32.                 tail[k]=p;
  33.             }
  34.             p=p->next;                     /*取下一个待排序的元素*/
  35.         }
  36.         p=NULL;
  37.            for (j=0;j<r;j++)                /*对于每一个链队循环*/
  38.             if (head[j]!=NULL)             /*进行收集*/
  39.             {    if (p==NULL)
  40.                 {    p=head[j];
  41.                     t=tail[j];
  42.                 }
  43.                 else
  44.                 {    t->next=head[j];
  45.                     t=tail[j];
  46.                 }
  47.             }
  48.         t->next=NULL;                    /*最后一个结点的next域置NULL*/
  49.     }
  50. }
  52. void main()
  53. {
  54.     RecType *h=NULL,*p,*t;
  55.     char *A[]={"75","87","68","92","88","61","77","96","80","72"};
  56.     int i,n=10;
  57.     for (i=0;i<n;i++)        /*构造不带头结点的单链表h*/
  58.     {    
  59.         p=(RecType *)malloc(sizeof(RecType));
  60.         strcpy(p->data,A[i]);
  61.         if (h==NULL)
  62.         {    
  63.             h=p;
  64.             t=h;
  65.         }
  66.         else
  67.         {    
  68.             t->next=p;
  69.             t=p;
  70.         }
  71.     }
  72.     t->next=NULL;
  73.     printf("排序前:");
  74.     for (i=0;i<n;i++)
  75.         printf("%3s",A[i]);
  76.     printf("\n");
  77.     RadixSort(h,10,2);
  78.     printf("排序后:");
  79.     p=h;
  80.     while (p!=NULL)
  81.     {    
  82.         printf("%3s",p->data);
  83.         p=p->next;
  84.     }
  85.     printf("\n");
  86. }