数据结构大型实验报告---用户登录系统模拟姓名：金天昊班级：网络工程一班浙江工业大学计算机学院目录实验分析 (3)实验目的 (3)实验基本数据结构 (3)实验基本流程图 (3)输入的形式和输入值的范围 (4)输出的形式 (4)程序所能达到的功能 (4)调试分析 (5)讨论等系调试过程中的主要技术问题以及具体解决方法 (5)技术难点分析 (5)测试结果 (7)心得体会 (11)附录 (12)实验分析实验目的在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。

用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。

由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。

另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。

请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。

实验基本数据结构实验基本流程图输入的形式与输入值的范围用户名与密码均采用string形输出的形式界面输出选择框程序所能达到的功能模拟用户登入系统实现用户登录、注册、删除、修改密码以及信息的本地存储和读取。

调试分析讨论分析调试过程中的技术问题以及具体的解决方法①问题：AVL树元素的添加删除需要修改路径上的所有节点的平衡因子方法：引入一个栈类（Stack）用于将搜索目的节点路径上的节点依次压入栈中②问题：用户名与密码可能是数字也可能是字母亦可能是数字与字母的组合方法：统一采用string技术难点分析技术难点：实现二叉树的平衡，即树的旋转二叉树的旋转共四种，分别为左旋、右旋、左右旋、右左旋转，对应情况如下：左旋右旋左右旋右左旋测试结果用户的注册、登录、删除、修改密码以及信息的本地存储和读取customer.txt文件中）。

①用户登录②用户注册③用户删除④用户密码修改登录时测试不存在的用户或者错误的密码用户删除时验证密码错误提示删除失败修改密码时验证密码错误提示修改失败心得体会与大一不同，这一次的大型实验是我一个人独立完成的。

中间也遇到了些许困难，但通过自己的钻研以及查阅了相关的资料成功的解决了问题。

这个实验中最难的部分在于平衡旋转，平衡旋转使用在新建用户和删除用户上，期中尤为困难的是删除，这个环节中还需引入栈用于存储搜索目的用户过程中路径上的节点指针，从而达到从删除节点开始往根节点进行调整的操作。

通过这次大型实验我的编码能力得到了训练，熟悉了平衡二叉树的建立，也锻炼了算法的分析能力。

附录//==================================================================// Customer.h////==================================================================#include <iostream>using namespace std;#include "Stack.h"class CCustomer{public:CCustomer();~CCustomer();bool empty();//判空void remove();//删除用户void ChangePassword();//修改密码void Save();//保存用户信息到本地文本文件中bool search(string name);//判断用户是否已存在void insert(string name, string paw); //新增用户void entry(string name, string paw); //用于判断登陆时的帐号密码是否正确private:class CustomerNode{public:string username;string password;int balanceFactor;CustomerNode * left;CustomerNode * right;CustomerNode(){balanceFactor = 0;left = 0;right = 0;}CustomerNode(string name, string word){username = name;password = word;balanceFactor = 0;left = 0;right = 0;}};typedef CustomerNode *CustomerPointer;CustomerPointer Root;Stack<CustomerPointer> path;Stack<CustomerPointer> path2;void release(CustomerPointer TreeRoot);//析构函数的辅助函数void save_aux(CustomerPointer root);//保存用户信息的辅助函数void Rotation(int newBF, CustomerPointer root); //旋转函数，用于调整二叉树的结构void search2(string name, bool &flag, CustomerPointer &location,CustomerPointer &parent); //删除操作的辅助函数//左旋转函数CustomerPointer L_Rotate(CustomerPointer root){CustomerPointer lc;lc = root->right;root->right = lc->left;lc->left = root;if (lc->balanceFactor == -1){root->balanceFactor = 0;lc->balanceFactor = 0;}else{root->balanceFactor = -1;lc->balanceFactor = 1;}return lc;}//右旋转函数CustomerPointer R_Rotate(CustomerPointer root){CustomerPointer lc;lc = root->left;root->left = lc->right;lc->right = root;if (lc->balanceFactor == 1){root->balanceFactor = 0;lc->balanceFactor = 0;}else{root->balanceFactor = 1;lc->balanceFactor = -1;}return lc;}//左-右旋转函数CustomerPointer LR_Rotate(CustomerPointer root){CustomerPointer ptr = root->left;CustomerPointer lc = ptr->right;root->left = lc->right;ptr->right = lc->left;lc->left = ptr;lc->right = root;switch (lc->balanceFactor){case 0://情况1：新节点插入之前，原旋转根的左孩子没有右孩子，新插入的节点成为其右孩子root->balanceFactor = 0;ptr->balanceFactor = 0;break;case 1://情况2：新节点插入之前，原旋转根的左孩子有右孩子C，新节点被插入到C的左子树中root->balanceFactor = -1;ptr->balanceFactor = 0;case -1://情况3：新节点插入之前，原旋转根的左孩子有右孩子C，新节点被插入到C的右子树中root->balanceFactor = 0;ptr->balanceFactor = 1;break;}lc->balanceFactor = 0;return lc;}//右-左旋转函数CustomerPointer RL_Rotate(CustomerPointer root){CustomerPointer ptr = root->right;CustomerPointer lc = ptr->left;root->right = lc->left;ptr->left = lc->right;lc->right = ptr;lc->left = root;switch (lc->balanceFactor){case 0: //情况1：新节点插入之前，原根的右孩子没有左孩子，新插入的节点成为其左孩子root->balanceFactor = 0;ptr->balanceFactor = 0;break;case 1: //情况2：新节点插入之前，原根的右孩子有左孩子C，新节点被插入到C的右子树中root->balanceFactor = 0;ptr->balanceFactor = -1;case -1://情况3：新节点插入之前，原根的右孩子有左孩子C，新节点被插入到C的左子树中root->balanceFactor = 1;ptr->balanceFactor = 0;break;}lc->balanceFactor = 0;return lc;}};//================================================================== ==================================================================== //// Stack.h////================================================================== ==================================================================== #include <string>#include<iostream>using namespace std;template <typename DataType>class Stack{private:class Node{public:DataType data;Node *next;Node(DataType value,Node *link = 0):data(value),next(link){}};public:typedef Node * NodePointer;Stack();~Stack();bool empty();void push( DataType &value);DataType top() ;void pop();private:NodePointer myTop;};template <typename DataType>inline Stack<DataType>::Stack():myTop(0){}template <typename DataType>inline Stack<DataType>::~Stack(){Stack::NodePointer currPtr = myTop,nextPtr;while (currPtr != 0){nextPtr = currPtr->next;delete currPtr;currPtr = nextPtr;}}template <typename DataType>inline bool Stack<DataType>::empty(){return (myTop == 0);}template <typename DataType>inline void Stack<DataType>::push( DataType & value) {myTop = new Stack::Node(value,myTop);}template <typename DataType>inline DataType Stack<DataType>::top(){return (myTop->data);}template <typename DataType>inline void Stack<DataType>::pop(){Stack::NodePointer ptr = myTop;myTop = myTop->next;delete ptr;}//================================================================== ==================================================================== //// Customer.cpp//////================================================================== ==================================================================== #include "Customer.h"#include<string>#include<iostream>#include <fstream>using namespace std;CCustomer::CCustomer(){Root = 0;}CCustomer::~CCustomer(){release(Root);}void CCustomer::release(CustomerPointer TreeRoot){if (TreeRoot != 0){release(TreeRoot->left);release(TreeRoot->right);delete TreeRoot;}}//判空bool CCustomer::empty(){return Root == 0;}//删除用户void CCustomer::remove(){string name;string paw;cout << "请输入想删除的用户名："<<endl;cin >> name;while (!path.empty())path.pop();bool flag;CustomerPointer lc;CustomerPointer parent;search2(name, flag, lc, parent);if (!flag){//没有找到该用户；system("cls");cout << "该用户不存在" << endl;return;}cout<<"请输入该用户的密码："<<endl;cin>>paw;if (paw != lc->password){system("cls");cout<<"密码错误，删除失败"<<endl;return;}if (lc->left != 0 && lc->right != 0){ //如果要删除的节点有左右节点；CustomerPointer rchild = lc->right; //定义辅助指针rchild指向被删节点的右孩子；parent = lc;while (rchild->left != 0){ //寻找被删节点的中序后继节点，便于删除；path.push(rchild);//寻找时同样需要将访问路径上的节点压入栈中；parent = rchild;rchild = rchild->left;}lc->username = rchild->username; //交换被删节点与其后继节点的用户名与密码；lc->password = rchild->password;lc = rchild;}CustomerPointer lchild = lc->left; //指向lc的子树的指针if (lchild == 0){lchild = lc->right;//若左节点不存在，则指向右节点（右节点也可能为0）；}if (parent == 0){//若要删除的是根节点；Root = lchild;}else if (parent->left == lc) //若lc是parent的左节点；{parent->left = lchild;//则parent的左指针指向lchild；}else{//若lc是parent的右节点；parent->right = lchild;//则parent的右指针指向lchild；}string username = lc->username;delete lc;while (!(path.empty())){//修改平衡因子并旋转；CustomerPointer ptr = path.top();//从删除位置开始，逐层向上修改平衡因子，需要弹出栈中元素；if (username>ptr->username)//若删除的是左子树中的节点；ptr->balanceFactor++;else if (username<ptr->username) //若删除的是右子树中的节点；ptr->balanceFactor--;int newBF = ptr->balanceFactor;//修改后的平衡因子；path.pop();//删除栈顶元素；if (newBF != 0){ //如果修改后的平衡因子不为0；if (newBF == 1 || newBF == -1) //平衡因子为1或-1时说明删除后的树还是平衡的，结束循环；return;else if (newBF == 2 || newBF == -2)//如果为2或-2，则进行旋转；Rotation(newBF, ptr);}}system("cls");cout << "删除成功!" << endl;}void CCustomer::search2(string name, bool &flag, CustomerPointer &lc, CustomerPointer &parent){lc = Root;parent = 0;flag = false;while (!flag && lc != 0){if (name<lc->username){path.push(lc);parent = lc;lc = lc->left;}else if (lc->username<name){path.push(lc);parent = lc;lc = lc->right;}elseflag = true;}}//修改密码void CCustomer::ChangePassword(){string name;CustomerPointer lc = Root;cout << "请输入要修改密码的用户名"<<endl;cin >> name;bool flag = false;while (!flag && lc != 0){if (name<lc->username){lc = lc->left;}else if (name>lc->username){lc = lc->right;}else{flag = true; //找到该用户}}if (flag == false)//未找到该用户{{system("cls");cout << "该用户名不存在" << endl;}return;}else{string Pword1;string Pword2;cout <<"请输入原密码："<<endl;cin >> Pword1;if (Pword1 == lc->password)//密码正确{cout << "请输入新密码："<<endl;cin >> Pword2;lc->password = Pword2;system("cls");cout << "密码修改成功！" << endl;}else{system("cls");cout << "原密码错误！修改失败！" << endl;return;}}}bool CCustomer::search(string name){CustomerPointer lc = Root;bool flag = false;while (lc!= 0 && flag == false){if (name<lc->username){lc = lc->left;}else if (name>lc->username){lc = lc->right;}else{flag = true;//该用户已存在}}return flag;}void CCustomer::insert(string name, string paw) {while (!path.empty()){path.pop();}CustomerPointer lc = Root;CustomerPointer parent = 0;bool flag = false;while (lc != 0 && !flag){parent = lc;//保存当前节点if (name<lc->username){path.push(lc);lc = lc->left;}else if (lc->username<name){path.push(lc);lc = lc->right;}else{flag = true;}}if (!flag){lc = new CustomerNode(name, paw);if (parent == 0){//如果二叉树为空，则插入的节点为根节点；Root = lc;}else if (name<parent->username){//如果要插入的节点的用户名小于插入点中的用户名；parent->left = lc;}else{parent->right = lc;}}while (!path.empty()){//插入完成后，修改插入路径上的平衡因子，可能会旋转；CustomerPointer lc = path.top();//从插入位置开始，逐层向上修改平衡因子，需要弹出栈中元素；if (name>lc->username){//若插入到当前节点的右子树中时；(lc->balanceFactor)--;}else if (name<lc->username){//若插入到当前节点的左子树中时；(lc->balanceFactor)++;}int newBF = lc->balanceFactor;//修改后的平衡因子；CustomerPointer ptr = lc;path.pop();if (newBF == 0){//若修改后的平衡因子为0，则该树已经平衡，结束循环；break;}if (newBF == 2 || newBF == -2){//若修改后的平衡因子为2或者-2，则需要旋转；Rotation(newBF, ptr);return;}}}void CCustomer::entry(string name, string paw){CustomerPointer lc = Root;bool flag = false;//检查用户名是否匹配while (!flag && lc != 0){if (name<lc->username){lc = lc->left;}else if (lc->username<name){lc = lc->right;}else{//如果用户名相等；if (paw == lc->password){//密码相等；flag = true;system("cls");cout<<"登录成功"<<" "<<"当前用户："<<" "<<name<<endl;}else{flag = true;system("cls");cout<<"密码错误"<<endl;}}if(!flag){system("cls");cout<<"该用户不存在";}}}void CCustomer::Rotation(int newBF, CustomerPointer root) {//当平衡因子为2或者-2时则需要进行旋转；CustomerPointer newroot = 0;if (newBF == 2){//如果平衡因子为2时，可能进行右旋或者左右旋；int leftBF = root->left->balanceFactor;if (leftBF == -1){newroot = LR_Rotate(root);}else{newroot = R_Rotate(root);}}else if (newBF == -2){//如果平衡因子为-2时，可能进行左旋或者右左旋；int rightBF = root->right->balanceFactor;if (rightBF == 1){newroot = RL_Rotate(root);}else{newroot = L_Rotate(root);}}if (!(path.empty())){//此时的栈顶元素为原旋转根的双亲；CustomerPointer ptr = path.top();//弹出栈顶元素；if ((ptr->username)>(root->username)){ptr->left = newroot;}else{ptr->right = newroot;}}elseRoot = newroot;//如果栈是空的，说明原根为AVL的根，只需交换根；}void CCustomer::Save(){ofstream outfile("Customer.txt", ios::out);if (!outfile){cerr << "用户文件不存在，请检查" << endl;exit(1);}save_aux(Root);while (!path2.empty()){CustomerPointer lc = path2.top(); //一边出栈，一边将出来的元素读到文件中；outfile << lc->username << " " << lc->password << endl;path2.pop();}outfile.close();system("cls");cout<<"保存成功！";}void CCustomer::save_aux(CustomerPointer root){if(root != 0){path2.push(root);save_aux(root->left);save_aux(root->right);}}//================================================================== ==================================================================== //// main.cpp//////================================================================== ==================================================================== #include"Customer.h"#include<iostream>#include <fstream>using namespace std;int main(){ifstream infile("Customer.txt", ios::in);if (!infile){cerr << "用户信息不存在，请检查！" << endl;exit(1);}CCustomer C;string num;string name;string paw;while (infile >> name){infile >> paw;C.insert(name, paw);}infile.close();while (1){cout << " 欢迎进入登录系统" << endl;cout << "============================================" << endl;cout << "**************** 1.用户登录 **************" << endl;cout << "**************** 2.用户注册 **************" << endl;cout << "**************** 3.用户删除 **************" << endl; cout << "**************** 4.修改用户密码***********" << endl; cout << "**************** 5.保存******************" << endl; cout << "**************** 6.退出*******************" << endl; cout << " ========================================" << endl; cout << endl;cout << "请选择："<<endl;cin >> num;if (num == "1"){string name;string paw;cout << "请输入用户名："<<endl;cin >> name;cout << "请输入密码："<<endl;cin >> paw;C.entry(name,paw);}else if (num == "2"){string name;string paw;cout << "请要注册的用户名："<<endl;cin >> name;if (C.search(name) == true){system("cls");cout << "用户名已经存在，不能注册！" << endl;}else{cout << "请要注册用户的密码："<<endl;cin >> paw;system("cls");C.insert(name, paw);cout<<"注册成功！";}}else if (num == "3"){C.remove();}else if (num == "4"){C.ChangePassword();}else if (num == "5"){C.Save();}else if (num == "6"){system("cls");cout<<"退出成功"<<endl;break;}else{system("cls");cout << "无效的口令，请重新输入" << endl;}}return 0;}31。