《数据结构作业系统_第十章答案(7页).doc》由会员分享，可在线阅读，更多相关《数据结构作业系统_第十章答案(7页).doc（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-数据结构作业系统_第十章答案-第 7 页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; SqLi
3、st;比较函数和交换函数:Status 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;j
4、i;j+) if(GT(L.rj,L.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 ColorT
5、ype;typedef struct 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 假设定义堆为满足如下性质的完全
6、三叉树：(1) 空树为堆；(2) 根结点的值不小于所有子树根的值，且所有子树 均为堆。编写利用上述定义的堆进行排序的算法，并分析推导算法的时间复杂度。实现下列函数：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
7、 a.keyb.key ? 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+
8、1m<(H.rj,H.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(
9、%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; RedType;typedef struct RedType rMAXSIZE+1; / r0闲置或用作哨兵单元 int length; SqList;KeyType MidElement(Sq
10、List &L) int i,j,k,n; RedType temp; if(L.length=0)return #; for(i=1;iL.length;i+) k=i; temp=L.ri; for(j=i+1;jL.rj.key) temp=L.rj; k=j; temp=L.ri; L.ri=L.rk; L.rk=temp; if(L.length%2=0)n=L.length/2; else n=L.length/2+1; return L.rn.key;10.43 已知记录序列a1.n 中的关键字各不相同，可按如下所述实现计数排序：另设数组c1.n，对每个记录ai， 统计序列中关键
11、字比它小的记录个数存于ci， 则ci=0的记录必为关键字最小的记录，然后依ci值的大小对a中记录进行重新排列，试编写算法实现上述排序方法。实现下列函数：void CountSort(SqList &L);/* 采用顺序表存储结构，L.r存储序列a，L.length为n */* 在函数内自行定义计数数组c */顺序表的类型SqList定义如下：typedef struct KeyType key; RedType;typedef struct RedType rMAXSIZE+1; / r0闲置或用作哨兵单元 int length; SqList;void CountSort(SqList &L)/* 采用顺序表存储结构，L.r存储序列a，L.length为n */* 在函数内自行定义计数数组c */ int i,j,count; int c100; SqList s; for(i=1;i=L.length;i+) count=0; for(j=1;jL.rj.key) count+; ci-1=count; for(i=1;i=L.length;i+) s.ri=L.ri; s.length=L.length; for(i=0;iL.length;i+) L.rci+1=s.ri+1;