数据结构_内部排序_链式基数排序 .

数据结构

没做这个算法之前觉得静态链表没什么用， 没做这个算法之前觉得静态链表没什么用，写了这个算法才发现原来静态链表是如此的巧 才发现之前的看法是多么的浅薄无知，看来以后还要更虚心了，嘿嘿... 妙，才发现之前的看法是多么的浅薄无知，看来以后还要更虚心了，嘿嘿... 基数排序，关键是两个过程，分配和回收，分配是按关键字顺序将记录进行分类为， 基数排序，关键是两个过程，分配和回收，分配是按关键字顺序将记录进行分类为，回收 是将分配过程中顺序打乱的记录重新链接成静态链表。 是将分配过程中顺序打乱的记录重新链接成静态链表。这样从按一定顺序对关键字进行分 配和回收到最后就能得到一个有序序列。即为基数排序原理。 配和回收到最后就能得到一个有序序列。即为基数排序原理。"RadixSort.h"plaincopy clipboard view plaincopy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16#define MAX_NUM_OF_KEY 8 #define Radix 10 #define MAX_SPACE 10000typedef int KeyType;typedef struct SLCell { KeyType keys[MAX_NUM_OF_KEY]; int next; SLCell() { for(int i=0;i<MAX_NUM_OF_KEY;i++) for( keys[i]=0; next=0; }17 }SLCell; 18 19 typedef struct SLList 20 { 21 22SLCell r[MAX_SPACE]; int keynum;23 24 25 26 27 28int recnum; SLList() { keynum=0; recnum=0; recnum=0; }29 }SLList; 30 31 typedef int ArrType[Radix]; 32PrintSSList(const &L)//输出静态链表 33 void PrintSSList(const SLList &L)//输出静态链表34 { 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 } 50for( for(int i=L.r[0].next;i!=0;i=L.r[i].next) { j=L.keynumint j=L.keynum-1; while(L.r[i].keys[j]==0&&j>0) j---; while(L.r[i].keys[j]==0&&j>0) j--; if(j==0) if(j==0) (j==0 cout<<0; else { while(j>=0) while(j>=0) cout<<L.r[i].keys[j--]; cout<<L.r[i].keys[j--]; -} cout<<" "; } cout<<endl;GetRandomNum(SLList&L,int nnum,int 51 void GetRandomNum(SLList&L,int nnum,int base)52//得到 个在1...ba 1...base //得到 nnum 个在1...base 之间的随机数53 { 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 } 75srand((unsigned)time(NULL)); int num=base,t; while(num!=0)//得到关键字个数 while(num!=0)//得到关键字个数 (num!=0)// { L.keynum++; num/=Radix; } for( for(int i=1;i<=nnum;i++) { num=rand()%base+1; t=0; while(num!=0)//分配关键字 while(num!=0)//分配关键字 ile(num!=0)// { L.r[i].keys[t++]=num%Radix; num/=Radix; } L.recnum++;//静态链表长度增一 L.recnum++;//静态链表长度增一 } for( i=0;i<L.recnum;i++)//链接静态链表 for(int i=0;i<L.recnum;i++)//链接静态链表 L.r[i].next=i+1;*r, r,int 76 void Distribute(SLCell *r,int i,ArrType&f,ArrType&e)77 78 { 79 80 81 82//按第 //按第 i 个关键字分配记录for(int i=0;i<Radix;i++) for( f[i]=0; int p,j; for(p=r[0].next;p!=0;p=r[p].next) for(p=r[0].next;p!=0;p=r[p].next)83 84 85 86 87 88 89 90 91 } 92{ j=r[p].ke

数据结构

ys[i]; if(f[j]==0) if(f[j]==0) f[j]=p; else r[e[j]].next=p; e[j]=p; }93 void Collect(SLCell *r,ArrType&f,ArrType&e) 94 95 { 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 } 111//回收记录 //回收记录int j; for(j=0;f[j]==0;j++); for(j=0;f[j]==0;j++); r[0].next=f[j]; int t=e[j]; while(j<Radix) while(j<Radix) { for(j++;j<Radix&&f[j]==0;j++); for(j++;j<Radix&&f[j]==0;j++); (j++;j<Radi if(j<Radix&&f[j]!=0) if(j<Radix&&f[j]!=0) { r[t].next=f[j]; t=e[j]; } } r[t].next=0;RadixSort(SLList&L)//基数排序 112 void RadixSort(SLList&L)//基数排序113 { 114 115 116 117 118 119 120 }ArrType f,e; for( for(int i=0;i<L.keynum;i++) { Distribute(L.r,i,f,e); Collect(L.r,f,e); }