《数据结构作业系统_第十章答案》由会员分享，可在线阅读，更多相关《数据结构作业系统_第十章答案（8页珍藏版）》请在金锄头文库上搜索。
1、10.23 试以L.rk+1作为监视哨改写教材10.2.1节中给出的直接插入排序算法。其中，L.r1.k为待排序记录且k0;i-) L.rL.length+1=L.ri+1; if(GT(L.ri,L.ri+1) L.rL.length+1=L.ri; L.ri=L.ri+1; for(j=i+2;LT(L.rj,L.rL.length+1);j+) L.rj-1=L.rj; L.rj-1=L.rL.length+1; 10.26 如下所述改写教科书1.4.3节中的起泡排序算法：将算法中用以起控制作用的布尔变量change改为一个整型变量，指示每一趟排序中进行交换的最后一个记录的位置，并以它作
2、为下一趟起泡排序循环终止的控制值。实现下列函数：void BubbleSort(SqList &L);/* 元素比较和交换必须调用以下比较函数和交换函数：*/* Status LT(RedType a, RedType b); 比较： */* void Swap(RedType &a, RedType &b); 交换 */顺序表的类型SqList定义如下：typedef struct KeyType key; . RedType;typedef struct RedType rMAXSIZE+1; / r0闲置或用作哨兵单元 int length; SqList;比较函数和交换函数:Statu
3、s LT(RedType a, RedType b); / 比较函数：void Swap(RedType &a, RedType &b); / 交换函数void BubbleSort(SqList &L)/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/* Status LT(RedType a, RedType b); 比较： */* void Swap(RedType &a, RedType &b); 交换 */ int i,j,change=1; for(i=L.length;i1;i=change) change=1; for(j=1;ji;j+) if(GT(L.rj,L
4、.rj+1) Swap(L.rj,L.rj+1); change=j; 10.32 荷兰国旗问题：设有一个仅由红、白、兰这三种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、兰的顺序排好，即排成荷兰国旗图案。实现下列函数：void HFlag(FlagList &f)/* 荷兰国旗的元素为red，white和blue，*/* 分别用字符0,1和2表示 */荷兰国旗的顺序表的类型FlagList定义如下：#define red 0#define white 1#define blue 2typedef char ColorType;typedef struc
5、t ColorType rMAX_LENGTH+1; int length; FlagList;void swap(ColorType &a,ColorType &b) ColorType temp; temp=a; a=b; b=temp;void HFlag(FlagList &f) int i,j,k; char c; for(i=1,j=1,k=f.length;j0;j=j/2,k=j/2) if(eh.rk.key) h.rj.key=h.rk.key; locate=k; h.rlocate.key=e; 10.35 假设定义堆为满足如下性质的完全三叉树：(1) 空树为堆；(2)
6、 根结点的值不小于所有子树根的值，且所有子树 均为堆。编写利用上述定义的堆进行排序的算法，并分析推导算法的时间复杂度。实现下列函数：void HeapSort(HeapType &h);堆（顺序表）的类型HeapType定义如下：typedef char KeyType;typedef struct KeyType key; . . RedType;typedef struct RedType rMAXSIZE+1; int length; SqList, HeapType;比较函数和交换函数:Status LT(RedType a, RedType b) return a.keyb.key
7、? TRUE : FALSE; void Swap(RedType &a, RedType &b) RedType c; c=a; a=b; b=c; void HeapAdjust(HeapType &H,int s,int m) int j,flag; RedType rc; rc=H.rs; for(j=3*s-1;j=m;j=3*j-1) flag=0; printf(Do %dn ,j); if(jm<(H.rj,H.rj+1) j+;flag=1;printf(); if(flag)if(jm<(H.rj,H.rj+1) j+; else if(j+1m<(H.rj,H
8、.rj+2)j=j+2; if(!LT(rc,H.rj)break; H.rs=H.rj; s=j; H.rs=rc; void HeapSort(HeapType &h)/* 元素比较和交换必须调用以下比较函数和交换函数：*/* Status LT(RedType a, RedType b); 比较： */* void Swap(RedType &a, RedType &b); 交换 */ int i; /printf(%d,h.length); for(i=(h.length+1)/3;i0;i-) HeapAdjust(h,i,h.length); printf(%d,OK n,i); for(i=h.length;i1;i-) Swap(h.r1,h.ri); HeapAdjust(h,1,i-1); 10.42 序列的中值记录指的是：如果将此序列排序后，它是第n/2个记录。试写一个求中值记录的算法。实现下列函数：KeyType MidElement(SqList &L);顺序表的类型SqList定义如下：typedef struct KeyType key;
