10.35.txt

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

void HeapSort(HeapType &h)
/* 元素比较和交换必须调用以下比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"  */
/* Status GT(RedType a, RedType b);   比较：">"  */
/* void Swap(RedType &a, RedType &b); 交换       */
{
    int i, j, k, max, s;                           //奇怪的比较次数！！
    RedType temp;
    if(h.length < 2) return;
    if(h.length == 2){        
        if(GT(h.r[1], h.r[2]))  Swap(h.r[1], h.r[2]);
        return;
    }        
    for(i = h.length/3; i > 0; i--){
        s = i;
        temp = h.r[s];
        for(j = 3*s - 1; j <= h.length; j = j*3 - 1){
            max = j;
            if( j+1 <= h.length && GT(h.r[j+1], h.r[max]) ) max = j+1;
            if( j+2 <= h.length && GT(h.r[j+2], h.r[max]) ) max = j+2;
            if(  GT(temp, h.r[max])) break;
            h.r[s] = h.r[max];
            j = max;
            s = j;
        }
        h.r[s] = temp;
    }
    for(i = h.length; i > 1; i--){
        Swap(h.r[1], h.r[i]);
        s = 1;
        temp = h.r[s];
        for(j = 3*s - 1; j <= i-1; j = j*3 - 1){
            max = j;
            if( j+1 <= i-1 && GT(h.r[j+1], h.r[max]) ) max = j+1;
            if( j+2 <= i-1 && GT(h.r[j+2], h.r[max]) ) max = j+2;
            if( GT(temp, h.r[max])) break;
            h.r[s] = h.r[max];
            j = max;
            s = j;
        }
        h.r[s] = temp;
    }
}