基于AVL的用戶登錄系統(tǒng)實驗報告

1、用戶登錄系統(tǒng)計自1302 李林通 2013268103132014.12.8一. 實驗內(nèi)容分析：1. 實驗?zāi)康暮鸵螅骸締栴}描述】在登錄服務(wù)器系統(tǒng)時，都需要驗證用戶名和密碼，如telnet遠程登錄服務(wù)器。用戶輸入用戶名和密碼后，服務(wù)器程序會首先驗證用戶信息的合法性。由于用戶信息的驗證頻率很高，系統(tǒng)有必要有效地組織這些用戶信息，從而快速查找和驗證用戶。另外，系統(tǒng)也會經(jīng)常會添加新用戶、刪除老用戶和更新用戶密碼等操作，因此，系統(tǒng)必須采用動態(tài)結(jié)構(gòu)，在添加、刪除或更新后，依然能保證驗證過程的快速。請采用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)模擬用戶登錄系統(tǒng)，其功能要求包括用戶登錄、用戶密碼更新、用戶添加和用戶刪除等?！净疽?/p>

2、】1. 要求自己編程實現(xiàn)二叉樹結(jié)構(gòu)及其相關(guān)功能，以存儲用戶信息，不允許使用標準模板類的二叉樹結(jié)構(gòu)和函數(shù)。同時要求根據(jù)二叉樹的變化情況，進行相應(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文件中。如果采用類模板，則類的聲明和實現(xiàn)都放在.h文件中。4. 要求源程序中有相應(yīng)注釋；5. 不強制要求采用

3、類模板，也不要求采用可視化窗口；6. 要求測試例子要比較詳盡，各種極限情況也要考慮到，測試的輸出信息要詳細易懂，表明各個功能的執(zhí)行正確；7. 要求采用visual c+ 6.0及以上版本進行調(diào)試；2. 基本數(shù)據(jù)結(jié)構(gòu)：采用二叉平衡查找樹（avl），采用了模板類，以用戶名（ip）作為比較的關(guān)鍵詞進行插入。二叉平衡查找樹是在二叉搜索樹（bst）的基礎(chǔ)上進行了優(yōu)化，使得樹基本達到平衡。定義內(nèi)部類node來存儲avl樹的節(jié)點信息。class nodepublic:t date; / 記錄節(jié)點的值int balance,deep; / 表示節(jié)點的平衡值和它向下的最大深度node * left; / 指向左

4、節(jié)點node * right; / 指向右節(jié)點node():balance(0),left(null),right(null),deep(1)node(t item):date(item),balance(0),left(null),right(null),deep(1);3. 實驗思路：要創(chuàng)建一顆包含用戶信息的樹，要能適應(yīng)頻繁的查找，想到生活中登陸時都是先輸入用戶名，且每個人的用戶名是唯一的，所以，我將用戶名（string類型）作為avl樹的比較參數(shù)，這樣就可以實現(xiàn)快速的插入、刪除和查找，重定義user類的比較函數(shù)bool operator (const user & t1,const us

5、er & t2) / 按 id 比較大小return t1.id t2.id;avl樹是用模板類實現(xiàn)的，這樣就可以直接比較兩個用戶類，方便了很多。4. 類：/ 用戶的類class userpublic:string id; / 用戶名string pass; / 密碼user();user(string a,string b = );friend bool operator (const user & t1,const user & t2); / 按 id 比較大小friend bool operator = (const user & t1,const user & t2); / id 相等

6、，就算相等friend ostream& operator(ostream& out,const user& us); /重定義輸出流;/ avl的類template class avlclass node / 內(nèi)部節(jié)點類public:t date; / 節(jié)點的值int balance , deep; / 節(jié)點的平衡值和深度node * left;node * right;node():balance(0),left(null),right(null),deep(1)node(t item):date(item),balance(0),left(null),right(null),deep(1

7、);typedef node* nodepoint;public:nodepoint myroot; / 根節(jié)點avl();bool empty() const;bool search(t& item); / 找到與 item 的ip相同的節(jié)點，利用引用提取信息void insert(const t& item);/ 加入節(jié)點 itemvoid remove(const t& item);/ 刪除節(jié)點 itemvoid update(const t& item); / 更新 item 的節(jié)點void display(node* st)const; / 輸出全部信息 void display(n

8、ode* st , vector& str); /遍歷所有節(jié)點，將所需信息存到 str中void graph(ostream& out) const; / 將整棵樹以圖的形式輸出void leftrotating(node* pa , node* pos); / 平衡樹 左轉(zhuǎn)void rightrotating(node* pa , node* pos);/ 平衡樹 右轉(zhuǎn)void left_rightrotating(node* pa , node* pos);/ 平衡樹 左右轉(zhuǎn)void right_leftrotating(node* pa , node* pos);/ 平衡樹 右左轉(zhuǎn)pri

9、vate: / 定位到 item 在的節(jié)點void search2(const t& item,bool& found,nodepoint& locptr,nodepoint& parent,stack& step) const;void update(node* p);/ 用于旋轉(zhuǎn)后的更新void graphaux(ostream& out,int indent,nodepoint substrrroot) const;/ 登陸的類class landingstring nowuser;avl user;public:void graph();landing();/ 構(gòu)造函數(shù)bool wel

10、come(int fst);/ 首頁void readfile(); / 從文件中讀入信息void writefile(); / 將用戶信息寫入文件中，以 end 結(jié)尾int landing(); / 登陸界面bool use(); / 用戶界面bool insertuser(); / 增加用戶bool deleteuser(); / 刪除用戶bool change(); / 修改密碼private:string getpass(); / 獲取密碼void encode(string& str); / 密碼加密void decode(string& str); / 密碼解密;4. 實驗流程5.

11、類間的關(guān)系二. 實驗驗證分析1. 輸入形式：基本以 string 串的形式輸入輸出，用戶名應(yīng)該只包含字母以及數(shù)字2. 功能：增加 / 刪除讀者讀者： 修改密碼3. 錯誤測試數(shù)據(jù)1）用戶名不能重復(fù)2）用戶名不能包含非法字符3）注冊新用戶，兩次密碼要相同4）只能刪除存在的用戶5）刪除用戶是也要輸入密碼6）登錄時，用戶名要合法7）登陸時密碼要正確8）修改密碼時要和原密碼不相同4. 正確測試數(shù)據(jù)1） 主界面2） 注冊界面3） 刪除界面4） 用戶界面三調(diào)試分析1.難點1. 輸入密碼是怎樣顯示成星號，并且如何后退？上網(wǎng)查詢2. 查詢操作時，怎么能找到相應(yīng)用戶的節(jié)點？考慮到用戶名的唯一性，所以將用戶名作為a

12、vl樹的關(guān)鍵詞，以字符串來比較大小，進行排序，重定義user類的比較操作符，只比較ip,因此，在查詢的時候，新建一個user的對象，其ip賦值為所要查詢的ip，然后調(diào)用查找函數(shù)，可找到對應(yīng)的點3. avl樹的實現(xiàn)？3-1 先了解二叉查找樹（bst）的實現(xiàn)二叉查找樹（bst）是一種很好的數(shù)據(jù)結(jié)構(gòu)，它的特點是，對其任一節(jié)點，都滿足該節(jié)點的左子樹的所有點的值都小于該節(jié)點，而右子樹則是大于。我采用鏈表來實現(xiàn)它，創(chuàng)建關(guān)于節(jié)點的一個類 node ，內(nèi)含描述該節(jié)點的值，及左右指針。我定義 insert() 函數(shù)來實現(xiàn)新節(jié)點的插入，以下是部分代碼：template void avl:insert(const

13、t& item)nodepoint sc = myroot;if(sc = null) / 如果該樹為空，先創(chuàng)建根節(jié)點myroot = new node(item);return;stack step; / 記錄插入時走過的路徑，之后的平衡會用到int s,gs;while(1)step.push(sc);if(item date) / 如果新節(jié)點的值小于當前節(jié)點，則跳到左子樹if(sc-left = null)sc-left = new node(item);s = 0;break;else sc = sc-left;else if(sc-date right = null)sc-right

14、 = new node(item);s = 1;break;else sc = sc-right;else return ; / 不然，說明該節(jié)點已經(jīng)存在，直接結(jié)束.查找、刪除函數(shù)也是類似的步驟。3-2 avl樹的旋轉(zhuǎn)avl樹相對于bst樹，多了平衡兩字，樹都有高度，而avl樹就是要求每一個節(jié)點的左子樹和右子樹的高度差不超過1，這樣就能使其盡可能的減小整棵樹的高度，使時間復(fù)雜度能穩(wěn)定在o(logn), 但我們不可能去約束用戶的輸入，因此，引入了四種旋轉(zhuǎn)：是新插入的節(jié)點右旋左旋先右旋再左旋先左旋后右旋以下是左-右旋的代碼：template void avl:left_rightrotating(

15、node* pa , node* pos)nodepoint s,ss; / s 記錄的是 ss 的父節(jié)點s = pos-left;ss = s-right;pos-left = ss;s-right = ss-left;ss-left = s;update(s);update(ss); / 以上部分是左旋if(pa = null) myroot = ss;else if(pa-left = pos)pa-left = ss;else pa-right = ss;pos-left = ss-right;ss-right = pos;update(pos);update(ss);還有一個重要的部

16、分是選擇何種旋轉(zhuǎn)，以下例舉插入函數(shù)中的部分代碼：int pre;nodepoint pa,tmp;while(!step.empty() / step 內(nèi)存的是從根節(jié)點到當前節(jié)點的路徑，由于stack的特性，離棧頂越近，深度越深gs = s; / gs 記錄當前節(jié)點的父節(jié)點是祖父節(jié)點的左節(jié)點（0）還是右節(jié)點（1）tmp = step.top(); / 不斷彈出元素，并更新balance值和deep值step.pop();if(tmp-left = sc) s = 0; else s = 1; / s 記錄當前節(jié)點是父節(jié)點的左節(jié)點（0）還是右節(jié)點（1）pre = tmp-balance;upda

17、te(tmp);if(pre = tmp-balance) break;if(abs(tmp-balance) 1) / 如果平衡被打破if(step.empty() pa = null;else pa = step.top();if(!s & !gs) rightrotating(pa,tmp);else if(s & gs) leftrotating(pa,tmp);else if(!s & gs) left_rightrotating(pa,tmp);else right_leftrotating(pa,tmp);2.調(diào)試錯誤：1. avl樹的旋轉(zhuǎn)更新，有個地方將 deep值 和 bal

18、ance值搞反了。2. 賦值操作時，對象搞反了。四. 測試結(jié)果1. 添加用戶ps: 輸入用戶名時，輸入0，才會退出。 用戶名要只有字母或數(shù)字2. 刪除用戶ps: 刪除用戶是也需要密碼3. 用戶登陸ps: 密碼錯誤三次會自動跳到上一層4. 修改密碼五關(guān)于avl樹的驗證初始階段 加入節(jié)點 a 右旋加入節(jié)點 x , y 左旋加入節(jié)點 q 右左旋加入節(jié)點 d ，k 左右旋刪除節(jié)點 c六附錄avl.h#include #include #include #include #include #include #include using namespace std;#ifndef myavlclass#d

19、efine myavlclasstemplate class avlclass nodepublic:t date;int balance,deep;node * left;node * right;node():balance(0),left(null),right(null),deep(1)node(t item):date(item),balance(0),left(null),right(null),deep(1);typedef node* nodepoint;public:nodepoint myroot;avl();bool empty() const;bool search(t

20、& item); / 找到 item 所在的節(jié)點，將所需信息復(fù)制到 key上void insert(const t& item);/ 加入節(jié)點 itemvoid remove(const t& item);/ 刪除節(jié)點 itemvoid update(const t& item); / 更新 item 的節(jié)點void display(node* st)const; / 輸出全部信息 void display(node* st,vector& cnt); / 遍歷所有節(jié)點，將所需的信息存到 str中void graph(ostream& out) const; / 將整棵樹以圖的形式輸出void

21、 leftrotating(node* pa , node* pos); / 平衡樹 左轉(zhuǎn)void rightrotating(node* pa , node* pos);/ 平衡樹 右轉(zhuǎn)void left_rightrotating(node* pa , node* pos);/ 平衡樹 左右轉(zhuǎn)void right_leftrotating(node* pa , node* pos);/ 平衡樹 右左轉(zhuǎn)private: / 定位到 item 在的節(jié)點void search2(const t& item,bool& found,nodepoint& locptr,nodepoint& pare

22、nt,stack& step) const;void update(node* p);/ 用于旋轉(zhuǎn)后的更新void graphaux(ostream& out,int indent,nodepoint substrrroot) const;template avl:avl()myroot = null; / 樹的根節(jié)點設(shè)置為空template bool avl:empty() constreturn myroot = null; / 判斷樹的根節(jié)點是否為空template bool avl:search(t& item)nodepoint sc = myroot;while(sc != nul

23、l)if(sc-date = item) / sc-date = item 說明關(guān)鍵詞匹配，找到了目標item = sc-date; / 將所有的信息賦值給 item ，因為item是引用，外部也發(fā)生了變化return true;if(sc-date right; / 若目標關(guān)鍵詞大于當前節(jié)點，說明在右子樹else sc = sc-left; / 否則，說明在左子樹return false;template void avl:update(node* p)if(p-left = null & p-right = null) p-deep = 1; / 若無左右子樹，深度為 1else if(p

24、-left = null) p-deep = (p-right-deep)+1; else if(p-right = null) p-deep = (p-left-deep)+1; / 若只有一顆子樹，深度為其子樹深度+1else p-deep = max(p-left-deep,p-right-deep)+1; / 否則，深度為max(左，右)+1if(p-left = null & p-right = null) p-balance = 0; / 平衡值類似else if(p-left = null) p-balance = -(p-right-deep);else if(p-right

25、= null) p-balance = p-left-deep;else p-balance = (p-left-deep)-(p-right-deep);/ 調(diào)試錯誤1: 由于覺得形式相似，直接復(fù)制，導(dǎo)致 deep 沒改成 balance/if(p-left != null) coutleft-deepright != null) coutright-deep 2222n;/coutdatendeep balancen;template void avl:update(const t& item) / 更新目標的值nodepoint sc = myroot;while(sc != null)

26、if(sc-date right;else if(item date) sc = sc-left;else / 找到目標后，賦值更新sc-date = item;return;template void avl:display(node* st)const if(st-left != null) display(st-left);if(st != null) coutdateright != null) display(st-right);template void avl:display(node* st,vector& cnt)if(st = null) return ;if(st-lef

27、t != null) display(st-left,cnt);cnt.push_back(st-date); / 將節(jié)點信息放到向量 cnt 中if(st-right != null) display(st-right,cnt);/ 錯誤3 ：遞歸調(diào)用display時忘加 str 參數(shù)template void avl:graph(ostream& out) constgraphaux(out,0,myroot);template void avl:graphaux(ostream& out,int indent,nodepoint subtreeroot) constif(subtreer

28、oot != null)graphaux(out,indent+7,subtreeroot-right);outsetw(indent) dateleft);template void avl:insert(const t& item) nodepoint sc = myroot;if(sc = null) / 若當前樹為空，直接創(chuàng)建根節(jié)點myroot = new node(item);return;stack step; / 用于記錄從根節(jié)點走到目標節(jié)點的路徑int s,gs;while(1)step.push(sc);/coutitem daten;if(item date) / 如果新節(jié)

29、點的值小于當前節(jié)點，則跳到左子樹if(sc-left = null)sc-left = new node(item);s = 0;sc-balance+;sc-deep = max(sc-deep,2);break;else sc = sc-left;else if(sc-date right = null)sc-right = new node(item);s = 1;sc-balance-;sc-deep = max(sc-deep,2);break;else sc = sc-right;else return ;if(step.size() left = sc) s = 0;else s

30、 = 1; / 0表示在左子樹，1表示在右子樹pre = tmp-balance;update(tmp); / 更新 tmp 節(jié)點的balance和deepif(pre = tmp-balance) break; / 若 tmp 節(jié)點的balance值未發(fā)生變化，則其祖先也不會變化if(abs(tmp-balance) 1) / 如果平衡被打破if(step.empty() pa = null;else pa = step.top();if(!s & !gs) rightrotating(pa,tmp); / 當新節(jié)點位于左子樹的左子樹else if(s & gs) leftrotating(

31、pa,tmp); / 當新節(jié)點位于右子樹的右子樹else if(!s & gs) left_rightrotating(pa,tmp); / 當新節(jié)點位于左子樹的右子樹else right_leftrotating(pa,tmp); / 當新節(jié)點位于右子樹的左子樹template void avl:search2(const t& item,bool& found,nodepoint& sc,nodepoint& fa,stack& step) constsc = myroot;fa = null;found = false;while(sc != null) / 找到sc節(jié)點，用fa記錄其父

32、節(jié)點，用step記錄其路徑step.push(sc);if(item date)fa = sc;sc = sc-left;else if(sc-date right;elsefound = true;return;template void avl:remove(const t& item)nodepoint sc,fa,tmp;bool found;stack step;search2(item,found,sc,fa,step); / 先找到要刪除節(jié)點的位置if(!found) return;/ 接下來要讓此節(jié)點與其右子樹的最左邊節(jié)點進行交換，有可能沒有，也有可能就是其右節(jié)點if(sc-l

33、eft != null & sc-right != null)tmp = sc-right;step.push(tmp);fa = sc;while(tmp-left != null) / 一直走到最左邊f(xié)a = tmp;tmp = tmp-left;step.push(tmp);sc-date = tmp-date; / 交換sc = tmp;/ 連接sc的父節(jié)點與它的子樹if(fa = null) / 若只有一個節(jié)點myroot = null;else if(sc = fa-right) / 若sc是右節(jié)點if(sc-left != null)fa-right = sc-left;else

34、fa-right = sc-right;elseif(sc-left != null)fa-left = sc-left;elsefa-left = sc-right;if(sc = myroot) myroot = null;delete sc; / 刪除節(jié)點if(step.size() balance;update(tmp);if(pre = tmp-balance) break;if(step.empty() pa = null;else pa = step.top();if(tmp-balance = -2)if(tmp-right-balance = 1) right_leftrot

35、ating(pa,tmp);else leftrotating(pa,tmp);else if(tmp-balance = 2)if(tmp-left-balance = -1) left_rightrotating(pa,tmp);else rightrotating(pa,tmp);template void avl:leftrotating(node* pa , node* pos)node* tmp = pos-right;if(pa = null) myroot = tmp;/ 當前節(jié)點的父節(jié)點連接其右節(jié)點else if(pa-left = pos)pa-left = tmp;els

36、e pa-right = tmp;/ 其右節(jié)點的左子樹變成當前節(jié)點的右子樹pos-right = tmp-left;tmp-left = pos;update(pos);update(tmp);template void avl:rightrotating(node* pa , node* pos)node* tmp = pos-left;if(pa = null) myroot = tmp;/ 當前節(jié)點的父節(jié)點連接其左節(jié)點else if(pa-right = pos)pa-right = tmp;else pa-left = tmp;/ 其左節(jié)點的右子樹變成當前節(jié)點的左子樹pos-left

37、= tmp-right;tmp-right = pos;update(pos);update(tmp);template void avl:left_rightrotating(node* pa , node* pos)nodepoint s,ss;s = pos-left;ss = s-right;pos-left = ss;s-right = ss-left;ss-left = s;update(s);update(ss); / 以上部分是左旋，以下是右旋if(pa = null) myroot = ss;else if(pa-left = pos)pa-left = ss;else pa

38、-right = ss;pos-left = ss-right;ss-right = pos;update(pos);update(ss);template void avl:right_leftrotating(node* pa , node* pos)nodepoint s,ss;s = pos-right;ss = s-left;pos-right = ss;s-left = ss-right;ss-right = s;update(s);update(ss); / 以上部分是右旋，以下是左旋if(pa = null) myroot = ss;else if(pa-right = pos

39、)pa-right = ss;else pa-left = ss;pos-right = ss-left;ss-left = pos;update(pos);update(ss);#endiflanding.h#ifndef landing#define landing#include avl.h#include user.h#include #include #include #include class landingstring nowuser;avl user;public:void graph();landing();/ 構(gòu)造函數(shù)bool welcome(int fst);/ 首頁v

40、oid readfile(); / 從文件中讀入信息void writefile(); / 將用戶信息寫入文件中，以 end 結(jié)尾int landing(); / 登陸界面bool use(); / 用戶界面bool insertuser(); / 增加用戶bool deleteuser(); / 刪除用戶bool change(); / 修改密碼private:string getpass(); / 獲取密碼void encode(string& str); / 密碼加密void decode(string& str); / 密碼解密;#endifuser.h#ifndef myuser#d

41、efine myuser#include #include #include using namespace std;class userpublic:string id; / 用戶名string pass; / 密碼user();user(string a,string b = );friend bool operator (const user & t1,const user & t2); / 按 id 比較大小friend bool operator = (const user & t1,const user & t2); / id 相等，就算相等friend ostream& operatorid)if(id = end) break;uinpass;decode(pass); / 信息解密user us(id,p