數據結構實驗報告二叉樹應用Unix目錄文件結構顯示

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

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

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

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

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

6、采用遞歸嵌套的后序遍歷方式。另外要注意，采用孩子兄弟雙親鏈表表示時，父目錄下的所有子目錄和子文件都在該父目錄的左子樹上（右子樹第一個節(jié)點是該目錄的兄弟節(jié)點），所以白努力的時候只需要遍歷目錄對的左子樹即可。3.輸出樹形結構的函數outPut() 輸出是一個先序遍歷的過程。為完成對樹形的輸出，兄弟目錄之間需要相同的縮進，用|上下相連，而父子目錄或父目錄和子文件之間需要設定正確的縮進，子目錄或子文件要比父目錄向右縮進8個空格。設置一個標志數組flag11(每個目錄下最大的層次數為10)，當前Tree*temp指針所指的節(jié)點如果有兄弟節(jié)點，則置flag數組值為1，否則置為0；并由此節(jié)點反復查詢它的祖先

7、節(jié)點的情況，直到根節(jié)點為止。輸出時，遇到flag=1時，屏幕輸出“| ”，表明是兄弟節(jié)點；遇到flag=0則輸出“ ”， 有相同的縮進，而子節(jié)點總比父節(jié)點向右縮進8個空格。 4.消除輸入中多余空格的函數skipWhiteSpace(string &s,int *i) 從用戶輸入數據中讀入一行后，調用該函數來跳過s字符串中si之后的空格，以方便后面的處理。 此外，關于讀入目錄名稱、大小，以及將string類型的Size值轉換成int類型的函數的實現(xiàn)，相對比較簡單，此處不再贅述。利用VC+ 6.0將以下代碼輸入#include #include #include using namespace s

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

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

10、hild = NULL;NextSibling = NULL;parent = NULL;/* 析構函數，刪除同一根結點下的各個子結點，釋放空間 */Tree:Tree()Tree* temp;Tree* temp1;temp = FirstChild;while(temp != NULL)temp1 = temp;temp = temp-NextSibling;delete temp1;/* 先序遍歷根結點下的所有結點，將每一個結點的Size值都加到根結點的Size中去*/void Tree:reSize()Tree* temp = this; /* 如果當前的結點沒有孩子結點，則它的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;/* 按照先序遍歷的方式有縮進地來輸出樹形結構 */void Tree:outPut()Tree* temp; /*用來指向當前結點的祖先結點*/Tree* temp1;bool flag11;/*用來標志輸出縮進、層次情況的數組*/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(); /* 輸出當前的結點信息 */temp1= FirstChild;/* 用來指向當前結點的子結點 */while(temp1 != NULL)outfile.open(output.txt,ios:app);if(!outfile)coutparent != NULL)/*當前temp指針所指的結點如果有兄弟結點，則置flag數組值為1，否則置為0；并由此結點反復查詢它的祖先結點的情況，直到根結點為止*/if(i=10)/

14、檢查當前的父目錄包含的子文件(或目錄數)是否大于10；coutinput error!-dictionary contains more than 10 levels.parent; if(temp-NextSibling != NULL)flagi+ = true; elseflagi+ = false;/*兄弟結點之間有相同的縮進，子結點比父結點向右縮進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)+;/* 獲取輸入行中一對()之間的字符串，即為同一雙親結點下的子結點 */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類型，因此需要將它轉變成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、型轉換成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; /*只有一個根結點的情況*/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、 實驗結果： 為了測試程序的正確性，需要分別測試它在正常情況和異常情況下的表現(xiàn)情況。 正常情況下的輸入數據要求是：目錄的初始大小一般設為1，目錄名中不能包含(,),和*這些字符，加入多余的空格不影響最后的輸出結果；同一父目錄下的兄弟節(jié)點用一對圓括號括起來；同一層上的不同父節(jié)點下的子節(jié)點均列在同一行中，但按照父節(jié)點的不同永圓括號加以界定。 測試輸入 */usr 1 (*mark 1 *alex 1) (hw.c 3 *course 1) (hw.c