在ZIP歸檔文件中，保留著所有壓縮文件和目錄的相對路徑和名稱。當使用WinZIP等GUI軟件打開ZIP歸檔文件時，可以從這些信息中重建目錄的樹狀結構。請編寫程序實現目錄的樹狀結構的重建工作。
輸入格式:
輸入首先給出正整數N（≤104），表示ZIP歸檔文件中的文件和目錄的數量。隨后N行，每行有如下格式的文件或目錄的相對路徑和名稱（每行不超過260個字符）：
- 路徑和名稱中的字符僅包括英文字母（區分大小寫）；
- 符號“\”僅作為路徑分隔符出現；
- 目錄以符號“\”結束；
- 不存在重復的輸入項目；
- 整個輸入大小不超過2MB。
輸出格式:
假設所有的路徑都相對于root目錄。從root目錄開始，在輸出時每個目錄首先輸出自己的名字，然后以字典序輸出所有子目錄，然后以字典序輸出所有文件。注意，在輸出時，應根據目錄的相對關系使用空格進行縮進，每級目錄或文件比上一級多縮進2個空格。
輸入樣例:
7
b
c\
ab\cd
a\bc
ab\d
a\d\a
a\d\z\輸出樣例:
rootadzabcabcddcb一、問題核心與難點
本任務要求根據給定的文件路徑列表，構建完整的目錄樹結構，并按照特定格式輸出。主要挑戰在于：
- ??路徑層級解析??：需要正確處理路徑分隔符""，識別目錄與文件
- ??樹形結構構建??：動態創建多級目錄節點
- ??字典序輸出??：保證同級目錄和文件的順序正確
二、數據結構設計
采用樹形結構進行存儲，每個節點包含：
struct Node {string name;map<string, Node*> dirs; // 有序存儲子目錄map<string, Node*> files; // 有序存儲文件
};使用map容器實現自動字典序排序，其中：
dirs存儲下級目錄節點files存儲當前目錄下的文件
三、實現流程詳解
1. 路徑分割處理
通過split函數解析路徑字符串：
vector<string> split(const string &s) {vector<string> tokens;// 處理邏輯：遇到"\"分割路徑組件// 保留空組件用于目錄判斷
}該函數將類似"a\d\z"的路徑轉換為["a", "d", "z"]，同時通過原字符串末尾的""判斷是否為目錄。
2. 樹形結構構建
Node* current = root;
for (auto &comp : tokens) {if (需要創建目錄) {current->dirs[comp] = new Node(comp);}current = 下一級節點;
}逐級創建目錄節點，文件存儲在終末節點的files集合中。
3. 遞歸輸出邏輯
void printTree(Node* node, int indent) {// 輸出當前節點// 遞歸輸出子目錄// 輸出文件
}采用深度優先遍歷，通過縮進參數控制格式，實現：
- 目錄優先于文件輸出
- 同級元素按字母序排列
四、關鍵實現技巧
- ??目錄/文件區分??：通過原始路徑的結尾字符判斷類型
- ??自動排序機制??：利用map的有序特性簡化排序邏輯
- ??內存管理??：使用裸指針需注意內存釋放（實際應用中建議使用智能指針）
五、示例分析
輸入樣例：
a\d\z\處理流程：
- 識別為目錄
- 分割為["a", "d", "z"]
- 在root下創建a節點
- 在a節點下創建d節點
- 在d節點下創建z目錄節點
完整代碼：
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>using namespace std;struct Node {string name;map<string, Node*> dirs;map<string, Node*> files;Node(string n) : name(n) {}
};vector<string> split(const string &s) {vector<string> tokens;string token;for (char c : s) {if (c == '\\') {if (!token.empty()) {tokens.push_back(token);token.clear();}} else {token += c;}}if (!token.empty()) {tokens.push_back(token);}return tokens;
}void printTree(Node* node, int indent) {if (indent == 0) {cout << node->name << endl;} else {cout << string(indent * 2, ' ') << node->name << endl;}for (auto &dir : node->dirs) {printTree(dir.second, indent + 1);}// 輸出子文件for (auto &file : node->files) {cout << string((indent + 1) * 2, ' ') << file.second->name << endl;}
}int main() {int n;cin >> n;cin.ignore(); // 忽略換行符Node* root = new Node("root");for (int i = 0; i < n; ++i) {string s;getline(cin, s);bool isDir = !s.empty() && s.back() == '\\';vector<string> tokens = split(s);Node* current = root;for (size_t j = 0; j < tokens.size(); ++j) {string comp = tokens[j];bool isLast = (j == tokens.size() - 1);if (isLast) {if (isDir) {if (current->dirs.find(comp) == current->dirs.end()) {current->dirs[comp] = new Node(comp);}current = current->dirs[comp];} else {current->files[comp] = new Node(comp);}} else {if (current->dirs.find(comp) == current->dirs.end()) {current->dirs[comp] = new Node(comp);}current = current->dirs[comp];}}}printTree(root, 0);return 0;
}
