1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 實(shí)驗(yàn)報告 學(xué)院： 專業(yè)： 班級： 姓名： 學(xué)號： 實(shí)驗(yàn)報告實(shí)驗(yàn)題目：二叉樹應(yīng)用文件目錄結(jié)構(gòu)顯示2、 實(shí)驗(yàn)?zāi)康暮鸵螅?給出Unix下目錄和文件信息，要求編程實(shí)現(xiàn)將其排列成一定縮進(jìn)的樹。具體要求如下。 輸入要求： 輸入數(shù)據(jù)包含幾個測試方案。每一個案例由幾行組成，每一行都代表了目錄樹的層次結(jié)構(gòu)。第一行代表目錄的根節(jié)點(diǎn)。若是目錄節(jié)點(diǎn)，那么它的孩子節(jié)點(diǎn)將在第二行中被列出，同時用一對圓括號“()”界定。同樣，如果這些孩子節(jié)點(diǎn)鐘某一個也是目錄的話，那么這個目錄所包含的內(nèi)容將在隨后的一行中列出，有一對圓括號將首位界定。目錄的輸入格式為：*name size,文件的輸入格式為：name s

2、ize，其中*代表當(dāng)前節(jié)點(diǎn)的目錄，name代表文件或目錄的名稱，由一串長度不大于10的字符組成，并且name字符串中不能包含有(,),*。size是該文件/目錄的大小，為大于0的整數(shù)。每一個案例中最多只能包含10層，每一層最多有10個文件/目錄。 輸出要求： 對每一個測試案例，輸出時要求：第d層的文件/目錄名前面需要插入8*d個空格，兄弟節(jié)點(diǎn)之間要在同一列上。不要使用Tab(制表符)來統(tǒng)一輸出的縮進(jìn)。每一個目錄的大小(size)是它包含的所有子目錄和文件大小以及它自身大小的總和。3、 實(shí)驗(yàn)過程：目錄結(jié)構(gòu)是一種典型的樹形結(jié)構(gòu)，為了方便對目錄的查找、遍歷等操作，可以選擇孩子兄弟雙親鏈表來存儲樹的結(jié)

3、構(gòu)。程序中要求對目錄的大小進(jìn)行重新計(jì)算，根據(jù)用戶的輸入來建立相應(yīng)的孩子兄弟雙親鏈表，最后輸出樹形結(jié)構(gòu)?？梢砸靡粋€Tree類，將樹的構(gòu)造、銷毀、目錄的大小重新計(jì)算(reSize)、建立樹形鏈表結(jié)構(gòu)(parse)、樹形結(jié)構(gòu)輸出(outPut)等一系列操作都封裝起來，同時對于每一個樹的節(jié)點(diǎn)，它的私有變量除了名稱(Name)、大小(Size)和層數(shù)(Depth)之外，根據(jù)孩子兄弟雙親鏈表表示的需要，還要設(shè)置三個指針，即父指針(Tree*parent)、下一個兄弟指針(Tree*NextSibling)和第一個孩子指針(Tree*FirstChild)。 1.建立樹形鏈表結(jié)構(gòu)的函數(shù)parse() 根據(jù)

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

5、rear就增加1；如果是文件類型的目錄，則需要按照Name和Size建立一個樹的節(jié)點(diǎn)，并和head所指的父節(jié)點(diǎn)建立關(guān)聯(lián)，但是不用放入treeArray中。 為進(jìn)一步說明這個樹形鏈表結(jié)構(gòu)的構(gòu)成，可參考下圖。它是根據(jù)如下的具體輸入例子所形成的結(jié)構(gòu)示意。 輸入： */usr1 (*mark 1 *alex 1) (hw.c3 *course 1)(hw.c 5) (aa.txt 12) 2.目錄大小重新計(jì)算函數(shù)reSize() 輸入數(shù)據(jù)中對目錄大小的初始值一般為1，而目錄的真正大小應(yīng)該是自身的大小和它包含的所有文件及子目錄的大小之和。因此，在計(jì)算目錄大小的時候，需要遍歷它下面所有的文件和子目錄，可以

6、采用遞歸嵌套的后序遍歷方式。另外要注意，采用孩子兄弟雙親鏈表表示時，父目錄下的所有子目錄和子文件都在該父目錄的左子樹上（右子樹第一個節(jié)點(diǎn)是該目錄的兄弟節(jié)點(diǎn)），所以白努力的時候只需要遍歷目錄對的左子樹即可。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é)點(diǎn)如果有兄弟節(jié)點(diǎn)，則置flag數(shù)組值為1，否則置為0；并由此節(jié)點(diǎn)反復(fù)查詢它的祖先

7、節(jié)點(diǎn)的情況，直到根節(jié)點(diǎn)為止。輸出時，遇到flag=1時，屏幕輸出“| ”，表明是兄弟節(jié)點(diǎn)；遇到flag=0則輸出“ ”， 有相同的縮進(jìn)，而子節(jié)點(diǎn)總比父節(jié)點(diǎn)向右縮進(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ù)的實(shí)現(xiàn)，相對比較簡單，此處不再贅述。利用VC+ 6.0將以下代碼輸入#include #include #include using namespace s

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

9、數(shù) */void parse(); /* 根據(jù)輸入數(shù)據(jù)來建立樹形結(jié)構(gòu) */void reSize(); /* 重新統(tǒng)計(jì)樹結(jié)點(diǎn)的大小 */void outPut();/* 輸出樹形結(jié)構(gòu) */Tree(); /* 析構(gòu)函數(shù) */;/* 樹結(jié)點(diǎn)數(shù)組treeArray,以及用來標(biāo)注雙親結(jié)點(diǎn)位置的head和目錄結(jié)點(diǎn)的rear*/Tree* treeArray100;int head = 0, rear = 0;/* 建立只有一個結(jié)點(diǎn)的樹，其三個指針域均為空 */Tree:Tree(string Name, int Size)this-Name = Name;this-Size = Size;FirstC

10、hild = NULL;NextSibling = NULL;parent = NULL;/* 析構(gòu)函數(shù)，刪除同一根結(jié)點(diǎn)下的各個子結(jié)點(diǎn)，釋放空間 */Tree:Tree()Tree* temp;Tree* temp1;temp = FirstChild;while(temp != NULL)temp1 = temp;temp = temp-NextSibling;delete temp1;/* 先序遍歷根結(jié)點(diǎn)下的所有結(jié)點(diǎn)，將每一個結(jié)點(diǎn)的Size值都加到根結(jié)點(diǎn)的Size中去*/void Tree:reSize()Tree* temp = this; /* 如果當(dāng)前的結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)，則它的Siz

11、e值不變，即為輸入時候的值 */if(temp-FirstChild != 0)temp = temp-FirstChild;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;

12、for(int i=1;is.length();i+)if(si=* | si=( | si=) | si= | si=)return false;return true;/* 按照先序遍歷的方式有縮進(jìn)地來輸出樹形結(jié)構(gòu) */void Tree:outPut()Tree* temp; /*用來指向當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn)*/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

13、(!checkName(Name)coutinput error!-Nameendl;exit(0);outfile|_NameSizen;outfile.close(); /* 輸出當(dāng)前的結(jié)點(diǎn)信息 */temp1= FirstChild;/* 用來指向當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn) */while(temp1 != NULL)outfile.open(output.txt,ios:app);if(!outfile)coutparent != NULL)/*當(dāng)前temp指針?biāo)傅慕Y(jié)點(diǎn)如果有兄弟結(jié)點(diǎn)，則置flag數(shù)組值為1，否則置為0；并由此結(jié)點(diǎn)反復(fù)查詢它的祖先結(jié)點(diǎn)的情況，直到根結(jié)點(diǎn)為止*/if(i=10)/

14、檢查當(dāng)前的父目錄包含的子文件(或目錄數(shù))是否大于10；coutinput error!-dictionary contains more than 10 levels.parent; if(temp-NextSibling != NULL)flagi+ = true; elseflagi+ = false;/*兄弟結(jié)點(diǎn)之間有相同的縮進(jìn)，子結(jié)點(diǎn)比父結(jié)點(diǎn)向右縮進(jìn)8個空格*/while(i-)if(flagi = true)outfile| ;elseoutfileoutPut();temp1 = temp1-NextSibling;/* 跳過字符串s中，第(*i)個之后多余的空格 */void s

15、kipWhiteSpace(string& s, int* i)while(s*i = t | s*i = )(*i)+;/* 獲取輸入行中一對()之間的字符串，即為同一雙親結(jié)點(diǎn)下的子結(jié)點(diǎn) */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;

16、/* 由于用戶輸入時候目錄的大小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 getName(string& s, int* i)string name = ;while(s*i != & s*i != t)name += s(*i)+;return name;/* 提取目錄/文件的大小，然后將string類

17、型轉(zhuǎn)換成integer類型 */int getSize(string&s, int* i)string size = ;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 = getSiz

18、e(s,&i);temp-NextSibling = 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é)點(diǎn)的情況*/if(head = rear)break;/* 主測試文件main.cpp*/int main()Tre

19、e* fileTree;string s;string name;int size;outfile.open(output.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、 實(shí)驗(yàn)結(jié)果： 為了測試程序的正確性，需要分別測試它在正常情況和異常情況下的表現(xiàn)情況。 正常情況下的輸入數(shù)據(jù)要求是：目錄的初始大小一般設(shè)為1，目錄名中不能包含(,),和*這些字符，加入多余的空格不影響最后的輸出結(jié)果；同一父目錄下的兄弟節(jié)點(diǎn)用一對圓括號括起來；同一層上的不同父節(jié)點(diǎn)下的子節(jié)點(diǎn)均列在同一行中，但按照父節(jié)點(diǎn)的不同永圓括號加以界定。 測試輸入 */usr 1 (*mark 1 *alex 1) (hw.c 3 *course 1) (hw.c