数据结构作业系统_第十章答案.docVIP

10.23② 试以L.r[k+1]作为监视哨改写教材10.2.1节 中给出的直接插入排序算法。其中，L.r[1..k]为待排 序记录且kMAXSIZE。 实现下列函数： 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;i0;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;i1;i=change) { change=1; for(j=1;ji;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; typedef struct { ColorType r[MAX_LENGTH+1]; int