jbs.h.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > asd.rar > JBS.H


#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 &amt;&amt; 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 &amt;&amt; 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