数据结构大型实验报告

数据结构大型实验——用户登录系统1数据结构大型实验——用户登录系统姓名：***学号：***班级：***浙江工业大学计算机学院完成时间：2014.12.31数据结构大型实验——用户登录系统2一、实验内容分析1.实验目的【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。【基本要求】1.要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图；2.要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。3.要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。4.要求源程序中有相应注释；5.不强制要求采用类模板，也不要求采用可视化窗口；6.要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确；7.要求采用VisualC++6.0及以上版本进行调试；2.实验中的基本数据结构使用了平衡树(AVL)来存储用户信息，通过在插入和删除节点时左平衡和右平衡操作能使树始终保持平衡。以下为实验中涉及到的类。类名称成员变量及成员函数UserNode(用户信息类)private:stringname;//用户名stringpassword;//密码inth;//以该节点为根的子树高度intbf;//平衡因子：左树高度减去右树高度UserNode*left;//指向左子树的指针UserNode*right;//指向右子树的指针UserNode*parent;//指向父亲节点的指针public:friendclassAVL;UserNode();UserNode(stringn=,stringp=);数据结构大型实验——用户登录系统3intLh();//左子树高度intRh();//右子树高度voidgeth();//更新以当前节点为根结点的子树高度voidgetbf();//更新当前节点的平衡因子stringgetpswd();//获取密码voidsetpswd(string);//修改密码friendvoidsave(UserNode*,ostream&);//输出数据AVL(功能类)private:UserNode*root;public:AVL():root(NULL){}//构造函数boolempty()const;//判空UserNode*find(stringitem);//查找节点voidLRotate(UserNode*,UserNode*);//左旋voidRRotate(UserNode*,UserNode*);//右旋voidLRRotate(UserNode*,UserNode*,UserNode*);//左右旋voidRLRotate(UserNode*,UserNode*,UserNode*);//右左旋voidupdate(UserNode*);//调整平衡voidinsert(string,string);//插入节点boolDelete(UserNode*);//删除节点voidprintNode(UserNode*,int);//打印一个节点voidprint();//打印树friendistream&operator(istream&,AVL&);//输入文件friendostream&operator(ostream&,AVL&);//输出文件Menu(界面菜单类)private:AVLuser;public:Menu();//构造函数voidmainmenu();//主菜单voidshow();//查看所有用户voidload();//登陆voidregist();//注册voidChange(UserNode*);//修改密码voidDel(UserNode*);//删除用户voidclose();//将用户保存到txt中3.程序流程图数据结构大型实验——用户登录系统44.类及类间关系5.主要函数间调用关系主菜单登陆注册更改密码删除用户查看所有用户退出登陆返回主菜单重新注册查看所有用户退出退出查看所有用户返回主菜单退出UserNodeAVLmenu数据结构大型实验——用户登录系统5四种旋转方式判断：Delete(UserNode*)（删除函数）删除节点后更新树方式相同，但是删除方式为将要删除的节点与其右子树中最小的节点交换，所以要分右子树是否为空两种情况讨论。Menumenumenu.mainmenu()Load()registChange()Del()show()close()Main()AVL::find()Menu()Close()①②①Yes其他AVL::Delete(UserNode*AVL::insert(string,string)UserNode::setpswd(string)②NoUserNode*item=newUserNode(na,pswd);update(item-parent)LRotate(UserNode*A,UserNode*B)RRotate(UserNode*A,UserNode*B)LRRotate(UserNode*A,UserNode*B)RLRotate(UserNode*A,UserNode*B)插入函数，参数为用户名、密码定义用户节点更新插入节点路径上的节点Insert(stringna,stringpswd)数据结构大型实验——用户登录系统6二、实验验证分析1.输入的形式和输入值的范围用户名类型：string密码类型：string2.输出的形式输出的形式都是字符串，并通过换行符(‘\n’)，水平制表符(‘\t’)等来规范输出,实现美观性.下面截图演示.3.程序所能达到的功能a.用户登录;b.用户密码更新;c用户添加(注册)d.用户删除;e.查看所有用户4.测试数据(包括正确的输入及其输出结果和含有错误的输入及其输出结果)在主菜单输入1数据结构大型实验——用户登录系统7则进入登陆界面当输入数据非法时数据结构大型实验——用户登录系统8则提醒重新输入其他界面类似三、调试分析1.讨论分析调试过程中的主要技术问题以及具体的解决方法（至少３个）数据结构大型实验——用户登录系统9a)在用户修改密码时由于密码时私有数据，无法修改，登陆时也无法判断密码是否正确；解决方法：定义两个函数getpswd()和setpswd(string)分别用于获取密码和修改密码；b)关于文件的输入输出；解决方法：参考了上学期的C++大型实验c)有关调整树平衡时左右旋和右左旋；解决方法：结合网上和书中解释，先手画过程在写代码，再根据代码画过程。2.技术难点分析（至少３个）a)关于平衡因子的计算，原本UserNode类中int型的成员变量只有平衡因子，如何计算无从入手；后来又添加了变量h(高度)，在每次某个节点有调整后就更新它的高度，同时更新平衡因子；b)简单左旋（右旋），假设A表示离插入项最近的具有平衡因子-2（+2）的祖先节点，B表示A的右（左）孩子，需要重新设置3条链：(1)另A的父亲指向B；(2)另A的右链等于B的左链（另A的左链等于B的右链）；(3)另B的左（右）链指向A；左旋具体代码实现如下：其中geth()和getbf()函数分别为更新高度和平衡因子；左-右旋（右-左旋），假设A表示离插入项最近的具有平衡因子+2（-2）的祖先节点，B表示A的左（右）孩子，C表示B的右孩子，需要重新设置6条链：(1)另B（A）的右链等于C的左链；(2)另A（B）的左链等于C的右链；(3)另A的父亲指向C;(4)另C的右（左）链指向A;(5)另B的父亲指向C;(6)另C的左（右）链指向B；左-右旋具体代码实现如下：数据结构大型实验——用户登录系统10c)调整平衡，从当前节点向上调整，当找到不平衡节点时，根据平衡因子和不平衡状态判断使用哪种旋转方法，具体代码实现及判断方法如下：d)删除节点，分该节点是否有右子树两种情况讨论；(1)没有右子树：先判断删除节点是否为根结点，若是，则直接另根结点指向删除节点的左子树；否则另删除节点的父亲节点的左子树或右子树（根据删除节点为其的左孩子还是右孩子）等于删除节点的左子树，然后从删除节点的父亲节点开始调整平衡；具体代码实现如下：其中pa为删除节点的父亲节点；数据结构大型实验——用户登录系统11(2)有右子树：将当前节点与其右子树中最左边的节点(设为p)交换，然后只需改变一条链，即另p的父亲节点左子树或右子树（根据p为其的左孩子还是右孩子）等于p的右子树(因为p为最左边的节点，所以没有左子树)，然后从p的父亲节点开始调整平衡；具体代码实现如下：3.印象最深刻的３个调试错误，及修正方法a)忘记考虑在选择操作时有错误输入的情况，导致输入不正确时程序退出；修正方法：将输入数据从int改为string型，在进行是否合法判断，若不合法，提醒重新输入；b)总是忘记父亲节点的存在，在删除节点时，忘记将该节点的右子树的父亲节点指向该节点的父亲节点，导致删除用户时第一次成功，第二次就程序就直接崩溃；c)注册新账户时，发现每次注册成功后查看所有用户都没有新注册的账户，以为是插入函数写错了，调了半天才发现原来是注册时没有调用插入函数；d)只在程序退出时保存文件，导致当用户数据发生变化后中途查看txt时，没有及时保存；修正方法：在每次用户数据发生变化时都调用输出文件的函数；e)txt中有用户数据，查看用户时却为空；修正方法：在menu的构造函数中读入用户数据。数据结构大型实验——用户登录系统12四、测试结果1.展示程序的运行结果，包括输入和输出，分析数据的正确性；主界面输入1，登陆界面数据结构大型实验——用户登录系统13登录失败分两种情况1.用户名不存在数据结构大型实验——用户登录系统142.密码错误数据结构大型实验——用户登录系统15登陆成功输入1，修改密码数据结构大型实验——用户登录系统16修改成功输入2，删除用户删除前数据结构大型实验——用户登录系统17删除后以上为输入3，查看所有用户实现主菜单输入2，注册数据结构大型实验——用户登录系统18注册失败分两种情况1.用户名已存在数据结构大型实验——用户登录系统192.两次密码输入不同数据结构大型实验——用户登录系统20注册成功2.应用边界数据、或极端数据测试系统，分析结果的正确性。1)左旋在一棵空树中按次序插入d,h,k;ddhdhkdhkd不平衡,旋转数据结构大型实验——用户登录系统21程序内先插入d,h再插入k数据结构大型实验——用户登录系统22旋转2)右左旋继续插入f,e;dhkfdhkfeehkfdd不平衡,旋转数据结构大型实验——用户登录系统23程序内先插入f再插入e数据结构大型实验——用户登录系统24旋转3)左右旋继续插入g;ehkfdgefhkdgh不平衡,旋转数据结构大型实验——用户登录系统25程序内插入g旋转数据结构大型实验——用户登录系统264)右旋继续插入a程序内插入aefhkdgadfhkagee不平衡,旋转数据结构大型实验——用户登录系统27旋转以上结果均正确数据结构大型实验——用户登录系统28五、附录UserNode.h:#ifndefUSERNODE#defineUSERNO