基于AVL的用户登录系统实验报告

用户登录系统计自1302 李林通 2013268103132014.12.8一. 实验内容分析：1. 实验目的和要求：【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。【基本要求】1. 要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图；2. 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。3. 要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。4. 要求源程序中有相应注释；5. 不强制要求采用类模板，也不要求采用可视化窗口；6. 要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确；7. 要求采用Visual C+ 6.0及以上版本进行调试；2. 基本数据结构：采用二叉平衡查找树（AVL），采用了模板类，以用户名（IP）作为比较的关键词进行插入。二叉平衡查找树是在二叉搜索树（BST）的基础上进行了优化，使得树基本达到平衡。定义内部类Node来存储AVL树的节点信息。class Nodepublic:T date; / 记录节点的值int balance,deep; / 表示节点的平衡值和它向下的最大深度Node * left; / 指向左节点Node * right; / 指向右节点Node():balance(0),left(NULL),right(NULL),deep(1)Node(T item):date(item),balance(0),left(NULL),right(NULL),deep(1);3. 实验思路：要创建一颗包含用户信息的树，要能适应频繁的查找，想到生活中登陆时都是先输入用户名，且每个人的用户名是唯一的，所以，我将用户名（string类型）作为AVL树的比较参数，这样就可以实现快速的插入、删除和查找，重定义User类的比较函数bool operator < (const User & t1,const User & t2) / 按 id 比较大小return t1.id < t2.id;AVL树是用模板类实现的，这样就可以直接比较两个用户类，方便了很多。4. 类：/ 用户的类class Userpublic:string id; / 用户名string pass; / 密码User();User(string a,string b = "");friend bool operator < (const User & t1,const User & t2); / 按 id 比较大小friend bool operator = (const User & t1,const User & t2); / id 相等，就算相等friend ostream& operator<<(ostream& out,const User& us); /重定义输出流;/ AVL的类template <typename T>class AVLclass Node / 内部节点类public:T date; / 节点的值int balance , deep; / 节点的平衡值和深度Node * left;Node * right;Node():balance(0),left(NULL),right(NULL),deep(1)Node(T item):date(item),balance(0),left(NULL),right(NULL),deep(1);typedef Node* NodePoint;public:NodePoint myRoot; / 根节点AVL();bool empty() const;bool search(T& item); / 找到与 item 的IP相同的节点，利用引用提取信息void insert(const T& item);/ 加入节点 itemvoid remove(const T& item);/ 删除节点 itemvoid update(const T& item); / 更新 item 的节点void display(Node* st)const; / 输出全部信息 void display(Node* st , vector<T>& str); /遍历所有节点，将所需信息存到 str中void graph(ostream& out) const; / 将整棵树以图的形式输出void LeftRotating(Node* pa , Node* pos); / 平衡树 左转void RightRotating(Node* pa , Node* pos);/ 平衡树 右转void Left_RightRotating(Node* pa , Node* pos);/ 平衡树 左右转void Right_LeftRotating(Node* pa , Node* pos);/ 平衡树 右左转private: / 定位到 item 在的节点void search2(const T& item,bool& found,NodePoint& locptr,NodePoint& parent,stack<NodePoint>& step) const;void update(Node* p);/ 用于旋转后的更新void graphAux(ostream& out,int indent,NodePoint substrrRoot) const;/ 登陆的类class Landingstring nowuser;AVL<User> user;public:void graph();Landing();/ 构造函数bool welcome(int fst);/ 首页void readfile(); / 从文件中读入信息void writefile(); / 将用户信息写入文件中，以 End 结尾int landing(); / 登陆界面bool Use(); / 用户界面bool insertuser(); / 增加用户bool deleteuser(); / 删除用户bool change(); / 修改密码private:string getpass(); / 获取密码void encode(string& str); / 密码加密void decode(string& str); / 密码解密;4. 实验流程5.类间的关系二. 实验验证分析1. 输入形式：基本以 string 串的形式输入输出，用户名应该只包含字母以及数字2. 功能：增加 / 删除读者读者： 修改密码3. 错误测试数据1）用户名不能重复2）用户名不能包含非法字符3）注册新用户，两次密码要相同4）只能删除存在的用户5）删除用户是也要输入密码6）登录时，用户名要合法7）登陆时密码要正确8）修改密码时要和原密码不相同4. 正确测试数据1） 主界面2） 注册界面3） 删除界面4） 用户界面三调试分析1.难点1. 输入密码是怎样显示成星号，并且如何后退？上网查询2. 查询操作时，怎么能找到相应用户的节点？考虑到用户名的唯一性，所以将用户名作为AVL树的关键词，以字符串来比较大小，进行排序，重定义User类的比较操作符，只比较IP,因此，在查询的时候，新建一个User的对象，其IP赋值为所要查询的IP，然后调用查找函数，可找到对应的点3. AVL树的实现？3-1 先了解二叉查找树（BST）的实现二叉查找树（BST）是一种很好的数据结构，它的特点是，对其任一节点，都满足该节点的左子树的所有点的值都小于该节点，而右子树则是大于。我采用链表来实现它，创建关于节点的一个类 Node ，内含描述该节点的值，及左右指针。我定义 insert() 函数来实现新节点的插入，以下是部分代码：template <typename T>void AVL<T>:insert(const T& item)NodePoint sc = myRoot;if(sc = NULL) / 如果该树为空，先创建根节点myRoot = new Node(item);return;stack<NodePoint> step; / 记录插入时走过的路径，之后的平衡会用到int s,gs;while(1)step.push(sc);if(item < sc->date) / 如果新节点的值小于当前节点，则跳到左子树if(sc->left = NULL)sc->left = new Node(item);s = 0;break;else sc = sc->left;else if(sc->date < item) / 如果新节点的值大于当前节点，则跳到右子树if(sc->right = NULL)sc->right = new Node(item);s = 1;break;else sc = sc->right;else return ; / 不然，说明该节点已经存在，直接结束.查找、删除函数也是类似的步骤。3-2 AVL树的旋转AVL树相对于BST树，多了平衡两字，树都有高度，而AVL树就是要求每一个节点的左子树和右子树的高度差不超过1，这样就能使其尽可能的减小整棵树的高度，使时间复杂度能稳定在O(logN), 但我们不可能去约束用户的输入，因此，引入了四种旋转：是新插入的节点右旋左旋先右旋再左旋先左旋后右旋以下是左-右旋的代码：template <typename T>void AVL<T>:Left_RightRotating(Node* pa , Node* pos)NodePoint s,ss; / s 记录的是 ss 的父节点s = pos->left;ss = s->right;pos->left = ss;s->right = ss->left;ss->left = s;update(s);update(ss); / 以上部分是左旋if(pa = NULL) myRoot = ss;else if(pa->left = pos)pa->left = ss;else pa->right = ss;pos->left = ss->right;ss->right = pos;update(pos);update(ss);还有一个重要的部分是选择何种旋转，以下例举插入函数中的部分代码：int pre;NodePoint pa,tmp;while(!step.empty() / step 内存的是从根节点到当前节点的路径，由于stack的特性，离栈顶越近，深度越深gs = s; / gs 记录当前节点的父节点是祖父节点的左节点（0）还是右节点（1）tmp = step.top(); / 不断弹出元素，并更新balance值和deep值step.pop();if(tmp->left = sc) s = 0; else s = 1; / s 记录当前节点是父节点的左节点（0）还是右节点（1）pre = tmp->balance;update(tmp);if(pre = tmp->balance) break;if(abs(tmp->balance) > 1) / 如果平衡被打破if(step.empty() pa = NULL;else pa = step.top();if(!s && !gs) RightRotating(pa,tmp);else if(s && gs) LeftRotating(pa,tmp);else if(!s && gs) Left_RightRotating(pa,tmp);else Right_LeftRotating(pa,tmp);2.调试错误：1. AVL树的旋转更新，有个地方将 deep值 和 balance值搞反了。2. 赋值操作时，对象搞反了。四. 测试结果1. 添加用户Ps: 输入用户名时，输入0，才会退出。 用户名要只有字母或数字2. 删除用户Ps: 删除用户是也需要密码3. 用户登陆Ps: 密码错误三次会自动跳到上一层4. 修改密码五关于AVL树的验证初始阶段 加入节点 a 右旋加入节点 x , y 左旋加入节点 q 右左旋加入节点 d ，k 左右旋删除节点 c六附录AVL.h#include <iostream>#include <stdio.h>#include <string.h>#include <string>#include <stack>#include <vector>#include <cmath>using namespace std;#ifndef MYAVLCLASS#define MYAVLCLASStemplate <typename T>class AVLclass Nodepublic:T date;int balance,deep;Node * left;Node * right;Node():balance(0),left(NULL),right(NULL),deep(1)Node(T item):date(item),balance(0),left(NULL),right(NULL),deep(1);typedef Node* NodePoint;public:NodePoint myRoot;AVL();bool empty() const;bool search(T& item); / 找到 item 所在的节点，将所需信息复制到 key上void insert(const T& item);/ 加入节点 itemvoid remove(const T& item);/ 删除节点 itemvoid update(const T& item); / 更新 item 的节点void display(Node* st)const; / 输出全部信息 void display(Node* st,vector<T>& cnt); / 遍历所有节点，将所需的信息存到 str中void graph(ostream& out) const; / 将整棵树以图的形式输出void LeftRotating(Node* pa , Node* pos); / 平衡树 左转void RightRotating(Node* pa , Node* pos);/ 平衡树 右转void Left_RightRotating(Node* pa , Node* pos);/ 平衡树 左右转void Right_LeftRotating(Node* pa , Node* pos);/ 平衡树 右左转private: / 定位到 item 在的节点void search2(const T& item,bool& found,NodePoint& locptr,NodePoint& parent,stack<NodePoint>& step) const;void update(Node* p);/ 用于旋转后的更新void graphAux(ostream& out,int indent,NodePoint substrrRoot) const;template <typename T>AVL<T>:AVL()myRoot = NULL; / 树的根节点设置为空template <typename T>bool AVL<T>:empty() constreturn myRoot = NULL; / 判断树的根节点是否为空template <typename T>bool AVL<T>:search(T& item)NodePoint sc = myRoot;while(sc != NULL)if(sc->date = item) / sc->date = item 说明关键词匹配，找到了目标item = sc->date; / 将所有的信息赋值给 item ，因为item是引用，外部也发生了变化return true;if(sc->date < item) sc = sc->right; / 若目标关键词大于当前节点，说明在右子树else sc = sc->left; / 否则，说明在左子树return false;template <typename T>void AVL<T>:update(Node* p)if(p->left = NULL && p->right = NULL) p->deep = 1; / 若无左右子树，深度为 1else if(p->left = NULL) p->deep = (p->right->deep)+1; else if(p->right = NULL) p->deep = (p->left->deep)+1; / 若只有一颗子树，深度为其子树深度+1else p->deep = max(p->left->deep,p->right->deep)+1; / 否则，深度为max(左，右)+1if(p->left = NULL && p->right = NULL) p->balance = 0; / 平衡值类似else if(p->left = NULL) p->balance = -(p->right->deep);else if(p->right = NULL) p->balance = p->left->deep;else p->balance = (p->left->deep)-(p->right->deep);/ 调试错误1: 由于觉得形式相似，直接复制，导致 deep 没改成 balance/if(p->left != NULL) cout<<p->left->deep<<" 1111n"/if(p->right != NULL) cout<<p->right->deep<<" 2222n"/cout<<p->date<<"n"<<p->deep<<" "<<p->balance<<"n"template <typename T>void AVL<T>:update(const T& item) / 更新目标的值NodePoint sc = myRoot;while(sc != NULL)if(sc->date < item) sc = sc->right;else if(item < sc->date) sc = sc->left;else / 找到目标后，赋值更新sc->date = item;return;template <typename T>void AVL<T>:display(Node* st)const if(st->left != NULL) display(st->left);if(st != NULL) cout<<st->date<<"n"if(st->right != NULL) display(st->right);template <typename T>void AVL<T>:display(Node* st,vector<T>& cnt)if(st = NULL) return ;if(st->left != NULL) display(st->left,cnt);cnt.push_back(st->date); / 将节点信息放到向量 cnt 中if(st->right != NULL) display(st->right,cnt);/ 错误3 ：递归调用display时忘加 str 参数template <typename T>void AVL<T>:graph(ostream& out) constgraphAux(out,0,myRoot);template <typename T>void AVL<T>:graphAux(ostream& out,int indent,NodePoint subtreeRoot) constif(subtreeRoot != NULL)graphAux(out,indent+7,subtreeRoot->right);out<<setw(indent)<<" "<<subtreeRoot->date<<"n"graphAux(out,indent+7,subtreeRoot->left);template <typename T>void AVL<T>:insert(const T& item) NodePoint sc = myRoot;if(sc = NULL) / 若当前树为空，直接创建根节点myRoot = new Node(item);return;stack<NodePoint> step; / 用于记录从根节点走到目标节点的路径int s,gs;while(1)step.push(sc);/cout<<item<<" "<<sc->date<<"n"if(item < sc->date) / 如果新节点的值小于当前节点，则跳到左子树if(sc->left = NULL)sc->left = new Node(item);s = 0;sc->balance+;sc->deep = max(sc->deep,2);break;else sc = sc->left;else if(sc->date < item) / 如果新节点的值大于当前节点，则跳到右子树if(sc->right = NULL)sc->right = new Node(item);s = 1;sc->balance-;sc->deep = max(sc->deep,2);break;else sc = sc->right;else return ;if(step.size() <= 1) return; / 不然，说明该节点已经存在，直接结束step.pop();int pre;NodePoint pa,tmp;while(!step.empty() gs = s; / s表示的是当前节点子节点，gs表示当前节点的孙子节点tmp = step.top();step.pop();if(tmp->left = sc) s = 0;else s = 1; / 0表示在左子树，1表示在右子树pre = tmp->balance;update(tmp); / 更新 tmp 节点的balance和deepif(pre = tmp->balance) break; / 若 tmp 节点的balance值未发生变化，则其祖先也不会变化if(abs(tmp->balance) > 1) / 如果平衡被打破if(step.empty() pa = NULL;else pa = step.top();if(!s && !gs) RightRotating(pa,tmp); / 当新节点位于左子树的左子树else if(s && gs) LeftRotating(pa,tmp); / 当新节点位于右子树的右子树else if(!s && gs) Left_RightRotating(pa,tmp); / 当新节点位于左子树的右子树else Right_LeftRotating(pa,tmp); / 当新节点位于右子树的左子树template <typename T>void AVL<T>:search2(const T& item,bool& found,NodePoint& sc,NodePoint& fa,stack<NodePoint>& step) constsc = myRoot;fa = NULL;found = false;while(sc != NULL) / 找到sc节点，用fa记录其父节点，用step记录其路径step.push(sc);if(item < sc->date)fa = sc;sc = sc->left;else if(sc->date < item)fa = sc;sc = sc->right;elsefound = true;return;template <typename T>void AVL<T>:remove(const T& item)NodePoint sc,fa,tmp;bool found;stack<NodePoint> step;search2(item,found,sc,fa,step); / 先找到要删除节点的位置if(!found) return;/ 接下来要让此节点与其右子树的最左边节点进行交换，有可能没有，也有可能就是其右节点if(sc->left != NULL && sc->right != NULL)tmp = sc->right;step.push(tmp);fa = sc;while(tmp->left != NULL) / 一直走到最左边fa = tmp;tmp = tmp->left;step.push(tmp);sc->date = tmp->date; / 交换sc = tmp;/ 连接sc的父节点与它的子树if(fa = NULL) / 若只有一个节点myRoot = NULL;else if(sc = fa->right) / 若sc是右节点if(sc->left != NULL)fa->right = sc->left;elsefa->right = sc->right;elseif(sc->left != NULL)fa->left = sc->left;elsefa->left = sc->right;if(sc = myRoot) myRoot = NULL;delete sc; / 删除节点if(step.size() <= 1) return;step.pop();int pre;NodePoint pa;while(!step.empty() / 更新树，操作和插入时一样tmp = step.top();step.pop();pre = tmp->balance;update(tmp);if(pre = tmp->balance) break;if(step.empty() pa = NULL;else pa = step.top();if(tmp->balance = -2)if(tmp->right->balance = 1) Right_LeftRotating(pa,tmp);else LeftRotating(pa,tmp);else if(tmp->balance = 2)if(tmp->left->balance = -1) Left_RightRotating(pa,tmp);else RightRotating(pa,tmp);template <typename T>void AVL<T>:LeftRotating(Node* pa , Node* pos)Node* tmp = pos->right;if(pa = NULL) myRoot = tmp;/ 当前节点的父节点连接其右节点else if(pa->left = pos)pa->left = tmp;else pa->right = tmp;/ 其右节点的左子树变成当前节点的右子树pos->right = tmp->left;tmp->left = pos;update(pos);update(tmp);template <typename T>void AVL<T>:RightRotating(Node* pa , Node* pos)Node* tmp = pos->left;if(pa = NULL) myRoot = tmp;/ 当前节点的父节点连接其左节点else if(pa->right = pos)pa->right = tmp;else pa->left = tmp;/ 其左节点的右子树变成当前节点的左子树pos->left = tmp->right;tmp->right = pos;update(pos);update(tmp);template <typename T>void AVL<T>:Left_RightRotating(Node* pa , Node* pos)NodePoint s,ss;s = pos->left;ss = s->right;pos->left = ss;s->right = ss->left;ss->left = s;update(s);update(ss); / 以上部分是左旋，以下是右旋if(pa = NULL) myRoot = ss;else if(pa->left = pos)pa->left = ss;else pa->right = ss;pos->left = ss->right;ss->right = pos;update(pos);update(ss);template <typename T>void AVL<T>:Right_LeftRotating(Node* pa , Node* pos)NodePoint s,ss;s = pos->right;ss = s->left;pos->right = ss;s->left = ss->right;ss->right = s;update(s);update(ss); / 以上部分是右旋，以下是左旋if(pa = NULL) myRoot = ss;else if(pa->right = pos)pa->right = ss;else pa->left = ss;pos->right = ss->left;ss->left = pos;update(pos);update(ss);#endifLanding.h#ifndef LANDING#define LANDING#include "AVL.h"#include "User.h"#include <conio.h>#include <fstream>#include <ctype.h>#include <windows.h>class Landingstring nowuser;AVL<User> user;public:void graph();Landing();/ 构造函数bool welcome(int fst);/ 首页void readfile(); / 从文件中读入信息void writefile(); / 将用户信息写入文件中，以 End 结尾int landing(); / 登陆界面bool Use(); / 用户界面bool insertuser(); / 增加用户bool deleteuser(); / 删除用户bool change(); / 修改密码private:string getpass(); / 获取密码void encode(string& str); / 密码加密void decode(string& str); / 密码解密;#endifUser.h#ifndef MYUSER#define MYUSER#include <iostream>#include <iomanip>#include <string>using namespace std;class Userpublic:string id; / 用户名string pass; / 密码User();User(string a,string b = "");friend bool operator < (const User & t1,const User & t2); / 按 id 比较大小friend bool operator = (const User & t1,const User & t2); / id 相等，就算相等friend ostream& operator<<(ostream& out,const User& us); /重定义输出流;#endifLanding.cpp#include "Landing.h"void Landing:graph()user.graph(cout);Landing:Landing()nowuser.clear();/ 构造函数bool Landing:welcome(int fst) / 首页if(!fst) readfile();/ 错误4：每次回到这个函数都会读一遍文件system("cls");printf("nnn");printf("ttt欢迎进入用户登录系统*_*nn");printf("ttt1.注册用户n");printf("ttt2.删除用户n");printf("ttt3.用户登录n");printf("ttt4.退出n");printf("ttt请选择相应的序号 : ");int k,tmp;scanf("%d",&k);if(k = 1)while(!insertuser(); / 调用添加用户函数else if(k = 2)while(!deleteuser(); / 调用删除用户函数else if(k = 3)while(tmp = landing() = 0); / 调用登录函数if(tmp = 1) while(!Use();nowuser.clear();else if(k = 4) writefile(); / 调用写入文件函数return true;else if(k = 5) graph();Sleep(5000);else printf("nttt请输入正确的编号！n");Sleep(1000); / 停留 1sreturn false;void Landing:readfile() / 从文件中读入信息string id,pass;ifstream uin("user.txt");while(uin>>id)if(id = "End") break;uin>>pass;decode(pass); / 信息解密User us(id,pass); / 创建新的对象user.insert(us); / 插入节点void Landing:writefile() / 将用户信息写入文件中，以 End 结尾ofstream uout("user.txt");vector<User> cnt;user.display(user.myRoot,cnt);for(int i=0;i<cnt.size();i+)encode(cnti.pass); / 信息加密uout<<cnti.id<<" "<<cnti.pass<<"n"uout<<"End"int Landing:landing() / 登陆界面system("cls");printf("nnn");string id,pass;char ch;int times;bool flag;printf("ttt欢迎进入用户登陆界面！(按0退出)nn");printf("ttt请输入用户名 ：");cin>>id;if(id = "0") return -1;User us(id);if(!user.search(us) / 如果找不到该用户printf("nttt不存在该用户名！");Sleep(700);return 0;times = 3;flag = false;while(times-) / 密码最多错 3 次pass.clear();printf("nttt请输入密码 ：");pass = getpass(); / 调用获取密码函数if(us.pass != pass) printf("nttt密码错误！请重试！n");else flag = true; break;if(!flag)printf("nttt请确认用户名是否正确！n");Sleep(1000);return -1;else nowuser = id;return 1;bool Landing:Use() / 用户界面system("cls");int k;bool flag = true;printf("nnn");printf("ttt欢迎进入用户界面！nn");printf("ttt1.修改密码n");printf("ttt2.返回上一层n");printf("ttt请输入操作对应的编号 : ");scanf("%d",&k);switch(k)case 1:while(!change()printf("nttt是否重新修改？（Y or N）：");char ch;scanf(" %c",&ch);if(ch = N | ch = n) break;return false;case 2:return true;default:flag = false;break;if(!flag)printf("nttt请输入正确的操作！n");Sleep(800);return false;bool Landing:insertuser() / 增加用户system("cls");printf("nnn");printf("ttt欢迎进入增加用户界面！(按0退出)nn");string id,pass,repass;vector<string> cnt;char ch;printf("ntt请输入新增的用户名(由字母、数字组成) ：");cin>>id;if(id = "0") return true;/ 若包含非字母或数字字符，视为非法for(int i=0; i<id.length(); i+)if(!isalpha(idi) && !isdigit(idi)printf("nttt用户名包含非法字符！n");Sleep(700);return false;if(user.search(User(id) / 查找树中是否已经存在此用户名printf("nttt改用户名已存在！n");elseprintf("nttt请输入密码 ：");pass = getpass();printf("nttt请再次输入密码：");repass = getpass();if(repass != pass)printf("nttt密码不一致！ 注册失败！n");else user.insert(User(id,pass); / 插入新节点printf("nttt注册成功！n");printf("ntt是否继续增加读者？（Y or N）: ");scanf(" %c",&ch);if(ch = Y | ch = y) return false;return true;bool Landing:deleteuser() / 删除用户system("cls");printf("nnn");printf("nttt欢迎进入删除用户界面！(按0退出)nn");string id;printf("nttt请输入要删除的用户名 ：");cin>>id;if(id = "0") return true;User r(id);if(!user.search(r) printf("nttt该读者不存在！n");else printf("nttt请输入密码：");string pass = getpass();if(pass != r.pass)printf("nttt密码错误！n");