数据结构大型实验报告

1、数据结构大型实验用户登录系统数据结构大型实验 用户登录系统姓名：*学号：*班级：*浙江工业大学计算机学院完成时间：2014.12.31一、实验内容分析1.实验目的【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用

2、户密码更新、用户添加和用户删除等。【基本要求】1. 要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类的二叉树结构和函数。同时要求根据二叉树的变化情况，进行相应的平衡操作，即AVL平衡树操作，四种平衡操作都必须考虑。测试时，各种情况都需要测试，并附上测试截图； 2. 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。3. 要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。4.

3、 要求源程序中有相应注释；5. 不强制要求采用类模板，也不要求采用可视化窗口；6. 要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确；7. 要求采用Visual C+ 6.0及以上版本进行调试；2.实验中的基本数据结构使用了平衡树(AVL)来存储用户信息，通过在插入和删除节点时左平衡和右平衡操作能使树始终保持平衡。以下为实验中涉及到的类。类名称成员变量及成员函数UserNode(用户信息类)private:string name; /用户名string password; /密码int h; /以该节点为根的子树高度 int bf; /平衡因子：

4、左树高度减去右树高度UserNode *left; /指向左子树的指针UserNode *right; /指向右子树的指针UserNode *parent; /指向父亲节点的指针public:friend class AVL;UserNode();UserNode(string n="",string p=""); int Lh(); /左子树高度 int Rh(); /右子树高度 void geth(); /更新以当前节点为根结点的子树高度 void getbf(); /更新当前节点的平衡因子 string getpswd(); /获取密码void s

5、etpswd(string); /修改密码 friend void save(UserNode*,ostream&); /输出数据AVL(功能类)private:UserNode *root;public:AVL():root(NULL) /构造函数bool empty() const; /判空 UserNode* find(string item); /查找节点 void LRotate(UserNode*,UserNode*); /左旋 void RRotate(UserNode*,UserNode*); /右旋 void LRRotate(UserNode*,UserNode*,

6、UserNode*);/左右旋 void RLRotate(UserNode*,UserNode*,UserNode*);/右左旋 void update(UserNode*); /调整平衡void insert(string,string); /插入节点 bool Delete(UserNode*); /删除节点 void printNode(UserNode* ,int ); /打印一个节点 void print(); /打印树 friend istream& operator >> (istream&,AVL&); /输入文件 friend ostre

7、am& operator << (ostream&,AVL&); /输出文件Menu(界面菜单类)private:AVL user;public:Menu(); /构造函数void mainmenu(); /主菜单 void show(); /查看所有用户 void load(); /登陆 void regist(); /注册 void Change(UserNode*); /修改密码 void Del(UserNode*); /删除用户 void close(); /将用户保存到txt中3.程序流程图主菜单登陆注册更改密码删除用户查看所有用户退出登陆返回主

8、菜单重新注册查看所有用户退出退出查看所有用户返回主菜单退出4.类及类间关系UserNodeAVLmenu5.主要函数间调用关系Menu menumenu.mainmenu()Load()registChange()Del()show()close()Main()AVL:find()Menu()Close()Yes其他AVL:Delete(UserNode*)AVL:insert(string,string)UserNode:setpswd(string)NoInsert(string na, string pswd)UserNode *item=new UserNode(na,pswd);up

9、date(item->parent)LRotate(UserNode*A ,UserNode* B)RRotate(UserNode*A,UserNode* B)LRRotate(UserNode*A ,UserNode* B)RLRotate(UserNode*A ,UserNode* B)插入函数，参数为用户名、密码定义用户节点更新插入节点路径上的节点四种旋转方式判断：Delete(UserNode* )（删除函数）删除节点后更新树方式相同，但是删除方式为将要删除的节点与其右子树中最小的节点交换，所以要分右子树是否为空两种情况讨论。二、实验验证分析1.输入的形式和输入值的范围用户名类

10、型：string 密码类型：string2.输出的形式输出的形式都是字符串，并通过换行符(n)，水平制表符(t)等来规范输出,实现美观性.下面截图演示.3.程序所能达到的功能a.用户登录; b.用户密码更新; c用户添加(注册) d.用户删除; e.查看所有用户4.测试数据(包括正确的输入及其输出结果和含有错误的输入及其输出结果)在主菜单输入1则进入登陆界面当输入数据非法时则提醒重新输入其他界面类似三、调试分析1.讨论分析调试过程中的主要技术问题以及具体的解决方法（至少个）a)在用户修改密码时由于密码时私有数据，无法修改，登陆时也无法判断密码是否正确；解决方法：定义两个函数getpswd()和

11、setpswd(string)分别用于获取密码和修改密码；b)关于文件的输入输出；解决方法：参考了上学期的C+大型实验c)有关调整树平衡时左右旋和右左旋；解决方法：结合网上和书中解释，先手画过程在写代码，再根据代码画过程。2.技术难点分析（至少个）a)关于平衡因子的计算，原本UserNode类中int型的成员变量只有平衡因子，如何计算无从入手；后来又添加了变量h(高度)，在每次某个节点有调整后就更新它的高度，同时更新平衡因子；b)简单左旋（右旋），假设A表示离插入项最近的具有平衡因子-2（+2）的祖先节点，B表示A的右（左）孩子，需要重新设置3条链：(1)另A的父亲指向B；(2)另A的右链等于

12、B的左链（另A的左链等于B的右链）；(3)另B的左（右）链指向A；左旋具体代码实现如下：其中geth()和getbf()函数分别为更新高度和平衡因子；左-右旋（右-左旋），假设A表示离插入项最近的具有平衡因子+2（-2）的祖先节点，B表示A的左（右）孩子，C表示B的右孩子，需要重新设置6条链：(1)另B（A）的右链等于C的左链； (2)另A（B）的左链等于C的右链；(3)另A的父亲指向C;(4)另C的右（左）链指向A;(5)另B的父亲指向C;(6)另C的左（右）链指向B；左-右旋具体代码实现如下：c)调整平衡，从当前节点向上调整，当找到不平衡节点时，根据平衡因子和不平衡状态判断使用哪种旋转方法

13、，具体代码实现及判断方法如下：d)删除节点，分该节点是否有右子树两种情况讨论；(1)没有右子树：先判断删除节点是否为根结点，若是，则直接另根结点指向删除节点的左子树；否则另删除节点的父亲节点的左子树或右子树（根据删除节点为其的左孩子还是右孩子）等于删除节点的左子树，然后从删除节点的父亲节点开始调整平衡；具体代码实现如下：其中pa为删除节点的父亲节点；(2)有右子树：将当前节点与其右子树中最左边的节点(设为p)交换，然后只需改变一条链，即另p的父亲节点左子树或右子树（根据p为其的左孩子还是右孩子）等于p的右子树(因为p为最左边的节点，所以没有左子树)，然后从p的父亲节点开始调整平衡；具体代码实现

14、如下：3.印象最深刻的个调试错误，及修正方法a)忘记考虑在选择操作时有错误输入的情况，导致输入不正确时程序退出；修正方法：将输入数据从int改为string型，在进行是否合法判断，若不合法，提醒重新输入；b) 总是忘记父亲节点的存在，在删除节点时，忘记将该节点的右子树的父亲节点指向该节点的父亲节点，导致删除用户时第一次成功，第二次就程序就直接崩溃；c)注册新账户时，发现每次注册成功后查看所有用户都没有新注册的账户，以为是插入函数写错了，调了半天才发现原来是注册时没有调用插入函数；d)只在程序退出时保存文件，导致当用户数据发生变化后中途查看txt时，没有及时保存；修正方法：在每次用户数据发生变化

15、时都调用输出文件的函数；e)txt中有用户数据，查看用户时却为空；修正方法：在menu的构造函数中读入用户数据。四、测试结果1.展示程序的运行结果，包括输入和输出，分析数据的正确性；主界面输入1，登陆界面登录失败分两种情况1.用户名不存在2.密码错误登陆成功输入1，修改密码修改成功输入2，删除用户删除前删除后以上为输入3，查看所有用户实现主菜单输入2，注册注册失败分两种情况 1.用户名已存在2.两次密码输入不同注册成功2.应用边界数据、或极端数据测试系统，分析结果的正确性。1)左旋在一棵空树中按次序插入d,h,k;ddhdhkdhkd不平衡,旋转程序内先插入d,h再插入k旋转2)右左旋继续插入

16、f,e;dhkfdhkfeehkfdd不平衡,旋转程序内先插入f再插入e旋转3)左右旋继续插入g;ehkfdgefhkdgh不平衡,旋转程序内插入g旋转4)右旋继续插入aefhkdgadfhkagee不平衡,旋转程序内插入a旋转以上结果均正确五、附录UserNode.h:#ifndef USERNODE#define USERNODE#include<iostream>#include<string>using namespace std;class UserNodeprivate:string name; /用户名 string password; /密码 int h

17、; /以该节点为根的子树高度 int bf; /平衡因子：左树高度减去右树高度UserNode *left; /指向左子树的指针UserNode *right; /指向右子树的指针UserNode *parent; /指向父亲节点的指针public:friend class AVL;UserNode();UserNode(string n="",string p=""); int Lh(); /左子树高度 int Rh(); /右子树高度 void geth(); /更新以当前节点为根结点的子树高度 void getbf(); /更新当前节点的平衡因子

18、string getpswd(); /获取密码void setpswd(string); /修改密码 friend void save(UserNode*,ostream&); /输出数据 ;#endifUserNode.cpp:#include<iostream>#include"UserNode.h"using namespace std;UserNode:UserNode(string n,string p) /构造函数 name=n;password=p;h=1;bf=0;left=right=parent=NULL;int UserNode:L

19、h() /左子树高度 return left=NULL?0:left->h;int UserNode:Rh() /右子树高度return right=NULL?0:right->h;void UserNode:geth() /更新以当前节点为根结点的子树高度 h=max(Lh(),Rh()+1;void UserNode:getbf() /更新当前节点的平衡因子 bf=Lh()-Rh();string UserNode:getpswd() /获取密码return password;void UserNode:setpswd(string pswd) /修改密码 password=p

20、swd;void save(UserNode* item,ostream &output) /输出数据 if (item=NULL) return;output<<item->name<<" "<<item->password<<"n"save(item->left,output);save(item->right,output);function.h:#ifndef FUCTION#define FUCTION#include<iostream>#include

21、"UserNode.h"using namespace std;class AVLprivate:UserNode *root;public:AVL():root(NULL) /构造函数bool empty() const; /判空 UserNode* find(string item); /查找节点 void LRotate(UserNode*,UserNode*); /左旋 void RRotate(UserNode*,UserNode*); /右旋 void LRRotate(UserNode*,UserNode*,UserNode*); /左右旋 void RLRo

22、tate(UserNode*,UserNode*,UserNode*); /右左旋 void update(UserNode*); /调整平衡void insert(string,string); /插入节点 bool Delete(UserNode*); /删除节点 void printNode(UserNode* ,int ); /打印一个节点 void print(); /打印树 friend istream& operator >> (istream&,AVL&); /输入文件 friend ostream& operator <<

23、; (ostream&,AVL&); /输出文件 ;#endiffunction.cpp:#include<iostream>#include<iomanip>#include"function.h"using namespace std;bool AVL:empty() const /判空 if(root=NULL) return 1;return 0;UserNode* AVL:find(string item) /查找节点UserNode* cur=root;while(cur!=NULL)if(item<cur->

24、name) cur=cur->left;else if(item>cur->name) cur=cur->right;else return cur;return NULL;void AVL:LRotate(UserNode* A,UserNode* B) /左旋 B->parent=A->parent;if(A->parent!=NULL)if(A->parent->left=A) A->parent->left=B;else A->parent->right=B;A->parent=B;A->righ

25、t=B->left;if(B->left!=NULL) B->left->parent=A;B->left=A;A->geth();B->geth();A->getbf();B->getbf();void AVL:RRotate(UserNode* A,UserNode* B) /右旋 B->parent=A->parent;if(A->parent!=NULL)if(A->parent->left=A) A->parent->left=B;else A->parent->right=B

26、;A->parent=B;A->left=B->right;if(B->right!=NULL) B->right->parent=A;B->right=A;A->geth();B->geth();A->getbf();B->getbf();void AVL:LRRotate(UserNode* A,UserNode* B,UserNode* C) /左右旋 C->parent=A->parent;if(A->parent!=NULL)if(A->parent->left=A) A->pare

27、nt->left=C;else A->parent->right=C;A->left=C->right;if(C->right!=NULL) C->right->parent=A;B->right=C->left;if(C->left!=NULL) C->left->parent=B;C->right=A;A->parent=C;C->left=B;B->parent=C;A->geth();B->geth();C->geth();A->getbf();B->ge

28、tbf();C->getbf();void AVL:RLRotate(UserNode* A,UserNode* B,UserNode* C) /右左旋 C->parent=A->parent;if(A->parent!=NULL)if(A->parent->left=A) A->parent->left=C;else A->parent->right=C;A->right=C->left;if(C->left!=NULL) C->left->parent=A;B->left=C->right

29、;if(C->right!=NULL) C->right->parent=B;C->left=A;A->parent=C;C->right=B;B->parent=C;A->geth();B->geth();C->geth();A->getbf();B->getbf();C->getbf();void AVL:update(UserNode* item) /调整平衡for(UserNode* cur=item;cur!=NULL;cur=cur->parent)cur->geth();cur->ge

30、tbf();if(cur->bf=2) /找到不平衡点 if(cur->left->Lh()>=cur->left->Rh() RRotate(cur,cur->left); /在左孩子的左子树中，右旋 else LRRotate(cur,cur->left,cur->left->right); /在左孩子的右子树中，左右旋 else if(cur->bf=-2) /找到不平衡点 if(cur->right->Lh()<=cur->right->Rh() LRotate(cur,cur->ri

31、ght); /在右孩子的右子树中，左旋 else RLRotate(cur,cur->right,cur->right->left); /在右孩子的左子树中，右左旋 if(cur->parent=NULL) root=cur; /更新根结点 void AVL:insert(string na,string pswd) /插入节点 UserNode *item=new UserNode(na,pswd);UserNode* cur=root;if(root=NULL) /当前树为空 root=item;return;while(cur!=NULL)if(item->

32、name<cur->name) /比当前值小，进入左子树 if(cur->left=NULL) /找到插入位置 cur->left=item;item->parent=cur;break; else cur=cur->left;else if(item->name>cur->name) /比当前值大，进入右子树 if(cur->right=NULL) /找到插入位置 cur->right=item;item->parent=cur;break; else cur=cur->right;update(item->

33、parent); /更新路径上的节点 bool AVL:Delete(UserNode* item) /删除节点 ，删除成功返回1 UserNode* pa;if(item=NULL) return 0;pa=item->parent;if(item->right=NULL) /如果右子树为空 if(pa=NULL) /item为根结点 root=item->left;if(item->left!=NULL) item->left->parent=NULL;delete item;return 1;if(pa->left=item) pa->le

34、ft=item->left;else pa->right=item->left;if(item->left!=NULL) item->left->parent=pa;delete item;update(pa);elseUserNode* p;p=item->right;while(p->left!=NULL) p=p->left; /找到item节点右子树中最小的节点 pstring tmp;tmp=item->name;item->name=p->name;p->name=tmp; /交换用户名 tmp=item

35、->password;item->password=p->password;p->password=tmp; /交换密码 pa=p->parent;if(pa->left=p) pa->left=p->right; /删除p else pa->right=p->right;if(p->right!=NULL) p->right->parent=pa;delete p;update(pa);return 1;void AVL:printNode(UserNode* item,int deep) /打印一个节点 if(i

36、tem!=NULL)printNode(item->right,deep+1);cout<<setw(4*deep)<<" "cout<<item->name<<"n"printNode(item->left,deep+1);void AVL:print() /打印树 printNode(root,0);istream& operator >>(istream &input,AVL &t)/输入文件，读取用户同时插入树 string name,passw

37、ord;while(input>>name>>password) t.insert(name,password);return input;ostream& operator <<(ostream &output,AVL &t) /输出文件，将用户保存到txt中 save(t.root,output);return output;menu.h:#ifndef MENU#define MENU#include"function.h"class Menuprivate:AVL user;public:Menu(); /

38、构造函数void mainmenu(); /主菜单 void show(); /查看所有用户 void load(); /登陆 void regist(); /注册 void Change(UserNode*); /修改密码 void Del(UserNode*); /删除用户 void close(); /将用户保存到txt中;#endifmenu.cpp:#include<iostream>#include<fstream>#include"function.h"#include"menu.h"using namespace

39、std;Menu:Menu()ifstream fin("data.txt");fin>>user;fin.close();void Menu:mainmenu() /主菜单system("cls"); cout<<"nnnnnnnttt 欢迎进入用户登录系统n"cout<<"tt=n"cout<<"tt请选择操作：nnn"cout<<"tttt1.登陆n"cout<<"tttt2.注册n&qu

40、ot;cout<<"tttt3.查看所有用户n"cout<<"tttt4.退出nnn"cout<<"tt=n"cout<<"tt输入14: "string ch;cin>>ch;while(ch.length()!=1|ch>"4"|ch<"1")cout<<"tt输入错误！请重新输入14: "cin>>ch;int d=ch0-'0'switc

41、h(d)case 1:load();break;case 2:regist();break;case 3:show();break; case 4:close();break;void Menu:show() /查看所有用户system("cls"); user.print();cout<<"nnntt=n"cout<<"tt请选择操作：n"cout<<"tttt1.返回主菜单n"cout<<"tttt2.退出n"cout<<"

42、;tt=n"cout<<"tt输入12: "string ch;cin>>ch;while(ch.length()!=1|ch>"2"|ch<"1")cout<<"tt输入错误！请重新输入12: "cin>>ch;int d=ch0-'0'switch(d)case 1:mainmenu();break;case 2:close();break;void Menu:load() /登陆 string name,password;s

43、ystem("cls");cout<<"nnnnnnnttt 欢迎进入用户登录界面n"cout<<"tt=nnn"cout<<"ttt请输入用户名: "cin>>name;cout<<"nttt请输入密码: "cin>>password;UserNode* p;p=user.find(name); system("cls");if(p!=NULL&&password=p->getps

44、wd()cout<<"nnnnnnntttt登录成功！n"cout<<"tt=n"cout<<"tt请选择操作：nnn"cout<<"tttt1.更改密码n"cout<<"tttt2.删除用户n"cout<<"tttt3.查看所有用户n"cout<<"tttt4.返回主菜单n"cout<<"tttt5.退出nnn"cout<<&q

45、uot;tt=n"cout<<"tt输入15: "string ch;cin>>ch;while(ch.length()!=1|ch>"5"|ch<"1")cout<<"tt输入错误！请重新输入15: "cin>>ch;int d=ch0-'0'switch(d)case 1:Change(p);break;case 2:Del(p);break;case 3:show();break;case 4:mainmenu();brea

46、k; case 5:close();break;elseif(p=NULL) cout<<"nnnnnnntttt该用户名不存在！n"else if(password!=p->getpswd() cout<<"nnnnnnntttt密码错误！n"cout<<"tt=n"cout<<"tt请选择操作：nnn"cout<<"tttt1.重新登陆n"cout<<"tttt2.注册n"cout<<

47、;"tttt3.查看所有用户n"cout<<"tttt4.退出nnn"cout<<"tt=n"cout<<"tt输入14: "string ch;cin>>ch;while(ch.length()!=1|ch>"4"|ch<"1")cout<<"tt输入错误！请重新输入14: "cin>>ch;int d=ch0-'0'switch(d)case 1:loa

48、d();break;case 2:regist();break;case 3:show();break;case 4:break;void Menu:regist() /注册 string name,password,password2;int f=0; system("cls");cout<<"nnnnnnnttt 欢迎进入用户注册界面n"cout<<"tt=nnn"cout<<"ttt请输入想要注册的用户名: "cin>>name;cout<<&quo

49、t;nttt请输入密码: "cin>>password;cout<<"nttt请确认密码: "cin>>password2;UserNode* p;p=user.find(name);system("cls");if(p=NULL&&password=password2)user.insert(name,password);close();cout<<"nnnnnnntttt 注册成功！n"f=1;else if(p!=NULL) cout<<&qu

50、ot;nnnnnnnttt 该用户名已存在,注册失败！n"f=2;else if(password!=password2) cout<<"nnnnnnnttt 两次密码不同,注册失败！n"f=3;cout<<"tt=n"cout<<"tt请选择操作：nnn"cout<<"tttt1.登陆n"cout<<"tttt2.重新注册n"cout<<"tttt3.查看所有用户n"cout<<&

51、quot;tttt4.退出nnn"cout<<"tt=n"cout<<"tt输入14: "string ch;cin>>ch;while(ch.length()!=1|ch>"4"|ch<"1")cout<<"tt输入错误！请重新输入14: "cin>>ch;int d=ch0-'0'switch(d)case 1:load();break;case 2:regist();break;case 3:show();break;case 4:close();break;default:regist();break;void Menu: