winnertree.cpp

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#include "WinnerTree.h"
template <class T>
bool WinnerTree<T>::Initial(T a[], int size
         /*int(*algor)(int a, int b)*/) {
//a[]是胜者树选手数组, size是选手数,函数Winner
//用于得到两选手a, b比赛的胜者
    if (size > maxSize || size < 2) return false;
	
    n = size;  e = a;

	cout << "初始化数组e：" << endl;
	for(int i = 1; i <= n; i ++) cout << i << ": " << e[i] << endl;

    int i, s;
    for (s = 1; 2*s <= n-1; s += s);  //计算s=2^log2(n-1)
    lowExt = 2*(n-s);  offset = 2*s-1;
    for (i = 2; i <= lowExt; i += 2)   //最远层外结点比赛
		Play ((offset+i)/2, i-1, i);
		    //选手i-1和i比赛, 胜者升入双亲(offset+i)/2
    if (n%2 == 0) i = lowExt+2;    //次远层外结点比赛
    else {           //当n为奇数时,内结点要与外结点比赛
        Play (n/2, t[n-1], lowExt+1);
		i = lowExt+3;		//i再进到次远层其他外结点
    }					
    for ( ; i <= n; i += 2)	//其他次远层外结点比赛
        Play((i-lowExt+n-1)/2, i-1, i); 
	cout << "初始化数组t：" << endl;
	for(int i = 1; i < n; i ++) cout << i << ": " << t[i] << endl;
    return true;
}

template <class T>
void WinnerTree<T>::Play (int k, int lc, int rc 
        /*int (*algor)(int a, int b)*/) {
//通过比赛对树初始化。在t[k]处开始比赛, lc和rc是
//t[k]的左子女和右子女。
    t[k] = Winner (lc, rc);	//在e[lc]和e[rc]间选出胜者
    while (k > 1 && k % 2 != 0) {
 		                               //从右子女向上比赛, 直到根
        t[k/2] = Winner(t[k-1], t[k]);
        k /= 2;			//到双亲结点
    }
} 

template <class T>
bool WinnerTree<T>::
rePlay (int i) {
//针对元素i值的改变,重新组织胜者树。
	if (i <= 0 || i > n) return false;
    int k, lc, rc;		  //比赛结点及其左右子女
    if (i <= lowExt) {	  //最远层外结点
        k = (offset+i)/2;	  //计算 i 的双亲
        lc = 2*k-offset;  rc = lc+1;       //计算左右子女
    }
    else {			  //次远层外结点
        k = (i-lowExt+n-1)/2;
        if (2*k == n-1) { lc = t[2*k];  rc = i; }
        else { lc = 2*k-n+1+lowExt;  rc = lc+1; }
    }
	
	//cout << "i: " << i << " k: " << k << " lc: " << lc << " rc: " << rc << endl; 
	t[k] = Winner(lc, rc);
	//cout << "t[" << k << "]: " << t[k] << " e[" << lc << "]: " << e[lc] << " e[" << rc << "]: " << e[rc] << endl;
	k /= 2;
    for ( ; k >= 1; k /= 2)		//逐层向上比赛直到根
	{
		if(2 * k + 1 >= n) t[k] = Winner(t[2*k], lowExt + 1);
		else t[k] = Winner(t[2*k], t[2*k+1]);
	    //cout << "t[" << k << "]=" << " " << t[k] << ";t[" << 2*k << "]=" << t[2*k] << ";t[" << 2*k+1 << "]=" << t[2*k+1] << endl; 
	}
	return true;
}

template <class T> 
void TournamentSort (T a[], 
          int size) {
//建立树的顺序存储数组tree, 将数组a[ ]中的元素复
//复制到胜者树中, 对它们进行排序, 并把结果返送
//回数组中, left 和right是排序元素的起点和终点。
	WinnerTree<T> WT(size);	      //胜者树对象
	T* data= new T[size+1];			      //存储输入数据
	int i;
	for (i = 1; i <= size; i++) cin >> data[i];	
	WT.Initial (data, size);   //构造初始胜者树
	for (i = 0; i < size; i++) {
        a[i] = WT.Winner();	      //输出胜者
        WT.Update ();		      //修改胜者的值    
		WT.rePlay (WT.Winner(1));	      //重构胜者树
        if (WT.Winner() == maxValue) break;
	}
}