課程設(shè)計樹的遍歷

1、.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計樹的遍歷專業(yè)計算機科學(xué)與技術(shù)班級xxxxx學(xué)號xxxxxx學(xué)生姓名xxxxxxxxx目 錄1 設(shè)計題目12 設(shè)計分析23 設(shè)計實現(xiàn)44.2 測試輸入134.3 正確輸出144.4 實際輸出165 分析與探討175.1 測試結(jié)果分析175.2 探討與改進(jìn)176 設(shè)計小結(jié)171 設(shè)計題目 給出Unix下目錄和文件信息，要求編程實現(xiàn)將其排列成一定縮進(jìn)的樹。具體要求如下。輸入要求：輸入數(shù)據(jù)包含幾個測試方案。每一個案例由幾行組成，每一行都代表了目錄樹的層次結(jié)構(gòu)。第一行代表目錄的根節(jié)點。若是目錄節(jié)點，那么它的孩子節(jié)點將在第二行中被列出，同時用一對圓括號“()”界定。同樣，如果這些孩子節(jié)點

2、鐘某一個也是目錄的話，那么這個目錄所包含的內(nèi)容將在隨后的一行中列出，有一對圓括號將首位界定。目錄的輸入格式為：*name size,文件的輸入格式為：name size，其中*代表當(dāng)前節(jié)點的目錄，name代表文件或目錄的名稱，由一串長度不大于10的字符組成，并且name字符串中不能包含有(,),*。size是該文件/目錄的大小，為大于0的整數(shù)。每一個案例中最多只能包含10層，每一層最多有10個文件/目錄。輸出要求：對每一個測試案例，輸出時要求：第d層的文件/目錄名前面需要插入8*d個空格，兄弟節(jié)點之間要在同一列上。不要使用Tab(制表符)來統(tǒng)一輸出的縮進(jìn)。每一個目錄的大小(size)是它包含的

3、所有子目錄和文件大小以及它自身大小的總和。輸入例子：*/usr1(*mark 1 *alex 1)(hw.c3 *course 1)(hw.c 5)(aa.txt 12)*/usr 1()表示含有兩個不同的根目錄，目錄名都是/usr,第一個根目錄/usr下包含mark和alex兩個子目錄，mark目錄下包含大小為3的文件hw.c和子目錄course,alex目錄下有一個大小為5的文件hw.c，子目錄course下包含文件aa.txt，其大小為12；第二個根目錄/usr下為空。輸出例子：|_*usr24 |_*mark17| |_hw.c3| |_*course13| |_aa.txt12|_*

4、alex6 |_hw.c5 |_*/usr12 設(shè)計分析目錄結(jié)構(gòu)是一種典型的樹形結(jié)構(gòu)，為了方便對目錄的查找、遍歷等操作，可以選擇孩子兄弟雙親鏈表來存儲樹的結(jié)構(gòu)。程序中要求對目錄的大小進(jìn)行重新計算，根據(jù)用戶的輸入來建立相應(yīng)的孩子兄弟雙親鏈表，最后輸出樹形結(jié)構(gòu)?？梢砸靡粋€Tree類，將樹的構(gòu)造、銷毀、目錄的大小重新計算(reSize)、建立樹形鏈表結(jié)構(gòu)(parse)、樹形結(jié)構(gòu)輸出(outPut)等一系列操作都封裝起來，同時對于每一個樹的節(jié)點，它的私有變量除了名稱(Name)、大小(Size)和層數(shù)(Depth)之外，根據(jù)孩子兄弟雙親鏈表表示的需要，還要設(shè)置三個指針，即父指針(Tree*paren

5、t)、下一個兄弟指針(Tree*NextSibling)和第一個孩子指針(Tree*FirstChild)。1.建立樹形鏈表結(jié)構(gòu)的函數(shù)parse()根據(jù)輸入來確定樹形關(guān)系時，首先讀取根節(jié)點目錄/文件名和大小值，并根據(jù)這些信息建立一個新的節(jié)點；然后讀入后面各行信息，對于同一括號中的內(nèi)容，即具有相同父節(jié)點的那些節(jié)點建立兄弟關(guān)聯(lián)。這個函數(shù)實際上是采取遍歷建立樹形鏈表結(jié)構(gòu)。定義一個Tree*類型的數(shù)組treeArray，用來存放目錄的節(jié)點信息，并定義兩個整型變量head和rear，head值用來標(biāo)記當(dāng)前節(jié)點的父節(jié)點位置，每處理完一對括號，head需要增加1，即下一對待處理括號的父節(jié)點在treeArra

6、y中要往后移一個位置。如果當(dāng)前處理的節(jié)點是目錄類型，則將它放在treeArray數(shù)組中，rear是treeArray的下標(biāo)變量，加入一個目錄節(jié)點信息，rear就增加1；如果是文件類型的目錄，則需要按照Name和Size建立一個樹的節(jié)點，并和head所指的父節(jié)點建立關(guān)聯(lián)，但是不用放入treeArray中。為進(jìn)一步說明這個樹形鏈表結(jié)構(gòu)的構(gòu)成，可參考圖3-1。treeArrayFirstChild/usrmarkalexhw.ccoursehw.caa.txtparentNextSiblingparentFirstChildparentparentFirstChildparentNextSiblin

7、g圖3-1通過parse()構(gòu)建的數(shù)據(jù)結(jié)構(gòu)事例它是根據(jù)如下的具體輸入例子所形成的結(jié)構(gòu)示意。輸入：*/usr1(*mark 1 *alex 1)(hw.c3 *course 1)(hw.c 5)(aa.txt 12)形成的數(shù)據(jù)結(jié)構(gòu)如圖2.5所示。2.目錄大小重新計算函數(shù)reSize()輸入數(shù)據(jù)中對目錄大小的初始值一般為1，而目錄的真正大小應(yīng)該是自身的大小和它包含的所有文件及子目錄的大小之和。因此，在計算目錄大小的時候，需要遍歷它下面所有的文件和子目錄，可以采用遞歸嵌套的后序遍歷方式。另外要注意，采用孩子兄弟雙親鏈表表示時，父目錄下的所有子目錄和子文件都在該父目錄的左子樹上（右子樹第一個節(jié)點是該目

8、錄的兄弟節(jié)點），所以白努力的時候只需要遍歷目錄對的左子樹即可。3.輸出樹形結(jié)構(gòu)的函數(shù)outPut()輸出是一個先序遍歷的過程。為完成對樹形的輸出，兄弟目錄之間需要相同的縮進(jìn)，用|上下相連，而父子目錄或父目錄和子文件之間需要設(shè)定正確的縮進(jìn)，子目錄或子文件要比父目錄向右縮進(jìn)8個空格。設(shè)置一個標(biāo)志數(shù)組flag11(每個目錄下最大的層次數(shù)為10)，當(dāng)前Tree*temp指針?biāo)傅墓?jié)點如果有兄弟節(jié)點，則置flag數(shù)組值為1，否則置為0；并由此節(jié)點反復(fù)查詢它的祖先節(jié)點的情況，直到根節(jié)點為止。輸出時，遇到flag=1時，屏幕輸出“| ”，表明是兄弟節(jié)點；遇到flag=0則輸出“ ”， 有相同的縮進(jìn)，而子節(jié)點

9、總比父節(jié)點向右縮進(jìn)8個空格。4.消除輸入中多余空格的函數(shù)skipWhiteSpace(string &s,int *i)從用戶輸入數(shù)據(jù)中讀入一行后，調(diào)用該函數(shù)來跳過s字符串中si之后的空格，以方便后面的處理。此外，關(guān)于讀入目錄名稱、大小，以及將string類型的Size值轉(zhuǎn)換成int類型的函數(shù)的實現(xiàn)，相對比較簡單，此處不再贅述。3 設(shè)計實現(xiàn)利用visual c+，新建一個c+文件，將以下代碼輸入。#include #include #include using namespace std;string s = ;int startPos = 0;ofstream outfile;ifstrea

10、m infile;/*構(gòu)造Tree類*/class Treestring Name; /* 樹的根結(jié)點名稱 */int Size; /* 樹的大小，用于統(tǒng)計這棵樹本身及其包含的所以子樹大小的總和*/Tree* FirstChild; /* 指向它的第一個孩子結(jié)點 */Tree* NextSibling; /* 指向它的下一個兄弟結(jié)點 */Tree* parent; /* 指向雙親結(jié)點 */public:Tree(string Name = , int Size = 0);/* 構(gòu)造函數(shù) */void parse(); /* 根據(jù)輸入數(shù)據(jù)來建立樹形結(jié)構(gòu) */void reSize(); /* 重

11、新統(tǒng)計樹結(jié)點的大小 */void outPut();/* 輸出樹形結(jié)構(gòu) */Tree(); /* 析構(gòu)函數(shù) */;/* 樹結(jié)點數(shù)組treeArray,以及用來標(biāo)注雙親結(jié)點位置的head和目錄結(jié)點的rear*/Tree* treeArray100;int head = 0, rear = 0;/* 建立只有一個結(jié)點的樹，其三個指針域均為空 */Tree:Tree(string Name, int Size)this-Name = Name;this-Size = Size;FirstChild = NULL;NextSibling = NULL;parent = NULL;/* 析構(gòu)函數(shù)，刪除同

12、一根結(jié)點下的各個子結(jié)點，釋放空間 */Tree:Tree()Tree* temp;Tree* temp1;temp = FirstChild;while(temp != NULL)temp1 = temp;temp = temp-NextSibling;delete temp1;/* 先序遍歷根結(jié)點下的所有結(jié)點，將每一個結(jié)點的Size值都加到根結(jié)點的Size中去*/void Tree:reSize()Tree* temp = this; /* 如果當(dāng)前的結(jié)點沒有孩子結(jié)點，則它的Size值不變，即為輸入時候的值 */if(temp-FirstChild != 0)temp = temp-Firs

13、tChild;while(temp != 0)temp-reSize();Size += temp-Size;temp = temp-NextSibling;/*檢查Name中有無非法字符*/bool checkName(string s)if(s0!=* & s.length() 10)return false;if(s0=* & s.length() 11)return false;if(s0!=* & (s0=( | s0=) | s0= | s0=)return false;for(int i=1;is.length();i+)if(si=* | si=( | si=) | si= |

14、 si=)return false;return true;/* 按照先序遍歷的方式有縮進(jìn)地來輸出樹形結(jié)構(gòu) */void Tree:outPut()Tree* temp; /*用來指向當(dāng)前結(jié)點的祖先結(jié)點*/Tree* temp1;bool flag11;/*用來標(biāo)志輸出縮進(jìn)、層次情況的數(shù)組*/int i;outfile.open(output.txt,ios:app);if(!outfile)coutcannot append the output file.n;exit(0);if(!checkName(Name)coutinput error!-Nameendl;exit(0);outfi

15、le|_NameSizen;outfile.close(); /* 輸出當(dāng)前的結(jié)點信息 */temp1= FirstChild;/* 用來指向當(dāng)前結(jié)點的子結(jié)點 */while(temp1 != NULL)outfile.open(output.txt,ios:app);if(!outfile)coutparent != NULL)/*當(dāng)前temp指針?biāo)傅慕Y(jié)點如果有兄弟結(jié)點，則置flag數(shù)組值為1，否則置為0；并由此結(jié)點反復(fù)查詢它的祖先結(jié)點的情況，直到根結(jié)點為止*/if(i=10)/檢查當(dāng)前的父目錄包含的子文件(或目錄數(shù))是否大于10；coutinput error!-dictionary c

16、ontains more than 10 levels.parent; if(temp-NextSibling != NULL)flagi+ = true; elseflagi+ = false;/*兄弟結(jié)點之間有相同的縮進(jìn)，子結(jié)點比父結(jié)點向右縮進(jìn)8個空格*/while(i-)if(flagi = true)outfile| ;elseoutfileoutPut();temp1 = temp1-NextSibling;/* 跳過字符串s中，第(*i)個之后多余的空格 */void skipWhiteSpace(string& s, int* i)while(s*i = t | s*i = )(

17、*i)+;/* 獲取輸入行中一對()之間的字符串，即為同一雙親結(jié)點下的子結(jié)點 */string getSubDir(string& line, int* startPos)string res = ;skipWhiteSpace(line,startPos);while(line*startPos != )res += line(*startPos)+;res += line(*startPos)+;skipWhiteSpace(line, startPos);return res;/* 由于用戶輸入時候目錄的大小Size值為String類型，因此需要將它轉(zhuǎn)變成integer類型*/int s

18、tringToNum(string s)int num = 0;unsigned int i = 0;while(i s.length()num *= 10;num += si+ - 0;return num;/* 提取目錄/文件的名稱 */string getName(string& s, int* i)string name = ;while(s*i != & s*i != t)name += s(*i)+;return name;/* 提取目錄/文件的大小，然后將string類型轉(zhuǎn)換成integer類型 */int getSize(string&s, int* i)string size

19、 = ;while(unsigned int)(*i) FirstChild = new Tree(name,size);temp-parent = treeArrayhead%100;if(name0 = *)treeArray(rear+)%100 = temp;skipWhiteSpace(s,&i);while(si != )skipWhiteSpace(s,&i);name = getName(s,&i);skipWhiteSpace(s,&i);size = getSize(s,&i);temp-NextSibling = new Tree(name,size);skipWhite

20、Space(s,&i);temp = temp-NextSibling;temp-parent = treeArrayhead%100;if(name0 = *)treeArray(rear+)%100 = temp;head +; /*測試是否一行掃描完畢*/if(unsigned int)startPos = line.length()break; /*只有一個根結(jié)點的情況*/if(head = rear)break;/* 主測試文件main.cpp*/int main()Tree* fileTree;string s;string name;int size;outfile.open(o

21、utput.txt);if(!outfile)coutcannot open the output file!n;exit(0);outfileThe result is as follows:n;outfile.close();infile.open(input.txt,ios:out);if(!infile)coutparse();fileTree-reSize();fileTree-outPut();delete fileTree;infile.close();return 0;4測試方法4.1測試目的為了測試程序的正確性，需要分別測試它在正常情況和異常情況下的表現(xiàn)情況。正常情況下的輸入

22、數(shù)據(jù)要求是：目錄的初始大小一般設(shè)為1，目錄名中不能包含(,),和*這些字符，加入多余的空格不影響最后的輸出結(jié)果；同一父目錄下的兄弟節(jié)點用一對圓括號括起來；同一層上的不同父節(jié)點下的子節(jié)點均列在同一行中，但按照父節(jié)點的不同永圓括號加以界定。4.2 測試輸入*/usr 1(*mark 1 *alex 1)(hw.c 3 *course 1) (hw.c 5)(aa.txt 12)*/usr 1()*/usr000009 1(*mark 1 *alex 1 *bill 1)(*book 1 *course 1 junk.c 6) (junk.c 8) (*work 1 *course 1)(ch1.r

23、 3 ch2.r 2 ch3.r 4) (*cop3530 1) () (*cop3212 1)(*fall96 1 *spr97 1 *sum97 1) (*fall96 1 *fall97 1)(syl.r 1) (syl.r 5) (syl.r 2) (grades 3 prog1.r 4 prog2.r 1) (prog2.r 2 prog1.r 7 grades 9)4.3 正確輸出The result is as follows:|_*/usr24 |_*mark17 | |_hw.c3 | |_*course13 | |_aa.txt12 |_*alex6 |_hw.c5|_*/

24、usr1|_*/usr00000972 |_*mark30 | |_*book10 | | |_ch1.r3 | | |_ch2.r2 | | |_ch3.r4 | |_*course13 | | |_*cop353012 | | |_*fall962 | | | |_syl.r1 | | |_*spr976 | | | |_syl.r5 | | |_*sum973 | | |_syl.r2 | |_junk.c6 |_*alex9 | |_junk.c8 |_*bill32 |_*work1 |_*course30 |_*cop321229 |_*fall969 | |_grades3 | |_prog1.r4 | |_prog2.r1 |_*fall9719 |_prog2.r2 |_prog1.r7 |_grades9保存此文件，命名為“Tree”，在此文件夾中新建一個名為“input”的文本文件，在此文件中鍵入“測試輸入”的代碼，經(jīng)過運行可以在“