第十章 内部排序.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

　{
　　H.r[1]<->H.r[i];
　　Heap_Adjust(H,1,i-1);
　}
}//TriHeap_Sort

void Heap_Adjust(Heap &H,int s,int m)//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆
{
　rc=H.r[s];
　for(j=3*s-1;j<=m;j=3*j-1)
　{
　　if(j<m&&H.r[j].key<H.r[j+1].key) j++;
　　if(j<m&&H.r[j].key<H.r[j+1].key) j++;
　　H.r[s]=H.r[j];
　　s=j;
　}
　H.r[s]=rc;
}//Heap_Adjust
分析:本算法与课本上的堆排序算法相比,只有两处改动:1.建初始堆时,i的上限从H.length/3开始(为什么?) 2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最左边的孩子的序号的计算公式为j=3*s-1(为什么?)

10.36

void Merge_Sort(int a[ ],int n)//归并排序的非递归算法
{
　for(l=1;l<n;l*=2) //l为一趟归并段的段长
　　for(i=0;(2*i-1)*l<n;i++) //i为本趟的归并段序号
　　{
　　　start1=2*l*i; //求出待归并的两段的上下界
　　　end1=start1+l-1;
　　　start2=end1+1;
　　　end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);//注意end2可能超出边界
　　　Merge(a,start1,end1,start2,end2); //归并
　　}
}//Merge_Sort

void Merge(int a[ ],int s1,int e1,int s2,int e2)//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]
{
　int b[MAXSIZE]; //设立辅助存储数组b
　for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)
　{
　　if(a[i]<a[j]) b[k]=a[i++];
　　else b[k]=a[j++];
　}
　while(i<=e1) b[k++]=a[i++];
　while(j<=e2) b[k++]=a[j++]; //归并到b中
　for(i=s1;i<=e2;i++) //复制回去
　　a[i]=b[i];
}//Merge

10.37

void LinkedList_Merge_Sort1(LinkedList &L)//链表结构上的归并排序非递归算法
{
　for(l=1;l<L.length;l*=2) //l为一趟归并段的段长
　　for(p=L->next,e2=p;p->next;p=e2)
　　{
　　　for(i=1,q=p;i<=l&&q->next;i++,q=q->next);
　　　e1=q;
　　　for(i=1;i<=l&&q->next;i++,q=q->next);
　　　e2=q; //求出两个待归并子序列的尾指针
　　　if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //归并
　　}
}//LinkedList_Merge_Sort1

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
　q=p->next;r=e1->next; //q和r为两个子序列的起始位置
　while(q!=e1->next&&r!=e2->next)
　{
　　if(q->data<r->data) //选择关键字较小的那个结点接在p的后面
　　{
　　　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.38

void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构
{
　LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针
　for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针
　　if(!p->next||p->data>p->next->data) end[i++]=p;
　while(end[0]->next) //当不止一个子序列时进行两两归并
　{
　　j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置
　　for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列
　　{
　　　e1=end[j];e2=end[j+1]; //确定两个子序列
　　　if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并
　　　end[k++]=e2; //用新序列的尾指针取代原来的尾指针
　　　j+=2; //转到后面两个子序列
　　}
　}//while
}//LinkedList_Merge_Sort2

void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
　q=p->next;r=e1->next;
　while(q!=e1->next&&r!=e2->next)
　{
　　if(q->data<r->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<l1;i++) //插入第i个元素
　{
　　for(j=start2;j<l1+l2&&a[j]<a[start1+i];j++); //寻找插入位置
　　k=j-start2; //k为要向右循环移动的位数
　　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<p;i++) //对p个循环链分别进行右移
　{
　　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<s,第二个子序列有s个记录."可是题目中并没有说明,第一个序列的长度<2s.请会做的朋友提供解法.

10.41

void Hash_Sort(int a[ ])//对1000个关键字为四位整数的记录进行排序
{
　int b[10000];
　for(i=0;i<1000;i++) //直接按关键字散列
　{
　　for(j=a[i];b[j];j=(j+1)%10000);
　　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)%10000)
　　　　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<n;i++) //对每一个元素统计比它大和比它小的元素个数gt和lt
　　for(j=0;j<n;j++)
　　{
　　　if(a[j]>a[i]) b[i].gt++;
　　　else if(a[j]<a[i]) b[i].lt++;
　　}
　mid=0;
　min_dif=abs(b[0].gt-b[0].lt);
　for(i=0;i<n;i++) //找出gt值与lt值最接近的元素,即为中值记录
　　if(abs(b[i].gt-b[i].lt)<min_dif) mid=i;
　return mid;
}//Get_Mid

10.43

void Count_Sort(int a[ ],int n)//计数排序算法
{
　int c[MAXSIZE];
　for(i=0;i<n;i++) //对每一个元素
　{
　　for(j=0,count=0;j<n;j++) //统计关键字比它小的元素个数
　　　if(a[j]<a[i]) count++:
　　c[i]=count;
　}
　for(i=0;i<n;i++) //依次求出关键字最小,第二小,...,最大的记录
　{
　　min=0;
　　for(j=0;j<n;j++)
　　　if(c[j]<c[min]) min=j; //求出最小记录的下标min
　　a[i]<->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<n;i++) number[a[i]]++; //计数
　for(pos[0]=0,i=1;i<n;i++)
　　pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置
　for(i=0;i<n;i++) //构造有序数组c
　　c[pos[a[i]]++]=a[i];
　for(i=0;i<n;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<n;i++) number[a[i][j]]++; //计数
　　for(pos[0]=0,i=1;i<n;i++)
　　　pos[i]=pos[i-1]+num[i]; //把关键字的值映射为元素在排好的序列中的位置
　　for(i=0;i<n;i++) //构造有序数组c
　　　c[pos[a[i][j]]++]=a[i];
　　for(i=0;i<n;i++)
　　　a[i]=c[i];
　}//for
}//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<n;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<i;j++)
　　　if(d[j].key>d[j+1].key)
　　　{
　　　　d[j]<->d[j+1];
　　　　change=1;
　　　}
　}//for
　for(i=0;i<n;i++) //按照影子序列里记录的原来位置复制原序列
　　a[i]=b[d[i].pos];
}//Shadow_Sort

 


<　全文完　>