数据结构作业系统答案

1、数据结构作业系统第十章答案标准化文件发布号：（9456EUATWKMWUBWUNNINNULDDQTYKII10.23试以L.rk+1作为监视哨改写教材10.2.1节 中给出的直接插入排序算法。其中，L.rl.k为待排 序记录且k<MAXSIZEo实现下列函数：void lnsertSort(SqList &L);顺序表的类型SqList定义如下：typedef struct KeyType key; RedType;typedef struct RedType rMAXSIZE+l; / r0闲置或用作哨兵单元int leng th; SqList;void lnsertSor

2、t(SqList &L)int i,j；for(i=L.length-l;i>0;i-)L.rL.length+l=L.ri+l;if(GT(L.ri,Lri+l)L.rL.length+l=L.ri;L.ri=L.ri+l; for(j=i+2;LT(L.rj,L.rL.length+l);j+)L.rU-l=L.rU；L.rj-l=L.rL.length+l;10.26如下所述改写教科书1.4.3节中的起泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型变 量，指示每一趟排序中进行交换的最后一个记录的位置，并 以它作为下一趟起泡排序循环终止的控制值。实现下

3、列函数：void BubbleSort(SqList &L);厂元素比较和交换必须调用以下比较函数和交换函数：*/* Status LT(RedType a, RedType b);比较："v” */* Status GT(RedType a, RedType b);比较:*/* void Swap(RedType &a, RedType &b);交换 */顺丿了表的类型SqList定义如下：typedef struct KeyType key; RedType;typedef struct RedType rMAXSIZE+l; / r0闲置或用作哨兵单元i

4、nt len gth; SqList;比较函数和交换函数：Status LT(RedType a, RedType b); / 比较函数Status GT(RedType a, RedType b); / 比较函数： Vvoid Swap(RedType &a, RedType &b); / 交换函数void BubbleSort(SqList &L)/*元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b);比较:,<H*/* Status GTfRedType a, RedType b);

5、比较:,>H*/* void Swap(RedType &a, RedType &b);交换*/int izjzchange=l;for(i=Len gth;i>l;i=cha nge)cha ng e=l;for(j=l;j<i;j+)if(GT(L.rU/L.rO+l)Swap(L.rj,L.rj+l)；cha ng e=j;10.32荷兰国旗问题：设有一个仅由红、白、兰 这三种颜色的条块组成的条块序列。请编写一个时 间复杂度为O(n)的算法，使得这些条块按红、白、 兰的顺序排好，即排成荷兰国旗图案。实现下列函数：void HFIag(FlagList &

6、amp;f)/*"荷兰国旗”的元素为red, white和blue, */*分别用字符0池和2表示*/”荷兰国旗“的顺序表的类型FlagList定义如下：#define red 'O1#define white '1'#define blue '2'typedef char ColorType;typedef struct ColorType rMAX_LENGTH+l;int len gth; FlagList;void swap(ColorType &a,ColorType &b)ColorType temp;temp=a;

7、a=b;b=temp;void HFIag(FlagList &f)int i jk;char c;for(i=l,j=l,k=f.length;j<=k;)c=f.rj;讦(c=red)swap(f.ri+,f.rj+)；讦(c=white)j+;讦(c=blue)swap(f.rj,f.rk-);10.34® B知(kl,k2,.,kp)是堆，则可以写一个时 间复杂度为O(log(n)的算法将(kl,k2,.,kp,kp+l) 调整为堆。试编写“从p“起，逐个插入建堆“的算法, 并讨论由此方法建堆的时间复杂度。实现下列函数：void CreateHeap(HeapT

8、ype &h, char *s);堆（顺序表）的类型HeapType定义如下:typedef char KeyType;typedef struct KeyType key; RedType;typedef struct RedType rMAXSIZE+l;intlen gth; SqList, HeapType;void CreateHeap(HeapType &h, char *s)int i jlocatek;KeyType e;hen gth=O;for(i=0;si!=,0,;i+)heng th+;h.rhen gth.key=si;e=h.rhen gthj.k

9、ey;locate=hen gth;k=h.length/2;for(j=h.length;k>0;j=j/2,k=j/2)if(e<h.rk.key)h.rj.key=h.rk.key;locate=k;h.rlocate.key=e;10.35 假设定义堆为满足如下性质的完全三义树:空树为堆；根结点的值不小于所有子树根的值，且所有子树 均为堆。编写利用上述定义的堆进行排序的算法，并分析推导 算法的时间复杂度。实现下列函数：void HeapSort(HeapType &h);堆(顺序表)的类型HeapType定义如下：typedef char KeyType;typed

10、ef struct KeyType key; RedType;typedef struct RedType rMAXSIZE+l;int len gth;SqList, HeapType;比较函数和交换函数：Status LT(RedType a, RedType b) return a.key<b.key TRUE : FALSE;Status GT(RedType a, RedType b) return a.key>b.key TRUE : FALSE;void Swap(RedType &a, RedType &b) RedType c; c=a; a=b;

11、 b=c;void HeapAdjustfHeapType &Hnt sint m)int j,flag;RedType rc;rc=H.rs;for(j=3*s-l;j<=m;j=3*j-l)flag=O; printf(HDo %dn "J);&&LT(H.rj,H.rj+l)j+;flag“;printf(”“); if(flag)if(j <m&&LT(H.rULH.rU+l)j+; else if(j+l<m&&LT(H.rj,H.rj+2)j=j+2; if(!LT(rc?H.rj)break;H.

12、rs=H.rj;S=j；H.rs=rc;void HeapSort(HeapType &h)/*元素比较和交换必须调用以下比较函数和交换函数:/* Status LT(RedType a, RedType b);比较：*/* Status GT(RedType a, RedType b);比较：*/* void Swap(RedType &a, RedType &b);交换 */int i;/printf("%d"zh.length);for(i=(h.length+l)/3;i>0;i-)HeapAdjust(h,i,hength);prin

13、tf("%dzOK n",i);for(i=hength;i>l;iTSwap(h.rl,h.ri);HeapAdjust(h,l/i-l);10.42序列的呻值记剥指的是:如果将此序列排序 后，它是第n/2个记录。试写一个求中值记录的算法。实现下列函数：KeyType MidElement(SqList &L);顺序表的类型SqList定义如下:typedef struct KeyType key; RedType;typedef struct RedType rMAXSIZE+l; / r0闲置或用作哨兵单元 int len gth; SqList;Key

14、Type MidElement(SqList &L)int i,j,k,n;RedType temp;讦(L.length=O)return '#*;for(i=l;i<Len gth;i+)k=i;temp=L.ri;for(j=i+l;j<=Length;j+)if (temp.key>L.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+l;return L.rn.key;10.43已知记录序列al.n中的关

15、键字各不相同， 可按如下所述实现计数排序：另设数组cl.n,对每 个记录ai,统计序列中关键字比它小的记录个数存 于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+l; / r0闲置或用作哨兵单元int len gth; SqList;void CountSort(SqList &L)厂采用顺序表存储结构，L存储序列a, L.length为n穴