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

用户登录系统计自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 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& 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& step) const;void update(Node* p);/ 用于旋转后的更新void graphAux(ostream& out,int indent,NodePoint substrrRoot) const;/ 登陆的类class Landingstring nowuser;AVL 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 void AVL:insert(const T& item)NodePoint sc = myRoot;if(sc = NULL) / 如果该树为空，先创建根节点myRoot = new Node(item);return;stack step; / 记录插入时走过的路径，之后的平衡会用到int s,gs;while(1)step.push(sc);if(item date) / 如果新节点的值小于当前节点，则跳到左子树if(sc-left = NULL)sc-left = new Node(item);s = 0;break;else sc = sc-left;else if(sc-date 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 void AVL: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 #include #include #include #include #include #include using namespace std;#ifndef MYAVLCLASS#define MYAVLCLASStemplate 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& 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& step) const;void update(Node* p);/ 用于旋转后的更新void graphAux(ostream& out,int indent,NodePoint substrrRoot) const;template AVL:AVL()myRoot = NULL; / 树的根节点设置为空template bool AVL:empty() constreturn myRoot = NULL; / 判断树的根节点是否为空template bool AVL: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 right; / 若目标关键词大于当前节点，说明在右子树else sc = sc-left; / 否则，说明在左子树return false;template void AVL: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) coutleft-deepright != NULL) coutright-deep 2222n;/coutdatendeep balancen;template void AVL:update(const T& item) / 更新目标的值NodePoint sc = myRoot;while(sc != NULL)if(sc-date right;else if(item date) sc = sc-left;else / 找到目标后，赋值更新sc-date = item;return;template void AVL:display(Node* st)const if(st-left != NULL) display(st-left);if(st != NULL) coutdateright != NULL) display(st-right);template void AVL:display(Node* st,vector& 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 void AVL:graph(ostream& out) constgraphAux(out,0,myRoot);template void AVL:graphAux(ostream& out,int indent,NodePoint subtreeRoot) constif(subtreeRoot != NULL)graphAux(out,indent+7,subtreeRoot-right);outsetw(indent) dateleft);template void AVL:insert(const T& item) NodePoint sc = myRoot;if(sc = NULL) / 若当前树为空，直接创建根节点myRoot = new Node(item);return;stack step; / 用于记录从根节点走到目标节点的路径int s,gs;while(1)step.push(sc);/coutitem daten;if(item 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 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() 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 void AVL:search2(const T& item,bool& found,NodePoint& sc,NodePoint& fa,stack& step) constsc = myRoot;fa = NULL;found = false;while(sc != NULL) / 找到sc节点，用fa记录其父节点，用step记录其路径step.push(sc);if(item date)fa = sc;sc = sc-left;else if(sc-date right;elsefound = true;return;template void AVL:remove(const T& item)NodePoint sc,fa,tmp;bool found;stack 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() 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 void AVL: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 void AVL: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 void AVL: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 void AVL: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 #include #include #include class Landingstring nowuser;AVL 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 #include #include 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& operatorid)if(id = End) break;uinpass;decode(pass); / 信息解密User us(id,p