DS博客作业04--树大作业
生活随笔
收集整理的這篇文章主要介紹了
DS博客作业04--树大作业
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
1.樹的存儲(chǔ)結(jié)構(gòu)
本組采用的樹的存儲(chǔ)結(jié)構(gòu)為鏈?zhǔn)浇Y(jié)構(gòu)，選擇如圖所示的結(jié)構(gòu)體
Name為結(jié)點(diǎn)的名稱
LevelNum為孩子節(jié)點(diǎn)的個(gè)數(shù)
*Children[20]用來指向不同的孩子結(jié)點(diǎn)(類似于二叉樹的結(jié)構(gòu)體,且數(shù)組大小這里取20,不夠可以再增加)2.樹的函數(shù)說明
1.void Creatstr(string *str,int &length) 讀取并分割文件中的字符串
strtok是字符串分割函數(shù),作用是將ch字符串中的字符串分割,分割的規(guī)則是在ch碰到與split變量有關(guān)的符號(hào)，都會(huì)將其改成‘\0’例如 split = "<>"ch = <html>用strtok分割后ch就變成了html,注意split中若有空格,ch中的空格也會(huì)被改成'\0',而且不是碰到 <> 在一起時(shí)才會(huì)將其改成'\0',只要字符串中含有 < 或者 > 都會(huì)被其改成'/0'void Creatstr(string *str,int &length)利用這個(gè)函數(shù)strtok()對(duì)讀取到的文件中的字符串進(jìn)行分割并且存入一個(gè)字符串?dāng)?shù)組中比如 文件中的內(nèi)容如下<html><head><title>Demo</title></head><body><div>A<p>B</p>C</div><span>D</span></body></html>利用Creatstr(string *str,int &length)進(jìn)行處理后str字符串?dāng)?shù)組中str[0] = htmlstr[1] = headstr[2] = titlestr[3] = Demostr[4] = /title......依次類推
而length就是字符串?dāng)?shù)組str的大小2.void CreatTree(string str,BTNode &T,int length) 建立多叉樹
利用Creatstr()函數(shù)得到的字符串?dāng)?shù)組str[ ]以及其長度length進(jìn)行建樹，建樹方法如下
建立兩個(gè)類型為<BTNode*>的棧 s1,s2
for i=0 to length-1 //遍歷str
{若str[i][0]!='/' 建立一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的名稱為str[i]，進(jìn)s1棧若str[i][0]=='/' (在s1棧中找到與之匹配的元素，例如 /html 對(duì)應(yīng)html （在下方有解釋）){while (不匹配) { s1.top()進(jìn)s2棧且s1.pop() }找到匹配元素后(經(jīng)過while循環(huán)后匹配元素此時(shí)在s1.top()) { BTNode* T=s1.top() s1.pop() //用指針T存放棧頂元素然后讓棧頂出棧T對(duì)應(yīng)的結(jié)點(diǎn)的孩子結(jié)點(diǎn)個(gè)數(shù)即為棧s2的長度 即T->LevelNum=s2.size()將s2的元素依次出棧直到棧空,并且依次存放到T->Children[ ]中最后將T入s1棧}}
}然后這里是配對(duì)的操作 即代碼中的1 2 3步驟str2=str[i]str2.erase(str2.begin())用str2保存str[i],再用erase函數(shù)去除'/'字符str2.begin()是指向str2字符串的第一個(gè)字符,str.erase(p)就是刪去str中p對(duì)應(yīng)的字符所以str2.erase(str2.begin())是將str2字符串中的第一個(gè)字符串刪去例如 str2=/htmel，經(jīng)過erase()函數(shù)處理后就變成了 html 然后再去找s1中配對(duì)的元素3.int FindPositionCode(BTNode T,string name,int a,int flag,int &flag2)
該函數(shù)有5個(gè)參數(shù)BTNode *T為樹，str name所查找元素的名稱，int *a為數(shù)組的頭地址，且a[ ]數(shù)組中的元素全部為-1int flag為孩子結(jié)點(diǎn)Children[ ]對(duì)應(yīng)的下標(biāo)，頭節(jié)點(diǎn)沒有對(duì)應(yīng)下標(biāo)就用 -1int &flag2為了判斷所查找的元素是否存在，存在時(shí)返回0，不存在時(shí)返回1
該函數(shù)運(yùn)行結(jié)果會(huì)把位置編碼儲(chǔ)存再數(shù)組a[ ]中
而位置編碼由上面的樹狀圖來解釋
例如元素e的位置就為00，f的為01，g的為02，h的為10.....
但是經(jīng)過該函數(shù)處理后的數(shù)組a[ ]中a[0]一定為-1,后面的元素也都會(huì)是-1
所以數(shù)組a有用的部分就是 for a[1] to a[i] (a[i]的下一個(gè)元素a[i+1]=-1)
例如e的位置編碼為00，則數(shù)組a[10]將會(huì)是-1 0 0 -1 -1 -1 -1 -1 -1 -1f的位置編碼為01，則數(shù)組a[10]將會(huì)是-1 0 1 -1 -1 -1 -1 -1 -1 -14.void FindPosition(BTNode T,int a) 按格式輸出元素路徑
該函數(shù)利用上面FindPositionCode()函數(shù)得到的數(shù)組a[ ],然后進(jìn)行處理，最后按格式輸出路徑5.void CreatFileTree(BTNode T,int i,FILE fp) 建立文檔樹并寫入tree.txt文件中
用遞歸遍歷樹T，然后再按照格式輸出文檔樹
(類似于線序遍歷，看代碼慢慢體會(huì))3.樹結(jié)果演示
4.碰到問題
1.選擇樹的結(jié)構(gòu)體上花費(fèi)較多時(shí)間
2.建樹算法為本小組自創(chuàng)的非遞歸算法，在設(shè)計(jì)過程中花費(fèi)較多時(shí)間，最后參考算術(shù)表達(dá)式轉(zhuǎn)化成中綴表達(dá)式的算法設(shè)計(jì)出來
3.在設(shè)計(jì)輸出路徑的功能中，采取先獲取位置編碼然后再進(jìn)行輸出處理的做法也是本小組自創(chuàng)，在設(shè)計(jì)過程中也花費(fèi)較多時(shí)間
4.在調(diào)式上，因?yàn)閭鲄r(shí)忘了加符號(hào)&，導(dǎo)致程序崩潰5.小結(jié)
1.雖然采用了比較不同的結(jié)構(gòu)體，但是采取該結(jié)構(gòu)體后可能會(huì)造成空間上的浪費(fèi)
2.采用該結(jié)構(gòu)體在遍歷時(shí)時(shí)間復(fù)雜度比較高，而且建樹過程較為復(fù)雜
3.好處就是建樹的模型比較清晰做法比較獨(dú)特6.小組成員分配說明
main()函數(shù):劉羽 1.5分
Creatstr()函數(shù):阮承南 1.5分
CreatTree()函數(shù):唐洪俊 2分
FindPositionCode()函數(shù):沈宇濤 2分
FindPositionCode()函數(shù):沈宇濤
CreatFileTree()函數(shù):蔡豐俊 2分
博客園:張明海 1分轉(zhuǎn)載于:https://www.cnblogs.com/syt666/p/10896350.html
總結(jié)
以上是生活随笔為你收集整理的DS博客作业04--树大作业的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： laravel homestead环境默
- 下一篇： CodeForces 375D Tree