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

1、用户登录系统计自1302 李林通 2013268103132014.12.8一. 实验内容分析：1. 实验目的和要求：【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。【基本要求

2、】1. 要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即avl平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图；2. 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。3. 要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。4. 要求源程序中有相应注释；5. 不强制要求采用

3、类模板，也不要求采用可视化窗口；6. 要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确；7. 要求采用visual c+ 6.0及以上版本进行调试；2. 基本数据结构：采用二叉平衡查找树（avl），采用了模板类，以用户名（ip）作为比较的关键词进行插入。二叉平衡查找树是在二叉搜索树（bst）的基础上进行了优化，使得树基本达到平衡。定义内部类node来存储avl树的节点信息。class nodepublic:t date; / 记录节点的值int balance,deep; / 表示节点的平衡值和它向下的最大深度node * left; / 指向左

4、节点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 us

5、er & 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 相等

6、，就算相等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

7、);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(n

8、ode* 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);/ 平衡树 右左转pri

9、vate: / 定位到 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 wel

10、come(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.

11、类间的关系二. 实验验证分析1. 输入形式：基本以 string 串的形式输入输出，用户名应该只包含字母以及数字2. 功能：增加 / 删除读者读者： 修改密码3. 错误测试数据1）用户名不能重复2）用户名不能包含非法字符3）注册新用户，两次密码要相同4）只能删除存在的用户5）删除用户是也要输入密码6）登录时，用户名要合法7）登陆时密码要正确8）修改密码时要和原密码不相同4. 正确测试数据1） 主界面2） 注册界面3） 删除界面4） 用户界面三调试分析1.难点1. 输入密码是怎样显示成星号，并且如何后退？上网查询2. 查询操作时，怎么能找到相应用户的节点？考虑到用户名的唯一性，所以将用户名作为a

12、vl树的关键词，以字符串来比较大小，进行排序，重定义user类的比较操作符，只比较ip,因此，在查询的时候，新建一个user的对象，其ip赋值为所要查询的ip，然后调用查找函数，可找到对应的点3. avl树的实现？3-1 先了解二叉查找树（bst）的实现二叉查找树（bst）是一种很好的数据结构，它的特点是，对其任一节点，都满足该节点的左子树的所有点的值都小于该节点，而右子树则是大于。我采用链表来实现它，创建关于节点的一个类 node ，内含描述该节点的值，及左右指针。我定义 insert() 函数来实现新节点的插入，以下是部分代码：template void avl:insert(const

13、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

14、 = 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(

15、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);还有一个重要的部

16、分是选择何种旋转，以下例举插入函数中的部分代码：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;upda

17、te(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值 和 bal

18、ance值搞反了。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#d

19、efine 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

20、& 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

21、 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& pare

22、nt,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 != nul

23、l)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

24、-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

25、= 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)

26、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-lef

27、t != 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(subtreer

28、oot != 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) / 如果新节

29、点的值小于当前节点，则跳到左子树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

30、 = 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(

31、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记录其父

32、节点，用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-l

33、eft != 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;else

34、fa-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_leftrot

35、ating(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;els

36、e 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

37、= 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

38、-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

39、)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);/ 首页v

40、oid 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#d

41、efine 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