基于C语言实现的登陆验证【100013034】

# 1实验题目与要求 【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。 【基本要求】 要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图； 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。 要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。 不强制要求采用类模板，也不要求采用可视化窗口；要求源程序中有相应注释； 要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确； 【实现提示】 用户信息(即用户名和密码)可以存储在文件中，当程序启动时，从文件中读取所有的用户信息，并建立合适的查找二叉树； 验证过程时，需要根据登录的用户名，检索整个二叉树，找到匹配的用户名，进行验证；更新用户密码时，也需要检索二叉树，找到匹配项后进行更新，同时更新文件中存储的用户密码。 添加用户时，不仅需要在文件中添加，也需要在二叉树中添加相应的节点；删除用户时，也是如此； 【运行结果要求】要求能够实现用户登录验证、添加用户、删除用户和更新用户密码功能，实验报告要求有详细的功能测试截图。 验收要求：1、通过管理员权限，正向打印用户信息的平衡二叉查找树； 2、管理员在删除、插入用户信息后，需重新旋转调整AVL树，并正向打印； 3、用户只能看到自己的信息，只能更改密码。 【考核要求】要求程序能正常运行，全面完成题目要求。 【题目难度】难，成绩等级高 # 2设计思路 ## 2.1系统总体设计 系统需要实现“用户登陆系统”的功能，由于线性表的时间复杂度为O(n)，效率较低，不足以满足大容量高并发的需求，所以使用二叉搜索树的结构进行数据存储。由于二叉存储树可能存在不平衡的问题，影响数据结构的效率，所以我们使用Avl树进行存储。 ## 2.2系统功能设计  ### 2.2.1用户登陆验证功能 用户输入用户名和密码，系统会在数据库中查找该用户。如果用户不存在或者密码错误，发出相应的提示，否则根据用户所属的类型（管理员/普通用户），完成登陆 ### 2.2.2添加用户功能 管理员用户有权限添加用户，输入要添加的用户名和密码，如果在数据库中存在同名用户，提示添加失败，否则将用户信息存放到数据库里 ### 2.2.3显示用户功能 管理员用户有权限显示用户，使用打印命令，可以正向打印出Avl树中存储的用户信息。 ### 2.2.4删除用户功能 管理员用户有权限删除用户，输入要删除的用户名称，如果数据库中存在该用户，就将其删除，否则提示错误。 ### 2.2.5修改密码功能 普通用户可以更改自己的密码 ## 2.3类的设计  ### 2.3.1AvlTree类 AvlTree类定义了一棵Avl树，包含了Node节点和ShadowTreeNode节点，包含了用影子树正向打印树，旋转节点，添加节点等功能。 #### 2.3.1.1Save函数  在 save 函数中，我们使用了 fstream 对象来进行文件的输出，使用了中序遍历的方法，先保存中间节点的内容，然后递归保存左右子树。使用中序遍历而非其他遍历的好处是，在读取文件重新构建树的时候，前序遍历保存的文件可以避免树的旋转。 #### 2.3.1.2AddNode函数  在插入新的节点时，我们需要一层一层向下寻找插入点，进行插入。完成插入后，如果树失衡了，要使用 [Spin ](#_Spin函数)函数进行调整。 #### 2.3.1.3Remove函数  在执行删除操作的时候，我们也一层一层向下找，找到那个要被删除的节点。然后，视情况， 在左子树或右子树找到最大或最小的节点，将其移到根节点的位置，再将原来的节点删除， 即实现了删除特定节点的功能。完成删除后，如果树发生了失衡，要调用 [Spin ](#_Spin函数)函数进行调整 #### 2.3.1.4Print函数  Print 函数使用了影子树实现 Avl 树的正向打印。影子树是通过保存树中每一个节点的横纵坐标信息，来正向打印二叉树的一种数据结构。通过影子树打印，可以获取更好的打印效果。 #### 2.3.1.5Spin函数 LeftSpin 函数和 RightSpin 函数互成镜像，所以我只介绍右旋。  看这棵树，它原本是平衡的。由于节点 25 插入，这棵树变的不平衡。25 被插在 35 节点左子树的左子树上，所以我们只需要进行一次右旋操作。  首先，使用 left 指针指向左节点，即 30  将根节点的左指针指向 30 节点的 right。可以看到，尽管 30 节点对应的右指针是 nullptr， 我在这里将其画出，所得结构显得清晰。  将 left 节点的右指针指向 root  返回左节点的指针，让上层节点对应的指针指向前面提到的 left 节点  整理树的结构，删除已经消失的指针的之前加上的nullptr ![](https://www.writebug.com/myres/static/uploads/2021/10/31/9c1b38e5dcf638c1a0713e0118e60c99.wri