{
if(q->data
p->next=q;p=q; q=q->next; } else {
p->next=r;p=r; r=r->next; }
}//while
while(q!=e1->next) {
p->next=q;p=q; q=q->next; }
while(r!=e2->next) {
p->next=r;p=r; r=r->next; }
}//LinkedList_Merge,与上一题完全相同 10.39
void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列 {
start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;i for(j=start2;j RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位 start1+=k+1; start2=j; //修改两序列尚未归并部分的起始位置 } }//SL_Merge void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18 { len=end-start+1; for(i=1;i<=k;i++) if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p for(i=0;i j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) { a[j]=temp; temp=a[l]; a[l]=a[j]; j=l;l=start+(j-start+k)%len; //依次向右移 } a[start+i]=temp; }//for }//RSh 10.40 书后给出的解题思路在表述上存在问题,无法理解.比如说,\把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1 void Hash_Sort(int a[ ])//对1000个关键字为四位整数的记录进行排序 { int b[10000]; for(i=0;i<1000;i++) //直接按关键字散列 { for(j=a[i];b[j];j=(j+1)000); b[j]=a[i]; } for(i=0,j=0;i<1000;j++) //将散列收回a中 if(b[j]) { for(x=b[j],k=j;b[k];k=(k+1)000) if(b[k]==x) { a[i++]=x; b[k]=0; } }//if }//Hash_Sort 10.42 typedef struct { int gt; //大于该记录的个数 int lt; //小于该记录的个数 } place; //整个序列中比某个关键字大或小的记录个数 int Get_Mid(int a[ ],int n)//求一个序列的中值记录的位置 { place b[MAXSIZE]; for(i=0;i if(a[j]>a[i]) b[i].gt++; else if(a[j] min_dif=abs(b[0].gt-b[0].lt); for(i=0;i void Count_Sort(int a[ ],int n)//计数排序算法 { int c[MAXSIZE]; for(i=0;i for(j=0,count=0;j for(i=0;i min=0; for(j=0;j if(c[j] c[min]=INFINITY; //修改该记录的c值为无穷大以便下一次选取 } }//Count_Sort 10.44 void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序 { int number[w+1],pos[w+1]; for(i=0;i pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置 for(i=0;i a[i]=c[i]; }//Enum_Sort 分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用. 10.45 typedef enum {0,1,2,3,4,5,6,7,8,9} digit; //个位数类型 typedef digit[3] num; //3位自然数类型,假设低位存储在低下标,高位存储在高下标 void Enum_Radix_Sort(num a[ ],int n)//利用计数实现基数排序,其中关键字为3位自然数,共有n个自然数 { int number ,pos ; num c[MAXSIZE]; for(j=0;j<3;j++) //依次对个位,十位和百位排序 { for(i=0;i pos[i]=pos[i-1]+num[i]; //把关键字的值映射为元素在排好的序列中的位置 for(i=0;i }//Enum_Radix_Sort 分析:计数排序是一种稳定的排序方法.正因为如此,它才能够被用来实现基数排序. 10.46 typedef struct { int key; int pos; } Shadow; //影子序列的记录类型 void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//对元素很大的记录序列b进行排序,结果放入a中,不移动元素 { Shadow d[MAXSIZE]; for(i=0;i d[i].key=b[i].key; d[i].pos=i; } for(i=n-1,change=1;i>1&&change;i--) //对影子序列执行冒泡排序 { change=0; for(j=0;j if(d[j].key>d[j+1].key) { d[j]<->d[j+1]; change=1; } }//for