jishu.cpp

基数数值排序的源程序

#include <stdio.h>
#include <conio.h>
#include <stdlib.h> 
#include <string.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];
  int len=strlen(s);
  printf("输入要进行排序的数：（输入 0 结束）  \n"); 
  scanf("%s",s); 
   head=NULL; 
   *d=0; 
   terminal=NULL; 
   while(s[0]!='0') 
   { temp=(lnode)malloc(sizeof(struct node)); 
      if (len > *d) *d=len; 
	  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) 
{ printf("\n"); 
  while (h!=NULL) 
  { printf("%d ",h->k); 
    h=h->next; } 
   getch(); 
} 


lnode radixsort(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;
  printf("                 基数排序               \n");
  printf("--------------------------------------------------------\n");
  h=my_input(&d); 
  h=radixsort(h,d);
  printf("排序的结果是：\n");
  my_output(h); 
  my_free(h); 
}