数据结构大型实验报告.doc

用户登录系统 2014年6月13日目录一实验内容3 1.1.实验目的 .3 1.2实验的数据结构及流程.3二 实验验证分析.72.1 LL型调整验证.7 2.2RR型调整验证.82.3LR型调整验证.9 2.4RL型调整验证.10 三、调试分析.11 3.1技术难点及解决方案.113.2印象深刻的调试错误及解决方法.11四、测试结果12 4.1用户登录.12 4.2用户注册.16 4.3删除用户.19 4.4极端数据的测试.21五、实验总结22一 实验内容1.1.实验目的 这次实验是让我们模拟用户登录系统。由于用户信息的验证频率很高，系统必须有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快捷。1.2实验的数据结构及流程1.2.1数据结构 系统用到了两个类AVLNode和AVLTree,其中AVLTree的唯一一个数据成员就是指向AVLNode结点的指针。 1.2.2流程图 主界面删除用户打印AVL树退出修改密码用户注册用户登录用户名存在吗用户名存在吗 删除成功添加成功输入新密码YN Y 1.2.3 函数间的调用关系main函数调用类的成员函数。插入新结点时，AVLInsert要根据平衡因子调用4个调整函数LL_Rotate、RR_Rotate、LR_Rotate和RL_Rotate函数。关键代码：if(a-bf=2)b=a-lchild;if(b-bf=1)p=LL_Rotate(a);elsep=LR_Rotate(a);else/此时a-bf的值应为-2b=a-rchild;if(b-bf=1)p=RL_Rotate(a);elsep=RR_Rotate(a);二 实验验证分析将用户信息存储在文件中，程序运行时从文件中读取，并建立 适的二叉树。注意：文件中每行输入三个字符，第一个字符为用户名，第二个字符为空格，第三个字符为密码。2.1LL型调整验证 在文件user.txt输入如下：运行程序，并选择4打印AVLTree，结果如下图：2. 2 RR型调整 在文件user.txt输入如下：运行程序，并选择4打印AVLTree，结果如下图：2.3 RL型调整 在文件user.txt输入如下： 运行程序，并选择4打印AVLTree，结果如下图：2.4 LR型调整在文件user.txt输入如下：运行程序，并选择4打印AVLTree，结果如下图：3 调试分析3.1 技术难点及解决方案 3.1.1插入新结点后如果二叉树失去平衡，如何找到最小不 平衡子树？ 在寻找新结点的插入位置时，始终令指针a指向离插入结点最近的且平衡因子不为0的结点，同时令指针f指向结点*a的父结点，如这样的结点不存在，则指针a指向根结点。由此可知，当插入新结点后如果二叉树失去平衡时，指针a所指向的结点就是最小不平衡子树的根。3.1.2新结点插入时，需修改哪些相关结点的平衡因子？如何修改？ 失去平衡的最小子树的根节点*a在插入新结点*s之前，平衡因子必然不为0，必然是离插入结点最近的且平衡因子不为0的结点。插入新结点后，需修改从结点*a到新结点路径上个结点的平衡因子。只需从*a的子结点*b开始，顺序扫描该路径上结点*p,若结点*s插入在*p的左子树上，*p的平衡因子由0变为1；否则新结点插入在*p的右子树上，*p的平衡因子由0变为-1.3.1.3 如何判断以*a为根的子树是否失去平衡？ 当结点*a的平衡因子为1（或-1）时，若新结点插入在结点*a的右（或左）子树中，左右子树等高，结点*a的平衡因子为0，则以*a为根的子树没有失去平衡；新结点插入在结点*a的左（或右）子树中，则以*a为根的子树失去平衡，因对以*a为根的最小不平衡子树进行平衡化调整。3.1.4 失去平衡后，如何确定旋转类型并作出相应的调整？ 当结点*a的平衡因子为2时，若*a的左孩子*b的平衡因子为1，表示新结点插入到结点*b的左子树中，应采用LL型调整，否则结点*b的平衡因子为-1，表示新结点插入到结点*b的右子树中，应采用LR型调整；当结点*a的平衡因子为-2时，若*a的左孩子*b的平衡因子为1，表示新结点插入到结点*b的左子树中，应采用RL型调整，否则结点*b的平衡因子为-1，表示新结点插入到结点*b的右子树中，应采用RR型调整；3.2 印象深刻的调试错误及解决方法 由于该项目需要建3个文件，类的声明放在AVLTree.h文件中，类的实现放在AVLTree.cpp文件中，main函数单独放在test.cpp文件中，其中在AVLTree.cpp文件中应使用#include AVLTree.h导入类的声明文件，而test.cpp只需使用#include AVLTree.h导入类的声明文件即可，而我当时错误的test.cpp使用#include AVLTree.cpp导入了类的实现文件，所以一直报错。我在它报错的位置查了很多次都没发现bug,最后在老师的帮助下才发现了问题所在。 我在插入新结点时，也一直报错，最后才发现在AVLNode的构造方法中并没把成员变量bf初始化为0，而插入新结点是需要根据bf的值做相应调整，所以一直报错。虽然这些都是小Bug,却花了我大量的时间查找错误。 四 测试结果下面进行的测试,文件user.txt存储的初始数据为：4.1用户登录运行程序，并按提示先选择4，打印出AVL树(这样做是方便登录)，选择1,进入登录界面，按提示分别输入用户名和密码，输入正确后，截图如下接着选择是否更新密码（只能输入Y或N）,当输入Y并输入重置密码后，截图如下这时，重新打开文件user.txt,会发现用户信息发生了更新：错误输入： 当输入的不是Y或N时，会输出“您的选择有错”4.2用户注册运行程序，并按提示先选择4，打印出AVL树(这样做是方便登录)，选择2进图注册界面,按提示分别输入要注册的用户名和密码，输入正确后,如果输入的用户名不存在，注册成功，并更新文件user.txt，否则注册失败。用户名已存在时：用户名不存在时这时，文件user.txt中的信息为：4.3删除用户运行程序，并按提示先选择4，打印出AVL树(这样做是方便登录)，选择2进图删除界面,按提示分别输入要注册的用户名，如果输入的用户名不存在，提示“您要删除的用户不存在!”；否则，删除成功，并更新文件user.txt，4.4极端数据的测试在user.txt中重新输入以下信息：运行程序，并按4打印AVL树，得到结果为：5 实验总结 通过两到三周的编写，我们终于用户登录系统。对于这次实验，心里还是蛮有信心的，前期花了大量的时间在类AVL