數(shù)據(jù)結(jié)構(gòu)大型實(shí)驗(yàn)報(bào)告.doc

用戶登錄系統(tǒng) 2014年6月13日目錄一實(shí)驗(yàn)內(nèi)容3 1.1.實(shí)驗(yàn)?zāi)康?.3 1.2實(shí)驗(yàn)的數(shù)據(jù)結(jié)構(gòu)及流程.3二 實(shí)驗(yàn)驗(yàn)證分析.72.1 LL型調(diào)整驗(yàn)證.7 2.2RR型調(diào)整驗(yàn)證.82.3LR型調(diào)整驗(yàn)證.9 2.4RL型調(diào)整驗(yàn)證.10 三、調(diào)試分析.11 3.1技術(shù)難點(diǎn)及解決方案.113.2印象深刻的調(diào)試錯(cuò)誤及解決方法.11四、測試結(jié)果12 4.1用戶登錄.12 4.2用戶注冊(cè).16 4.3刪除用戶.19 4.4極端數(shù)據(jù)的測試.21五、實(shí)驗(yàn)總結(jié)22一 實(shí)驗(yàn)內(nèi)容1.1.實(shí)驗(yàn)?zāi)康?這次實(shí)驗(yàn)是讓我們模擬用戶登錄系統(tǒng)。由于用戶信息的驗(yàn)證頻率很高，系統(tǒng)必須有效地組織這些用戶信息，從而快速查找和驗(yàn)證用戶。另外，系統(tǒng)也會(huì)經(jīng)常添加新用戶、刪除老用戶和更新用戶密碼等操作，因此，系統(tǒng)必須采用動(dòng)態(tài)結(jié)構(gòu)，在添加、刪除或更新后，依然能保證驗(yàn)證過程的快捷。1.2實(shí)驗(yàn)的數(shù)據(jù)結(jié)構(gòu)及流程1.2.1數(shù)據(jù)結(jié)構(gòu) 系統(tǒng)用到了兩個(gè)類AVLNode和AVLTree,其中AVLTree的唯一一個(gè)數(shù)據(jù)成員就是指向AVLNode結(jié)點(diǎn)的指針。 1.2.2流程圖 主界面刪除用戶打印AVL樹退出修改密碼用戶注冊(cè)用戶登錄用戶名存在嗎用戶名存在嗎 刪除成功添加成功輸入新密碼YN Y 1.2.3 函數(shù)間的調(diào)用關(guān)系main函數(shù)調(diào)用類的成員函數(shù)。插入新結(jié)點(diǎn)時(shí)，AVLInsert要根據(jù)平衡因子調(diào)用4個(gè)調(diào)整函數(shù)LL_Rotate、RR_Rotate、LR_Rotate和RL_Rotate函數(shù)。關(guān)鍵代碼：if(a-bf=2)b=a-lchild;if(b-bf=1)p=LL_Rotate(a);elsep=LR_Rotate(a);else/此時(shí)a-bf的值應(yīng)為-2b=a-rchild;if(b-bf=1)p=RL_Rotate(a);elsep=RR_Rotate(a);二 實(shí)驗(yàn)驗(yàn)證分析將用戶信息存儲(chǔ)在文件中，程序運(yùn)行時(shí)從文件中讀取，并建立 適的二叉樹。注意：文件中每行輸入三個(gè)字符，第一個(gè)字符為用戶名，第二個(gè)字符為空格，第三個(gè)字符為密碼。2.1LL型調(diào)整驗(yàn)證 在文件user.txt輸入如下：運(yùn)行程序，并選擇4打印AVLTree，結(jié)果如下圖：2. 2 RR型調(diào)整 在文件user.txt輸入如下：運(yùn)行程序，并選擇4打印AVLTree，結(jié)果如下圖：2.3 RL型調(diào)整 在文件user.txt輸入如下： 運(yùn)行程序，并選擇4打印AVLTree，結(jié)果如下圖：2.4 LR型調(diào)整在文件user.txt輸入如下：運(yùn)行程序，并選擇4打印AVLTree，結(jié)果如下圖：3 調(diào)試分析3.1 技術(shù)難點(diǎn)及解決方案 3.1.1插入新結(jié)點(diǎn)后如果二叉樹失去平衡，如何找到最小不 平衡子樹？ 在尋找新結(jié)點(diǎn)的插入位置時(shí)，始終令指針a指向離插入結(jié)點(diǎn)最近的且平衡因子不為0的結(jié)點(diǎn)，同時(shí)令指針f指向結(jié)點(diǎn)*a的父結(jié)點(diǎn)，如這樣的結(jié)點(diǎn)不存在，則指針a指向根結(jié)點(diǎn)。由此可知，當(dāng)插入新結(jié)點(diǎn)后如果二叉樹失去平衡時(shí)，指針a所指向的結(jié)點(diǎn)就是最小不平衡子樹的根。3.1.2新結(jié)點(diǎn)插入時(shí)，需修改哪些相關(guān)結(jié)點(diǎn)的平衡因子？如何修改？ 失去平衡的最小子樹的根節(jié)點(diǎn)*a在插入新結(jié)點(diǎn)*s之前，平衡因子必然不為0，必然是離插入結(jié)點(diǎn)最近的且平衡因子不為0的結(jié)點(diǎn)。插入新結(jié)點(diǎn)后，需修改從結(jié)點(diǎn)*a到新結(jié)點(diǎn)路徑上個(gè)結(jié)點(diǎn)的平衡因子。只需從*a的子結(jié)點(diǎn)*b開始，順序掃描該路徑上結(jié)點(diǎn)*p,若結(jié)點(diǎn)*s插入在*p的左子樹上，*p的平衡因子由0變?yōu)?；否則新結(jié)點(diǎn)插入在*p的右子樹上，*p的平衡因子由0變?yōu)?1.3.1.3 如何判斷以*a為根的子樹是否失去平衡？ 當(dāng)結(jié)點(diǎn)*a的平衡因子為1（或-1）時(shí)，若新結(jié)點(diǎn)插入在結(jié)點(diǎn)*a的右（或左）子樹中，左右子樹等高，結(jié)點(diǎn)*a的平衡因子為0，則以*a為根的子樹沒有失去平衡；新結(jié)點(diǎn)插入在結(jié)點(diǎn)*a的左（或右）子樹中，則以*a為根的子樹失去平衡，因?qū)σ?a為根的最小不平衡子樹進(jìn)行平衡化調(diào)整。3.1.4 失去平衡后，如何確定旋轉(zhuǎn)類型并作出相應(yīng)的調(diào)整？ 當(dāng)結(jié)點(diǎn)*a的平衡因子為2時(shí)，若*a的左孩子*b的平衡因子為1，表示新結(jié)點(diǎn)插入到結(jié)點(diǎn)*b的左子樹中，應(yīng)采用LL型調(diào)整，否則結(jié)點(diǎn)*b的平衡因子為-1，表示新結(jié)點(diǎn)插入到結(jié)點(diǎn)*b的右子樹中，應(yīng)采用LR型調(diào)整；當(dāng)結(jié)點(diǎn)*a的平衡因子為-2時(shí)，若*a的左孩子*b的平衡因子為1，表示新結(jié)點(diǎn)插入到結(jié)點(diǎn)*b的左子樹中，應(yīng)采用RL型調(diào)整，否則結(jié)點(diǎn)*b的平衡因子為-1，表示新結(jié)點(diǎn)插入到結(jié)點(diǎn)*b的右子樹中，應(yīng)采用RR型調(diào)整；3.2 印象深刻的調(diào)試錯(cuò)誤及解決方法 由于該項(xiàng)目需要建3個(gè)文件，類的聲明放在AVLTree.h文件中，類的實(shí)現(xiàn)放在AVLTree.cpp文件中，main函數(shù)單獨(dú)放在test.cpp文件中，其中在AVLTree.cpp文件中應(yīng)使用#include AVLTree.h導(dǎo)入類的聲明文件，而test.cpp只需使用#include AVLTree.h導(dǎo)入類的聲明文件即可，而我當(dāng)時(shí)錯(cuò)誤的test.cpp使用#include AVLTree.cpp導(dǎo)入了類的實(shí)現(xiàn)文件，所以一直報(bào)錯(cuò)。我在它報(bào)錯(cuò)的位置查了很多次都沒發(fā)現(xiàn)bug,最后在老師的幫助下才發(fā)現(xiàn)了問題所在。 我在插入新結(jié)點(diǎn)時(shí)，也一直報(bào)錯(cuò)，最后才發(fā)現(xiàn)在AVLNode的構(gòu)造方法中并沒把成員變量bf初始化為0，而插入新結(jié)點(diǎn)是需要根據(jù)bf的值做相應(yīng)調(diào)整，所以一直報(bào)錯(cuò)。雖然這些都是小Bug,卻花了我大量的時(shí)間查找錯(cuò)誤。 四 測試結(jié)果下面進(jìn)行的測試,文件user.txt存儲(chǔ)的初始數(shù)據(jù)為：4.1用戶登錄運(yùn)行程序，并按提示先選擇4，打印出AVL樹(這樣做是方便登錄)，選擇1,進(jìn)入登錄界面，按提示分別輸入用戶名和密碼，輸入正確后，截圖如下接著選擇是否更新密碼（只能輸入Y或N）,當(dāng)輸入Y并輸入重置密碼后，截圖如下這時(shí)，重新打開文件user.txt,會(huì)發(fā)現(xiàn)用戶信息發(fā)生了更新：錯(cuò)誤輸入： 當(dāng)輸入的不是Y或N時(shí)，會(huì)輸出“您的選擇有錯(cuò)”4.2用戶注冊(cè)運(yùn)行程序，并按提示先選擇4，打印出AVL樹(這樣做是方便登錄)，選擇2進(jìn)圖注冊(cè)界面,按提示分別輸入要注冊(cè)的用戶名和密碼，輸入正確后,如果輸入的用戶名不存在，注冊(cè)成功，并更新文件user.txt，否則注冊(cè)失敗。用戶名已存在時(shí)：用戶名不存在時(shí)這時(shí)，文件user.txt中的信息為：4.3刪除用戶運(yùn)行程序，并按提示先選擇4，打印出AVL樹(這樣做是方便登錄)，選擇2進(jìn)圖刪除界面,按提示分別輸入要注冊(cè)的用戶名，如果輸入的用戶名不存在，提示“您要?jiǎng)h除的用戶不存在!”；否則，刪除成功，并更新文件user.txt，4.4極端數(shù)據(jù)的測試在user.txt中重新輸入以下信息：運(yùn)行程序，并按4打印AVL樹，得到結(jié)果為：5 實(shí)驗(yàn)總結(jié) 通過兩到三周的編寫，我們終于用戶登錄系統(tǒng)。對(duì)于這次實(shí)驗(yàn)，心里還是蠻有信心的，前期花了大量的時(shí)間在類