jbs.h

数据结构程序设计21

#ifndef JBS
#define JBS
#include<iostream.h>
#include<fstream.h>
#include<iomanip>
#include<conio.h>
#include<string>
#include"FullBinaryTree.h"
#define N 10
ofstream out1("锦标赛排序.txt");
const int MAXNUM=1000000;
template<class Type> class DataNode
{
	public:
	Type data;                           //数据值
	int index;                            //树中的结点号，即在完全二叉树顺序存储中的下标
	int active;                          //是否参选的标志，=1,参选；=0，不再参选
	DataNode()
	{
		data=MAXNUM;
		active=0;
	}
};

int PowerOfTow(int n,int i=0)                    
{
		int a=pow(2,i);
		if(n>a)
			return PowerOfTow(n,++i);
		else
		return a;
}

template<class Type> 
void print(DataNode<Type>*tree,int n)
{
	int ts=2*PowerOfTow(n)-1;
	FullBinaryTree<Type> fullTree;
	for(int i=0;i<ts;i++)
	{
		if(tree[i].data!=MAXNUM && tree[i].active!=0)
			fullTree.Insert(tree[i].data);
		else
		{
			Type e;
			fullTree.Insert(e);
		}
	}
	fullTree.print(cout);
	fullTree.print(out1);
}
template<class Type>
void printAsLine(DataNode<Type> *tree,int n)
{
	int num=2*PowerOfTow(n)-1;
	int height=0;
	for(int i=0;i<num;i++)
	{
		if(tree[i].data!=MAXNUM && tree[i].active!=0)
		{	cout<<tree[i].data<<"\t";
		    out1<<tree[i].data<<"\t";}
		if((i+1)==2*pow(2,height)-1)
		{
			height++;
			cout<<endl;
			out1<<endl;
		}
	}
	cout<<endl;
	out1<<endl;
}

template <class Type> void TournamentSort(Type a[],int n,bool out)
{
	DataNode <Type> *tree;
	int bottomRowSize=PowerOfTow(n);

	int TreeSize=2*bottomRowSize-1;
	int loadindex=bottomRowSize-1;
	tree=new DataNode<Type>[TreeSize];
	int j=0;
	for(int i=loadindex;i<TreeSize;i++)
	{
		tree[i].index=i;
		if(j<n)
		{
			tree[i].active=1;
			tree[i].data=a[j++];
		}
		else
		{
			tree[i].active=0;
		}
	}
	i=loadindex;
	while(i)
	{
		j=i;
		while(j<2*i)
		{
			if(!tree[j+1].active||tree[j].data<=tree[j+1].data)
				tree[(j-1)/2]=tree[j];
			else
				tree[(j-1)/2]=tree[j+1];
			j+=2;
		}
		i=(i-1)/2;
	}
	for(i=0;i<n;i++)
	{		
		if(out)
		{
			if(i==0)
			{cout<<"初始胜者树为："<<endl;
			 out1<<"初始胜者树为："<<endl;}
			else
			{cout<<"取出一个数后的结果为："<<endl;
			 out1<<"取出一个数后的结果为："<<endl;}
			if(n<=8)
			print(tree,n);
			else
			printAsLine(tree,n);
		}
		a[i]=tree[0].data;
		if(i==n-1)
			a[n-1]=tree[0].data;
		tree[0].data=MAXNUM;
		tree[tree[0].index].active=0;
		UpdateTree(tree,tree[0].index);

	}
  
	   delete []tree;
}


template <class Type> void UpdateTree(DataNode<Type> *tree,int i)
//锦标赛排序中的调整算法：i是表中当前最小元素的下标，即胜者。从它开始向上调整。
{
	if(i%2==0)                             //i为偶数，对手为左结点
		tree[(i-1)/2]=tree[i-1];
	else
		tree[(i-1)/2]=tree[i+1];         //i为奇数，对手为右结点

	i=(i-1)/2;                             //i上升到双亲结点位置
	int j;

	while(i)
	{
		if(i%2==0)                      //确定i的对手是左结点还是右结点
			j=i-1;
		else 
			j=i+1;
		if(!tree[i].active||!tree[j].active) //比赛对手中间有个空
		{
			if(tree[i].active)               //非空者上升到双亲结点
				tree[(i-1)/2]=tree[i];
			else
				tree[(i-1)/2]=tree[j];
		}
		else                                   //比赛对手都不为空
		{
			if(tree[i].data<tree[j].data)
				tree[(i-1)/2]=tree[i];
			else                               //胜者上升到双亲结点
				tree[(i-1)/2]=tree[j];			
		}
		i=(i-1)/2;                             //i上升到双亲结点
	}
}


template<class Type>
void printResult(Type a[],int n)
{
	cout<<"结果为："<<endl;
	for(int i=0;i<n;i++)
		cout<<a[i]<<'\t';
	cout<<endl;
}

#endif