10.35(2).txt

数据结构实验 如下： Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */

void Adjust(HeapType &h, int s, int m);

void HeapSort(HeapType &h)
/* 元素比较和交换必须调用以下比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"  */
/* Status GT(RedType a, RedType b);   比较：">"  */
/* void Swap(RedType &a, RedType &b); 交换       */
{                                                         
    int i;
    for(i = h.length/3; i > 0; i--) 
        Adjust(h,i,h.length);
    for(i = h.length; i > 1; i--){
        Swap(h.r[1], h.r[i]);
        Adjust(h, 1, i-1);
    }
}

void Adjust(HeapType &h,int s,int m)
{
    RedType rc;
    int j;
    rc = h.r[s];
    for(j = 3*s - 1; j <= m; j = 3*j - 1){
        if(j < m && LT(h.r[j], h.r[j+1])){
            j++;
            if(j < m && LT(h.r[j], h.r[j+1]))
                j++;
        }
    else if(j < m - 1 && LT(h.r[j], h.r[j+2])) 
        j+=2;
    if(!LT(rc,h.r[j])) break;
    h.r[s] = h.r[j];
    s = j;
  }
  h.r[s] = rc;
}