09.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

///////////////////////////////////////////////////////////////////
//9.3有序字典---9.3.3用二叉搜索树实现有序字典
///////////////////////////////////////////////////////////////////

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

template<class T>
class BinaryTreeNode
{
	public:
		BinaryTreeNode() { LeftChild=RightChild=Parent=0;bal=LeafBal();}
		BinaryTreeNode(const T& e)
		{ data=e;LeftChild=RightChild=Parent=0;bal=LeafBal();}
		BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r,BinaryTreeNode *p)
		{ data=e;LeftChild=l;RightChild=r;Parent=p;bal=LeafBal();}
		T GetData();
		BinaryTreeNode<T> *Left() const;
		BinaryTreeNode<T> *Right() const;
		BinaryTreeNode<T> *Par() const;
		BinaryTreeNode<T> * &Child(int dir);
		int GetBalance();
		void SetBalance(int b);
		virtual int LeafBal(){return 0;}

	private:
		T data;
		int bal;
		BinaryTreeNode<T> *LeftChild,
			              *RightChild,
						  *Parent;
};
template<class T>
T BinaryTreeNode<T>::GetData()
{
	return data;
}
template<class T>
BinaryTreeNode<T> *BinaryTreeNode<T>::Left() const
{
	return LeftChild;
}
template<class T>
BinaryTreeNode<T> *BinaryTreeNode<T>::Right() const
{
	return RightChild;
}
template<class T>
BinaryTreeNode<T> *BinaryTreeNode<T>::Par() const
{
	return Parent;
}
template<class T>
BinaryTreeNode<T> * &BinaryTreeNode<T>::Child(int dir)
{
	if(dir==0)return LeftChild;
	else return RightChild;
}
template<class T>
int BinaryTreeNode<T>::GetBalance()
{
	return bal;
}
template<class T>
void BinaryTreeNode<T>::SetBalance(int b)
{
	bal=b;
}



template<class T>
class BinaryTree
{
	public:
		BinaryTreeNode<T>* Search(const T&x)const;
		BinaryTreeNode<T>* Insert(const T&x);
		BinaryTreeNode<T>* Delete(const T&x);
		bool Member(const T&x) {return Search(x);}

		BinaryTreeNode<T>* &GetRoot();
		void Rotation(BinaryTreeNode<T>* &p,BinaryTreeNode<T>* &q,int dir);
		void DoubleRotation(BinaryTreeNode<T> &p,BinaryTreeNode<T>* &q,BinaryTreeNode<T>* &r,int dir)
		virtual void InsertRebal(BinaryTreeNode<T>* ) {}
		virtual void DeleteRebal(BinaryTreeNode<T>* ,BinaryTreeNode<T>* ) {}
};

template<class T>
BinaryTreeNode<T> * & BSTree<T>::GetRoot()
{
	return root;
}
template<class T>
BinaryTreeNode<T> * BSTree<T>::Search(const T&x)const
{
	BinaryTreeNode<T> *p=root;
	while(p)
	{
		if(x<p->data) p=p->LeftChild;
		else if(x>p->data) p=p->RightChild;
		else break;
	}
	return p;
}
template<class T>
BinaryTreeNode<T> * BSTree<T>::Insert(const T&x)
{//插入运算
	BinaryTreeNode<T> *p=root,
					 *pp=0;
	while(p)
	{//考察当前结点中存储的元素p->data
		pp=p;
		//选择搜索子树
		if(x<p->data) p=p->LeftChild;
		else if(x>p->data) p=p->RightChild;
		else return 0;
	}
	//新结点
	BinaryTreeNode<T> *r=new BinaryTreeNode<T> (x);
	if(root)
	{
		if(x<pp->data) pp->LeftChild=r;
		else pp->RightChild=r;
		r->Parent=pp;
//		InsertRebal(r);//重新平衡
	}
	else root=r;
	return r;
}
template<class T>
BinaryTreeNode<T> * BSTree<T>::Delete(const T&x)
{//删除运算
	BinaryTreeNode<T> *p=root,//当前结点指针
					 *pp=0;//p的父结点指针
	while(p&&p->data!=x)
	{//搜索删除结点
		pp=p;
		if(x<p->data) p=p->LeftChild;
		else if(x>p->data) p=p->RightChild;
	}
	if(!p) return 0;
	if(p->LeftChild&&p->RightChild)
	{//P有两个儿子结点
		//搜索P的左子树中的最大元素
		BinaryTreeNode<T> *s=p->LeftChild,
					     *ps=p;
		while(s->RightChild)
		{
			ps=s;
			s=s->RightChild;
		}
		//用S中的元素替换P中的元素
		p->data=s->data;
		p=s;
		pp=ps;
	}
	//P最多只有一个儿子结点
	BinaryTreeNode<T> *c;
	if(p->LeftChild) c=p->LeftChild;
	else c=p->RightChild;
	//删除结点P
	if(p==root)
	{
		root=c;
		if(c) c->Parent=0;
	}
	else 
	{//确定P 是其父结点的左儿子结点还是右儿子结点
		if(p==pp->LeftChild)
		{
			pp->LeftChild=c;
			p->LeftChild=p;//这步为重新平衡作准备
		}
		else pp->RightChild=c;
		if(c) c->Parent=p->Parent;
	}
//	DeleteRebal(c,p);//重新平衡
	delete p;
	return c;
}







		
/*template<class T>
inline void BinaryTree<T>::Rotation(BinaryTreeNode<T>* &p,
								BinaryTreeNode<T>* &q,int dir)
{
	BinaryTreeNode<T>* r=q->Child(1-dir);
	BinaryTreeNode<T>* x=p->Parent;
	p->Child(dir)=r;
	q->Child(1-dir)=p;
	p->Parent=q;
	if(r) r->Parent=p;
	if(!x) root=q;
	else if(p==x->LeftChild) x->LeftChild=q;
	    else x->RightChild=q;
	q->Parent=x;
}*/
/////////////////////////////////////////////////////////////////
//优先队列9.4.4用数组实现堆
////////////////////////////////////////////////////////////////
template<class T>
class MinHeap
{
	public:
		MinHeap(int MinHeapSize);
		~MinHeap() {delete[]heap;}
		int Size() const {return Last;}
		T Min() { return heap[1];}
		MinHeap<T> & Insert(const T& x);
		MinHeap<T> & DeleteMin(T & x);
		void Initialize(T a[],int size,int ArraySize);
		void Deactivate() {heap=0;}
	private:
		int Last,MaxSize;
		T *heap;
};
template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{
	MaxSize=MinHeapSize;
	heap=new T[MaxSize+1];
	Last=0;
}
template<class T>
MinHeap<T> & MinHeap<T>::Insert(const T& x)
{
	int i=++Last;
	while(i!=1 && x<heap[i/2])
	{
		heap[i]=heap[i/2];
		i/=2;
	}
	heap[i]=x;
	return *this;
}
template<class T>
MinHeap<T> & MinHeap<T>::DeleteMin(T & x)
{
	x=heap[1];
	T y=heap[Last--];
	int i=1,
		ci=2;
	while(ci<=Last)
	{
		if(ci<Last && heap[ci]>heap[ci+1]) ci++;
		if(y<=heap[ci]) break;
		heap[i]=heap[ci];
		i=ci;
		ci*=2;
	}
	heap[i]=y;
	return *this;
}
template<class T>
void MinHeap<T>::Initialize(T a[],int size,int ArraySize)
{
	delete [] heap;
	heap=a;
	Last=size;
	MaxSize=ArraySize;
	for(int i=Last/2;i>=1;i--)
	{
		T y=heap[i];
		int c=2*i;
		while(c<=Last)
		{
			if(c<Last && heap[c]>heap[c+1]) c++;
			if(y<=heap[c]) break;
			heap[c/2]=heap[c];
			c*=2;
		}
		heap[c/2]=y;
	}
}


/*template<class T>
void HeapSort(T a[],int n)
{
	MinHeap<T> H(1);
	H.Initialize(a,n,n);
	T x;
	for(int i=n-1;i>=1;i--)
	{
		H.DeleteMin(x);
		a[i+1]=x;
	}
	H.Dectivate();
}*/
/////////////////////////////////////////////////////
//9.5.2用父亲数组实现并查集
///////////////////////////////////////////////////////
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
//#include"time.h"
//clock_t start,finish;

class UnionFind
{
public:
	UnionFind(int n);

	~UnionFind() {delete [] parent;delete [] root;}
	int Find(int e);
	void Union(int i,int j);
	bool *root;
//private:
	int *parent;
	
};

UnionFind::UnionFind(int n)
{
	root=new bool[n+1];
	parent=new int[n+1];
	for(int e=1;e<=n;e++)
	{
		parent[e]=1;
		root[e]=true;
	}
}
int UnionFind::Find(int e)
{
	int j=e;
	while(!root[j]) j=parent[j];
	int f=e;
	while(f!=j)
	{
		int pf=parent[f];
		parent[f]=j;
		f=pf;
	}
	return j;
}
void UnionFind::Union(int i,int j)
{
	if(parent[i]<parent[j])
	{
			parent[j]+=parent[i];
			root[i]=false;
			parent[i]=j;		
	}
	else 
	{
			parent[i]+=parent[j];
			root[j]=false;
			parent[j]=i;		
	}
}
int main()
{
//	start=clock();
	ifstream in("input.txt");
	if(in.fail())
	{
		out<<"the input.txt is not exist";
		exit(1);
	}
	ofstream out("output.txt");


//	finish=clock();
//	cout<<finish-start;
	return 0;
}