用戶登錄系統(tǒng)

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

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

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

4、是在二叉搜索樹BSTBST 的根底上進行了優(yōu)化,使得樹根本到達平衡.定義內部類userNodeuserNode 來存儲 AVLAVL 樹的節(jié)點信息.2 .系統(tǒng)功能設計：要創(chuàng)立一顆包含用戶名和用戶密碼的二叉樹,要能適應頻繁的查找,由于每個用戶名是唯一的,將用戶名stringstring 類型作為 AVLAVL 樹的比擬參數,這樣就可以實現快速的插入、 刪除和查找,重定義 userNodeuserNode 類的比擬函數.AVLAVL 樹是用模板類實現的,這樣就可以直接比擬兩個用戶類,方便了很多.圖1系統(tǒng)功能結構圖3.類的設計:/節(jié)點的類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);/新建一個節(jié),點voidremove(userNode*&r,userNode*&temp);voidremove(userNode*&temp);/刪除一

7、個節(jié)點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);/搜索一個節(jié)點userNode*searchLeftMaxNode(userNode*&r,userNode*&R);/框架類classframe3歡迦下載精品文檔(treemyTree;public:frame();voidview();/顯示主界面voidLogin();/登錄界面voidtestInsert();/插入一個節(jié)點voidprintTree();/畫出一棵樹;4 .主程序的設計:圖2類的調

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

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

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

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

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

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

15、：159159請輸入密碼請輸入密碼; ;2323密碼輸入密碼輸入正確正確, ,成功登陸成功登陸院更改密碼2 2、蒯除賬號震鍵繼續(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);/新建一個節(jié),點voidremove(userNode*&r,userNode*&temp);voidremove(userNode*&temp);/刪除一個節(jié)點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);/搜索一個節(jié)點

19、userNode*searchLeftMaxNode(userNode*&r,userNode*&R);Frame.h#includetree.hclassframe精品文檔改變樹的高度精品文檔treemyTree;public:frame();voidview();/顯示主界面voidLogin();/登錄界面voidtestInsert();/插入一個節(jié)點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構造函數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);/假設樹為空,直接新建節(jié)點elseif(r-getName()=t.getName()/假設節(jié)點值相等,那么用戶名重復return;stringrename;cout用？戶名？t.getName()已？經-存?在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注?。績詃,endl3、 .畫-樹?。啃?？圖？endl4、 .退？出？endl;coutn;cout|歡送進入用戶治理系統(tǒng)|endl;cout|1.登錄|endl;cout|2.注冊|endl;cout|3.畫樹形圖|endl;cout|4.退出|endl;coutn;cout請選擇(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