《AVL树模拟用户登录系统的实验报告 (2)》由会员分享，可在线阅读，更多相关《AVL树模拟用户登录系统的实验报告 (2)（35页珍藏版）》请在金锄头文库上搜索。
1、一.实验内容分析：1. 实验目的：模拟用户登录系统，在O (lgn)时间内完成用户登录、删除、修改等工 作。2. 设计思路：主要分以下四个类：AVLTreeNod :存储平衡树节点；AVLTre :AVL平衡树的主要实现算法；UserInfo:存储用户信息；Interface:界面,与用户交互；3. 流程图以及类的主要包含和调用关系：随机救测试与 STLmap被取立件构苣函弑主界面Interface删昧测试主界面登陆界面添加用户界面删除界面修改密玛界面析构函数Main函数有序散测试STLmap粒主二.实验验证分析AVLTree -*4 fJr插无节点暗踪节点构咨，创蜜树遍历输出文件标注：橙色为
2、类，靠为成员函勤绿邑为主夏汗刑可函数By-hufeiya(1) 输入的形式和输入值的范围;控制台的输入：证户户码 验用用密 登添- - - - - 1 2 3 4 0如图，输入为数字，超出范围将提示不正确并返回重新输入G:UsershufeiyaDocumentsVisual Studio文件的输入：程序会找寻当前目录的database.data文件，并读入数据，如果未找到则自创此文件，创建空树(2) 输出的形式；程序退出时析构函数保存文件到database.data并覆盖原文件。(3) 程序所能达到的功能；在O(lgn)时间内添加、查找、删除、修改用户信息。(4) 测试数据：本系统包含三个测
3、试函数样例：1. 顺序插入测试(分别在debug和release环境下和STL map比较速度)2. 随机插入测试(分别在debug和release环境下和STL map比较速度)3. 删除测试测试函数均在main文件里void randomTest();/随机数测试void orderTest();/顺序插入测试void deleteTest();/删除测试void main_interface();/主界面1,2均在debug模式下插入100W数据，在release模式下插入1000W数据。顺序插入的实现是用整数1 n转换为string，位数不够的在前面补0。测试结果：l.debug下顺序
4、插入测试:2.Release下顺序插入测试r G:User&hufeiyaDocumentsViSLial Studio Z01ZProjectsAVLsampleRel. - 口现在测试 浦输A.要宣找3.debug下随机插入测试4.release下随机插入测试实践证明map的红黑树在顺序插入测试时慢于我的avl树，但随机插入测试表现比AVL树 要好。3.删除数据的图形化表示（R L = 为平衡因子以检验正确性）G:UsershufeiyaDacjmentsVisual Studio8 = 7 =6 = 5 =4 = 38 =28 = 21 =2 = 18 R 15 =14 = 100 =
5、1 =下面删除3 （树中无3）：亳此兀素3不能删除8 =7 =6 =匚 4 =38 =28 =21 =2 =18 K15 =14 =103 =1 =还是一样，下面删除28 =7 = 6 =5 = 4 =38 = 28 =21 = 18 =15 L14 =100 = 1 =删除成功，下面删除78 L 6 = 5 =4 =38 = 2S = 21 =18 =15 L 14 = 100 =1 =删除成功。三.调试分析（1）讨论分析调试过程中的主要技术问题以及具体的解决方法（至少3个）；1. 代码重复问题：有重复的代码不是好代码。左右旋和左旋右旋有大量重复，经过分析发现左右 旋可以分解为先左旋后右旋，
6、但平衡因子调整方法不一。所以分解左旋和右旋为两 个函数，调整平衡因子单分一个函数。2. 空间占用问题：平衡因子只有3个取值却占了一个int 4个字节是极大的浪费，所以改用char 型。编程实践中发现树高也可以取消，也极大的节省了空间。3. 时间浪费问题：先调整平衡因子再旋转最后再调整平衡因子浪费时间，经分析后可以采取一些 代码上的改动而将第一次调整省略。（2）技术难点分析（至少3个）；1. 由于放弃树高调整平衡因子，所以平衡因子的调整是编程最困难之处，采用方法是根据插入子数是左子树还是右子树调整父亲的平衡因子。2. 删除时需先采用BST的删除方式，再分情况用类似AVL插入节点时的调整方法， 必
7、须完全搞懂BST和AVL才能正确地处理删除问题。3. 代码阅读问题：纯算法程序一般难以阅读，尤其是像AVL这类复杂算法，即使 是自己也是编了前面忘了后面，所以程序添加了海量的注释，每个函数每个重要语句都 有功能解说，代码命名取其意思，格式遵循cleanCode。（3）印象最深刻的3个调试错误，及修正方法；1. 最深的当然是访问了没初始化的内存！几乎90%调试问题都与此有关。大部分 非法访问内存经调试都归结于平衡因子的错误。解决方法是在纸上画出几个正确的例 子，再输入进程序调试，看平衡因子的错误具体地址和引起其错误的代码。反复调试修 改直到测试再大数据量也不会报错。2. 链接错误。好像是1005
8、，此错误的原因是.h文件内除了成员函数不能有其它函数。 原来是我用的友元重载比较函数（必须用友元，否则类对象比较时重载不匹配。）网上 查了好半天才知道的原因。解决方法：友元重载比较运算符函数放到cpp文件里。3. 头文件包含问题要彻底搞明白，.h文件必须加头文件卫士，.cpp必须不加而且不 能被 #include,。4. 测试结果：（1）展示程序的运行结果，包括输入和输出，分析数据的正确性；1.database.data文件（存放用户名密码）data base, data -记事本_ nX文件F）编辑旧梧式查看帮助fewew 4564 fewfew 541541 fvrbt 156 grger
9、h 341563 gthtfer 1545 gvrehb 41354 hufeiya 123456A2. 用户登录G:UsershufeiyaDocjmentsWisual Studio Z012Projei证户户码 验用用密 陆加 12 3 4 0 G:Uwrshu伯四。眼口州如13叫叫31印溯口201请输入新添加的账号，密码（0 M退回上级）F dasFsd. 54156415&-G:User&liufeiyaDocumentsVisual Studic登陆成功!请按任意键继续一.4. 删除用户G:UsershufeiyaDocumentsVisu-aI Studio 2012Pi青输入要
10、删除的账号，密码（0 口返回上级）erf erfet*raaaaa.4.更新用户 G:User&liufeiyaDocumentsVisuaI Studio 201请输入要更新的账号和旧密码S 0返回上级）（2）应用边界数据、或极端数据测试系统，分析结果的正确性。实验分析验证里已进行充分测试。5. 附录：附上源代码，并标明源代码的所属文件，并且源代码必须有注释。/AVLTreeNode.h/AVL树节点类功能：提供主键、左右子指针、父指针，平衡因子说明：平衡因子为char，节约空间（L相当于1，R相当于-1,=相当于0）修改时间：2013-12-25 14:29:44/#ifndef AVLT
11、reeNode_H#define AVLTreeNode_H#includeUserInfo.h”class AVLTreeNodepublic:UserInfo key;AVLTreeNode *left;AVLTreeNode *right;AVLTreeNode *parent; char balanceFactor;AVLTreeNode()left = 0;right = 0;parent = 0;balanceFactor =;AVLTreeNode(UserInfo s)key = s;left = 0;right = 0;parent = 0;balanceFactor =;#
12、endif/=/ AVLTree.h/ AVL平衡树，实现了添加、查找、图形输出等功能/ Author: hufeiya ZJUT/ 2013-12-4 14:38:04/ 2013-12-24 14:35:42 添加了删除方法/插入经过3KW数据严格测试，删除不严格测试/=#ifndef AVLTree_H#define AVLTree_H#include #include #include #include AVLTreeNode.h using namespace std;class AVLTreeprivate: public:AVLTree();析构函数。调用/插入元素。调用/图形输
13、入。调用/中序遍历修改文件。调用查找元素，返回地址。删除元素。调用AVLTree();void insert(AVLTreeNode *n);void graph();void inOrder(ofstream & fs);AVLTreeNode* find(UserInfo target);void remove(UserInfo key);private:AVLTreeNode *root;void ClearTree(AVLTreeNode *n); /清除所有元素void graphAux(AVLTreeNode *subtree, int a);/递归图形输出void inOrderAux(ofstream & fs,AVLTreeNode *subtree); /递归中序遍历void restoreAVL(AVLTreeNode *ancestor, AVLTreeNode *newNode); /添加节点后重建树void adjustBalanceFactors(AVLTreeNode *end, AVLTreeNode *start); /调整平衡因子(插入 时)void rotateLeft(AVLTreeNode *n); /左旋，插入删除共用void rotateRight(AVLTreeNode *n);/右旋，插入删除共用vo
