program.cpp

用三种方式实现find()操作

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct Node 
{
	int father;
	int count;
	int weight;
	Node(int i):father(i),count(1),weight(0){};
};
//////////////////////////////////////////////
// 找到序号i对应的根结点的序号				//
//////////////////////////////////////////////		
int Find_Root(const vector<Node>&Vec,int i)
{
	Node curNode=Vec.at(i);
	while (i!=curNode.father)
	{
		i=curNode.father;
		curNode=Vec.at(curNode.father);
	}
	return i;
	
}
//////////////////////////////////////
//		用递归进行路径压缩			//
//////////////////////////////////////
int Find(vector<Node>&Vec,int i,int &w)
{
	Node &curNode=Vec.at(i);
	int father_new_weight=0;
	if (i!=curNode.father)
	{
		curNode.father=Find(Vec,curNode.father,father_new_weight);
		curNode.weight=curNode.weight+father_new_weight;
		w=curNode.weight;
	}
	else
	{
		w=0;
	}
	return curNode.father;
}
//////////////////////////////////////
//		用栈进行路径压缩			//
//////////////////////////////////////
int Find_Stack(vector<Node>&Vec,int i)
{
	stack<int> Stack;
	int root=0;
	Node curNode=Vec.at(i);
	while (i!=curNode.father)
	{
		Stack.push(i);
		i=curNode.father;
		curNode=Vec.at(i);
	
	}
	if (Stack.size()!=0)
	{
		root=Vec.at(Stack.top()).father;
		int cur=0;
		while (Stack.size()!=0)
		{
			cur=Stack.top();
			Stack.pop();
			Node &thisNode=Vec.at(cur);
			if (thisNode.father==root)
			{
				continue;
			}
			else
			{
				thisNode.weight+=Vec.at(thisNode.father).weight;
				thisNode.father=root;
			}
		}
	}
	return root;
}
//////////////////////////////////////
//		仅用while进行路径压缩		//
//////////////////////////////////////
int Find_While(vector<Node>&Vec,int i)
{
	int root=Find_Root(Vec,i);
	int cur=0;
	const Node &rootNode=Vec.at(root);
	while (i!=root)
	{
		Node&thisNode=Vec.at(i);
		cur=thisNode.father;
		i=thisNode.father;
		thisNode.father=root;
		while(i!=root)
		{
			const Node& curNode=Vec.at(i);
			i=curNode.father;
			thisNode.weight+=curNode.weight;
		}
		i=cur;
	}
	return root;
} 
//////////////////////////////////////
//		找到i在对应树中的深度		//
//////////////////////////////////////
int Find_Depth(vector<Node>&Vec,int i,int num)
{
	Node &curNode=Vec.at(i);
	if (i==curNode.father)
	{
		return curNode.weight;
	}
	else
	{
		int root=0;
		switch(num)
		{
		case 1:
			{
				int father_new_weight=0;
				root=Find(Vec,i,father_new_weight);
				break;
			}
		case 2:
			{
				root=Find_Stack(Vec,i);
				break;
			}
		case 3:
			{
				root=Find_While(Vec,i);
				break;
			}
		default :
			{
				 root=0;
				break;
			}
		}
		return curNode.weight+Vec.at(root).weight;
	}
}
//////////////////////////////////////
//		实现两棵树的合并			//
//////////////////////////////////////
void Link(vector<Node>&Vec,int v,int r,int num)
{
	int Root_V=Find_Root(Vec,v);
	int Root_R=Find_Root(Vec,r);
	Node&Root_V_Node=Vec.at(Root_V);
	Node&Root_R_Node=Vec.at(Root_R);
	if (Root_R_Node.count<=Root_V_Node.count)
	{
		Root_R_Node.weight=Find_Depth(Vec,v,num)+1-Root_V_Node.weight+Root_R_Node.weight;
		Root_V_Node.count+=Root_R_Node.count;
		Root_R_Node.father=Root_V;
	}
	else
	{
		Root_R_Node.weight=Find_Depth(Vec,v,num)+1+Root_R_Node.weight;
		Root_V_Node.weight=Root_V_Node.weight-Root_R_Node.weight;
		Root_V_Node.father=Root_R;
		Root_R_Node.count+=Root_V_Node.count;
	}
}
void Do_Work(vector<Node>&Vec,int num)
{
	Link(Vec,2,1,num);
	Link(Vec,3,2,num);
	Link(Vec,5,4,num);
	Link(Vec,4,3,num);
	Link(Vec,7,6,num);
	Link(Vec,9,8,num);
	Link(Vec,8,7,num);
	Find_Depth(Vec,6,num);
	Link(Vec,6,5,num);
/*	Find_Depth(Vec,6,num);*/
	Find_Depth(Vec,4,num);
	Find_Depth(Vec,7,num);
/*	Find_Depth(Vec,8,num);*/
	for (int i=1;i<=Vec.size()-1;i++)
	{
		Node&curNode=Vec.at(i);
		cout<<"Node="<<i<<"\tfather="<<curNode.father<<"\tcount="<<curNode.count<<"\t"<<"weight="<<curNode.weight<<endl;
	}
}
///////////////////////////////
//		主程序入口			 //
///////////////////////////////
void main()
{
	vector<Node> Vec;
	char c;
	int num=0;
	do 
	{
		for (int i=0;i<=9;i++)
		{
			Vec.push_back(Node(i));
		}
		cout<<"***************************************"<<endl;
		cout<<"**           1.递归实现Find          **"<<endl;
		cout<<"**           2.栈实现Find            **"<<endl;
		cout<<"**           3.仅用While实现Find     **"<<endl;
		cout<<"**           4.退出                  **"<<endl;
		cout<<"***************************************"<<endl;
		cout<<"请选择(1-4):";
		cin>>c;
		num=c-48;
		switch(num)
		{
		case 1:
		case 2:
		case 3:
			{
				Do_Work(Vec,num);
				Vec.clear();
				break;
			}
		case 4:break;
		default:
			{
				cout<<"选择的数字不在范围内!!!请重新输入"<<endl;
				Vec.clear();
				break;
			}
		}
	} while(num!=4);
}