avl樹(shù)模擬用戶(hù)登錄系統(tǒng)的實(shí)驗(yàn)報(bào)告(附代碼和詳盡注釋)

1、一實(shí)驗(yàn)內(nèi)容分析：1.實(shí)驗(yàn)?zāi)康模耗M用戶(hù)登錄系統(tǒng)，在o（lgn）時(shí)間內(nèi)完成用戶(hù)登錄、刪除、修改等工作。2.設(shè)計(jì)思路：主要分以下四個(gè)類(lèi)：avltreenode:存儲(chǔ)平衡樹(shù)節(jié)點(diǎn)；avltree:avl平衡樹(shù)的主要實(shí)現(xiàn)算法；userinfo:存儲(chǔ)用戶(hù)信息；interface:界面,與用戶(hù)交互；3. 流程圖以及類(lèi)的主要包含和調(diào)用關(guān)系：二.實(shí)驗(yàn)驗(yàn)證分析（1） 輸入的形式和輸入值的范圍；控制臺(tái)的輸入：如圖，輸入為數(shù)字，超出范圍將提示不正確并返回重新輸入文件的輸入： 程序會(huì)找尋當(dāng)前目錄的database.data文件，并讀入數(shù)據(jù)，如果未找到則自創(chuàng)此文件，創(chuàng)建空樹(shù)（2） 輸出的形式； 程序退出時(shí)析構(gòu)函數(shù)保存文件

2、到database.data并覆蓋原文件。（3） 程序所能達(dá)到的功能； 在o(lgn)時(shí)間內(nèi)添加、查找、刪除、修改用戶(hù)信息。（4） 測(cè)試數(shù)據(jù)： 本系統(tǒng)包含三個(gè)測(cè)試函數(shù)樣例：1. 順序插入測(cè)試（分別在debug和release環(huán)境下和stl map比較速度）2. 隨機(jī)插入測(cè)試（分別在debug和release環(huán)境下和stl map比較速度）3. 刪除測(cè)試測(cè)試函數(shù)均在main文件里void randomtest();/隨機(jī)數(shù)測(cè)試void ordertest();/順序插入測(cè)試void deletetest();/刪除測(cè)試void main_interface();/主界面 1,2均在debug模式

3、下插入100w數(shù)據(jù)，在release模式下插入1000w數(shù)據(jù)。順序插入的實(shí)現(xiàn)是用整數(shù)1n轉(zhuǎn)換為string，位數(shù)不夠的在前面補(bǔ)0。測(cè)試結(jié)果：1.debug下順序插入測(cè)試：2.release下順序插入測(cè)試 3.debug下隨機(jī)插入測(cè)試4.release下隨機(jī)插入測(cè)試實(shí)踐證明map的紅黑樹(shù)在順序插入測(cè)試時(shí)慢于我的avl樹(shù)，但隨機(jī)插入測(cè)試表現(xiàn)比avl樹(shù)要好。3. 刪除數(shù)據(jù)的圖形化表示（rl=為平衡因子以檢驗(yàn)正確性）下面刪除3（樹(shù)中無(wú)3）：還是一樣，下面刪除2刪除成功，下面刪除7刪除成功。三.調(diào)試分析（1）討論分析調(diào)試過(guò)程中的主要技術(shù)問(wèn)題以及具體的解決方法（至少個(gè)）；1.代碼重復(fù)問(wèn)題：有重復(fù)的代碼不是

4、好代碼。左右旋和左旋右旋有大量重復(fù)，經(jīng)過(guò)分析發(fā)現(xiàn)左右旋可以分解為先左旋后右旋，但平衡因子調(diào)整方法不一。所以分解左旋和右旋為兩個(gè)函數(shù)，調(diào)整平衡因子單分一個(gè)函數(shù)。2. 空間占用問(wèn)題：平衡因子只有3個(gè)取值卻占了一個(gè)int 4個(gè)字節(jié)是極大的浪費(fèi)，所以改用char型。編程實(shí)踐中發(fā)現(xiàn)樹(shù)高也可以取消，也極大的節(jié)省了空間。3. 時(shí)間浪費(fèi)問(wèn)題：先調(diào)整平衡因子再旋轉(zhuǎn)最后再調(diào)整平衡因子浪費(fèi)時(shí)間，經(jīng)分析后可以采取一些代碼上的改動(dòng)而將第一次調(diào)整省略。（2） 技術(shù)難點(diǎn)分析（至少個(gè)）；1. 由于放棄樹(shù)高調(diào)整平衡因子，所以平衡因子的調(diào)整是編程最困難之處，采用方法是根據(jù)插入子數(shù)是左子樹(shù)還是右子樹(shù)調(diào)整父親的平衡因子。2. 刪除時(shí)

5、需先采用bst的刪除方式，再分情況用類(lèi)似avl插入節(jié)點(diǎn)時(shí)的調(diào)整方法，必須完全搞懂bst和avl才能正確地處理刪除問(wèn)題。3. 代碼閱讀問(wèn)題：純算法程序一般難以閱讀，尤其是像avl這類(lèi)復(fù)雜算法，即使是自己也是編了前面忘了后面，所以程序添加了海量的注釋?zhuān)總€(gè)函數(shù)每個(gè)重要語(yǔ)句都有功能解說(shuō)，代碼命名取其意思，格式遵循cleancode。（3） 印象最深刻的個(gè)調(diào)試錯(cuò)誤，及修正方法；1. 最深的當(dāng)然是訪問(wèn)了沒(méi)初始化的內(nèi)存！幾乎90%調(diào)試問(wèn)題都與此有關(guān)。大部分非法訪問(wèn)內(nèi)存經(jīng)調(diào)試都?xì)w結(jié)于平衡因子的錯(cuò)誤。解決方法是在紙上畫(huà)出幾個(gè)正確的例子，再輸入進(jìn)程序調(diào)試，看平衡因子的錯(cuò)誤具體地址和引起其錯(cuò)誤的代碼。反復(fù)調(diào)試修改

6、直到測(cè)試再大數(shù)據(jù)量也不會(huì)報(bào)錯(cuò)。2. 鏈接錯(cuò)誤。好像是1005，此錯(cuò)誤的原因是.h文件內(nèi)除了成員函數(shù)不能有其它函數(shù)。原來(lái)是我用的友元重載比較函數(shù)（必須用友元，否則類(lèi)對(duì)象比較時(shí)重載不匹配。）網(wǎng)上查了好半天才知道的原因。解決方法：友元重載比較運(yùn)算符函數(shù)放到.cpp文件里。3. 頭文件包含問(wèn)題要徹底搞明白，.h文件必須加頭文件衛(wèi)士，.cpp必須不加而且不能被#include,。測(cè)試結(jié)果：（1）展示程序的運(yùn)行結(jié)果，包括輸入和輸出，分析數(shù)據(jù)的正確性；1.database.data文件（存放用戶(hù)名密碼）2.用戶(hù)登錄3.添加用戶(hù)4.刪除用戶(hù)4. 更新用戶(hù)（2）應(yīng)用邊界數(shù)據(jù)、或極端數(shù)據(jù)測(cè)試系統(tǒng)，分析結(jié)果的正確性

7、。實(shí)驗(yàn)分析驗(yàn)證里已進(jìn)行充分測(cè)試。附錄：附上源代碼，并標(biāo)明源代碼的所屬文件，并且源代碼必須有注釋。/-/avltreenode.h/avl樹(shù)節(jié)點(diǎn)類(lèi)/功能：提供主鍵、左右子指針、父指針，平衡因子/說(shuō)明：平衡因子為char，節(jié)約空間（l相當(dāng)于1，r相當(dāng)于-1,=相當(dāng)于0）/修改時(shí)間：2013-12-25 14:29:44/-#ifndef avltreenode_h#define avltreenode_h#includeuserinfo.hclass avltreenodepublic:userinfo key;avltreenode *left;avltreenode *right;avltre

8、enode *parent;char balancefactor;avltreenode()left = 0;right = 0;parent = 0;balancefactor = =;avltreenode(userinfo s)key = s;left = 0;right = 0;parent = 0;balancefactor = =;#endif/=/ avltree.h/ avl平衡樹(shù)，實(shí)現(xiàn)了添加、查找、圖形輸出等功能/ author: hufeiya zjut/ 2013-12-4 14:38:04/ 2013-12-24 14:35:42 添加了刪除方法/ 插入經(jīng)過(guò)3kw數(shù)據(jù)嚴(yán)

9、格測(cè)試，刪除不嚴(yán)格測(cè)試/=#ifndef avltree_h#define avltree_h#include #include #include #include avltreenode.husing namespace std;class avltreeprivate:public:avltree(); avltree(); /析構(gòu)函數(shù)。調(diào)用void insert(avltreenode *n); /插入元素。調(diào)用void graph(); /圖形輸入。調(diào)用void inorder(ofstream & fs); /中序遍歷修改文件。調(diào)用avltreenode* find(userinfo

10、 target); /查找元素，返回地址。void remove(userinfo key); /刪除元素。調(diào)用private:avltreenode *root;void cleartree(avltreenode *n);/清除所有元素void graphaux(avltreenode *subtree,int a);/遞歸圖形輸出void inorderaux(ofstream & fs,avltreenode *subtree);/遞歸中序遍歷void restoreavl(avltreenode *ancestor, avltreenode *newnode);/添加節(jié)點(diǎn)后重建樹(shù)vo

11、id adjustbalancefactors(avltreenode *end, avltreenode *start);/調(diào)整平衡因子(插入時(shí))void rotateleft(avltreenode *n);/左旋，插入刪除共用void rotateright(avltreenode *n);/右旋，插入刪除共用void search2(const userinfo &data,bool &found,avltreenode *&x,avltreenode *&parent);/remove輔助函數(shù)void restoreavl2(avltreenode *start,bool left)

12、;/刪除節(jié)點(diǎn)后后重建樹(shù);#endif/-/interface.h/界面類(lèi)/功能：構(gòu)建界面、讀取和寫(xiě)入文件/修改時(shí)間：2013-12-25 14:27:17/-#ifndef interface_h#define interface_h#include #include #include #include #include avltree.husing namespace std;class interfacepublic:interface();/構(gòu)造函數(shù)，讀取文件，創(chuàng)建并建立樹(shù)interface();/保存信息到文件，銷(xiāo)毀樹(shù)，關(guān)閉文件void mainface();void login();

13、void adduser();void removeuser();void update();private:avltree *data;ifstream readstream;ofstream writestream;#endif/-/userinfo.h/用戶(hù)信息類(lèi)/功能：儲(chǔ)存用戶(hù)名、密碼等信息，重載部分操作符/修改時(shí)間：2013-12-25 14:26:05/-#ifndef userinfo_h#define userinfo_h#include #include using namespace std;class userinfopublic:userinfo()userinfo(s

14、tring name,string pass);userinfo(string name);/缺省密碼等于賬號(hào)userinfo(char* name);/缺省密碼等于賬號(hào)userinfo(const userinfo &b);/復(fù)制構(gòu)造函數(shù)friend bool operator (const userinfo &a,const userinfo &b);bool operator = (const userinfo &b);friend ostream& operator (ostream &os,const userinfo &b);friend class interface;frien

15、d class avltree;private:string username;string password;#endif下面是.cpp文件main.cpp:#include avltree.h#include #include #include #include #include #include #include interface.h#pragma warning(disable:4996)using namespace std;#define max 10000000string amax;avltreenode* pmax;void randomtest();/隨機(jī)數(shù)測(cè)試void

16、ordertest();/順序插入測(cè)試void deletetest();/刪除測(cè)試void main_interface();/主界面int main()/ordertest();/randomtest();/deletetest();main_interface();return 0;void deletetest()avltree & a = *new avltree();avltreenode *p = new avltreenode(4);a.insert(p);p = new avltreenode(15);a.insert(p);p = new avltreenode(21);a

17、.insert(p);p = new avltreenode(38);a.insert(p);p = new avltreenode(14);a.insert(p);p = new avltreenode(18);a.insert(p);p = new avltreenode(28);a.insert(p);p = new avltreenode(6);a.insert(p);p = new avltreenode(5);a.insert(p);p = new avltreenode(7);a.insert(p);p = new avltreenode(1);a.insert(p);p = n

18、ew avltreenode(2);a.insert(p);p = new avltreenode(100);a.insert(p);p = new avltreenode(8);a.insert(p);a.graph();a.remove(3);a.graph();a.remove(2);a.graph();a.remove(7);a.graph();delete &a;void randomtest()/freopen(g:1.txt,w,stdout);avltree &at = *new avltree();int s = 0;stringstream ss;map stlmap;sr

19、and(int)time(0);for (int i = 0; i max;i+)ssai;pi = new avltreenode(ai);ss.clear();cout隨機(jī)字符串生成完畢，現(xiàn)在插入到avl樹(shù)n;double oldtime = clock(),newtime;while(s max)at.insert(ps);s+;/coutsendl;/at.graph();newtime = clock() - oldtime;cout寫(xiě)入max個(gè)數(shù)據(jù)進(jìn)入avl共用時(shí)newtime/1000秒n;cout現(xiàn)在測(cè)試stlmap，寫(xiě)入相同字符串集合n;oldtime = clock();f

20、or(int i =0; i max;i+)stlmapai+;newtime = clock() - oldtime;cout寫(xiě)入max個(gè)數(shù)據(jù)進(jìn)入stl map共用時(shí)newtime/1000秒n;couttempname)userinfo tempuser(tempname);oldtime = clock();address = at.find(tempuser);if(0 != address)cout已找到,在地址為address處n;elsecout未找到n;newtime = clock() - oldtime;cout查找共用時(shí)newtime毫秒n;delete &at;void

21、 ordertest()/freopen(g:1.txt,w,stdout);avltree &at = *new avltree();int s = 0;stringstream ss;map stlmap;int temp;string zeronum = ,0,00,000,0000,00000,000000,0000000,00000000,000000000,;srand(int)time(0);for (int i = 1; i max;i+)string tempzero;int num =0;for(int j =i; j max;j*=10)num += 1;sstemp1;

22、tempzero += zeronumnum;tempzero += temp1;ai = tempzero;pi = new avltreenode(ai);ss.clear();cout順序字符串生成完畢，現(xiàn)在插入到avl樹(shù)n;double oldtime = clock(),newtime;while(s max)at.insert(ps);s+;/coutsendl;/at.graph();newtime = clock() - oldtime;cout寫(xiě)入max個(gè)順序字符進(jìn)入avl共用時(shí)newtime/1000秒n;cout現(xiàn)在測(cè)試stlmap，寫(xiě)入相同字符串集合n;oldtime

23、= clock();for(int i =0; i max;i+)stlmapai+;newtime = clock() - oldtime;cout寫(xiě)入max個(gè)順序字符進(jìn)入stl map共用時(shí)newtime/1000秒n;couttempname)userinfo tempuser(tempname);oldtime = clock();address = at.find(tempuser);if(0 != address)cout已找到,在地址為address處n;elsecout未找到n;newtime = clock() - oldtime;cout查找共用時(shí)newtime毫秒n;de

24、lete &at;void main_interface()interface &test = *new interface();delete &test;userinfo.cpp#include userinfo.huserinfo:userinfo(string name,string pass)username = name;password = pass;userinfo:userinfo(string name)username = name;password = name;userinfo:userinfo(char* name)username = name;password =

25、 name;userinfo:userinfo(const userinfo &b)/復(fù)制構(gòu)造函數(shù)username = b.username;password = b.password;bool operator (const userinfo &a,const userinfo &b)return a.username (const userinfo &a,const userinfo &b)return a.username b.username;bool userinfo:operator = (const userinfo &b)if(this-username = b.usernam

26、e)return true;elsereturn false;ostream& operator (ostream &os,const userinfo &b)osb.username;return os;interface.cpp#includeinterface.h/構(gòu)造函數(shù)，讀取文件，創(chuàng)建并建立樹(shù)interface:interface()readstream.open(database.data);if(!readstream.is_open()cerrnamepass)userinfo info(name,pass);avltreenode *node = new avltreenod

27、e(info);data-insert(node);mainface();void interface:mainface()while(true)cout-n;cout 1.登陸驗(yàn)證n;cout 2.添加用戶(hù)n;cout 3.刪除用戶(hù)n;cout 4.修改密碼n;cout 0.退出n;coutchoose;system(cls);switch (choose)case 1:login();break;case 2:adduser();break;case 3:removeuser();break;case 4:update();break;case 0:return;break;default

28、:cerr輸入不正確，請(qǐng)重新輸入n;system(pause);system(cls);break;void interface:login()while(true)cout-n;cout請(qǐng)輸入賬號(hào)，密碼（0 0返回上級(jí)）n;couttemp.usernametemp.password;system(cls);if(temp.username = 0 & temp.password = 0)return;avltreenode *nodefound = 0;nodefound = data-find(temp);if(nodefound = 0)cerrkey.password != temp

29、.password)cerr密碼錯(cuò)誤,請(qǐng)重新輸入n;system(pause);system(cls);elsecout登陸成功！n;system(pause);system(cls);return;void interface:adduser()while (true)cout-n;cout請(qǐng)輸入新添加的賬號(hào)，密碼（0 0返回上級(jí)）n;couttemp.usernametemp.password;system(cls);if(temp.username = 0 & temp.password = 0)return;if(data-find(temp) != 0)cerrinsert(temp

30、node);cout添加成功！按任意鍵返回n;system(pause);system(cls);return;void interface:removeuser()while (true)cout-n;cout請(qǐng)輸入要?jiǎng)h除的賬號(hào)，密碼（0 0返回上級(jí)）n;couttemp.usernametemp.password;system(cls);if(temp.username = 0 & temp.password = 0)return;avltreenode *nodefound = 0;nodefound = data-find(temp);if(nodefound = 0)cerrkey.

31、password != temp.password)cerrremove(temp);cout刪除成功！n;system(pause);system(cls);return;void interface:update()cout-n;cout請(qǐng)輸入要更新的賬號(hào)和舊密碼（0 0返回上級(jí)）n;couttemp.usernametemp.password;system(cls);if(temp.username = 0 & temp.password = 0)return;avltreenode *nodefound = 0;nodefound = data-find(temp);if(nodefo

32、und = 0)cerrkey.password != temp.password)cerr密碼錯(cuò)誤,請(qǐng)重新輸入n;system(pause);system(cls);elsecoutnewtemp;nodefound-key.password = newtemp;coutinorder(writestream);writestream.close();delete data;avltree.cpp:#includeavltree.h#include /-/ 默認(rèn)構(gòu)造/-avltree:avltree() root = null; / initialize root to null/-/ 析構(gòu)

33、函數(shù)/-avltree:avltree() /調(diào)用私有成員函數(shù)cleartree cleartree(root);/-/ cleartree()/ 后續(xù)遍歷刪除節(jié)點(diǎn)/-void avltree:cleartree(avltreenode *n) if(n != null) cleartree(n-left); cleartree(n-right); delete n; /-/ insert()/ 插入一個(gè)節(jié)點(diǎn)到樹(shù)中然后重建該樹(shù)/-void avltree:insert(avltreenode *newnode) avltreenode *temp, *back, *ancestor; temp

34、 = root; back = null; ancestor = null; / 先檢查是否為空樹(shù) if(root = null) root = newnode; return; / 不是空樹(shù)所以查找插入點(diǎn) while(temp != null) / 從樹(shù)根遍歷直至null back = temp; / 查找 ancestor，ancestor 為離插入點(diǎn)最近的不平衡的節(jié)點(diǎn)（平衡因子不是=） / 新節(jié)點(diǎn)被插入 if(temp-balancefactor != =) ancestor = temp; if(newnode-key key) temp = temp-left; else if(ne

35、wnode-key temp-key) temp = temp-right; else / cerr元素重復(fù)parent = back; / 先讓back指向它父親 if(newnode-key key) / 插入左子樹(shù) back-left = newnode; else / 插入右子樹(shù) back-right = newnode; / 調(diào)用restoreavl成員函數(shù)重新平衡該樹(shù) restoreavl(ancestor, newnode);/-/ restoreavl() / 功能：當(dāng)插入一個(gè)節(jié)點(diǎn)后重新平衡該樹(shù)/ ancestor:為離插入點(diǎn)最近的不平衡的節(jié)點(diǎn)（平衡因子不是=）/ newnod

36、e :新插入的節(jié)點(diǎn) /-void avltree:restoreavl(avltreenode *ancestor, avltreenode *newnode) /- / case 1: ancestor為沒(méi)找到,插入不影響平衡性 /- if(ancestor = null) if(newnode-key key) / 調(diào)整根的平衡因子 root-balancefactor = l; else root-balancefactor = r; / 調(diào)整平衡因子 adjustbalancefactors(root, newnode); /- / case 2: ancestor 存在，但不影響平衡性的情況 / ancestor.balancefactor = l 且 新插入點(diǎn)插入到右子樹(shù) / 或者 / ancestor.balancefactor = r 且 新插入點(diǎn)插入到左子樹(shù) /- else if(ancestor-balancefactor = l) & (newnode-key ancestor-key) | (ancestor-balancefactor = r) & (ne