用戶登錄系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu)大型實(shí)驗(yàn)2022/2022(1)實(shí)驗(yàn)題目用戶登錄系統(tǒng)學(xué)生姓名學(xué)生學(xué)號(hào)主要工作樹的結(jié)構(gòu)、框架編寫負(fù)責(zé)人學(xué)生班級(jí)任課教師提交日期2022.1.2精品文檔計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院II歡送下載精品文檔用戶登錄系統(tǒng)一.實(shí)驗(yàn)題目和要求：【問題描述】在登錄效勞器系統(tǒng)時(shí),都需要驗(yàn)證用戶名和密碼,如 telnettelnet 遠(yuǎn)程登錄效勞器.用戶輸入用戶名和密碼后,效勞器程序會(huì)首先驗(yàn)證用戶信息的合法性.由于用戶信息的驗(yàn)證頻率很高,系統(tǒng)有必要有效地組織這些用戶信息,從而快速查找和驗(yàn)證用戶.另外,系統(tǒng)也會(huì)經(jīng)常會(huì)添加新用戶、刪除老用戶和更新用戶密碼等操作,因此,系統(tǒng)必須采用動(dòng)態(tài)結(jié)構(gòu),在添加、刪除或更新后,依然能保

2、證驗(yàn)證過程的快速.請(qǐng)采用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)模擬用戶登錄系統(tǒng),其功能要求包括用戶登錄、用戶密碼更新、用戶添加和用戶刪除等.【根本要求】1 1 . .要求自己編程實(shí)現(xiàn)二叉樹結(jié)構(gòu)及其相關(guān)功能,以存儲(chǔ)用戶信息,不允許使用標(biāo)準(zhǔn)模板類的二叉樹結(jié)構(gòu)和函數(shù).同時(shí)要求根據(jù)二叉樹的變化情況,進(jìn)行相應(yīng)的平衡操作,即 AVLAVL 平衡樹操作,四種平衡操作都必須考慮.測(cè)試時(shí),各種情況都需要測(cè)試,并附上測(cè)試截圖；2 2 . .要求采用類的設(shè)計(jì)思路,不允許出現(xiàn)類以外的函數(shù)定義,但允許友元函數(shù).主函數(shù)中只能出現(xiàn)類的成員函數(shù)的調(diào)用,不允許出現(xiàn)對(duì)其它函數(shù)的調(diào)用.3 3 . .要求采用多文件方式： .h.h 文件存儲(chǔ)類的聲明,.cp

3、p.cpp 文件存儲(chǔ)類的實(shí)現(xiàn),主函數(shù) mainmain 存儲(chǔ)在另外一個(gè)單獨(dú)的 cpcpp p 文件中.如果采用類模板,那么類的聲明和實(shí)現(xiàn)都放在. .h h 文件中.4 4 . .要求源程序中有相應(yīng)注釋；5 5 . .不強(qiáng)制要求采用類模板,也不要求采用可視化窗口；6 6 . .要求測(cè)試?yán)右葦M詳盡,各種極限情況也要考慮到,測(cè)試的輸出信息要詳細(xì)易懂,說明各個(gè)功能的執(zhí)行正確；7 7 . .要求采用 VisualC+6.0VisualC+6.0 及以上版本進(jìn)行調(diào)試；設(shè)計(jì)思路:1歡迦下載精品文檔1.系統(tǒng)總體設(shè)計(jì)：采用平衡二叉查找樹AVD,AVD,以用戶名IPIP作為比擬的關(guān)鍵詞進(jìn)行插入.平衡二叉查找樹

4、是在二叉搜索樹BSTBST 的根底上進(jìn)行了優(yōu)化,使得樹根本到達(dá)平衡.定義內(nèi)部類userNodeuserNode 來存儲(chǔ) AVLAVL 樹的節(jié)點(diǎn)信息.2 .系統(tǒng)功能設(shè)計(jì)：要?jiǎng)?chuàng)立一顆包含用戶名和用戶密碼的二叉樹,要能適應(yīng)頻繁的查找,由于每個(gè)用戶名是唯一的,將用戶名stringstring 類型作為 AVLAVL 樹的比擬參數(shù),這樣就可以實(shí)現(xiàn)快速的插入、 刪除和查找,重定義 userNodeuserNode 類的比擬函數(shù).AVLAVL 樹是用模板類實(shí)現(xiàn)的,這樣就可以直接比擬兩個(gè)用戶類,方便了很多.圖1系統(tǒng)功能結(jié)構(gòu)圖3.類的設(shè)計(jì):/節(jié)點(diǎn)的類classuserNodeprivate:stringname

5、;stringpassword;shortintheight;2歡立下載精品文檔public:userNode*left;userNode*right;userNode(conststring&name,conststring&password);userNode(constuserNode&temp);voidsetName(conststring&name);voidsetPassword(conststring&password);stringgetName();stringgetPassword();intgetHeight();voidchan

6、geHeight(constintheight);/改變樹的高度boolcheckName(conststring&name);/樹的類classtreeprivate:userNode*root;public:tree();tree();voidinsert_node(userNode*&t,userNode&temp);voidinsert_node(userNode&temp);/新建一個(gè)節(jié),點(diǎn)voidremove(userNode*&r,userNode*&temp);voidremove(userNode*&temp);/刪除一

7、個(gè)節(jié)點(diǎn)voidclear(userNode*t);voidclear();voidprint();voidprint(intindex,userNode*r);/輸出一棵樹voidPrint();voidPrint(ofstream&ofile,userNode*&r);/寫入文件voidrotateL(userNode*&r);/左旋voidrotateR(userNode*&r);/右旋voidrotateDoubleLR(userNode*&r);/左右旋voidrotateDoubleRL(userNode*&r);/右左旋voidrig

8、htBalance(userNode*&r);voidleftBalance(userNode*&r);userNode*findNode(strings);/搜索一個(gè)節(jié)點(diǎn)userNode*searchLeftMaxNode(userNode*&r,userNode*&R);/框架類classframe3歡迦下載精品文檔(treemyTree;public:frame();voidview();/顯示主界面voidLogin();/登錄界面voidtestInsert();/插入一個(gè)節(jié)點(diǎn)voidprintTree();/畫出一棵樹;4 .主程序的設(shè)計(jì):圖2類的調(diào)

9、用三.調(diào)試分析：1 1 . .技術(shù)難點(diǎn)分析：(1)(1)查詢操作時(shí),怎么能找到相應(yīng)用戶的節(jié)點(diǎn)？考慮到用戶名的唯一性,所以將用戶名作為AVAVL L樹的關(guān)鍵詞,以字符用來比擬大小,進(jìn)行排序,重定義 userNodeuserNode 類的比擬操作符,只比擬 IP,IP,因此,在查詢的時(shí)候,新建一個(gè) userNodeuserNode 的對(duì)象,其 IPIP 賦值為所要查詢的 IP,IP,然后調(diào)用查找函數(shù),可找到對(duì)應(yīng)的點(diǎn)2 2 2)2)AVLAVL 樹的實(shí)現(xiàn)看書,上網(wǎng)查詢.先了解二叉查找樹(BSBST T的實(shí)現(xiàn),二叉查找樹(BSBST T是一種很好的數(shù)據(jù)結(jié)構(gòu),它的特點(diǎn)是,對(duì)其任一節(jié)點(diǎn),都滿足該節(jié)點(diǎn)的左子

10、樹的所有點(diǎn)的值都小于該節(jié)點(diǎn),而右子樹那么是大于.我采用鏈表來實(shí)現(xiàn)它,創(chuàng)立關(guān)于節(jié)點(diǎn)的4歡立下載精品文檔一個(gè)類NodeNode,內(nèi)含描述該節(jié)點(diǎn)的值,及左右指針.我定義insert_node()insert_node()函數(shù)來實(shí)現(xiàn)新節(jié)點(diǎn)的插入.AVAVL L樹相又t t于BSBST T樹,多了平衡兩字,樹都有高度,而AVAVL L樹就是要求每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差不超過 1,1,這樣就能使其盡可能的減小整棵樹的高度,使時(shí)間復(fù)雜度能穩(wěn)定在 O(logN),O(logN),但我們不可能去約束用戶的輸入,因此,引入了四種旋轉(zhuǎn)：是新插入的節(jié)點(diǎn)圖3右旋h圖4左旋5歡立下載精品文檔圖5先右旋再左旋(3

11、)(3)修改密碼或刪除用戶后如何返回上一界面?經(jīng)反復(fù)修改,未果,遂放棄.2.2.調(diào)試錯(cuò)誤分析:(1)(1)登陸時(shí)密碼要正確.6歡立下載精品文檔r rD:CD:C+型型5DateStructureexpwrimentDebugDate15DateStructureexpwrimentDebugDate1歐迎進(jìn)入歐迎進(jìn)入用用戶登錄界面！輸戶登錄界面！輸A.的返回上一界面的返回上一界面) )請(qǐng)輸入賬號(hào);159159請(qǐng)輸入密碼;231a蓄鍵繼續(xù).圖7用戶登錄界面(2)(2)登陸時(shí)用戶要存在D:C+VfciS2022DateStructureexpwrimentDebugDateStructureD:C

12、+VfciS2022DateStructureexpwrimentDebugDateStructure歡送進(jìn)入用戶登錄界面輸入地返回上一界面請(qǐng)輸入賬號(hào)12圖8用戶不存在界面(3)(3)新建用戶名不能已存在7歡立下載精品文檔D:C+vMi2022DateStructureexpwnmentDebugDateSt歡送進(jìn)入用戶注冊(cè)界面！輸入的返回上一界面請(qǐng)輸入用戶名：159該用戶已存在！請(qǐng)按任意鍵繼續(xù).圖9用戶名已存在界面四、測(cè)試結(jié)果分析：1 1主界面D:C+VTJS2015DateStructureexpwrimentDebugDateStructur,一一攫攫狗拼音狗拼音輸入法全輸入法全: :圖

13、10主界面用圖入形進(jìn)錄翦出迎登注一,)E!.2.3,4.2 2登錄界面8歡立下載精品文檔D:C+T22022DateStructureexpwrirrientDebugDateStructure歡送進(jìn)入用戶登錄界歡送進(jìn)入用戶登錄界面！面！? ?輸輸入酶返回上一原茴入酶返回上一原茴請(qǐng)輸入賬號(hào)：請(qǐng)輸入賬號(hào)：159159請(qǐng)輸入密碼請(qǐng)輸入密碼; ;密碼輸入正確密碼輸入正確, ,成功登陸成功登陸搜狗拼音輸入搜狗拼音輸入法金法金2 2圖11登錄界面3 3注冊(cè)界面D:C4-15DateStructureexpwrimentDebugDateStructur.欣迎進(jìn)入用戶注冊(cè)界面！輸入麗E回上一界面請(qǐng)輸入用戶

14、名;23請(qǐng)輸入密碼：23注冊(cè)成功！請(qǐng)按任意鍵繼續(xù).搜狗擰音輸入法全：圖12注冊(cè)界面4 4樹圖9歡立下載精品文檔5 5修改密碼D:C+T3S2022DateStructureexpwrimentDebugDateStructur.一口一口! !輸入新密碼：輸入新密碼：小小修修改成必改成必請(qǐng)按讖鍵繼續(xù).搜狗拼音輸入法全搜狗拼音輸入法全：圖14修改密碼6 6刪除用戶10求迎下載精品文檔D:C+ci2S2022DateStructureexpwr1mentDebugDateStructur.一口一口歡送進(jìn)入用戶登錄歡送進(jìn)入用戶登錄界面界面I? ?輸輸入酶返回入酶返回上一標(biāo)上一標(biāo)5請(qǐng)輸入賬號(hào)：請(qǐng)輸入賬號(hào)

15、：159159請(qǐng)輸入密碼請(qǐng)輸入密碼; ;2323密碼輸入密碼輸入正確正確, ,成功登陸成功登陸院更改密碼2 2、蒯除賬號(hào)震鍵繼續(xù)一搜狗拼搜狗拼音輸入法音輸入法全全：圖15刪除用戶界面五、附錄:Node.h#include#include#include#include#includeusingnamespacestd;classuserNodeprivate:stringname;stringpassword;shortintheight;public:userNode*left;userNode*right;userNode(conststring&name,conststring&

16、amp;password);userNode(constuserNode&temp);voidsetName(conststring&name);11求迎下載voidsetPassword(conststring&password);stringgetName();stringgetPassword();intgetHeight();voidchangeHeight(constintheight);/boolcheckName(conststring&name);Tree.h#includenode.h#includeclasstreeprivate:userN

17、ode*root;public:tree();tree();voidinsert_node(userNode*&t,userNode&temp);voidinsert_node(userNode&temp);/新建一個(gè)節(jié),點(diǎn)voidremove(userNode*&r,userNode*&temp);voidremove(userNode*&temp);/刪除一個(gè)節(jié)點(diǎn)voidclear(userNode*t);voidclear();voidprint();voidprint(intindex,userNode*r);/輸出一棵樹voidPrin

18、t();voidPrint(ofstream&ofile,userNode*&r);/寫入文件voidrotateL(userNode*&r);/左旋voidrotateR(userNode*&r);/右旋voidrotateDoubleLR(userNode*&r);/左右旋voidrotateDoubleRL(userNode*&r);/右左旋voidrightBalance(userNode*&r);voidleftBalance(userNode*&r);userNode*findNode(strings);/搜索一個(gè)節(jié)點(diǎn)

19、userNode*searchLeftMaxNode(userNode*&r,userNode*&R);Frame.h#includetree.hclassframe精品文檔改變樹的高度精品文檔treemyTree;public:frame();voidview();/顯示主界面voidLogin();/登錄界面voidtestInsert();/插入一個(gè)節(jié)點(diǎn)voidprintTree();/畫出一棵樹;Node.cpp#includenode.hvoiduserNode:setName(conststring&name)this-name=name;voiduserN

20、ode:setPassword(conststring&password)this-password=password;stringuserNode:getName()returnname;stringuserNode:getPassword()returnpassword;intuserNode:getHeight()returnthis=NULL?-1:height;voiduserNode:changeHeight(constinth)height=h;booluserNode:checkName(conststring&name)if(this-name=name)re

21、turntrue;elsereturnfalse;userNode:userNode(conststring&name,conststring&password)13螃a下載精品文檔this-name=name;this-password=password;height=0;left=NULL;right=NULL;userNode:userNode(constuserNode&temp)this-name=;this-password=temp.password;height=0;left=NULL;right=NULL;Tree.cpp#inclu

22、detree.h#include構(gòu)造函數(shù)tree:tree()root=NULL;voidtree:insert_node(userNode&temp)insert_node(root,temp);voidtree:insert_node(userNode*&r,userNode&t)if(r=NULL)r=newuserNode(t);/假設(shè)樹為空,直接新建節(jié)點(diǎn)elseif(r-getName()=t.getName()/假設(shè)節(jié)點(diǎn)值相等,那么用戶名重復(fù)return;stringrename;cout用？戶名？t.getName()已？經(jīng)-存?在u,?t1?修T改？re

23、name;t.setName(rename);insert_node(r,t);14螃a下載精品文檔elseif(r-getName()t.getName()(insert_node(r-left,t);if(r-left-getHeight()-r-right-getHeight()=2)(rightBalance(r);elseif(r-getName()right,t);if(r-right-getHeight()-r-left-getHeight()=2)(leftBalance(r);r-changeHeight(max(r-left-getHeight(),r-right-getH

24、eight()+1);/移除voidtree:remove(userNode*&r,userNode*&temp)(if(r=NULL)(return;elseif(temp-getName()getName()(remove(r-left,temp);if(r-right-getHeight()-r-left-getHeight()=2)leftBalance(r);elseif(temp-getName()r-getName()(remove(r-right,temp);if(r-left-getHeight()-r-right-getHeight()=2)rightBal

25、ance(r);15螃a下載精品文檔)else(if(r-left=NULL)(userNode*q=r;r=r-right;deleteq;)elseif(r-right=NULL)(userNode*q=r;r=r-left;deleteq;)else(userNode*R;r=searchLeftMaxNode(r,R);remove(r-left,R);if(r-right-getHeight()-r-left-getHeight()=2)leftBalance(r);)if(r)r-changeHeight(max(r-left-getHeight(),r-right-getHeig

26、ht()+1);)voidtree:remove(userNode*&temp)(remove(root,temp);16螃a下載精品文檔)voidtree:print()(print(0,root);)voidtree:print(intindex,userNode*r)(if(r)(print(index+8,r-right);coutsetw(index)getName()(left-getHeight()-r-right-getHeight()left);)voidtree:Print(ofstream&ofile,userNode*&r)(if(r)(Prin

27、t(ofile,r-left);ofilegetName(),getPassword()right);)voidtree:Print()(userNode*p=root;ofstreamofile;ofile.open(user.txt);assert(ofile.is_open();Print(ofile,p);ofile.close();)voidtree:rotateL(userNode*&r)(userNode*R=r-right;r-right=R-left;R-left=r;r-changeHeight(max(r-left-getHeight(),r-right-getH

28、eight()+1);R-changeHeight(max(R-left-getHeight(),r-getHeight()+1);r=R;17螃a下載精品文檔)voidtree:rotateR(userNode*&r)(userNode*L=r-left;r-left=L-right;L-right=r;r-changeHeight(max(r-left-getHeight(),r-right-getHeight()+1);L-changeHeight(max(L-left-getHeight(),r-getHeight()+1);r=L;)voidtree:rotateDouble

29、LR(userNode*&r)(rotateL(r-left);rotateR(r);)voidtree:rotateDoubleRL(userNode*&r)(rotateR(r-right);rotateL(r);)voidtree:rightBalance(userNode*&r)(userNode*temp=r-left;if(temp-left-getHeight()-temp-right-getHeight()=-1)rotateDoubleLR(r);elserotateR(r);)voidtree:leftBalance(userNode*&r)

30、(userNode*temp=r-right;if(temp-left-getHeight()-temp-right-getHeight()=1)rotateDoubleRL(r);elserotateL(r);)userNode*tree:findNode(strings)18螃a下載精品文檔(userNode*r=root;while(r)(if(s=r-getName()returnr;elseif(sgetName()r=r-left;elseif(sr-getName()r=r-right;returnNULL;userNode*tree:searchLeftMaxNode(user

31、Node*&r,userNode*&R)(boolLeft=false,Right=true;userNode*q=NULL;R=r;if(r-left-left=NULL&r-left-right=NULL)(q=r;r=r-left;q-left=NULL;r-left=q;r-right=q-right;q-right=NULL;R=q;else(if(r-left)r=r-left;while(r-right)(if(r-right-right=NULL)q=r;r=r-right;Right=false;if(Right)(if(r-left)(q=r;r=r

32、-left;19螃a下載精品文檔q-left=NULL;)r-left=R-left;r-right=R-right;R-left=NULL;R-right=NULL;q-right=R;)inttemp=r-getHeight();r-changeHeight(R-getHeight();R-changeHeight(0);returnr;)tree:tree()clear();)voidtree:clear()clear(root);)voidtree:clear(userNode*t)if(t=NULL)return;if(t!=NULL)clear(t-left);clear(t-ri

33、ght);deletet;)t=NULL;)Frame.cpp20螃a下載精品文檔#includeframe.h#includeframe:frame()(fstreamfile(user.txt);chars50;userNode*userPeople;while(!file.eof()(file.getline(s,50);for(inti=0;istrlen(s);i+)(if(si=,)(stringuser(&s0,&si),pass(&si+1,&sstrlen(s);userPeople=newuserNode(user,pass);myTree.

34、insert_node(*userPeople);break;file.close();voidframe:view()(while(1)(system(cls);/cout1、 .登？錄？endl2、0注??？?jī)?cè)d,endl3、 .畫-樹??？形？圖？endl4、 .退？出？endl;coutn;cout|歡送進(jìn)入用戶治理系統(tǒng)|endl;cout|1.登錄|endl;cout|2.注冊(cè)|endl;cout|3.畫樹形圖|endl;cout|4.退出|endl;coutn;cout請(qǐng)選擇(1/2/3/4):;stringn;getline(cin,n);if(n0-0=1)Login();elseif(n0-0=2)testInsert();elseif(n0-0=3)printTree();21螃a下載精品文檔elseif(n0-0=4)break;voidframe:Login()(system(cls);stringname,password;str