用户登录系统
数据结构大型实验
2015/2016(1)
实验
目 用户登录系统
学生姓名 ____
学生学号
主要工作 树的结构、框架编写 负责人 学生班级
任课教师 提交日期 2016.1.2
计算机科学与技术学院
浙江工业大学计算机科学与技术学院 大类基础课程大型实验
用户登录系统
一. 实验题目和要求:
【问题描述】
在登录服务器系统时,都需要验证用户名和密码,如telnet远程登录服务器。用户输入用户名和密码后,服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高,系统有必要有效地组织这些用户信息,从而快速查找和验证用户。另外,系统也会经常会添加新用户、删除老用户和更新用户密码等操作,因此,系统必须采用动态结构,在添加、删除或更新后,依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统,其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。
【基本要求】
1. 要求自己编程实现二叉树结构及其相关功能,以存储用户信息,不允许使用
模板类的二叉树结构和函数。同时要求根据二叉树的变化情况,进行相
应的平衡操作,即AVL平衡树操作,四种平衡操作都必须考虑。测试时,各
种情况都需要测试,并附上测试截图;
2. 要求采用类的设计思路,不允许出现类以外的函数定义,但允许友元函数。
主函数中只能出现类的成员函数的调用,不允许出现对其它函数的调用。 3. 要求采用多文件方式:.h文件存储类的声明,.cpp文件存储类的实现,主函
数main存储在另外一个单独的cpp文件中。如果采用类模板,则类的声明和
实现都放在.h文件中。
4. 要求源程序中有相应注释;
5. 不强制要求采用类模板,也不要求采用可视化窗口;
6. 要求测试例子要比较详尽,各种极限情况也要考虑到,测试的输出信息要详
细易懂,
明各个功能的执行正确;
7. 要求采用Visual C++ 6.0及以上版本进行调试;
二. 设计思路:
第 1 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
1.系统总体设计:
采用平衡二叉查找树(AVL),以用户名(IP)作为比较的关键词进行插入。平衡二叉查找树是在二叉搜索树(BST)的基础上进行了优化,使得树基本达到平衡。定义内部类userNode来存储AVL树的节点信息。
2.系统功能设计:
要创建一颗包含用户名和用户密码的二叉树,要能适应频繁的查找,因为每个用户名是唯一的,将用户名(string类型)作为AVL树的比较参数,这样就可以实现快速的插入、删除和查找,重定义userNode类的比较函数。AVL树是用模板类实现的,这样就可以直接比较两个用户类,方便了很多。
主界面
注册 画树 登录 退出
修删 改除
密用 码 户
图1 系统功能结构图
3.类的设计:
// 节点的类
class userNode
{
private:
string name;
string password;
short int height;
第 2 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
public:
userNode *left;
userNode *right;
userNode(const string &name,const string &password);
userNode(const userNode & temp);
void setName(const string &name);
void setPassword(const string &password);
string getName();
string getPassword();
int getHeight();
void changeHeight(const int height);//改变树的高度
bool checkName(const string &name); };
// 树的类
class tree
{
private:
userNode *root;
public:
tree();
~tree();
void insert_node(userNode *&t ,userNode &temp);
void insert_node(userNode &temp); //新建一个节点
void remove(userNode *&r,userNode *&temp);
void remove(userNode *&temp);//删除一个节点
void clear(userNode *t);
void clear();
void print();
void print(int index,userNode *r);//输出一棵树
void Print();
void Print(ofstream &ofile,userNode *&r);//写入文件
void rotateL(userNode *&r);//左旋
void rotateR(userNode *&r);//右旋
void rotateDoubleLR(userNode *&r);//左右旋
void rotateDoubleRL(userNode *&r);//右左旋
void rightBalance(userNode *&r);
void leftBalance(userNode *&r);
userNode *findNode(string s);//搜索一个节点
userNode *searchLeftMaxNode(userNode *&r,userNode *&R);
};
// 框架类
class frame
第 3 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告 {
tree myTree;
public:
frame();
void view();//显示主界面
void Login();//登录界面
void testInsert();//插入一个节点
void printTree();//画出一棵树
};
4.主程序的设计:
userNode
tree
frame
main
图2 类的调用
三. 调试
:
1.技术难点分析:
(1)查询操作时,怎么能找到相应用户的节点,
考虑到用户名的唯一性,所以将用户名作为AVL树的关键词,以字符串来比较大小,进行排序,重定义userNode类的比较操作符,只比较IP,因此,在查询的时候,新建一个userNode的对象,其IP赋值为所要查询的IP,然后调用查找函数,可找到对应的点
(2)AVL树的实现
看书,上网查询。先了解二叉查找树(BST)的实现,二叉查找树(BST)是一种很好的数据结构,它的特点是,对其任一节点,都满足该节点的左子树的所有点的值都小于该节点,而右子树则是大于。我采用链表来实现它,创建关于节点的
第 4 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告 一个类 Node ,内含描述该节点的值,及左右指针。我定义 insert_node() 函数来实现新节点的插入。AVL树相对于BST树,多了平衡两字,树都有高度,而AVL树就是要求每一个节点的左子树和右子树的高度差不超过1,这样就能使其尽可能的减小整棵树的高度,使时间复杂度能稳定在O(logN), 但我们不可能去约束用户的输入,因此,引入了四种旋转:
是新插入的节点
图3 右旋
图4 左旋
第 5 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
图5 先右旋再左旋
图6 先左旋再右旋
(3)修改密码或删除用户后如何返回上一界面,
经反复修改,未果,遂放弃。
2.调试错误分析:
(1)登陆时密码要正确。
第 6 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
图7 用户登录界面
(2)登陆时用户要存在
图8 用户不存在界面
(3)新建用户名不能已存在
第 7 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
图9 用户名已存在界面
四、 测试结果分析:
1)主界面
图10 主界面
2)登录界面
第 8 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
图11 登录界面
3)注册界面
图12 注册界面
4)树图
第 9 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
图13 树形图界面
5)修改密码
图14 修改密码
6)删除用户
第 10 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
图15 删除用户界面
五、附录:
Node.h
#include
#include
#include
#include
#include
using namespace std;
class userNode
{
private:
string name;
string password;
short int height;
public:
userNode *left;
userNode *right;
userNode(const string &name,const string &password);
userNode(const userNode & temp);
void setName(const string &name);
第 11 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
void setPassword(const string &password);
string getName();
string getPassword();
int getHeight();
void changeHeight(const int height);//改变树的高度
bool checkName(const string &name); };
Tree.h
#include"node.h"
#include
class tree
{
private:
userNode *root;
public:
tree();
~tree();
void insert_node(userNode *&t ,userNode &temp);
void insert_node(userNode &temp); //新建一个节点
void remove(userNode *&r,userNode *&temp);
void remove(userNode *&temp);//删除一个节点
void clear(userNode *t);
void clear();
void print();
void print(int index,userNode *r);//输出一棵树
void Print();
void Print(ofstream &ofile,userNode *&r);//写入文件
void rotateL(userNode *&r);//左旋
void rotateR(userNode *&r);//右旋
void rotateDoubleLR(userNode *&r);//左右旋
void rotateDoubleRL(userNode *&r);//右左旋
void rightBalance(userNode *&r);
void leftBalance(userNode *&r);
userNode *findNode(string s);//搜索一个节点
userNode *searchLeftMaxNode(userNode *&r,userNode *&R);
};
Frame.h
#include"tree.h"
class frame
{
第 12 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
tree myTree;
public:
frame();
void view();//显示主界面
void Login();//登录界面
void testInsert();//插入一个节点
void printTree();//画出一棵树
};
Node.cpp
#include"node.h"
void userNode::setName(const string &name) {
this->name=name;
}
void userNode::setPassword(const string &password)
{
this->password=password; }
string userNode::getName() {
return name;
}
string userNode::getPassword() {
return password;
}
int userNode::getHeight() {
return this==NULL?-1:height; }
void userNode::changeHeight(const int h)
{
height=h;
}
bool userNode::checkName(const string &name) {
if(this->name==name)return true;
else return false;
}
userNode::userNode(const string &name,const string &password)
{
第 13 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
this->name=name;
this->password=password;
height=0;
left=NULL;
right=NULL;
}
userNode::userNode(const userNode & temp) {
this->name=temp.name;
this->password=temp.password;
height=0;
left=NULL;
right=NULL;
}
Tree.cpp
#include"tree.h"
#include
//构造函数
tree::tree()
{
root=NULL;
}
void tree::insert_node(userNode &temp)
{
insert_node(root,temp); }
void tree::insert_node(userNode *&r,userNode &t)
{
if(r==NULL)
{
r=new userNode(t);//若树为空,直接新建节点
}
else if(r->getName()==t.getName())//若节点值相等,则用户名重复
{
return;
string rename;
cout<<"用?户?名?"<>rename;
t.setName(rename);
insert_node(r,t);
}
第 14 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
else if(r->getName()>t.getName())
{
insert_node(r->left,t);
if(r->left->getHeight()-r->right->getHeight()==2)
{
rightBalance(r);
}
}
else if(r->getName()right,t);
if(r->right->getHeight()-r->left->getHeight()==2)
{
leftBalance(r);
}
}
r->changeHeight( max(r->left->getHeight(),r->right->getHeight())+1 );
}
// 移除
void tree::remove(userNode *&r,userNode *&temp) {
if(r==NULL)
{
return;
}
else if(temp->getName()getName())
{
remove(r->left,temp);
if(r->right->getHeight()-r->left->getHeight()==2)
leftBalance(r);
}
else if(temp->getName()>r->getName())
{
remove(r->right,temp);
if(r->left->getHeight()-r->right->getHeight()==2)
rightBalance(r);
第 15 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
}
else
{
if(r->left==NULL)
{
userNode *q=r;
r=r->right;
delete q;
}
else if(r->right==NULL)
{
userNode *q=r;
r=r->left;
delete q;
}
else{
userNode *R;
r=searchLeftMaxNode(r,R);
remove(r->left,R);
if(r->right->getHeight()-r->left->getHeight()==2)
leftBalance(r);
}
}
if(r)
r->changeHeight(max(r->left->getHeight(),r->right->getHeight())+1);
}
void tree::remove(userNode *&temp) {
remove(root,temp);
第 16 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
}
void tree::print()
{
print(0,root);
}
void tree::print(int index,userNode *r) {
if(r)
{
print(index+8,r->right);
cout<getName()<<"("<left->getHeight()-r->right->getHeight()<<"
)"<left);
}
}
void tree::Print(ofstream &ofile,userNode *&r)
{
if(r)
{
Print(ofile,r->left);
ofile<getName()<<","<getPassword()<<'\n';
Print(ofile,r->right);
}
}
void tree::Print()
{
userNode *p=root;
ofstream ofile;
ofile.open("user.txt");
assert(ofile.is_open());
Print(ofile,p);
ofile.close();
}
void tree::rotateL(userNode *&r) {
userNode *R=r->right;
r->right=R->left;
R->left=r;
r->changeHeight(max(r->left->getHeight(),r->right->getHeight())+1);
R->changeHeight(max(R->left->getHeight(),r->getHeight())+1);
r=R;
第 17 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
}
void tree::rotateR(userNode *&r)
{
userNode *L=r->left;
r->left=L->right;
L->right=r;
r->changeHeight(max(r->left->getHeight(),r->right->getHeight())+1);
L->changeHeight(max(L->left->getHeight(),r->getHeight())+1);
r=L;
}
void tree::rotateDoubleLR(userNode *&r) {
rotateL(r->left);
rotateR(r);
}
void tree::rotateDoubleRL(userNode *&r) {
rotateR(r->right);
rotateL(r);
}
void tree::rightBalance(userNode *&r) {
userNode *temp=r->left;
if(temp->left->getHeight()-temp->right->getHeight()==-1)
rotateDoubleLR(r);
else rotateR(r);
}
void tree::leftBalance(userNode *&r) {
userNode *temp=r->right;
if(temp->left->getHeight()-temp->right->getHeight()==1)
rotateDoubleRL(r);
else rotateL(r);
}
userNode* tree::findNode(string s)
第 18 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
{
userNode *r=root;
while(r)
{
if(s==r->getName())
return r;
else if(sgetName())
r=r->left;
else if(s>r->getName())
r=r->right;
}
return NULL;
}
userNode*tree::searchLeftMaxNode(userNode *&r,userNode *&R)
{
bool Left=false,Right=true;
userNode *q=NULL;
R=r;
if(r->left->left==NULL&&r->left->right==NULL)
{
q=r;
r=r->left;
q->left=NULL;
r->left=q;
r->right=q->right;
q->right=NULL;
R=q;
}
else{
if(r->left)
r=r->left;
while(r->right)
{
if(r->right->right==NULL)
q=r;
r=r->right;
Right=false;
}
if(Right)
{
if(r->left)
{
q=r;
r=r->left;
第 19 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告
q->left=NULL;
}
}
r->left=R->left;
r->right=R->right;
R->left=NULL;
R->right=NULL;
q->right=R;
}
int temp=r->getHeight();
r->changeHeight(R->getHeight());
R->changeHeight(0);
return r;
}
tree::~tree()
{
clear();
}
void tree::clear()
{
clear(root);
}
void tree::clear(userNode *t)
{
if(t==NULL)return;
if(t!=NULL)
{
clear(t->left);
clear(t->right);
delete t;
}
t=NULL;
}
Frame.cpp
第 20 页 共 25 页
浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告 #include"frame.h"
#include
frame::frame()
{
fstream file("user.txt");
char s[50];
userNode *userPeople;
while(!file.eof())
{
file.getline(s,50);
for(int i=0;igetPassword())
{
cout<<"密码输入正确,成功登录"<>n;
if(name=="00")view();
else if(n==1)
{
system("cls");
myTree.remove(temp);
userNode *p;
cout<<"输入新密码:"<>newPassword;
p=new userNode(name,newPassword);
myTree.insert_node(*p);
cout <<"修改成功~"<< endl;
system("pause");
myTree.Print();
}
else if(n==2)
{
myTree.remove(temp);
cout<<"删除成功~"<