• 基数排序

    基数排序

    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. }