立志用最少的代碼做最高效的表達

---

在ZIP歸檔文件中，保留著所有壓縮文件和目錄的相對路徑和名稱。當使用WinZIP等GUI軟件打開ZIP歸檔文件時，可以從這些信息中重建目錄的樹狀結構。請編寫程序實現目錄的樹狀結構的重建工作。

輸入格式:
輸入首先給出正整數N（≤10^4），表示ZIP歸檔文件中的文件和目錄的數量。隨后N行，每行有如下格式的文件或目錄的相對路徑和名稱（每行不超過260個字符）：

路徑和名稱中的字符僅包括英文字母（區分大小寫）；
符號“\”僅作為路徑分隔符出現；
目錄以符號“\”結束；
不存在重復的輸入項目；
整個輸入大小不超過2MB。

輸出格式:
假設所有的路徑都相對于root目錄。從root目錄開始，在輸出時每個目錄首先輸出自己的名字，然后以字典序輸出所有子目錄，然后以字典序輸出所有文件。注意，在輸出時，應根據目錄的相對關系使用空格進行縮進，每級目錄或文件比上一級多縮進2個空格。

輸入樣例:
7
b
c
ab\cd
a\bc
ab\d
a\d\a
a\d\z

輸出樣例:
root
a
d
z
a
bc
ab
cd
d
c
b

---

解決思路

問題分析：

本題主要分為兩個子問題：一是根據輸入的信息建立樹，二是根據樹的結構輸出文件目錄。

根據題目描述，文件樹是一棵普通的數，不是二叉樹，但是仍然可以用左孩子右兄弟的二叉鏈表存儲。由于默認root是根目錄，所以首先建立根節點。在掃描每個文件或目錄的名稱時，都從root出發，逐層向下將每層節點插入相應的兄弟鏈表中。

觀察輸出格式的要求，節點應該是以前序遍歷輸出的。

---

實現要點：

建立樹時，注意輸出順序，即同層目錄排在文件前，同類按字典序輸出。

所以在插入到每個節點時，如果根節點左子樹為空，則直接插入，否則需要在其右子樹中循鏈掃描（它的兄弟節點） 并找到該節點插入的位置。

又注意到可能存在文件與目錄重名的情況，所以在存儲中，必須區別文件名或目錄名。

在輸出中，要注意不同層節點輸出不同的縮進。以層數為參考即可。

---

具體實現邏輯：

設置一個指針指向pos

讀入目錄：將目錄插入到以pos為根的子樹，把pos更新為插入的地址
插入規則：
首先判斷其是否有兒子節點，如果無，則直接建立節點插入即可。
反之，則在其兄弟鏈中查找位置（兒子節點的兄弟鏈）。

如果是文件，則插入以后結束即可。

先序遍歷

---

#include<iostream> #include<cstdio> using namespace std;struct TreeNode{string str;TreeNode* child; //左孩子TreeNode* sibling; //右兄弟int priority; //為0表示文件，為1表示目錄 }; typedef TreeNode* Position; typedef Position BinTree;//建樹，也可以說是初始化的過程 Position createNode(string s, int priority) {Position Node = new TreeNode;Node->str = s;Node->child = Node->sibling = NULL;Node->priority = priority;return Node; }//根據root的位置插入節點 /* 插入節點前要想明白一個點， 如果該文件或目錄還沒有創建，那么創建的一定是其兒子節點。 如果已經創建完畢了，那么插入的位置一定在該節點的右子樹中查找。如 a/b c/d 1、從根節點插入a后，根節點左子樹為a，a的左子樹為b 2、從根節點插入c時，發現其左子樹已經被占據，那么就遍歷其左子樹的右子樹 也就是根節點左子樹的兄弟節點，直到找到合適的位置。遍歷d時，也是同理。如果沒有被占據，則直接創建兒子節點。 */ Position insert(BinTree root, string s, int priority) {if(root->child == NULL) { //如果沒有兒子，那么直接插入就可以了 root->child = createNode(s, priority); return root->child; //下一次插入從兒子開始 }//定義兒子節點和父親節點。 Position tmpNode = root->child, father = root;//如果有兒子，則循鏈找插入位置//若待插入節點優先級更小或優先級一致但字典序更大，則繼續循鏈//注意：邊界條件為!=NULL，也就是到了鏈末尾while(tmpNode != NULL && ((priority<tmpNode->priority) || (tmpNode->priority == priority && s>tmpNode->str))) {father = tmpNode;tmpNode = tmpNode->sibling;}//退出循環的三種情況：//1、找到了鏈末尾 2、待插文件已存在 3、找到了應該插入的位置//情況1if(tmpNode == NULL) {Position Node = createNode(s, priority);Node->sibling = father->sibling; //保存一下它的兄弟節點 father->sibling = Node; return Node; } //情況2if(tmpNode->priority == priority && s==tmpNode->str)return tmpNode;//情況3else {Position Node = createNode(s, priority);if(father->str == root->str) { //如果該點為根節點下的第一個節點 Node->sibling = father->child;father->child = Node;}else {Node->sibling = father->sibling;father->sibling = Node;}return Node; } } //layer是層數，按層數輸出空格 void PreorderTraversal(BinTree BT, int layer) {int i;int childlayer, siblinglayer;if(BT) {for(i = 0; i < layer; i++) printf(" ");childlayer = layer+1;siblinglayer = layer;cout << BT->str << '\n';PreorderTraversal(BT->child, childlayer);PreorderTraversal(BT->sibling, siblinglayer);} }int main() {int N, i, bgn, end, j;string str;Position pos; //說是指針，其實就是節點BinTree root = createNode("root", 1);scanf("%d\n", &N);for(i = 0; i < N; i++) {getline(cin, str); pos = root; bgn = end = 0; //記錄文件首字符和最后一個字符的位置for(j = 0; j < str.length(); j++) {if(str[j] == '\\') {end = j;pos = insert(pos, str.substr(bgn, end-bgn), 1);bgn = end+1; //每次插入完成后更新起始字符位置 }}//讀完所有目錄后判斷字符串中是否還有文件 如果有，讀入文件 if(str[bgn] != '\0') {insert(pos, str.substr(bgn, str.length()-bgn), 0);} } PreorderTraversal(root, 0); //前序遍歷輸出 return 0; }

---

耗時

---

人生海海，潮起潮落，何須在乎潮落的時分，何須介意人生一時的崎嶇。???????——《人生海?！?/font>

總結

以上是生活随笔為你收集整理的【详细解析】基础实验4-2.6 目录树 (30 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。