数据结构大型实验报告

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

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

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

4、Node *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 setpswd(string); /修改密码 friend void save

5、(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*,UserNode*);/左右旋 void RLRotate(UserNode*,Us

6、erNode*,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 parent)LRotate(UserNode*A ,UserNode* B)RRotate(Use

7、rNode*A,UserNode* B)LRRotate(UserNode*A ,UserNode* B)RLRotate(UserNode*A ,UserNode* B)插入函数，参数为用户名、密码定义用户节点更新插入节点路径上的节点四种旋转方式判断：Delete(UserNode* )（删除函数）删除节点后更新树方式相同，但是删除方式为将要删除的节点与其右子树中最小的节点交换，所以要分右子树是否为空两种情况讨论。二、实验验证分析1.输入的形式和输入值的范围用户名类型：string 密码类型：string2.输出的形式输出的形式都是字符串，并通过换行符(n)，水平制表符(t)等来规范输出,实

8、现美观性.下面截图演示.3.程序所能达到的功能a.用户登录; b.用户密码更新; c用户添加(注册) d.用户删除; e.查看所有用户4.测试数据(包括正确的输入及其输出结果和含有错误的输入及其输出结果)在主菜单输入1则进入登陆界面当输入数据非法时则提醒重新输入其他界面类似三、调试分析1.讨论分析调试过程中的主要技术问题以及具体的解决方法（至少个）a)在用户修改密码时由于密码时私有数据，无法修改，登陆时也无法判断密码是否正确；解决方法：定义两个函数getpswd()和setpswd(string)分别用于获取密码和修改密码；b)关于文件的输入输出；解决方法：参考了上学期的C+大型实验c)有关调

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

10、为更新高度和平衡因子；左-右旋（右-左旋），假设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)调整平衡，从当前节点向上调整，当找到不平衡节点时，根据平衡因子和不平衡状态判断使用哪种旋转方法，具体代码实现及判断方法如下：d)删除节点，分该节点是否有右子树两种情况讨论；(1)没有右子树：先判断删除节点是否为根结点，若是

11、，则直接另根结点指向删除节点的左子树；否则另删除节点的父亲节点的左子树或右子树（根据删除节点为其的左孩子还是右孩子）等于删除节点的左子树，然后从删除节点的父亲节点开始调整平衡；具体代码实现如下：其中pa为删除节点的父亲节点；(2)有右子树：将当前节点与其右子树中最左边的节点(设为p)交换，然后只需改变一条链，即另p的父亲节点左子树或右子树（根据p为其的左孩子还是右孩子）等于p的右子树(因为p为最左边的节点，所以没有左子树)，然后从p的父亲节点开始调整平衡；具体代码实现如下：3.印象最深刻的个调试错误，及修正方法a)忘记考虑在选择操作时有错误输入的情况，导致输入不正确时程序退出；修正方法：将输入

12、数据从int改为string型，在进行是否合法判断，若不合法，提醒重新输入；b) 总是忘记父亲节点的存在，在删除节点时，忘记将该节点的右子树的父亲节点指向该节点的父亲节点，导致删除用户时第一次成功，第二次就程序就直接崩溃；c)注册新账户时，发现每次注册成功后查看所有用户都没有新注册的账户，以为是插入函数写错了，调了半天才发现原来是注册时没有调用插入函数；d)只在程序退出时保存文件，导致当用户数据发生变化后中途查看txt时，没有及时保存；修正方法：在每次用户数据发生变化时都调用输出文件的函数；e)txt中有用户数据，查看用户时却为空；修正方法：在menu的构造函数中读入用户数据。四、测试结果1.

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

14、衡,旋转程序内插入g旋转4)右旋继续插入aefhkdgadfhkagee不平衡,旋转程序内插入a旋转以上结果均正确五、附录UserNode.h:#ifndef USERNODE#define USERNODE#include#includeusing namespace std;class UserNodeprivate:string name; /用户名 string password; /密码 int h; /以该节点为根的子树高度 int bf; /平衡因子：左树高度减去右树高度UserNode *left; /指向左子树的指针UserNode *right; /指向右子树的指针User

15、Node *parent; /指向父亲节点的指针public:friend class AVL;UserNode();UserNode(string n=,string p=); int Lh(); /左子树高度 int Rh(); /右子树高度 void geth(); /更新以当前节点为根结点的子树高度 void getbf(); /更新当前节点的平衡因子 string getpswd(); /获取密码void setpswd(string); /修改密码 friend void save(UserNode*,ostream&); /输出数据 ;#endifUserNode.cpp:#in

16、clude#includeUserNode.husing namespace std;UserNode:UserNode(string n,string p) /构造函数 name=n;password=p;h=1;bf=0;left=right=parent=NULL;int UserNode:Lh() /左子树高度 return left=NULL?0:left-h;int UserNode:Rh() /右子树高度return right=NULL?0:right-h;void UserNode:geth() /更新以当前节点为根结点的子树高度 h=max(Lh(),Rh()+1;void

17、 UserNode:getbf() /更新当前节点的平衡因子 bf=Lh()-Rh();string UserNode:getpswd() /获取密码return password;void UserNode:setpswd(string pswd) /修改密码 password=pswd;void save(UserNode* item,ostream &output) /输出数据 if (item=NULL) return;outputname passwordleft,output);save(item-right,output);function.h:#ifndef FUCTION#d

18、efine FUCTION#include#includeUserNode.husing 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*

19、); /左右旋 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 ostream& operator (ostream&,AVL&)

20、; /输出文件 ;#endiffunction.cpp:#include#include#includefunction.husing 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(itemname) cur=cur-left;else if(itemcur-name) cur=cur-right;else return cur;return NU

21、LL;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-right=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-par

22、ent=A-parent;if(A-parent!=NULL)if(A-parent-left=A) A-parent-left=B;else A-parent-right=B;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-p

23、arent-left=A) A-parent-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-getbf();C-getbf();void AVL:RLRotate(UserNode* A,UserNode* B,UserNode*

24、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;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();vo

25、id AVL:update(UserNode* item) /调整平衡for(UserNode* cur=item;cur!=NULL;cur=cur-parent)cur-geth();cur-getbf();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()ri

26、ght-Rh() LRotate(cur,cur-right); /在右孩子的右子树中，左旋 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)i

27、f(item-namename) /比当前值小，进入左子树 if(cur-left=NULL) /找到插入位置 cur-left=item;item-parent=cur;break; else cur=cur-left;else if(item-namecur-name) /比当前值大，进入右子树 if(cur-right=NULL) /找到插入位置 cur-right=item;item-parent=cur;break; else cur=cur-right;update(item-parent); /更新路径上的节点 bool AVL:Delete(UserNode* item) /删

28、除节点 ，删除成功返回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-left=item-left;else pa-right=item-left;if(item-left!=NULL) item-left-parent=pa;delete i

29、tem;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-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

30、!=NULL) p-right-parent=pa;delete p;update(pa);return 1;void AVL:printNode(UserNode* item,int deep) /打印一个节点 if(item!=NULL)printNode(item-right,deep+1);coutsetw(4*deep) ;coutnameleft,deep+1);void AVL:print() /打印树 printNode(root,0);istream& operator (istream &input,AVL &t)/输入文件，读取用户同时插入树 string name,pa

31、ssword;while(inputnamepassword) 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#includefunction.hclass Menuprivate:AVL user;public:Menu(); /构造函数void mainmenu(); /主菜单 void show(); /查看所有用

32、户 void load(); /登陆 void regist(); /注册 void Change(UserNode*); /修改密码 void Del(UserNode*); /删除用户 void close(); /将用户保存到txt中;#endifmenu.cpp:#include#include#includefunction.h#includemenu.husing namespace std;Menu:Menu()ifstream fin(data.txt);finuser;fin.close();void Menu:mainmenu() /主菜单system(cls); cout

33、nnnnnnnttt 欢迎进入用户登录系统n;couttt=n;couttt请选择操作：nnn;couttttt1.登陆n;couttttt2.注册n;couttttt3.查看所有用户n;couttttt4.退出nnn;couttt=n;coutch;while(ch.length()!=1|ch4|ch1)coutch;int d=ch0-0;switch(d)case 1:load();break;case 2:regist();break;case 3:show();break; case 4:close();break;void Menu:show() /查看所有用户system(cl

34、s); user.print();coutnnntt=n;couttt请选择操作：n;couttttt1.返回主菜单n;couttttt2.退出n;couttt=n;coutch;while(ch.length()!=1|ch2|ch1)coutch;int d=ch0-0;switch(d)case 1:mainmenu();break;case 2:close();break;void Menu:load() /登陆 string name,password;system(cls);coutnnnnnnnttt 欢迎进入用户登录界面n;couttt=nnn;coutname;coutpas

35、sword;UserNode* p;p=user.find(name); system(cls);if(p!=NULL&password=p-getpswd()coutnnnnnnntttt登录成功！n;couttt=n;couttt请选择操作：nnn;couttttt1.更改密码n;couttttt2.删除用户n;couttttt3.查看所有用户n;couttttt4.返回主菜单n;couttttt5.退出nnn;couttt=n;coutch;while(ch.length()!=1|ch5|ch1)coutch;int d=ch0-0;switch(d)case 1:Change(p);

36、break;case 2:Del(p);break;case 3:show();break;case 4:mainmenu();break; case 5:close();break;elseif(p=NULL) coutgetpswd() coutnnnnnnntttt密码错误！n;couttt=n;couttt请选择操作：nnn;couttttt1.重新登陆n;couttttt2.注册n;couttttt3.查看所有用户n;couttttt4.退出nnn;couttt=n;coutch;while(ch.length()!=1|ch4|ch1)coutch;int d=ch0-0;swit

37、ch(d)case 1:load();break;case 2:regist();break;case 3:show();break;case 4:break;void Menu:regist() /注册 string name,password,password2;int f=0; system(cls);coutnnnnnnnttt 欢迎进入用户注册界面n;couttt=nnn;coutname;coutpassword;coutpassword2;UserNode* p;p=user.find(name);system(cls);if(p=NULL&password=password2)user.insert(name,password);close();coutnnnnnnntttt 注册成功！n;f=1;else if(p!=NULL) coutnnnnnnnttt 该用户名已存在,注册失败！n;f=2;else if(password!=passw