tele.cpp

本为电话号码查询系统

// tele.cpp : 定义控制台应用程序的入口点。
	//

	#include "stdafx.h"
	//2008.1.10打完书上代码
	//08.1.11完成插入
	//08.1.12完成查找2.18 开始不能返回avlnode类型，将avlnode声明拿到avltree声明外面即可
	//08.1.13完成外存文件读入+修改（待改）
    //08.1.14完成修改2.18
    //08.2.18完成删除//思想：与insert成镜面效应 在深刻理解insert基础上
    //08.2.18晚 完成求高度Height函数
	//[e-mail]
	//11106207 luoxiaoming
	#include<iostream>
	#include<string>
	#include<fstream>
	using namespace std;
	void Menu();
	void Welcome();
	////////////////////////////////////////////////////////
	class AVLTree;
	struct TeleNumber
	{
	friend class AVLTree;
	string name;//姓名
	string phoneNumber;//固定电话号码
	string mobileNumber;//移动电话号码
	string email;//电子邮箱
	} ;
	struct AVLNode//AVL树结点的类定义
	{
		friend AVLTree;
		TeleNumber data;
		AVLNode *left,*right;
		int balance;
		AVLNode():left(NULL),right(NULL),balance(0){}
		AVLNode(TeleNumber d,AVLNode *l=NULL,AVLNode *r=NULL):
		data(d),left(l),right(r),balance(0){}
	};
	class AVLTree
	{
	public:	
		protected:
			//TeleNumber RefValue;//插入结束标志			
			int Insert(AVLNode* &Tree,TeleNumber &x,int &taller);//插入//
			AVLNode *Search(AVLNode* &Tree,TeleNumber &x);
			int Remove(AVLNode* &Tree,TeleNumber &x,int &shorter);//删除
			void RotateLeft(AVLNode *Tree,AVLNode* &NewTree);//左单旋转
			void RotateRight(AVLNode *Tree,AVLNode* &NewTree);//右单旋转
			void LeftBalance(AVLNode* &Tree,int &taller);//左平衡化
			void RightBalance(AVLNode* &Tree,int &taller);//右平衡化
			int Height(AVLNode *tree)const;//求高度
		public:
			AVLNode *root;//根节点的指针
			AVLTree():root(NULL){}//构造函数:构造一棵空avl树
			//AVLTree(char Ref):RefValue(Ref),root(NULL){}//构造非空AVL树
			int Insert(TeleNumber x){int taller;return Insert(root,x,taller);}
			void Search();
			int Remove();
			void Change();
			void input();
			friend istream& operator>>(istream& in,const AVLTree& Tree);
			friend ostream& operator<<(ostream& out,const AVLTree& Tree);
			int Height() const;
			void Traverse(AVLNode *ptr,ostream& out) const;
			void Output(AVLNode *Tree)const;
			friend istream& operator>>(istream& in,const TeleNumber& Tree);
			friend ostream& operator<<(ostream& out,const TeleNumber& Tree);
	};

	/////////////////////////////////////////////////////////////////////////////
	void AVLTree::RotateLeft(AVLNode *Tree,AVLNode* &NewTree)                             
	{//右子树比左子树高:对以Tree为根的AVL树做左单旋转,旋转后新根在NewTree                
	NewTree=Tree->right;//新根为原根右子女                                              
	Tree->right=NewTree->left;//原根右子女(现为新根)的的左子女变为原根的右子女            
	NewTree->left=Tree;//新根的左子女为原根节点
	}
	/////////////////////////////////////////////////////////////////////////////
	void AVLTree::RotateRight(AVLNode *Tree,AVLNode* &NewTree)                       
	{//与左旋反向类似                                                     
	NewTree=Tree->left;                                                               
	Tree->left=NewTree->right;               
	NewTree->right=Tree;                                                               
	}
	////////////////////////////////////////////////////////////////////////////
	 void AVLTree::LeftBalance(AVLNode* &Tree,int &taller)
	{
	AVLNode *leftsub=Tree->left,*rightsub;
	switch(leftsub->balance)
	{
	case -1:
		Tree->balance=leftsub->balance=0;
		RotateRight(Tree,Tree);
		taller=0;
		break;
	case 0:
		cout<<"LeftBalance error:Tree already balanced.\n";                           
		break;
	case 1:
		rightsub=leftsub->right;
		switch(rightsub->balance)
		{
		case -1:
			Tree->balance=1;
			leftsub->balance=0;
			break;
		case 0:
			Tree->balance=leftsub->balance=0;                                          
			break;
		case 1:
			Tree->balance=0;
			leftsub->balance=-1;
			break;
		}
		rightsub->balance=0;
		RotateLeft(leftsub,Tree->left);                                               
		RotateRight(Tree,Tree);
		taller=0;
	}
	}
	///////////////////////////////////////////////////////////
	void AVLTree::RightBalance(AVLNode* &Tree,int &taller){
	AVLNode *rightsub=Tree->right,*leftsub;
	switch(rightsub->balance)
	{
	case 1:
		Tree->balance=rightsub->balance=0;
		RotateLeft(Tree,Tree);
		taller=0;
		break;
	case 0:
		cout<<"RightBalance error:Tree already balanced.\n";                              
		break;
	case -1:
		leftsub=rightsub->left;
		switch(leftsub->balance)
		{
		case 1:
			Tree->balance=-1;
			leftsub->balance=0;
			break;
		case 0:
			Tree->balance=rightsub->balance=0;
			break;                                                               
		case -1:
			Tree->balance=0;
			rightsub->balance=1;
			break;
		}
		leftsub->balance=0;
		RotateRight(rightsub,Tree->right);
		RotateLeft(Tree,Tree);
		taller=0;
	}
	}
	///////////////////////////////////////////////////////////////////////
	 int AVLTree::Insert(AVLNode* &tree,TeleNumber &x,int &taller)
	{//以tree为根的AVL树中插入新元素x,如果插入成功,taller返回1,否则返回0
	int success;//成功标志
	if(tree==NULL)//元素为空或某节点的空链域
	{
		tree=new AVLNode(x);//创建新的节点并插入
		success=tree!=NULL ? 1:0;//成功标志:存储分配成功为1
		if(success)
			taller=1;
	}
	else if(x.name==tree->data.name)
	{
		cout<<"the name has been there now!\n";
	}
	else if(x.name<tree->data.name)//判断是向左插入还是向右插入
	{
		success=Insert(tree->left,x,taller);//插入到左子树                
		if(taller)//插入成功
			switch(tree->balance)//判断平衡因子
		{
			case -1://原左子树高,不平衡,调整
				LeftBalance(tree,taller);
				break;
			case 0://原两子树等高,仅改平衡因子
				tree->balance=-1;
				break;                                                    
			case 1://原右子树高,仅改平衡因子
				tree->balance=0;
				taller=0;
				break;
		}
	}
	else if(x.name>tree->data.name)
	{
		success=Insert(tree->right,x,taller);
		if(taller)                                                      
			switch(tree->balance)
		{
			case -1:
				tree->balance=0;
				taller=0;
				break;
			case 0:
				tree->balance=1;
				break;                                 
			case 1:
				RightBalance(tree,taller);
				break;
		}
	}
	return success;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////
	///////////////////////Remove///////////////////////////////////////////////////////////////////
	 int AVLTree::Remove()
	{
		TeleNumber x;
		cout<<"input who you want delete:";
		cin>>x.name;
		int shorter;
		return Remove(root,x,shorter);
	}
	///////////////////////////////////////////////////////////////////////////
	 //删除的总体与插入对应
	 int AVLTree::Remove(AVLNode* &tree,TeleNumber &x,int &shorter)//////*********/////////**********
	{
		int success;
		int taller;
		AVLNode *p,*pre;
		
		if(tree==NULL)//tree为空
		{cout<<"查无此人！"<<endl;return 0;}

		else if(tree->data.name==x.name)
		{
			if(tree->left==NULL||tree->right==NULL)//tree最多有一个子女
			{
				p=tree;
				tree=(tree->left!=NULL)? tree->left:tree->right;//用那个子女（包括NULL的情况）代替它
				delete p;//?
				shorter=1;
				success=1;
			}
			else   //tree有两个子女
			{  ////////////////////////////////////
				pre=tree->left;        ////////////
				while(pre->right!=NULL)//求中序前驱
					pre=pre->right;    ////////////
				///////////////////////////////////
				tree=pre;//用中序下的前驱代替它
				success=Remove(pre,pre->data,shorter);//delete pre?
			}
		}
		
		else if(x.name<tree->data.name)
		{
			success=Remove(tree->left,x,shorter);
			if(shorter)
				switch(tree->balance)
			{
				case -1:
					tree->balance=0;break;
				case 0:
					tree->balance=1;shorter=0;break;
				case 1:
					{
						switch(tree->right->balance)
						{
						case -1:
							RightBalance(tree,taller);break;
						case 0:
							RotateLeft(tree,tree);shorter=0;break;
						case 1:
							RotateLeft(tree,tree);shorter=0;break;
						}
					}
			}
		}

		else if(x.name>tree->data.name)
		{
			success=Remove(tree->right,x,shorter);
			if(shorter)
				switch(tree->balance)
			{
				case 1:
					tree->balance=0;break;
				case 0:
					tree->balance=-1;shorter=0;break;
				case -1:
					{
						switch(tree->left->balance)
						{
						case 1:
							LeftBalance(tree,taller);break;
						case 0:
							RotateRight(tree,tree);shorter=0;break;
						case -1:
							RotateRight(tree,tree);shorter=0;break;
						}
					}
			}
		}
			
		return success;
	}
	 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	istream& operator>>(istream& in,AVLTree &Tree)
	{
		TeleNumber item;
		//cout<<"Construct AVL tree:\n";
		cout<<"请输入要添加的数据(以输入'#'结束):";
		in>>item.name;
		while(item.name!="#")
		{
			cout<<"input phoneNumber:";
			in>>item.phoneNumber;
			cout<<"input mobileNumber:";
			in>>item.mobileNumber;
			cout<<"input email:";
			in>>item.email;
			Tree.Insert(item);
			cout<<"请继续输入要添加的数据(以输入'#'结束):";
			in>>item.name;
		}
		return in;		
	}
	istream& operator>>(istream& in,TeleNumber& tree)
	{
		in>>tree.name;
		in>>tree.phoneNumber;
		in>>tree.mobileNumber;
		in>>tree.email;
		return in;
	}
	ostream& operator<<(ostream& out,TeleNumber& tree)
	{
		out<<tree.name;
		out<<tree.phoneNumber;
		out<<tree.mobileNumber;
		out<<tree.email;
		return out;
	}

	////////////////////////////////////////////////////////////////////////
	ostream& operator<<(ostream& out,AVLTree &Tree)
	{
	//out<<"Inorder traversal of AVL tree.\n";
	Tree.Traverse(Tree.root,out);
	out<<endl;
	return out;
	}
	/////////////////////////////////////////////////////////////////////////////////
	void AVLTree ::Traverse(AVLNode *ptr,ostream& out)const
	{
	if(ptr!=NULL)
	{
		Traverse(ptr->left,out);
		out<<ptr->data.name<<' ';    
		out<<ptr->data.phoneNumber<<' ';
		out<<ptr->data.mobileNumber<<' ';
		out<<ptr->data.email<<endl;
		Traverse(ptr->right,out);
	}
	}
	/////////////////////////////////////////////////////////////////////////////////////
	void AVLTree::Output(AVLNode* ptr)const
	{
		cout<<ptr->data.name<<' ';    
		cout<<ptr->data.phoneNumber<<' ';
		cout<<ptr->data.mobileNumber<<' ';
		cout<<ptr->data.email<<endl;	
	}
	//////////////////////////////////////////////////
	AVLNode* AVLTree::Search(AVLNode* &tree,TeleNumber &x)
	{	
		if(tree==NULL)
			return NULL;
		else if(x.name<tree->data.name)
			Search(tree->left,x);
		else if(x.name>tree->data.name)
			Search(tree->right,x);
		else 
			return tree;
	}
	void AVLTree::Search()
	{
		TeleNumber xx;AVLNode* p;
		cout<<"请输入要查找人的姓名:";
		cin>>xx.name;
		p=Search(root,xx);
		//Output(Search(root,xx));
		if(p==NULL)
			cout<<"查无此人!\n";
		else Output(p);
	}
	///////////////////////////////////////////////////
	void AVLTree::Change()
	{
		TeleNumber x;
		AVLNode* p;
		cout<<"请输入要修改的姓名:";
		cin>>x.name;
		p=Search(root,x);
		cout<<"请选择要修改内容:\n"
			<<"-p:phoneNumber\n"
			<<"-m:mobileNumber\n"
			<<"-e:email\n";
		char cho;
		cin>>cho;
		cout<<"改为:";
		switch(cho)
		{
		case 'p':
			cin>>p->data.phoneNumber;
			break;
		case 'm':
			cin>>p->data.mobileNumber;
			break;
		case 'e':
			cin>>p->data.email;
			break;
		default:
			cout<<"输入必须为p，m或e！\n";
		}	
	}
	int AVLTree::Height() const
	{
		return Height(root);
	}
	int AVLTree::Height(AVLNode * tree) const
	{
		if (tree == NULL)
			return 0;
		if (tree->balance == 1)
			return Height(tree->right) +1;
		return Height(tree->left) + 1;
	}
	void Welcome()
	{
		cout<<"#************************************************************#\n"
			<<"#************欢迎使用电话号码管理系统!!!!********************#\n"
			<<"#************************************************************#\n";
		cout<<"0:保存退出\n";
		cout<<"1:插入\n";
		cout<<"2:删除\n";	
		cout<<"3:查找\n";
		cout<<"4:修改\n";
		cout<<"请输入选择:";
	}
	//////////////////menu////////////////////////////
	void Menu()
	{
	AVLTree av;
	TeleNumber an;
	ifstream infile;
	ofstream outfile;
	infile.open("tele.txt");
	while(infile>>an)
	{
		av.Insert(an);
	}
	cout<<endl;
	cout<<av;
	while(1)
	{
	Welcome();
	int c;
	cin>>c;
	switch(c)                                                         
	{
	case 0:
		cout<<"谢谢使用!\n";
		outfile.open("tele.txt");
		outfile<<av;
		return;
	case 1:	
		cin>>av;
		cout<<av;
		//cout<<av.Height()<<endl;
		break;
	case 2:
		av.Remove();
		cout<<av;
		break;
	case 3:
		av.Search();
		cout<<av;
		break;
	case 4:
		av.Change();
		cout<<av;
		break;
	default:
		cout<<"输入的必须是数字0-4!!\n";
	}
	}
	}
	//////////////////////////////////////////////////


	int main()
	{
	Menu();
	system("pause");
	return 0;
	}
	//////////////////////////////////////////////////////////////////////