課程設(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 實際輸出 155 分析與探討 . 165.1 測試結(jié)果分析 165.2 探討與改進 176 設(shè)計小結(jié) . 171 設(shè)計題目給出Unix下目錄和文件信息，要求編程實現(xiàn)將其排列成一定縮進的樹。具體要 求如下。輸入要求： 輸入數(shù)據(jù)包含幾個測試方案。每一個案例由幾行組成，每一行都代表了目錄樹 的層次結(jié)構(gòu)。第一行代表目錄的根節(jié)點。若是目錄節(jié)點，那么它的孩子節(jié)點將在第 二行中被列出，同時用

2、一對圓括號“ () ”界定。同樣，如果這些孩子節(jié)點鐘某一個 也是目錄的話，那么這個目錄所包含的內(nèi)容將在隨后的一行中列出，有一對圓括號 將首位界定。目錄的輸入格式為：*name size,文件的輸入格式為：name size，其 中*代表當(dāng)前節(jié)點的目錄，n amd弋表文件或目錄的名稱，由一串長度不大于10的字符組成，并且nam字符串中不能包含有(,)',',', * '。size是 該文件 /目錄的大小，為大于 0的整數(shù)。每一個案例中最多只能包含 10層，每一層最 多有10個文件 /目錄。輸出要求：對每一個測試案例，輸出時要求：第d層的文件/目錄名前面需要插入8*

3、d個空格，兄弟節(jié)點之間要在同一列上。不要使用Tab(制表符)來統(tǒng)一輸出的縮進。每一個目錄的大小 (size) 是它包含的所有子目錄和文件大小以及它自身大小的總和。輸入例子：*/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；第 二個根目錄

4、 /usr 下為空。輸出例子：|_*usr24|_*mark17|_hw.c3|_*course13| |_aa.txt12|_*alex6|_hw.c5|_*/usr12 設(shè)計分析目錄結(jié)構(gòu)是一種典型的樹形結(jié)構(gòu)，為了方便對目錄的查找、遍歷等操作，可以 選擇孩子兄弟雙親鏈表來存儲樹的結(jié)構(gòu)。程序中要求對目錄的大小進行重新計算， 根據(jù)用戶的輸入來建立相應(yīng)的孩子兄弟雙親鏈表，最后輸出樹形結(jié)構(gòu)?？梢砸靡?個Tree類，將樹的構(gòu)造、銷毀、目錄的大小重新計算 (reSize)、建立樹形鏈表結(jié)構(gòu) (parse) 、樹形結(jié)構(gòu)輸出 (outPut) 等一系列操作都封裝起來，同時對于每一個樹的 節(jié)點，它的私有變量

5、除了名稱(Name)、大小(Size)和層數(shù)(Depth)之外，根據(jù)孩子 兄弟雙親鏈表表示的需要，還要設(shè)置三個指針，即父指針 (Tree*parent) 、下一個 兄弟指針 (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，用來存放

6、目錄的節(jié)點信息，并定義兩 個整型變量head和rear，head值用來標(biāo)記當(dāng)前節(jié)點的父節(jié)點位置，每處理完一對括 號，head需要增加1，即下一對待處理括號的父節(jié)點在treeArray中要往后移一個 位置。如果當(dāng)前處理的節(jié)點是目錄類型，則將它放在 treeArray 數(shù)組中， rear 是 treeArray 的下標(biāo)變量，加入一個目錄節(jié)點信息， rear 就增加1；如果是文件類型 的目錄，則需要按照Nam和Size建立一個樹的節(jié)點，并和head所指的父節(jié)點建立關(guān) 聯(lián)，但是不用放入 treeArray 中。為進一步說明這個樹形鏈表結(jié)構(gòu)的構(gòu)成，可參考圖 3-1treeArray圖3-1通過parse

7、()構(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é)點是該目錄的兄弟節(jié)點)，

8、所以白努力的時候只需要遍歷 目錄對的左子樹即可。3. 輸出樹形結(jié)構(gòu)的函數(shù) outPut() 輸出是一個先序遍歷的過程。為完成對樹形的輸出，兄弟目錄之間需要相同的 縮進，用 | '上下相連，而父子目錄或父目錄和子文件之間需要設(shè)定正確的縮進， 子目錄或子文件要比父目錄向右縮進 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=O則輸出“ ”

9、， 有相同的縮進，而子節(jié)點總比父節(jié)點向右縮進 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 <string>#inClude <iostream>#inClude <fstream>us

10、ing namespaCe std;string s = "" int startPos = 0; ofstream outfile; ifstream infile;/* 構(gòu)造 Tree 類*/Class Treestring Name; /*樹的根結(jié)點名稱 */int Size; /*樹大小的總和 */Tree* FirstChild; /*Tree* NextSibling; /*Tree* parent; /*樹的大小，用于統(tǒng)計這棵樹本身及其包含的所以子指向它的第一個孩子結(jié)點 */ 指向它的下一個兄弟結(jié)點 */ 指向雙親結(jié)點 */public:Tree(string

11、 Name = "", int Size = 0);/*構(gòu)造函數(shù) */void parse(); /* void reSize(); /* void outPut();Tree(); /*根據(jù)輸入數(shù)據(jù)來建立樹形結(jié)構(gòu) */ 重新統(tǒng)計樹結(jié)點的大小 */* 輸出樹形結(jié)構(gòu) */析構(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 Siz

12、e)this->Name = Name;this->Size = Size;FirstChild = NULL;NextSibling = NULL;parent = NULL;/* 析構(gòu)函數(shù)，刪除同一根結(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 中去 */

13、void Tree:reSize()Tree* temp = this;Size值不變，即為輸入時候的/* 如果當(dāng)前的結(jié)點沒有孩子結(jié)點，則它的 值 */if(temp->FirstChild != 0) temp = temp->FirstChild;while(temp != 0) temp->reSize();Size += temp->Size; temp = temp->NextSibling;/*檢查Nam中有無非法字符*/bool checkName(string s)if(s0!='*' && s.length() &

14、gt; 10) return false;if(s0='*' && s.length() > 11)return false;if(s0!='*'&&(s0='('| s0=')'| s0=''| s0='')return false;for(int i=1;i<s.length();i+)if(si='*'| si='('| si=')'| si=''| si='')retu

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

16、t;"input error!-"<<Name<<endl; exit(0); outfile<<"|_"<<Name<<""<<Size<<"n" outfile.close();/* 輸出當(dāng)前的結(jié)點信息 */temp1= FirstChild;/*用來指向當(dāng)前結(jié)點的子結(jié)點 */while(temp1 != NULL) outfile.open("output.txt",ios:app); if(!outfil

17、e)cout<<"cannot append the output file.n" exit(0);i = 0;temp = temp1; while(temp->parent != NULL)/*當(dāng)前temp指針?biāo)傅慕Y(jié)點如果有兄弟結(jié)點，則置 flag數(shù)組值為1否則置為 0；并由此結(jié)點反復(fù)查詢它的祖先結(jié)點的情況，直到根結(jié)點為止*/if(i>=10)/ 檢查當(dāng)前的父目錄包含的子文件 (或目錄數(shù))是否大于10； cout<<"inputerror!-dictionarycontains more than 10levels.&qu

18、ot;<<endl;exit(0);temp = temp->parent; if(temp->NextSibling != NULL) flagi+ = true;else flagi+ = false;/* 兄弟結(jié)點之間有相同的縮進，子結(jié)點比父結(jié)點向右縮進8個空格 */while(i-) if(flagi = true) outfile<<"|"elseoutfile<<""outfile.close(); temp1->outPut();temp1 = temp1->NextSibling

19、;/* 跳過字符串s中，第(*i)個之后多余的空格*/ void skipWhiteSpace(string& s, int* i)while(s*i = 't' | s*i = ' ') (*i)+;/* 獲取輸入行中一對 '()' 之間的字符串，即為同一雙親結(jié)點下的子結(jié)點string getSubDir(string& line, int* startPos)string res = "" skipWhiteSpace(line,startPos); while(line*startPos != '

20、)') res += line(*startPos)+;res += line(*startPos)+; skipWhiteSpace(line, startPos);return res;/*由于用戶輸入時候目錄的大小Size值為String類型，因此需要將它轉(zhuǎn)變成integer 類型*/int stringToNum(string s)int num = 0;unsigned int i = 0;while(i < s.length()num *= 10;num += si+ - '0'return num;/* 提取目錄 /文件的名稱 */ string g

21、etName(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 = ""while(unsigned int)(*i) < s.length() && s*i

22、!= ' ' && s*i !='t' && s *i != ')')size += s(*i)+; return stringToNum(size);/* 根據(jù)用戶的輸入字符串來構(gòu)建樹的結(jié)構(gòu) */ void Tree:parse()Tree* temp;string line;string name;int size;/*head 值用來標(biāo)記當(dāng)前結(jié)點的雙親結(jié)點位置；如果當(dāng)前處理的結(jié)點是目 錄類型，則將它放在 treeArray 數(shù)組中，下標(biāo)用 rear 來記錄；如果是文件類型的 目錄，只需要按照nam罰size建

23、立一個樹的結(jié)點，但是不用放入 treeArray中while(getline(infile,line,'n')startPos = 0;while(1)s = getSubDir(line, &startPos);int i = 1;skipWhiteSpace(s, &i);if(si != ')')newskipWhiteSpace(s,&i); name = getName(s,&i); skipWhiteSpace(s,&i); size = getSize(s,&i); temp = treeArrayh

24、ead%100->FirstChild 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->NextSibli

25、ng = new Tree(name,size); skipWhiteSpace(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*/

26、int main()Tree* fileTree;string s;string name;int size;outfile.open("output.txt");if(!outfile)cout<<"cannot open the output file!n" exit(0);outfile<<"The result is as follows:n" outfile.close();infile.open("input.txt",ios:out);if(!infile)cout<&l

27、t;"cannot open the input file!n" exit(0);while(getline(infile,s,'n')int i = 0; skipWhiteSpace(s, &i); name = getName(s,&i); skipWhiteSpace(s,&i); size = getSize(s,&i);fileTree = new Tree(name, size); if(name0 = '*')treeArrayrear+ = fileTree; fileTree->par

28、se(); fileTree->reSize(); fileTree->outPut(); delete fileTree;infile.close();return 0;4測試方法4.1 測試目的 為了測試程序的正確性，需要分別測試它在正常情況和異常情況下的表現(xiàn)情 況。正常情況下的輸入數(shù)據(jù)要求是：目錄的初始大小一般設(shè)為 1，目錄名中不能包 含(', )', ', '和 * '這些字符，加入多余的空格不影響最后的輸出 結(jié)果；同一父目錄下的兄弟節(jié)點用一對圓括號括起來；同一層上的不同父節(jié)點下的 子節(jié)點均列在同一行中，但按照父節(jié)點的不同永圓括號加以

29、界定。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 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

30、.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|_*/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 |_*fall96