田曉輝

（渭南師范學院網(wǎng)絡安全與信息化學院， 陜西渭南 714099）

1 樹形結(jié)構(gòu)

1.1 樹的定義[1]

一棵有根樹T，簡稱為樹，可定義為n(n≥0)個結(jié)點的有限集合。當n=0時，T稱為空樹；否則，T是非空樹，記作：

1.2 樹的存儲結(jié)構(gòu)

樹的主要存儲結(jié)構(gòu)有以下三種[2]：

[1]雙親表示法：

用一組連續(xù)的空間來存儲樹中的結(jié)點，在保存每個結(jié)點的同時附設一個指示器來指示其雙親結(jié)點在表中的位置。

[2]孩子表示法

把每個結(jié)點的孩子結(jié)點排列起來，構(gòu)成一個單鏈表，稱為孩子鏈表。n個結(jié)點共有n 個孩子鏈表（葉子結(jié)點的孩子鏈表為空表），而 n 個結(jié)點的數(shù)據(jù)和 n個孩子鏈表的頭指針又組成一個順序表。

[3]孩子兄弟表示法

這種表示法又稱為樹的二叉表示法，或者二叉鏈表表示法，即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中每個結(jié)點設有兩個鏈域，分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟（右兄弟）結(jié)點。

2 課程設計

2.1 問題描述

給出某操作系統(tǒng)的目錄和文件信息，編程將其以樹狀結(jié)構(gòu)顯示。輸入的信息有兩種，第一種為目錄信息。目錄下面可以存放文件或子目錄，即目錄結(jié)點可能存在孩子結(jié)點，若存在，其孩子結(jié)點信息要求在該目錄信息的下一行給出，孩子結(jié)點信息要求用圓括號“（）”括起。目錄的輸入格式為：[目錄名稱]大小。第二種是文件信息。輸入格式為：文件名稱 大小。目錄名或文件名為長度小于等于10的字符串，且目錄名或文件名不能包含‘（’，‘）’和‘*’。目錄的“大小”都表示為 1，文件的“大小”輸入值為文件的實際大小。

編程實現(xiàn)如下輸出，要求是有層次結(jié)構(gòu)的樹，每層結(jié)點（目錄結(jié)點或文件結(jié)點）都要比上一層結(jié)點多縮進多個空格。同層目錄或文件結(jié)點在同一列顯示。計算所有目錄的大小(為其子目錄大小+子文件大小+1)，并在目錄名和文件后面顯示各自大小。

2.2 算法思想

本文對目錄樹采用孩子兄弟鏈表法結(jié)合雙親法的存儲結(jié)構(gòu)，根據(jù)輸入的目錄和文件信息，先創(chuàng)建樹，再把孩子兄弟存儲結(jié)構(gòu)的樹以顯式的樹狀結(jié)構(gòu)輸出，每個結(jié)點要按其所在層次作相應的縮進。其中，創(chuàng)建樹采用層序遍歷算法實現(xiàn)，輸出樹采用先序遍歷算法實現(xiàn)。若某結(jié)點的第一個孩子結(jié)點有右孩子結(jié)點（兄弟結(jié)點），則需要按其所在層次進行縮進后輸出連接符|和多個空格；否則只輸出多個空格；計算某目錄的大小時，為該目錄結(jié)點的左子樹（以其第一個孩子為根的樹）所有結(jié)點的“大小”的和再加該目錄的“大小”。

3 實現(xiàn)

3.1 樹的存儲結(jié)構(gòu)

在輸出樹結(jié)構(gòu)時，由于先輸出的是同一層結(jié)點的第一個結(jié)點及其對應的子樹，再輸出同一層結(jié)點的第二個結(jié)點及其對應的子樹，所以，使用孩子兄弟鏈表存儲結(jié)構(gòu)時，用先序遍歷算法遍歷該結(jié)構(gòu)，剛好可以實現(xiàn)上面的輸出順序的要求；其次，由于每一個目錄結(jié)點（雙親結(jié)點）下面可能存在子目錄或文件結(jié)點（孩子結(jié)點），在縮進處理上，輸出子目錄或文件結(jié)點信息時，要比其雙親的目錄結(jié)點信息縮進更多，為了便于處理縮進，在孩子兄弟存儲結(jié)構(gòu)中增加了parent 域，得到了改進后的孩子兄弟存儲結(jié)構(gòu)[3]。

3.2 關(guān)鍵算法的設計

（1）創(chuàng)建樹的改進孩子兄弟存儲結(jié)構(gòu)：

首先讀入根目錄名稱和大小，創(chuàng)建根結(jié)點，將根結(jié)點的三個指針域置空；

讀入下一行目錄或文件信息并創(chuàng)建結(jié)點。創(chuàng)建新結(jié)點，該結(jié)點是根結(jié)點的第一孩子結(jié)點，建立其和根結(jié)點的鏈接。然后循環(huán)做如下的操作：若本行后面還有文件或目錄信息，建立新結(jié)點，建立其和雙親結(jié)點的鏈接，建立其和前一兄弟結(jié)點的鏈接。將該結(jié)點的“大小”值加到根結(jié)點的“大小”中去。重復該過程，直到本行信息讀取結(jié)束。

重復上面的過程，直到整體輸入結(jié)束。

(2)輸出樹：

設當前指針（位置）為根目錄，先輸出根結(jié)點；

將當前指針改為根結(jié)點的第一孩子結(jié)點

循環(huán)做如下操作：

輸出當前指針對應的結(jié)點及其子樹；

將當前指針移向當前指針的下一兄弟結(jié)點；

直至當前指針為空。

4 測試

運行程序時，輸入異常的測試數(shù)據(jù)時，提示“Input Error!”。輸入正確的測試數(shù)據(jù)：

得到如下圖1所示結(jié)果。

圖1 樹型結(jié)構(gòu)

[1]殷人昆.數(shù)據(jù)結(jié)構(gòu)C語言描述[M].北京:機械工業(yè)出版社,2011.6:108-109

[2]耿國華.數(shù)據(jù)結(jié)構(gòu)(用 C語言描述)[M].北京:高等教育出版社.2016:181-183

[3]何欽銘,陳根才.數(shù)據(jù)結(jié)構(gòu)課程設計[M].杭州:浙江大學出版社,2015.8:24-41