数据结构严蔚敏版第十章答案.docx
《数据结构严蔚敏版第十章答案.docx》由会员分享，可在线阅读，更多相关《数据结构严蔚敏版第十章答案.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构严蔚敏版第十章答案
第十章内部排序
10.23
voidInsert_Sort1（SqList&L）//监视哨设在高下标端的插入排序算法
{
k=L.length;
for（i=k-1;i;--i）//从后向前逐个插入排序
if（L.r[i].key>L.r[i+1].key）
{
L.r[k+1].key=L.r[i].key;//监视哨
for（j=i+1;L.r[j].key>L.r[i].key;++j）
L.r[j-1].key=L.r[j].key;//前移
L.r[j-1].key=L.r[k+1].key;//插入
}
}//Insert_Sort1
10.24
voidBiInsert_Sort（SqList&L）//二路插入排序的算法
{
intd[MAXSIZE];//辅助存储
x=L.r.key;d=x;
first=1;final=1;
for（i=2;i<=L.length;i++）
{
if（
L.r[i].key>=x）//插入前部
{
for（j=final;d[j]>L.r[i].key;j--）
d[j+1]=d[j];
d[j+1]=L.r[i].key;
final++;
}
else//插入后部
{
for（j=first;d[j] d[j-1]=d[j];
d[（j-2）%MAXSIZE+1]=L.r[i].key;
first=（first-2）%MAXSIZE+1;//这种形式的表达式是为了兼顾first=1的情况
}
}//for
for（i=first,j=1;d[i];i=i%MAXSIZE+1,j++）//将序列复制回去
L.r[j].key=d[i];
}//BiInsert_Sort
10.25
voidSLInsert_Sort（SLList&L）//静态链表的插入排序算法
{
L.r[0].key=0;L.r[0].next=1;
L.r[1].next=0;//建初始循环链表
for（i=2;i<=L.length;i++）//逐个插入
{
p=0;x=L.r[i].key;
while（L.r[L.r[p].next].key p=L.r[p].next;
q=L.r[p].next;
L.r[p].next=i;
L.r[i].next=q;
}//for
p=L.r[0].next;
for（i=1;i {
while（p q=L.r[p].next;
if（p!
=i）
{
L.r[p]<->L.r[i];
L.r[i].next=p;
}
p=q;
}//for
}//SLInsert_Sort
10.26
voidBubble_Sort1（inta[],intn）//对包含n个元素的数组a进行改进的冒泡排序
{
change=n-1;//change指示上一趟冒泡中最后发生交换的元素
while（change）
{
for（c=0,i=0;i if（a[i]>a[i+1]）
{
a[i]<->a[i+1];
c=i+1;//c指示这一趟冒泡中发生交换的元素
}
change=c;
}//while
}//Bubble_Sort1
10.27
voidBubble_Sort2（inta[],intn）//相邻两趟是反方向起泡的冒泡排序算法
{
low=0;high=n-1;//冒泡的上下界
change=1;
while（low {
change=0;
for（i=low;i if（a[i]>a[i+1]）
{
a[i]<->a[i+1];
change=1;
}
high--;//修改上界
for（i=high;i>low;i--）//从下向上起泡
if（a[i] {
a[i]<->a[i-1];
change=1;
}
low++;//修改下界
}//while
}//Bubble_Sort2
10.28
voidBubble_Sort3（inta[],intn）//对上一题的算法进行化简,循环体中只包含一次冒泡
{
intb[3];//b[0]为冒泡的下界,b[2]为上界,b[1]无用
d=1;b[0]=0;b[2]=n-1;//d为冒泡方向的标识,1为向上,-1为向下
change=1;
while（b[0] {
change=0;
for（i=b[1-d];i!
=b[1+d];i+=d）//统一的冒泡算法
if（（a[i]-a[i+d]）*d>0）//注意这个交换条件
{
a[i]<->a[i+d];
change=1;
}
b[1+d]-=d;//
修改边界
d*=-1;//换个方向
}//while
}//Bubble_Sort3
10.29
voidOE_Sort（inta[],intn）//奇偶交换排序的算法
{
change=1;
while（change）
{
change=0;
for（i=1;i if（a[i]>a[i+1]）
{
a[i]<->a[i+1];
change=1;
}
for（i=0;i if（a[i]>a[i+1]）
{
a[i]<->a[i+1];
change=1;
}
}//while
}//
OE_Sort
分析:
本算法的结束条件是连续两趟比较无交换发生
10.30
typedefstruct{
intlow;
inthigh;
}boundary;//子序列的上下界类型
voidQSort_NotRecurve（intSQList&L）//快速排序的非递归算法
{
low=1;high=L.length;
InitStack（S）;//S的元素为boundary类型
while（lowStackEmpty（S））//注意排序结束的条件
{
if（high-low>2）//如果当前子序列长度大于3且尚未排好序
{
pivot=Partition（
L,low,high）;//进行一趟划分
if（high-pivot>pivot-low）
{
Push（S,{pivot+1,high}）;//把长的子序列边界入栈
high=pivot-1;//短的子序列留待下次排序
}
else
{
Push（S,{low,pivot-1}）;
low=pivot+1;
}
}//if
elseif（low {
Easy_Sort（L,low,high）;//直接进行比较排序
low=high;//当前子序列标志为已排好序
}
else//如果当前子序列已排好序但栈中还有未排序的子序列
{
Pop（S,a）;//从栈中取出一个子序列
low=a.low;
high=a.high;
}
}//while
}//
QSort_NotRecurve
intPartition（SQList&L,intlow,inthigh）//一趟划分的算法,与书上相同
{
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while（low {
while（low=pivotkey）
high--;
L.r[low]=L.r[high];
while（low low++;
L.r[high]=L.r[low];
}//while
L.r[low]=L.r[0];
returnlow;
}//Partition
voidEasy_Sort（SQList&L,intlow,inthigh）//对长度小于3的子序列进行比较排序
{
if（high-low==1）//子序列只含两个元素
if（L.r[low].key>L.r[high].key）L.r[low]<->L.r[high];
else//子序列含有三个元素
{
if（L.r[low].key>L.r[low+1].key）L.r[low]<->L.r[low+1];
if（L.r[low+1].key>L.r[high].key）L.r[low+1]<->L.r[high];
if（L.r[low].key>L.r[low+1].key）L.r[low]<->L.r[low+1];
}
}//Easy_Sort
10.31
voidDivide（inta[],intn）//把数组a中所有值为负的记录调到非负的记录之前
{
low=0;high=n-1;
while（low {
while（low=0）high--;//以0作为虚拟的枢轴记录
a[low]<->a[high];
while（low a[low]<->a[high];
}
}//Divide
10.32
typedefenum{RED,WHITE,BLUE}color;//三种颜色
voidFlag_Arrange（colora[],intn）//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列
{
i=0;j=0;k=n-1;
while（j<=k）
switch（a[j]）
{
caseRED:
a[i]<->a[j];
i++;
j++;
break;
caseWHITE:
j++;
break;
caseBLUE:
a[j]<->a[k];
k--;//
这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况
}
}//Flag_Arrange
分析:
这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.
10.33
voidLinkedList_Select_Sort（LinkedList&L）//单链表上的简单选择排序算法
{
for（p=L;p->next->next;p=p->next）
{
q=p->next;x=q->data;
for（r=q,s=q;r->next;r=r->next）//在q后面寻找元素值最小的结点
if（r->next->data {
x=r->next->data;
s=r;
}
if（s!
=q）//找到了值比q->data更小的最小结点s->next
{
p->next=s->next;s->next=q;
t=q->
next;q->next=p->next->next;
p->next->next=t;
}//交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
10.34
voidBuild_Heap（Heap&H,intn）//从低下标到高下标逐个插入建堆的算法
{
for（i=2;i {//此时从H.r[1]到H.r[i-1]已经是大顶堆
j=i;
while（j!
=1）//把H.r[i]插入
{
k=j/2;
if（H.r[j].key>H.r[k].key）
H.r[j]<->H.r[k];
j=k;
}
}//for
}//
Build_Heap
10.35
voidTriHeap_Sort（Heap&H）//利用三叉树形式的堆进行排序的算法
{
for（i=H.length/3;i>0;i--）
Heap_Adjust（H,i,H.length）;
for（i=H.length;i>1;i--）
{
H.r[1]<->H.r[i];
Heap_Adjust（H,1,i-1）;
}
}//TriHeap_Sort
voidHeap_Adjust（Heap&H,ints,intm）//顺序表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 if（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
voidMerge_Sort（inta[],intn）//归并排序的非递归算法
{
for（l=1;l for（i=0;（2*i-1）*l {
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
voidMerge（inta[],ints1,inte1,ints2,inte2）//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]
{
intb[MAXSIZE];//设立辅助存储数组b
for（i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++）
{
if（a[i] elseb[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
voidLinkedList_Merge_Sort1（LinkedList&L）//链表结构上的归并排序非递归算法
{
for（l=1;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
voidLinkedList_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->datadata）//选择关键字较小的那个结点接在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
voidLinkedList_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
voidLinkedList_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->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
voidSL_Merge（inta[],intl1,intl2）//把长度分别为l1,l2且l1^2<（l1+l2）的两个有序子序列归并为有序序列
{
start1=0;start2=l1;//分别表示序列1和序列2的剩余未归并部分的起始位置
for（i=0;i {
for（j=start2;j k=j-start2;//k为要向右循环移动的位数
RSh（a,start1,j-1,k）;//将a[start1]到a[j-1]之间的子序列
升级会员 