alg10-11.cpp

严蔚敏数据结构的源c代码

 // alg10-11.cpp 链式基数排序
 typedef int InfoType; // 定义其它数据项的类型
 typedef int KeyType; // 定义RedType类型的关键字为整型
 struct RedType // 记录类型(同c10-1.h)
 {
   KeyType key; // 关键字项
   InfoType otherinfo; // 其它数据项
 };
 typedef char KeysType; // 定义关键字类型为字符型
 #include"c1.h"
 #include"c10-3.h"
 void InitList(SLList &L,RedType D[],int n)
 { // 初始化静态链表L（把数组D中的数据存于L中）
   char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
   int i,j,max=D[0].key; // max为关键字的最大值
   for(i=1;i<n;i++)
     if(max<D[i].key)
       max=D[i].key;
   L.keynum=int(ceil(log10(max)));
   L.recnum=n;
   for(i=1;i<=n;i++)
   {
     L.r[i].otheritems=D[i-1].otherinfo;
     itoa(D[i-1].key,c,10); // 将10进制整型转化为字符型,存入c
     for(j=strlen(c);j<L.keynum;j++) // 若c的长度<max的位数,在c前补'0'
     {
       strcpy(c1,"0");
       strcat(c1,c);
       strcpy(c,c1);
     }
     for(j=0;j<L.keynum;j++)
       L.r[i].keys[j]=c[L.keynum-1-j];
   }
 }

 int ord(char c)
 { // 返回k的映射(个位整数)
   return c-'0';
 }

 void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 算法10.15
 { // 静态键表L的r域中记录已按(keys[0],…,keys[i-1])有序。本算法按
   // 第i个关键字keys[i]建立RADIX个子表,使同一子表中记录的keys[i]相同。
   // f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录
   int j,p;
   for(j=0;j<RADIX;++j)
     f[j]=0; // 各子表初始化为空表
   for(p=r[0].next;p;p=r[p].next)
   {
     j=ord(r[p].keys[i]); // ord将记录中第i个关键字映射到[0..RADIX-1]
     if(!f[j])
       f[j]=p;
     else
       r[e[j]].next=p;
     e[j]=p; // 将p所指的结点插入第j个子表中
   }
 }

 int succ(int i)
 { // 求后继函数
   return ++i;
 }

 void Collect(SLCell r[],ArrType f,ArrType e)
 { // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
   // 一个链表，e[0..RADIX-1]为各子表的尾指针。算法10.16
   int j,t;
   for(j=0;!f[j];j=succ(j)); // 找第一个非空子表，succ为求后继函数
   r[0].next=f[j];
   t=e[j]; // r[0].next指向第一个非空子表中第一个结点
   while(j<RADIX-1)
   {
     for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一个非空子表
     if(f[j])
     { // 链接两个非空子表
       r[t].next=f[j];
       t=e[j];
     }
   }
   r[t].next=0; // t指向最后一个非空子表中的最后一个结点
 }

 void printl(SLList L)
 { // 按链表输出静态链表
   int i=L.r[0].next,j;
   while(i)
   {
     for(j=L.keynum-1;j>=0;j--)
       printf("%c",L.r[i].keys[j]);
     printf(" ");
     i=L.r[i].next;
   }
 }

 void RadixSort(SLList &L)
 { // L是采用静态链表表示的顺序表。对L作基数排序，使得L成为按关键字
   // 自小到大的有序静态链表，L.r[0]为头结点。算法10.17
   int i;
   ArrType f,e;
   for(i=0;i<L.recnum;++i)
     L.r[i].next=i+1;
   L.r[L.recnum].next=0; // 将L改造为静态链表
   for(i=0;i<L.keynum;++i)
   { // 按最低位优先依次对各关键字进行分配和收集
     Distribute(L.r,i,f,e); // 第i趟分配
     Collect(L.r,f,e); // 第i趟收集
     printf("第%d趟收集后:\n",i+1);
     printl(L);
     printf("\n");
   }
 }

 void print(SLList L)
 { // 按数组序号输出静态链表
   int i,j;
   printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
   for(i=1;i<=L.recnum;i++)
   {
     printf("keys=");
     for(j=L.keynum-1;j>=0;j--)
       printf("%c",L.r[i].keys[j]);
     printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
   }
 }

 void Sort(SLList L,int adr[]) // 改此句(类型)
 { // 求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号
   int i=1,p=L.r[0].next;
   while(p)
   {
     adr[i++]=p;
     p=L.r[p].next;
   }
 }

 void Rearrange(SLList &L,int adr[]) // 改此句(类型)
 { // adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。
   // 本算法按adr重排L.r，使其有序。算法10.18(L的类型有变)
   int i,j,k;
   for(i=1;i<L.recnum;++i) // 改此句(类型)
     if(adr[i]!=i)
     {
       j=i;
       L.r[0]=L.r[i]; // 暂存记录L.r[i]
       while(adr[j]!=i)
       { // 调整L.r[adr[j]]的记录到位直到adr[j]=i为止
	 k=adr[j];
	 L.r[j]=L.r[k];
         adr[j]=j;
         j=k; // 记录按序到位
       }
       L.r[j]=L.r[0];
       adr[j]=j;
     }
 }

 #define N 10
 void main()
 {
   RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
   SLList l;
   int *adr;
   InitList(l,d,N);
   printf("排序前(next域还没赋值):\n");
   print(l);
   RadixSort(l);
   printf("排序后(静态链表):\n");
   print(l);
   adr=(int*)malloc((l.recnum)*sizeof(int));
   Sort(l,adr);
   Rearrange(l,adr);
   printf("排序后(重排记录):\n");
   print(l);
 }