第十章习题(3)

{

if(q->datadata) {

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]a[min]; //与第i个记录交换

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

for(i=0;i