radix.cpp

这是本人精心搜集的关于常用图论算法的一套源码

//基数排序 
 #define   MAXN  100
 #define   MAXd  7                            // 设排序码由最多7位整数组成
 #define   rd   10                            // 设排序码

 typedef  struct {int key[MAXd],next; } rec;
 typedef  rec rfile[MAXN];
 void radsort(rfile r, int& p, int n, int d)   // p是头指针
 { int f[rd],e[rd];   int  i,j,k,t;            // rd是“基数”,图5.8设 rd=10
   for (i=1; i<=n;i++) r[i].next=i+1;           // 将原始文件构成初始链表
   r[n].next=0;
   for(i=d; i>0; i-- )                       // 总共进行d趟“分配”与“收集”
      { for(j=0; j<rd; j++ ) f[j]=0;         // 下行起进行一遍“分配”
        while(p){ k=r[p].key[i];             // 取出第i位排序码至 K,插入第k个链表
                  if(f[k])r[e[k]].next=p; else f[k]=p;
                  e[k]=p;    p=r[p].next;              // p 指向下一个记录
                 }//end_while
        j=0;  while (f[j]==0) j++;                     // 此行起以下为收集部分
        p=f[j];  t=e[j];                               // 找第一个非空队列
        while (j<rd-1) if(f[++j]) { r[t].next=f[j];  t=e[j]; }
        r[t].next=0;
     }// end_for i
}

#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
void main(void)
{
  int n,i,j,p=1;  rfile r;
  cout<<" Please input sorted elements number=? ";  cin>>n; 
  for(j=1;j<=3;j++)
   for(i=1;i<=n; i++)
        r[i].key[j]=rand() % 10;
  printf(" \norigil array is\n");
  for(i=1;i<=n; i++)
     { for(j=1;j<=3;j++)printf("%1d",r[i].key[j]);
       if(i%10==0)cout<<endl; else putchar('  ');
     }
  cout<<endl;
  radsort(r,p,n,3);
  printf("\n sort array is\n");
  i=p;  int c=0;
  while(i)
       {
         for(j=1;j<=3;j++)printf("%1d",r[i].key[j]); c++;
         if(c%10==0)cout<<endl; else putchar('  ');
         i=r[i].next;
        }
  cout<<endl;
}