1、用户系统数据结构大型实验 2023/20231 实验题目 学生姓名 主要工作 树的结构、框架编写 负责人 学生班级 任课教师 提交日期 计算机科学与技术学院用户系统 实验题目和要求：【问题描述】在效劳器系统时，都需要验证用户名和密码，如telnet远程效劳器。用户输入用户名和密码后，效劳器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户系统，其功能要求包括用户
2、、用户密码更新、用户添加和用户删除等。【根本要求】要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图；要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，那么类的声明和实现都放在.h文件中。要求源程序中有相应
3、注释；不强制要求采用类模板，也不要求采用可视化窗口；要求测试例子要比拟详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，说明各个功能的执行正确；要求采用Visual C+ 6.0及以上版本进行调试； 设计思路： 系统总体设计： 采用平衡二叉查找树AVL，以用户名IP作为比拟的关键词进行插入。平衡二叉查找树是在二叉搜索树BST的根底上进行了优化，使得树根本到达平衡。定义内部类userNode来存储AVL树的节点信息。系统功能设计：要创立一颗包含用户名和用户密码的二叉树，要能适应频繁的查找，因为每个用户名是唯一的，将用户名string类型作为AVL树的比拟参数，这样就可以实现快速的插入、删除
4、和查找，重定义userNode类的比拟函数。AVL树是用模板类实现的，这样就可以直接比拟两个用户类，方便了很多。图1 系统功能结构图类的设计：/ 节点的类class userNodeprivate:string name;string password; short int height; public:userNode xleft;userNode xright;userNode(const string &name,const string &password);userNode(const userNode & temp);void setName(const string &name)
5、;void setPassword(const string &password);string getName();string getPassword();int getHeight();void changeHeight(const int height);/改变树的高度bool checkName(const string &name);/ 树的类class treeprivate:userNode xroot;public:tree();tree();void insert_node(userNode x&t ,userNode &temp); void insert_node(us
6、erNode &temp); /新建一个节点void remove(userNode x&r,userNode x&temp);void remove(userNode x&temp);/删除一个节点void clear(userNode xt);void clear();void print();void print(int index,userNode xr);/输出一棵树void Print();void Print(ofstream &ofile,userNode x&r);/写入文件void rotateL(userNode x&r);/左旋void rotateR(userNode
7、 x&r);/右旋void rotateDoubleLR(userNode x&r);/左右旋void rotateDoubleRL(userNode x&r);/右左旋void rightBalance(userNode x&r);void leftBalance(userNode x&r);userNode xfindNode(string s);/搜索一个节点userNode xsearchLeftMaxNode(userNode x&r,userNode x&R); ;/ 框架类 图2 类的调用 调试分析：1.技术难点分析：1查询操作时，怎么能找到相应用户的节点？考虑到用户名的唯一性，
8、所以将用户名作为AVL树的关键词，以字符串来比拟大小，进行排序，重定义userNode类的比拟操作符，只比拟IP,因此，在查询的时候，新建一个userNode的对象，其IP赋值为所要查询的IP，然后调用查找函数，可找到对应的点2AVL树的实现看书，上网查询。先了解二叉查找树BST的实现，二叉查找树BST是一种很好的数据结构，它的特点是，对其任一节点，都满足该节点的左子树的所有点的值都小于该节点，而右子树那么是大于。我采用链表来实现它，创立关于节点的一个类 Node ，内含描述该节点的值，及左右指针。我定义 insert_node() 函数来实现新节点的插入。AVL树相对于BST树，多了平衡两字
9、，树都有高度，而AVL树就是要求每一个节点的左子树和右子树的高度差不超过1，这样就能使其尽可能的减小整棵树的高度，使时间复杂度能稳定在O(logN), 但我们不可能去约束用户的输入，因此，引入了四种旋转：是新插入的节点 图3 右旋 图4 左旋 图5 先右旋再左旋 图6 先左旋再右旋修改密码或删除用户后如何返回上一界面？经反复修改，未果，遂放弃。调试错误分析： 登陆时密码要正确。图7 用户界面 登陆时用户要存在 图8 用户不存在界面 新建用户名不能已存在 图9 用户名已存在界面测试结果分析：主界面 图10 主界面 界面 图11 界面 注册界面 图12 注册界面 树图 图13 树形图界面 修改密码
10、 图14 修改密码 删除用户 图15 删除用户界面附录：Node.h#include#include#include#include#includeusing namespace std; class userNodeprivate:string name;string password; short int height; public:userNode xleft;userNode xright;userNode(const string &name,const string &password);userNode(const userNode & temp);void setName(c
11、onst string &name);void setPassword(const string &password);string getName();string getPassword();int getHeight();void changeHeight(const int height);/改变树的高度bool checkName(const string &name);Tree.h#includenode.h#includeclass treeprivate:userNode xroot;public:tree();tree();void insert_node(userNode
12、x&t ,userNode &temp); void insert_node(userNode &temp); /新建一个节点void remove(userNode x&r,userNode x&temp);void remove(userNode x&temp);/删除一个节点void clear(userNode xt);void clear();void print();void print(int index,userNode xr);/输出一棵树void Print();void Print(ofstream &ofile,userNode x&r);/写入文件void rotat
13、eL(userNode x&r);/左旋void rotateR(userNode x&r);/右旋void rotateDoubleLR(userNode x&r);/左右旋void rotateDoubleRL(userNode x&r);/右左旋void rightBalance(userNode x&r);void leftBalance(userNode x&r);userNode xfindNode(string s);/搜索一个节点userNode xsearchLeftMaxNode(userNode x&r,userNode x&R); ;Frame.h#includetre
14、e.hclass frametree myTree;public:frame();void view();/显示主界面void Login();/界面void testInsert();/插入一个节点void printTree();/画出一棵树;Node.cpp#includenode.h void userNode:setName(const string &name)this-name=name;void userNode:setPassword(const string &password)this-password=password;string userNode:getName()return name;string