數(shù)據(jù)結(jié)構(gòu)大型實驗報告.doc

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