精品文档
typedef struct {
ColorType r[MAX_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;j<=k;) {
c=f.r[j]; if(c==red)
swap(f.r[i++],f.r[j++]); if(c==white) j++;
if(c==blue)
swap(f.r[j],f.r[k--]); } }
10.34③ 已知(k1,k2,...,kp)是堆，则可以写一个时 间复杂度为O(log(n))的算法将(k1,k2,...,kp,kp+1) 调整为堆。试编写\从p=1起，逐个插入建堆\的算法， 并讨论由此方法建堆的时间复杂度。
实现下列函数：
void CreateHeap(HeapType &h, char *s);
堆（顺序表）的类型HeapType定义如下：
收集于网络，如有侵权请联系管理员删除
精品文档
typedef char KeyType;
typedef struct { KeyType key; ... ... } RedType;
typedef struct {
RedType r[MAXSIZE+1]; int length;
} SqList, HeapType;
void CreateHeap(HeapType &h, char *s) {
int i,j,locate,k; KeyType e; h.length=0;
for(i=0;s[i]!='\\0';i++) {
h.length++;
h.r[h.length].key=s[i]; e=h.r[h.length].key; locate=h.length; k=h.length/2;
for(j=h.length;k>0;j=j/2,k=j/2) {
if(e h.r[j].key=h.r[k].key; locate=k; } } h.r[locate].key=e; } } 10.35③ 假设定义堆为满足如下性质的完全三叉树： (1) 空树为堆； (2) 根结点的值不小于所有子树根的值，且所有子树 均为堆。 收集于网络，如有侵权请联系管理员删除 精品文档 编写利用上述定义的堆进行排序的算法，并分析推导 算法的时间复杂度。 实现下列函数： void HeapSort(HeapType &h); 堆（顺序表）的类型HeapType定义如下： typedef char KeyType; typedef struct { KeyType key; ... ... } RedType; typedef struct { RedType r[MAXSIZE+1]; int length; } SqList, HeapType; 比较函数和交换函数: Status LT(RedType a, RedType b) { return a.key { return a.key>b.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.r[s]; for(j=3*s-1;j<=m;j=3*j-1) { flag=0; printf(\ if(j 收集于网络，如有侵权请联系管理员删除 精品文档 H.r[s]=H.r[j]; s=j; } H.r[s]=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(\ for(i=(h.length+1)/3;i>0;i--) { HeapAdjust(h,i,h.length); printf(\ } for(i=h.length;i>1;i--) { Swap(h.r[1],h.r[i]); HeapAdjust(h,1,i-1); } } 10.42④ 序列的\中值记录\指的是：如果将此序列排序 后，它是第n/2个记录。试写一个求中值记录的算法。 实现下列函数： KeyType MidElement(SqList &L); 顺序表的类型SqList定义如下： typedef struct { KeyType key; ... } RedType; 收集于网络，如有侵权请联系管理员删除
