利用AVL高度平衡的二叉树实现登录系统Word文档下载推荐.docx
《利用AVL高度平衡的二叉树实现登录系统Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《利用AVL高度平衡的二叉树实现登录系统Word文档下载推荐.docx（51页珍藏版）》请在冰点文库上搜索。
<
endl;
"
*******************************欢迎进入登录系统*********************************"
========================================================"
***********1.用户登录*********"
***********2.用户注册*********"
***********0.结束*********"
***********请选择：
*********"
}
/*==========================================操作界面========================================================*/
Menu_Operator（）
************1.修改密码**********"
************2.删除用户**********"
************0.返回上层**********"
************请选择**********"
/*==========================================结束界面=======================================================*/
Menu_Quit（）
********************************************************"
****************感使用****************"
用户类.h
#ifndefUSER
#defineUSER
#include"
Stack.h"
#include<
string>
classUser//用户类；
User（）;
//默认构造函数；
~User（）;
//析构函数；
boolempty（）;
//判空函数；
voidEdit（）;
//密码修改函数；
voidremove（）;
//用户删除函数；
voidsearch（stringname,stringpaw,bool&
found,bool&
found1）;
//查找函数，登录操作的辅助函数；
voidinsert（stringname,stringpaw）;
//插入函数，注册操作的辅助函数；
boolsearch3（stringname）;
//查找函数，注册操作的辅助函数；
voidgraph（ostream&
out）const;
//图形输出函数；
用于测试AVL的结构；
voidSave_User（）;
//保存函数，将用户信息保存到文件里；
private:
classUserNode//用户节点类；
{
public:
stringusername;
//用户名；
stringpassword;
//密码；
intbalanceFactor;
//AVL结构中的平衡因子；
UserNode*left;
//指向左节点的指针；
UserNode*right;
//指向右节点的指针；
UserNode（）//默认构造函数；
{
balanceFactor=0;
//平衡因子的值为0；
left=0;
//左指针为0；
right=0;
//右指针为0；
}
UserNode（stringname,stringpaw）//显示构造函数，定义参数name和paw；
password=paw;
//密码的值为paw；
username=name;
//用户名为name；
};
typedefUserNode*UserNodePointer;
Stack<
UserNodePointer>
path;
//定义一个Stack类型的变量，用于存储插入路径上的节点；
p;
//定义一个Stack类型的变量，保存文件需要；
UserNodePointermyRoot;
voidsearch2（stringname,bool&
found,UserNodePointer&
locptr,UserNodePointer&
parent）;
//删除操作的辅助函数；
voidgraphAux（ostream&
out,intindent,UserNodePointersubtreeRoot）const;
//图形输出函数的辅助函数；
voidrelease（UserNodePointersubtreeRoot）;
//析构函数的辅助函数；
voidSave（UserNodePointersubtreeRoot）;
//保存函数的辅助函数；
voidRotation（intnewBF,UserNodePointerroot）;
//旋转函数，用于调整二叉树的结构；
/*=============================右旋函数以及其定义========================================================*/
UserNodePointerR_rotation（UserNodePointerroot）
UserNodePointernewRoot=root->
left;
//将newRoot（新的旋转根）设为原旋转根的左孩子；
root->
left=newRoot->
right;
//原旋转根的左指针指向新旋转根的右节点（可以为0）；
newRoot->
right=root;
//新的旋转根的右指针指向原旋转根；
if（newRoot->
balanceFactor==1）//如果原旋转根的左孩子的平衡因子为1；
root->
balanceFactor=0;
//旋转后原旋转根的平衡因子为0；
newRoot->
//新的旋转根（即原旋转根的左孩子）的平衡因子也为0；
else//其他情况，即原旋转根的左孩子的平衡因子为0；
{//此种情况只有在删除时才会出现；
balanceFactor=1;
//旋转后原旋转根的平衡因子为1；
balanceFactor=-1;
//新的旋转根的平衡因子为-1；
returnnewRoot;
//返回新的旋转根；
}
/*=============================左旋函数以及其定义========================================================*/
UserNodePointerL_rotation（UserNodePointerroot）
//左旋函数的操作刚好和右旋操作相反；
//将newRoot（新的旋转根）设为原旋转根的右孩子；
right=newRoot->
//原旋转根的右指针指向新旋转根的左节点（可以为0）；
left=root;
//新的旋转根的左指针指向原旋转根；
balanceFactor==-1）//如果原旋转根的右孩子的平衡因子为-1
//新的旋转根（即原旋转根的右孩子）的平衡因子也为0；
else//其他情况，即原旋转根的右孩子的平衡因子为0；
//旋转后原旋转根的平衡因子为-1；
//新的旋转根的平衡因子为1；
/*=============================右左旋函数以及其定义=====================================================*/
UserNodePointerRL_rotation（UserNodePointerroot）
UserNodePointerptr=root->
//定义辅助指针，指向原旋转根的右孩子；
UserNodePointernewRoot=ptr->
//将新的旋转根设为旋转根的右孩子的左孩子；
//原旋转根的右指针指向新旋转根的左孩子；
ptr->
//原旋转根的右孩子的的左指针指向新旋转根的右孩子；
right=ptr;
//新的旋转根的右指针指向原旋转根的右孩子；
switch（newRoot->
balanceFactor）//右左旋操作有三种情况；
case0:
//情况1：
新节点插入之前，原旋转根的右孩子没有左孩子，新插入的节点成为其左孩子；
ptr->
//原旋转根的右孩子的平衡因子为0；
break;
case1:
//情况2：
新节点插入之前，原旋转根的右孩子有左孩子C，新节点被插入到C的右子树中；
//原旋转根的右孩子的平衡因子为-1；
case-1:
//情况3：
新节点插入之前，原旋转根的右孩子有左孩子C，新节点被插入到C的左子树中；
//新旋转根的平衡因子为0；
/*=============================左右旋函数以及其定义=====================================================*/
UserNodePointerLR_rotation（UserNodePointerroot）//左右旋操作与右左旋操作刚好相反；
//定义辅助指针，指向原旋转根的左孩子；
//将新的旋转根设为旋转根的左孩子的右孩子；
//原旋转根的左指针指向新旋转根的右孩子；
//原旋转根的左孩子的的右指针指向新旋转根的左孩子；
left=ptr;
//新的旋转根的左指针指向原旋转根的左孩子；
balanceFactor）//左右旋操作有三种情况；
新节点插入之前，原旋转根的左孩子没有右孩子，新插入的节点成为其右孩子；
//原旋转根的左孩子的平衡因子为0；
case1:
新节点插入之前，原旋转根的左孩子有右孩子C，新节点被插入到C的左子树中；
新节点插入之前，原旋转根的左孩子有右孩子C，新节点被插入到C的右子树中；
//原旋转根的左孩子的平衡因子为1；
//用户类cpp
User.h"
fstream>
iomanip>
/*=======================================构造函数的定义============================================================================*/
User:
User（）
myRoot=0;
/*======================================析构函数的定义=============================================================================*/
~User（）
release（myRoot）;
//调用析构的辅助函数release；
/*=====================================判空函数的定义==============================================================================*/
boolUser:
empty（）
returnmyRoot==0;
//返回myRoot等于0；
/*=====================================析构函数的辅助函数的定义====================================================================*/
voidUser:
release（UserNodePointersubtreeRoot）
if（subtreeRoot!
=0）
release（subtreeRoot->
left）;
//采用后序遍历实现析构；
right）;
deletesubtreeRoot;
/*=====================================查找函数（注册操作的辅助函数）的定义========================================================*/
search3（stringname）
UserNodePointerlocptr=myRoot;
//定义辅助指针指向根节点；
boolfound=true;
//定义bool类型的变量found为true；
while（found==true&
&
locptr!
=0）//当found为true且辅助指针不等于0时；
if（name<
locptr->
username）//如果name小于当前节点的用户名；
locptr=locptr->
//下降到左子树；
elseif（name>
username）//如果name大于当前节点的用户名；
//下降到右子树；
else
found=false;
//若相等，则found为false，循环结束；
returnfound;
//返回found；
/*=====================================BST图形输出函数的定义=======================================================================*/
graph（ostream&
out）const
graphAux（out,0,myRoot）;
/*=====================================保存操作的辅助函数的定义===================================================================*/
Save（UserNodePointersubtreeRoot）
=0）//用递归的方法；
p.push（subtreeRoot）;
//将二叉树中的所有元素压入栈中；
Save（subtreeRoot->
/*=====================================保存函数的定义============================================================================*/
Save_User（）
ofstreamoutfile（"
user.txt"
ios:
out）;
if（!
outfile）
cerr<
openerror!
exit
（1）;
Save（myRoot）;
while（!
p.empty（））
UserNodePointerlocptr=p.top（）;
//一边出栈，一边将出来的元素读到文件中；
outfile<
username<
"
password<
p.pop（）;
outfile.close（）;
/*=====================================graph的辅助函数的定义=======================================================================*/
graphAux（ostream&
out,intindent,UserNodePointersubtreeRoot）const
graphAux（out,indent
升级会员 