AVL树模拟用户登录系统的实验报告(附代码和详尽注释) (2)

1一．实验内容分析：1.实验目的：模拟用户登录系统，在O（lgn）时间内完成用户登录、删除、修改等工作。2.设计思路：主要分以下四个类：AVLTreeNode:存储平衡树节点；AVLTree:AVL平衡树的主要实现算法；UserInfo:存储用户信息；Interface:界面,与用户交互；3.流程图以及类的主要包含和调用关系：二.实验验证分析（1）输入的形式和输入值的范围；控制台的输入：2如图，输入为数字，超出范围将提示不正确并返回重新输入文件的输入：程序会找寻当前目录的database.data文件，并读入数据，如果未找到则自创此文件，创建空树（2）输出的形式；程序退出时析构函数保存文件到database.data并覆盖原文件。（3）程序所能达到的功能；在O(lgn)时间内添加、查找、删除、修改用户信息。（4）测试数据：本系统包含三个测试函数样例：1.顺序插入测试（分别在debug和release环境下和STLmap比较速度）2.随机插入测试（分别在debug和release环境下和STLmap比较速度）3.删除测试测试函数均在main文件里voidrandomTest();//随机数测试voidorderTest();//顺序插入测试voiddeleteTest();//删除测试voidmain_interface();//主界面1,2均在debug模式下插入100W数据，在release模式下插入1000W数据。顺序插入的实现是用整数1~n转换为string，位数不够的在前面补‘0’。3测试结果：1.debug下顺序插入测试：2.Release下顺序插入测试43.debug下随机插入测试4.release下随机插入测试实践证明map的红黑树在顺序插入测试时慢于我的avl树，但随机插入测试表现比AVL树要好。53.删除数据的图形化表示（‘R’‘L’‘=’为平衡因子以检验正确性）下面删除3（树中无3）：还是一样，下面删除26删除成功，下面删除7删除成功。三.调试分析（1）讨论分析调试过程中的主要技术问题以及具体的解决方法（至少３个）；1.代码重复问题：有重复的代码不是好代码。左右旋和左旋右旋有大量重复，经过分析发现左右旋可以分解为先左旋后右旋，但平衡因子调整方法不一。所以分解左旋和右旋为两个函数，调整平衡因子单分一个函数。2.空间占用问题：平衡因子只有3个取值却占了一个int4个字节是极大的浪费，所以改用char型。编程实践中发现树高也可以取消，也极大的节省了空间。3.时间浪费问题：先调整平衡因子再旋转最后再调整平衡因子浪费时间，经分析后可以采取一些代码上的改动而将第一次调整省略。（2）技术难点分析（至少３个）；1.由于放弃树高调整平衡因子，所以平衡因子的调整是编程最困难之处，采用方法7是根据插入子数是左子树还是右子树调整父亲的平衡因子。2.删除时需先采用BST的删除方式，再分情况用类似AVL插入节点时的调整方法，必须完全搞懂BST和AVL才能正确地处理删除问题。3.代码阅读问题：纯算法程序一般难以阅读，尤其是像AVL这类复杂算法，即使是自己也是编了前面忘了后面，所以程序添加了海量的注释，每个函数每个重要语句都有功能解说，代码命名取其意思，格式遵循《cleanCode》。（3）印象最深刻的３个调试错误，及修正方法；1.最深的当然是访问了没初始化的内存！！几乎90%调试问题都与此有关。大部分非法访问内存经调试都归结于平衡因子的错误。解决方法是在纸上画出几个正确的例子，再输入进程序调试，看平衡因子的错误具体地址和引起其错误的代码。反复调试修改直到测试再大数据量也不会报错。2.链接错误。好像是1005，此错误的原因是.h文件内除了成员函数不能有其它函数。原来是我用的友元重载比较函数（必须用友元，否则类对象比较时重载不匹配。）网上查了好半天才知道的原因。解决方法：友元重载比较运算符函数放到.cpp文件里。3.头文件包含问题要彻底搞明白，.h文件必须加头文件卫士，.cpp必须不加而且不能被#include,。４．测试结果：（1）展示程序的运行结果，包括输入和输出，分析数据的正确性；1.database.data文件（存放用户名密码）2.用户登录83.添加用户4.删除用户4.更新用户（2）应用边界数据、或极端数据测试系统，分析结果的正确性。实验分析验证里已进行充分测试。５．附录：附上源代码，并标明源代码的所属文件，并且源代码必须有注释。9//-----------------------------------------------------------------//AVLTreeNode.h//AVL树节点类//功能：提供主键、左右子指针、父指针，平衡因子//说明：平衡因子为char，节约空间（L相当于1，R相当于-1,=相当于0）//修改时间：2013-12-2514:29:44//-----------------------------------------------------------------#ifndefAVLTreeNode_H#defineAVLTreeNode_H#includeUserInfo.hclassAVLTreeNode{public:UserInfokey;AVLTreeNode*left;AVLTreeNode*right;AVLTreeNode*parent;charbalanceFactor;AVLTreeNode(){left=0;right=0;parent=0;balanceFactor='=';}AVLTreeNode(UserInfos){key=s;left=0;right=0;parent=0;balanceFactor='=';}};#endif//==================================================================//AVLTree.h//AVL平衡树，实现了添加、查找、图形输出等功能//Author:hufeiyaZJUT//2013-12-414:38:04//2013-12-2414:35:42添加了删除方法//插入经过3KW数据严格测试，删除不严格测试//==================================================================#ifndefAVLTree_H10#defineAVLTree_H#includeiostream#includeiomanip#includestring#includeAVLTreeNode.husingnamespacestd;classAVLTree{private:public:AVLTree();~AVLTree();//析构函数。调用①voidinsert(AVLTreeNode*n);//插入元素。调用④⑤⑥⑦voidgraph();//图形输入。调用②voidinOrder(ofstream&fs);//中序遍历修改文件。调用③AVLTreeNode*find(UserInfotarget);//查找元素，返回地址。voidremove(UserInfokey);//删除元素。调用⑥⑦⑧⑨private:AVLTreeNode*root;voidClearTree(AVLTreeNode*n);//清除所有元素①voidgraphAux(AVLTreeNode*subtree,inta);//递归图形输出②voidinOrderAux(ofstream&fs,AVLTreeNode*subtree);//递归中序遍历③voidrestoreAVL(AVLTreeNode*ancestor,AVLTreeNode*newNode);//添加节点后重建树④voidadjustBalanceFactors(AVLTreeNode*end,AVLTreeNode*start);//调整平衡因子(插入时)⑤voidrotateLeft(AVLTreeNode*n);//左旋，插入删除共用⑥voidrotateRight(AVLTreeNode*n);//右旋，插入删除共用⑦voidsearch2(constUserInfo&data,bool&found,AVLTreeNode*&x,AVLTreeNode*&parent);//remove辅助函数⑧voidrestoreAVL2(AVLTreeNode*start,boolleft);//删除节点后后重建树⑨};#endif//-----------------------------------------------------------------//Interface.h//界面类//功能：构建界面、读取和写入文件//修改时间：2013-12-2514:27:17//-----------------------------------------------------------------#ifndefInterface_H11#defineInterface_H#includefstream#includeiostream#includestring#includestdlib.h#includeAVLTree.husingnamespacestd;classInterface{public:Interface();//构造函数，读取文件，创建并建立树~Interface();//保存信息到文件，销毁树，关闭文件voidmainFace();voidlogIn();voidaddUser();voidremoveUser();voidupdate();private:AVLTree*data;ifstreamreadStream;ofstreamwriteStream;};#endif//-----------------------------------------------------------------//UserInfo.h//用户信息类//功能：储存用户名、密码等信息，重载部分操作符//修改时间：2013-12-2514:26:05//-----------------------------------------------------------------#ifndefUserInfo_H#defineUserInfo_H#includestring#includeiostreamusingnamespacestd;classUserInfo{public:UserInfo(){}UserInfo(stringname,stringpass);UserInfo(stringname);//缺省密码等于账号12UserInfo(char*name);//缺省密码等于账号UserInfo(constUserInfo&b);//复制构造函数friendbooloperator(constUserInfo&a,constUserInfo&b);friendbooloperator(constUserInfo&a,constUserInfo&b);booloperator==(constUserInfo&b);friendostream&operator(ostream&os,constUserInfo&b);friendclassInterface;friendclassAVLTree;private:stringusername;stringpassword;};#endif下面是.cpp文件Main.cpp:#includeAVLTree.h#includeiostream#includestdlib.h#includetime.h#includesstream#includestring#includemap#includeI