用戶登錄系統(tǒng)

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

2、構(gòu)模擬用戶登錄系統(tǒng)，其功能要求包括用戶登錄、用戶密碼更新、用戶添加和用戶刪除等?！净疽蟆?. 要求自己編程實現(xiàn)二叉樹結(jié)構(gòu)及其相關(guān)功能，以存儲用戶信息，不允許使用標(biāo)準(zhǔn)模板類的二叉樹結(jié)構(gòu)和函數(shù)。同時要求根據(jù)二叉樹的變化情況，進(jìn)行相應(yīng)的平衡操作，即AVL平衡樹操作，四種平衡操作都必須考慮。測試時，各種情況都需要測試，并附上測試截圖；2. 要求采用類的設(shè)計思路，不允許出現(xiàn)類以外的函數(shù)定義，但允許友元函數(shù)。主函數(shù)中只能出現(xiàn)類的成員函數(shù)的調(diào)用，不允許出現(xiàn)對其它函數(shù)的調(diào)用。3. 要求采用多文件方式：.h文件存儲類的聲明，.cpp文件存儲類的實現(xiàn)，主函 數(shù)main存儲在另外一個單獨的cpp文件中。如果采用

3、類模板，則類的聲明和實現(xiàn)都放在.h文件中。4. 要求源程序中有相應(yīng)注釋；5. 不強制要求米用類模板，也不要求米用可視化窗口；6. 要求測試?yán)右容^詳盡，各種極限情況也要考慮到，測試的輸出信息要詳細(xì)易懂，表明各個功能的執(zhí)行正確；7. 要求米用Visual C+ 6.0 及以上版本進(jìn)行調(diào)試；設(shè)計思路：1. 系統(tǒng)總休設(shè)計：采用平衡二叉查找樹（AVL,以用戶名（IP）作為比較的關(guān)鍵詞進(jìn)行插 入。平 衡二叉查找樹是在二叉搜索樹（BST的基礎(chǔ)上進(jìn)行了優(yōu)化，使得樹基本 達(dá)到平衡。定 義內(nèi)部類userNode來存儲AVL樹的節(jié)點信息。2. 系統(tǒng)功能設(shè)計：要創(chuàng)建一顆包含用戶名和用戶密碼的二叉樹，要能適應(yīng)頻繁的

4、查找，因為每個用戶名是唯一的，將用戶名（string類型）作為AVL樹的比較參數(shù)，這樣就 可以 實現(xiàn)快速的插入、刪除和查找，重定義userNode類的比較函數(shù)。AVL樹是 用模板類實現(xiàn)的，這樣就可以直接比較兩個用戶類，方便了很多。圖1系統(tǒng)功能結(jié)構(gòu)圖3. 類的設(shè)計:/節(jié)點的類class userNode private :stri ng n ame;stri ng password;short int height;public :userNode *left;userNode *right;userNode(c onst stri ng &n ame, const stri ng &passw

5、ord);userNode(c onst userNode & temp);void setName( const stri ng &n ame);void setPassword( const stri ng &password);stri ng getName();stri ng getPassword();int getHeight();void cha ngeHeight( const int height); /改變樹的高度 bool checkName(c onst stri ng &n ame);/樹的類class treeprivate :userNode *root;publ

6、ic :tree();tree();void in sert_ no de(userNode *&t ,userNode &temp);void in sert_ no de(userNode &temp);/ 新建一個節(jié)點void remove(userNode *&r,userNode *&temp);void remove(userNode *&temp); /刪除一個節(jié)點void clear(userNode *t);void clear();void pr in t();void pri nt( int in dex,userNode *r);/ 輸岀一棵樹void Prin t()

7、;void Prin t(ofstream & ofile,userNode *&r);/ 寫入文件void rotateL(userNode *&r);/左旋void rotateR(userNode *&r);/右旋void rotateDoubleLR(userNode *&r);/左右旋void rotateDoubleRL(userNode *&r);/右左旋void rightBala nce(userNode *&r);void leftBala nce(userNode *&r);userNode *fin dNode(stri ng s);/ 搜索一個節(jié)點userNode *

8、searchLeftMaxNode(userNode *&r,userNode *&R);/框架類class frametree myTree;public :frame();void view(); /顯示主界面void Login();/ 登錄界面void test In sert();/ 插入一個節(jié)點void prin tTree();/ 畫岀一棵樹;4. 主程序的設(shè)計三？調(diào)試分析：1. 技術(shù)難點分析：(1) 查詢操作時，怎么能找到相應(yīng)用戶的節(jié)點？考慮到用戶名的唯一性，所以將用戶名作為AVL樹的關(guān)鍵詞，以字符串來比較大小，進(jìn)行排序，重定義userNode類的比較操作符，只比較IP,因此，

9、在查詢的 時候，新建一個userNode的對象，其IP賦值為所要查詢的IP，然后調(diào)用查找 函數(shù)， 可找到對應(yīng)的點(2) AVL樹的實現(xiàn)看書，上網(wǎng)查詢。先了解二叉查找樹(BST的實現(xiàn)，二叉查找樹(BST是一種很好的數(shù) 據(jù)結(jié)構(gòu)，它的特點是，對其任一節(jié)點，都滿足該節(jié)點的左子樹的所有點的值都小于該節(jié)點，而右子樹則是大于。我采用鏈表來實現(xiàn)它，創(chuàng)建關(guān)于節(jié)點的一個類Node,內(nèi)含描述該節(jié)點的值，及左右指針。我定義insert_node()函數(shù)來實現(xiàn)新節(jié)點的插入。AVL樹相對于BST樹，多了平衡兩字，樹都有高度，而AVL樹就是要求每一個節(jié)點的左子樹和右子樹的高度差不超過1,這樣就能使其盡可能的減小整棵樹的高度

10、，使時間復(fù)雜度能穩(wěn)定在O(logN),但我們不可能去 約束用戶的輸入，因此，引入了四種旋轉(zhuǎn)：I是新插入的節(jié)點圖3右旋(B)圖4左旋二 m I _ 二 I I I飛 _I圖5先右旋再左旋A_R4h h-1圖6先左旋再右旋(3)修改密碼或刪除用戶后如何返回上一界面？經(jīng)反復(fù)修改，未果，遂放棄2. 調(diào)試錯誤分析：(1)登陸時密碼要正確r D:C + +iS?2015Date Structure expwrimentDebugDate 1歡迎進(jìn)人用戶登錄界面！(輸人00逅回上一界面請輸入賬號；159請輸入密碼；23密碼錯誤苗活程資鍵繼絃.圖7用戶登錄界面(2) 登陸時用戶要存在 D:C+ + 型試驗 2

11、015Date Structure expwrimentDebugDate Structure歡迎進(jìn)入用戶登錄界面(輸入盹返回上一界面 請輸入賬號|12請按任意犍繼續(xù)圖8用戶不存在界面(3) 新建用戶名不能已存在 D:C + 型試驗 2015Date Structure expwnmentDebugDate Sx歡迎進(jìn)入用戶注冊界面！ t輸入胴追回上一界面請輸入用戶名：159該用戶已存在！請按任意鍵繼綾圖9用戶名已存在界面四、測試結(jié)果分析1）主界面 D:C+U v 型試驗 201 5Date Structure expwrimentDebugDate Structur一岀形一 .黒一一用:-迎

12、進(jìn)圖登錄一 注鵜入2.3,4.入攫狗拼音輸入法全:圖10主界面2）登錄界面。匚 +伏型試驗 201 5Date Structure expwrimentDebugDa te Structur.,. 歡迎進(jìn)入用戶聲錄界面！t輸入歸返回上一鼎面亍請輸入賬號：159請輸入密碼：密碼輸入正確，成功登陸捜狗拼音輸入進(jìn)也圖ii登錄界面3）注冊界面-眉迎進(jìn)入用戶 D:C+ + tjaa20 15Date Structu re expwri m en tD e b ugDa te Structur. 注冊界面！v輸入唾回上一界面請輸入用戶名：23請輸入密碼：23注冊成功！請按任意鍵繼續(xù)？- ?扌叟狗捋音輸人法

13、全:圖12注冊界面4）樹圖D:C + 4-Aijt2015Date Structure expwrimentDebugDate Structur. 一EZ只DCBA23搜狗拼音輸入法全=圖13樹形圖界面5）修改密碼I1 D:C+VAT3CA2015Date Structure eKpwriirie ntDebugDate Structur輸入新密碼;請按農(nóng)鍵繼續(xù)？扌叟狗拼音輸入進(jìn)全：圖14修改密碼6）刪除用戶隸迎進(jìn)入用戶登錄界面I t輸入? D:C+15Date Structure expwrime ntDebugDate Structur ee返回上_請輸入賬號：159請輸入密碼：23密碼輸

14、入正礁，成功登陸h?鍵繼續(xù)-搜狗拼音輸入進(jìn)全:圖15刪除用戶界面五、附錄：Node.h#in elude vstri ng#in elude #in elude #i nclude #in elude using n amespaeestd;elass userNodeprivate :stri ng n ame;stri ng password;short int height;public :userNode *left;userNode *right;userNode(e onst stri ng &n ame, const stri ng &password); userNode(e

15、onst userNode & temp);void setName( eonst stri ng &n ame);void setPassword( const stri ng &password);stri ng getName();stri ng getPassword();int getHeight();void changeHeight( const int height); /改變樹的高度 bool checkName(const string &name);Tree.h#in clude no de.h#in clude class treeprivate :userNode *

16、root;public :tree();tree();void in sert_ no de(userNode *&t ,userNode & temp);void in sert_ no de(userNode & temp); /新建一個節(jié)點void remove(userNode *&r,userNode *&temp);void remove(userNode *&temp); / 刪除一個節(jié)點void clear(userNode *t);void clear();void prin t();void print( int in dex,userNode *r);/ 輸岀一棵樹voi

17、d Prin t();void Prin t(ofstream & ofile,userNode *&r);/ 寫入文件void rotateL(userNode *&r);/左旋void rotateR(userNode *&r);/右旋void rotateDoubleLR(userNode *&r);/ 左右旋void rotateDoubleRL(userNode *&r);/ 右左旋void rightBala nce(userNode *&r);void leftBala nce(userNode *&r);userNode *fin dNode(stri ng s);/ 搜索一個

18、節(jié)點userNode *searchLeftMaxNode(userNode *&r,userNode *&R);Frame.h#include tree.h class frametree myTree; public :frame();void view(); II顯示主界面void Log in ();II 登錄界面void test In sert();II 插入一個節(jié)點void prin tTree();II 畫岀一棵樹;Node.cpp#i nclude no de.h void userNode:setName( const stri ng &n ame)this -n ame=

19、n ame;void userNode:setPassword( const stri ng &password)this -password二password;stri ng userNode:getName()retur n n ame;stri ng userNode:getPassword()retur n password;int userNode:getHeight()return this =NULL?-1:height;void userNode:cha ngeHeight( const int h)height=h;bool userNode:checkName( const

20、 stri ng &n ame)if (this -name=name)return true ;else return false ;userNode:userNode( const stri ng &n ame, const stri ng &password)this -n ame=n ame;this -password=password;height=O;left=NULL;right=NULL;userNode:userNode( const userNode & temp) this -n ame=temp .n ame;this -password二temp.password;

21、height=O;left二NULL;right二NULL;Tree.cpp#include tree.h#in elude 構(gòu)造函數(shù)tree:tree()root=NULL;void tree:i nsert_ no de(userNode & temp)in sert_ no de(root,temp);void tree:i nsert_ no de(userNode *&r,userNode &t)if (r=NULL)r=newuserNode(t); /若樹為空，直接新建節(jié)點else if (r-getName()=t.getName() / 若節(jié)點值相等，則用戶名重復(fù)retur

22、n ;stri ng ren ame;cout?用？戶 名?vvt.getName()v 已？經(jīng)-存？在”，？請？修 T 改?getName()t.getName()in sert_ no de(r-left,t);if (r-left-getHeight()-r-right-getHeight()=2)rightBala n ce(r);else if (r-getName()right,t);if (r-right-getHeight()-r-left-getHeight()=2) leftBala n ce(r);r-cha n geHeight( max(r-left-getHeigh

23、t(),r-right-getHeight()+1 );/移除void tree:remove(userNode *&r,userNode *&temp)if (r=NULL)retur n ;else if (temp-getName()getName()remove(r-left,temp);if (r-right-getHeight()-r-left-getHeight()=2) leftBala n ce(r);else if (temp-getName()r-getName()remove(r-right,temp);if (r-left-getHeight()-r-right-ge

24、tHeight()=2) rightBala n ce(r);elseif (r-left=NULL)userNode *q=r;r=r-right;delete q;else if (r-right=NULL) userNode *q=r;r=r-left;delete q;else userNode *R;r=searchLeftMaxNode(r,R);remove(r-left,R);if (r-right-getHeight()-r-left-getHeight()=2) leftBala nce(r);if (r)r-cha n geHeight(max(r-left-getHei

25、ght(),r-right-getHeight()+1);void tree:remove(userNode *&temp)remove(root,temp);void tree:pri nt()pri nt(0,root);void tree:pri nt( int in dex,userNode *r)if (r)prin t(i ndex+8,r-right);coutgetName()v ( left-getHeight()-r-right-getHeight() )left);void tree:Pri nt(ofstream &ofile,userNode *&r)if (r)Pr

26、i nt(ofile,r-left);ofilegetName()vv , getPassword()vv n：Pri n t(ofile,r-right);void tree:Pri nt()userNode *p=root;ofstream ofile;ofile.ope n ( user.txt);assert(ofile.is_ope n();Prin t(ofile,p);ofile.close();void tree:rotateL(userNode *&r)userNode *R=r-right;r-right=R-left;R-left=r;r-cha n geHeight(m

27、ax(r-left-getHeight(),r-right-getHeight()+1);R-cha ngeHeight(max(R-left-getHeight(),r-getHeight()+1); r=R;void tree:rotateR(userNode *&r)userNode *L=r-left;r-left=L-right;L_right=r;r-cha n geHeight(max(r-left-getHeight(),r-right-getHeight()+1);L-cha n geHeight(max(L-left-getHeight(),r-getHeight()+1)

28、; r=L;void tree:rotateDoubleLR(userNode *&r)rotateL(r-left);rotateR(r);void tree:rotateDoubleRL(userNode *&r)rotateR(r-right);rotateL(r);void tree:rightBala nce(userNode *&r)userNode *temp=r-left;if (temp-left-getHeight()-temp-right-getHeight()=-1) rotateDoubleLR(r); else rotateR(r);void tree:leftBa

29、la nce(userNode *&r)userNode *temp=r-right;if (temp-left-getHeight()-temp-right-getHeight()=1) rotateDoubleRL(r); else rotateL(r);userNode* tree:findNode(string s)userNode *r=root;while (r)if (s=r-getName()retur n r;else if (sgetName()r=r-left;else if (sr-getName() r=r-right;retur n NULL;userNode*tr

30、ee:searchLeftMaxNode(userNode *&r,userNode *&R) bool Left= 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

31、(Right)if (r-left)q=r;r=r-left; q-left=NULL;r-left=R-left; r-right=R-right;R-left二NULL;R-right二NULL;q-right=R;int temp二r-getHeight();r-cha n geHeight(R-getHeight();R-cha n geHeight(O);retur n r;tree:tree()clear();void tree:clear()clear(root);void tree:clear(userNode *t)if (t=NULL) return ;if (t!二NUL

32、L)clear(t-left); clear(t-right); delete t;t=NULL;Frame.cpp#i nelude frame.h#in elude frame:frame()fstream file( user.txt);char s50;userNode *userPeople;while (!file.eof()file.getli ne(s,50);for(i nt i=0;istrle n( s);i+)if (si=,)stri ng user(&s0, &si),pass(&si+1, &sstrle n(s); userPeople二 new userNod

33、e(user,pass);myTree.i n sert_ no de(*userPeople);break;file.close();void frame:view()while (1)system( cis); coutvv1、C 登？錄？ vvendlvv2、C 注痢？冊 dendl3、C 畫-樹??？形圖?endl4、C 退？岀?endl;cout |歡迎進(jìn)入用戶管理系統(tǒng)cout |1.登錄|cout |2.注冊|cout |3.畫樹形圖|cout |4.退岀|cout I!ncout 1!請選擇(1/2/3/4 ):;cout n endl; endl; endl; endl; endl;Jstri ng n;getl in e(c in,n);if 何 0卜O =1 兒 ogi n();else if (n 0- 0 =2)test In sert();else if (n 0- 0 =3)pri ntTree();else if (n 0卜O =4) break ; void frame:Logi n()system( cis);stri ng n ame,password;stri ng n ewPassword;cout 歡迎進(jìn)入用戶登錄界面！(輸入00返回上一界面) endl en dl；cout?請輸入賬號:e ndl;getl in e(c i