数据结构作业系统_第
十章答案
精品文档
10.23② 试以L.r[k+1]作为监视哨改写教材10.2.1节 中给出的直接插入排序算法。其中，L.r[1..k]为待排 序记录且k 实现下列函数： void InsertSort(SqList &L); 顺序表的类型SqList定义如下： typedef struct { KeyType key; ... } RedType; typedef struct { RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList; void InsertSort(SqList &L) { int i,j; for(i=L.length-1;i>0;i--) { L.r[L.length+1]=L.r[i+1]; if(GT(L.r[i],L.r[i+1])) { L.r[L.length+1]=L.r[i]; L.r[i]=L.r[i+1]; } for(j=i+2;LT(L.r[j],L.r[L.length+1]);j++) L.r[j-1]=L.r[j]; L.r[j-1]=L.r[L.length+1]; } } 10.26② 如下所述改写教科书1.4.3节中的起泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型变 收集于网络，如有侵权请联系管理员删除 精品文档 量，指示每一趟排序中进行交换的最后一个记录的位置，并 以它作为下一趟起泡排序循环终止的控制值。 实现下列函数： void BubbleSort(SqList &L); /* 元素比较和交换必须调用以下比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\/* Status GT(RedType a, RedType b); 比较：\/* void Swap(RedType &a, RedType &b); 交换 */ 顺序表的类型SqList定义如下： typedef struct { KeyType key; ... } RedType; typedef struct { RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList; 比较函数和交换函数: Status LT(RedType a, RedType b); // 比较函数：\Status GT(RedType a, RedType b); // 比较函数：\void Swap(RedType &a, RedType &b); // 交换函数 void BubbleSort(SqList &L) /* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\ 收集于网络，如有侵权请联系管理员删除 精品文档 /* Status GT(RedType a, RedType b); 比较：\/* void Swap(RedType &a, RedType &b); 交换 */ { int i,j,change=1; for(i=L.length;i>1;i=change) { change=1; for(j=1;j if(GT(L.r[j],L.r[j+1])) { Swap(L.r[j],L.r[j+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 '2' typedef char ColorType; 收集于网络，如有侵权请联系管理员删除
