049.基数排序

  

   

    

     

    
    

     

      #include "stdio.h"
     
    
   

    

     

    
    

     

      #include "conio.h"
     
    
   

    

     

    
    

     

      #include "stdlib.h"
     
    
   

    

     

    
    

     

      #define MAX 5
     
    
   

    

     

    
    

     

      typedef struct node
     
    
   

    

     

    
    

     

      { int k;
     
    
   

    

     

    
    

     
  struct node *next;
     
    
   

    

     

    
    

     

      } *lnode;
     
    
   

    

     

    
    

     

      lnode my_input(int *d)
     
    
   

    

     

    
    

     

      { lnode head,temp,terminal;
     
    
   

    

     

    
    

     
 char s[MAX+1];
     
    
   

    

     

    
    

     
  printf("Input the records ('0' to end input):\n");
     
    
   

    

     

    
    

     
  scanf("%s",s);
     
    
   

    

     

    
    

     

        head=NULL;
     
    
   

    

     

    
    

     

        *d=0;
     
    
   

    

     

    
    

     

        terminal=NULL;
     
    
   

    

     

    
    

     
  while(s[0]!='0')
     
    
   

    

     

    
    

     

         {
     
    
   

    

     

    
    

     

         temp=(lnode)malloc(sizeof(struct node));
     
    
   

    

     

    
    

     
    if (strlen(s)>*d)
     
    
   

    

     

    
    

     

          *d=strlen(s);
     
    
   

    

     

    
    

     

          temp->k=atoi(s);
     
    
   

    

     

    
    

     
     if (head==NULL)
     
    
   

    

     

    
    

     

            { head=temp;
     
    
   

    

     

    
    

     

            terminal=temp;
     
    
   

    

     

    
    

     

            }
     
    
   

    

     

    
    

     
      else
     
    
   

    

     

    
    

     

            {
     
    
   

    

     

    
    

     

             terminal->next=temp;
     
    
   

    

     

    
    

     

              terminal=temp;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
         scanf("%s",s);
     
    
   

    

     

    
    

     

               }
     
    
   

    

     

    
    

     

      	  terminal->next=NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return head;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void my_output(lnode h)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	lnode t=h;
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     
	while (h!=NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("%d ",h->k);
     
    
   

    

     

    
    

     

      		h=h->next;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	h=t;
     
    
   

    

     

    
    

     
	/* getch(); */
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      lnode Radix_Sort(lnode head,int d)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      lnode p,q,h,t;
     
    
   

    

     

    
    

     

      int i,j,x,radix=1;
     
    
   

    

     

    
    

     

       h=(lnode)malloc(10*sizeof(struct node));
     
    
   

    

     

    
    

     

        t=(lnode)malloc(10*sizeof(struct node));
     
    
   

    

     

    
    

     
   for (i=d;i>=1;i--)
     
    
   

    

     

    
    

     

         {
     
    
   

    

     

    
    

     
   for (j=0;j<=9;j++)
     
    
   

    

     

    
    

     

         { 	h[j].next=NULL;
     
    
   

    

     

    
    

     

         	t[j].next=NULL;
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     

         p=head;
     
    
   

    

     

    
    

     
   while (p!=NULL)
     
    
   

    

     

    
    

     

         {
     
    
   

    

     

    
    

     

         	x=((p->k)/radix)%10;
     
    
   

    

     

    
    

     
   	if (h[x].next==NULL)
     
    
   

    

     

    
    

     

         	{
     
    
   

    

     

    
    

     

         		h[x].next=p;
     
    
   

    

     

    
    

     

         		t[x].next=p;
     
    
   

    

     

    
    

     

         	}
     
    
   

    

     

    
    

     
   	else
     
    
   

    

     

    
    

     

         	{
     
    
   

    

     

    
    

     

         		q=t[x].next;
     
    
   

    

     

    
    

     

         		q->next=p;
     
    
   

    

     

    
    

     

         		t[x].next=p;
     
    
   

    

     

    
    

     

         	}
     
    
   

    

     

    
    

     

         	p=p->next;
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

         j=0;
     
    
   

    

     

    
    

     
   while (h[j].next==NULL)
     
    
   

    

     

    
    

     

          j++;
     
    
   

    

     

    
    

     

          head=h[j].next;
     
    
   

    

     

    
    

     

          q=t[j].next;
     
    
   

    

     

    
    

     
    for (x=j+1;x<=9;x++)
     
    
   

    

     

    
    

     
    if (h[x].next!=NULL)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

          	q->next=h[x].next;
     
    
   

    

     

    
    

     

          	q=t[x].next;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          q->next=NULL;
     
    
   

    

     

    
    

     

          radix*=10;
     
    
   

    

     

    
    

     
    printf("\n---------------------\n");
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return head;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void my_free(lnode h)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	lnode temp=h;
     
    
   

    

     

    
    

     
	while (temp)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		h=temp->next;
     
    
   

    

     

    
    

     
		free(temp);
     
    
   

    

     

    
    

     

      		temp=h;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	lnode h;
     
    
   

    

     

    
    

     
	int d;
     
    
   

    

     

    
    

     
	clrscr();
     
    
   

    

     

    
    

     

      	h=my_input(&d);
     
    
   

    

     

    
    

     
	puts("The sequence you input is:");
     
    
   

    

     

    
    

     
	my_output(h);
     
    
   

    

     

    
    

     

      	h=Radix_Sort(h,d);
     
    
   

    

     

    
    

     
	puts("\nThe sequence after radix_sort is:");
     
    
   

    

     

    
    

     
	my_output(h);
     
    
   

    

     

    
    

     
	my_free(h);
     
    
   

    

     

    
    

     
	puts("\n Press any key to quit...");
     
    
   

    

     

    
    

     
	getch();
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：程序员编程指南，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_41055260/article/details/124491538