用户登录系统

1、浙江工业大学本科毕业设计文献综述数据结构大型实验 2015/2016（1） 实验题目 用户登录系统 学生姓名 _ 学生学号 主要工作 树的结构、框架编写 负责人 学生班级 任课教师 提交日期2016.1.2 计算机科学与技术学院II浙江工业大学计算机科学与技术学院 大类基础课程大型实验报告用户登录系统一. 实验题目和要求：【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户

2、和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。【基本要求】1. 要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图；2. 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。3. 要求采用多

3、文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。4. 要求源程序中有相应注释；5. 不强制要求采用类模板，也不要求采用可视化窗口；6. 要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确；7. 要求采用Visual C+ 6.0及以上版本进行调试；二. 设计思路：1. 系统总体设计： 采用平衡二叉查找树（AVL），以用户名（IP）作为比较的关键词进行插入。平衡二叉查找树是在二叉搜索树（BST）的基础上进行了优化，使得树基本达到平衡。定义内部类

4、userNode来存储AVL树的节点信息。2. 系统功能设计：要创建一颗包含用户名和用户密码的二叉树，要能适应频繁的查找，因为每个用户名是唯一的，将用户名（string类型）作为AVL树的比较参数，这样就可以实现快速的插入、删除和查找，重定义userNode类的比较函数。AVL树是用模板类实现的，这样就可以直接比较两个用户类，方便了很多。主界面画树登录注册退出删除用户修改密码图1 系统功能结构图3. 类的设计：/ 节点的类class userNodeprivate:string name;string password;short int height;public:userNode *lef

5、t;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 ch

6、eckName(const string &name);/ 树的类class treeprivate: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(userNod

7、e *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 righ

8、tBalance(userNode *&r);void leftBalance(userNode *&r);userNode *findNode(string s);/搜索一个节点userNode *searchLeftMaxNode(userNode *&r,userNode *&R);/ 框架类class frametree myTree;public:frame();void view();/显示主界面void Login();/登录界面void testInsert();/插入一个节点void printTree();/画出一棵树;4. 主程序的设计：t

9、reeframemainuserNode图2 类的调用三. 调试分析：1.技术难点分析：（1）查询操作时，怎么能找到相应用户的节点？考虑到用户名的唯一性，所以将用户名作为AVL树的关键词，以字符串来比较大小，进行排序，重定义userNode类的比较操作符，只比较IP,因此，在查询的时候，新建一个userNode的对象，其IP赋值为所要查询的IP，然后调用查找函数，可找到对应的点（2）AVL树的实现看书，上网查询。先了解二叉查找树（BST）的实现，二叉查找树（BST）是一种很好的数据结构，它的特点是，对其任一节点，都满足该节点的左子树的所有点的值都小于该节点，而右子树则是大于。我采用链表来实现它

10、，创建关于节点的一个类 Node ，内含描述该节点的值，及左右指针。我定义 insert_node() 函数来实现新节点的插入。AVL树相对于BST树，多了平衡两字，树都有高度，而AVL树就是要求每一个节点的左子树和右子树的高度差不超过1，这样就能使其尽可能的减小整棵树的高度，使时间复杂度能稳定在O(logN), 但我们不可能去约束用户的输入，因此，引入了四种旋转：是新插入的节点图3 右旋图4 左旋图5 先右旋再左旋图6 先左旋再右旋（3） 修改密码或删除用户后如何返回上一界面？经反复修改，未果，遂放弃。2. 调试错误分析：（1） 登陆时密码要正确。图7 用户登录界面（2） 登陆时用户要存在图

11、8 用户不存在界面（3） 新建用户名不能已存在图9 用户名已存在界面4、 测试结果分析：1） 主界面图10 主界面2） 登录界面图11 登录界面3） 注册界面图12 注册界面4） 树图图13 树形图界面5） 修改密码图14 修改密码6） 删除用户图15 删除用户界面5、 附录：Node.h#include<string>#include<cmath>#include<cassert>#include<iomanip>#include<iostream>using namespace std;class userNodeprivate:

12、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);void setPassword(const string &password);string getName();string getPassword();i

13、nt getHeight();void changeHeight(const int height);/改变树的高度bool checkName(const string &name);Tree.h#include"node.h"#include<fstream>class treeprivate:userNode *root;public:tree();tree();void insert_node(userNode *&t ,userNode &temp); void insert_node(userNode &temp);

14、/新建一个节点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

15、(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"tre

16、e.h"class frametree 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

17、=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:u

18、serNode(const string &name,const string &password)this->name=name;this->password=password;height=0;left=NULL;right=NULL;userNode:userNode(const userNode & temp)this->name=;this->password=temp.password;height=0;left=NULL;right=NULL;Tree.cpp#include"tree.h"#i

19、nclude <queue>/构造函数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<<"用?户

20、7;名?"<<t.getName()<<"已?经-存?在ú，?请?修T改?"<<endl;cin>>rename;t.setName(rename);insert_node(r,t);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()&

21、lt;t.getName()insert_node(r->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()

22、<r->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);elseif(r->left=NULL)userNode *q=r

23、;r=r->right;delete q;else if(r->right=NULL)userNode *q=r;r=r->left;delete q;elseuserNode *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->getHeig

24、ht()+1);void tree:remove(userNode *&temp)remove(root,temp); void tree:print()print(0,root);void tree:print(int index,userNode *r)if(r)print(index+8,r->right);cout<<setw(index)<<r->getName()<<"("<<r->left->getHeight()-r->right->getHeight()<&l

25、t;")"<<endl;print(index+8,r->left);void tree:Print(ofstream &ofile,userNode *&r)if(r)Print(ofile,r->left);ofile<<r->getName()<<","<<r->getPassword()<<'n'Print(ofile,r->right);void tree:Print()userNode *p=root;ofstream o

26、file;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-

27、>getHeight(),r->getHeight()+1);r=R;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 tre

28、e: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 rotat

29、eR(r);void tree:leftBalance(userNode *&r)userNode *temp=r->right;if(temp->left->getHeight()-temp->right->getHeight()=1)rotateDoubleRL(r);elserotateL(r);userNode* tree:findNode(string s)userNode *r=root;while(r)if(s=r->getName()return r;else if(s<r->getName()r=r->left;e

30、lse 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;

31、q->right=NULL;R=q;elseif(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;q->left=NULL; r->left=R->left;r->right=R->right;R->left=NULL;R->right=NULL; q->right=R; int temp=r->ge

32、tHeight();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#include"frame.h"#include<fstream>frame:

33、frame()fstream file("user.txt");char s50;userNode *userPeople;while(!file.eof()file.getline(s,50);for(int i=0;i<strlen(s);i+)if(si=',')string user(&s0,&si),pass(&si+1,&sstrlen(s);userPeople=new userNode(user,pass);myTree.insert_node(*userPeople);break;file.close(

34、);void frame:view()while(1)system("cls");/cout<<"1、登?录?"<<endl<<"2、注痢?册á"<<endl<<"3、画-树骸?形?图?"<<endl<<"4、退?出?"<<endl;cout << " -n"cout << " | 欢迎进入用户管理系统 |" <<

35、endl;cout << " | 1.登录 |" << endl;cout << " | 2.注册 |" << endl;cout << " | 3.画树形图 |" << endl;cout << " | 4.退出 |" << endl;cout << " -n"cout << " 请选择（1/2/3/4）："string n;getline(cin,n);

36、if(n0-'0'=1)Login();else if(n0-'0'=2)testInsert();else if(n0-'0'=3)printTree();else if(n0-'0'=4)break;void frame:Login()system("cls");string name,password;string newPassword;cout <<"欢迎进入用户登录界面！(输入00返回上一界面)" << endl << endl;cout<

37、;<"请输入账号："<<endl;getline(cin,name);if(name="00")view();userNode *temp=myTree.findNode(name);if(temp)cout<<"请输入密码:"<<endl; getline(cin,password);if(password=temp->getPassword()cout<<"密码输入正确，成功登录"<<endl<<endl;cout<<"-"<<endl;cout<<"1、更改密码"<<endl;cout<<"2、删除账号"<<endl; int n;cin>>n;if(name="00")view();else if(n=1)system("cls"