基于AVL的用户登录系统实验报告.doc

用户登录系统 计自1302 李林通 201326810313 2014.12.8 实验内容分析： 实验目的和要求： 【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。 【基本要求】 要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图； 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。 要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。 要求源程序中有相应注释； 不强制要求采用类模板，也不要求采用可视化窗口； 要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确； 要求采用Visual C++ 6.0及以上版本进行调试； 基本数据结构：采用二叉平衡查找树（AVL），采用了模板类，以用户名（IP）作为比较的关键词进行插入。二叉平衡查找树是在二叉有哪些信誉好的足球投注网站树（BST）的基础上进行了优化，使得树基本达到平衡。定义内部类Node来存储AVL树的节点信息。 class Node{ public: T date; // 记录节点的值 int balance,deep; // 表示节点的平衡值和它向下的最大深度 Node * left; // 指向左节点 Node * right; // 指向右节点 Node():balance(0),left(NULL),right(NULL),deep(1){} Node(T item):date(item),balance(0),left(NULL),right(NULL),deep(1){} }; 实验思路： 要创建一颗包含用户信息的树，要能适应频繁的查找，想到生活中登陆时都是先输入用户名，且每个人的用户名是唯一的，所以，我将用户名（string类型）作为AVL树的比较参数，这样就可以实现快速的插入、删除和查找，重定义User类的比较函数 bool operator (const User t1,const User t2) // 按 id 比较大小 { return t1.id t2.id; } AVL树是用模板类实现的，这样就可以直接比较两个用户类，方便了很多。 类： // 用户的类 class User{ public: string id; // 用户名 string pass; // 密码 User(); User(string a,string b = ); friend bool operator (const User t1,const User t2); // 按 id 比较大小 friend bool operator == (const User t1,const User t2); // id 相等，就算相等 friend ostream operator(ostream out,const User us); //重定义输出流 }; // AVL的类 template typename T class AVL{ class Node{ // 内部节点类 public: T date; // 节点的值 int balance , deep; // 节点的平衡值和深度 Node * left; Node * right; Node():balance(0),left(NULL),right(NULL),deep(1){} Node(T item):date(item),balance(0),left(NULL),right(NULL),deep(1){} }; typedef Node* NodePoint; public: NodePoint myRoot; // 根节点 AVL(); bool empty() const; bool se