7-3 File Path (25 分)


The figure shows the tree view of directories in Windows File Explorer. When a file is selected, there is a file path shown in the above navigation bar. Now given a tree view of directories, your job is to print the file path for any selected file.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10^3), which is the total number of directories and files. Then N lines follow, each gives the unique 4-digit ID of a file or a directory, starting from the unique root ID 0000. The format is that the files of depth d will have their IDs indented by d spaces. It is guaranteed that there is no conflict in this tree structure.

Then a positive integer K (≤100) is given, followed by K queries of IDs.

Output Specification:

For each queried ID, print in a line the corresponding path from the root to the file in the format: 0000->ID1->ID2->...->ID. If the ID is not in the tree, print Error: ID is not found. instead.

Sample Input:

140000 1234  2234   3234    4234    4235    2333   5234   6234    7234     9999  0001   8234 00024 9999 8234 0002 6666

Sample Output:

0000->1234->2234->6234->7234->99990000->1234->0001->82340000->0002Error: 6666 is not found.

题目限度

题目粗心

给定N个数字,每一个数字代表了文件或者文件夹,并且采纳缩进的形式示意每一个文件或者文件夹之间的绝对深度,缩进d格代表在d层。而后给定K个查问，要求输入从根节点到查问节点的门路，如果查问节点不存在输入Error: ID is not found.

算法思路

此题能够分为两步来进行，第一步建树，第二步深度优先搜寻。难点就是建树，因为咱们须要输入从根节点到查问节点的门路，并且字符串的长度就代表了节点的深度，那么咱们间接应用一个二维数组，第一维代表了层数，第二维代表了在以后层数的所有节点，同时应用pre数组记录每一个节点的前驱节点。

  • 建树过程：咱们应用字符串的长度size来代表节点的层数，那么每一次增加一个节点d，就记录以后节点的前驱节点，如果是第一个节点阐明是根节点root，前驱为-1，否则前驱就是上一层中的最初一个节点levelsize - 1.size() - 1];

建树结束后，对于每一个非法查问间接调用DFS进行深度搜寻，从指定节点向前搜寻，来到root后开始输入即可。

提交后果

AC代码

#include<cstdio>#include<iostream>#include<string>#include<unordered_map>#include<algorithm>#include<vector>using namespace std;int pre[10004];// 记录每一个节点的前驱节点unordered_map<int, bool> isExist;// 标记节点是否存在vector<int> level[1005];// 每一档次的结点，依照程序int root;// 根节点void DFS(int end) {    if (root == end) {        printf("%04d", end);        return;    }    DFS(pre[end]);    printf("->%04d", end);}int main() {    int N;    scanf("%d", &N);    string current;    // 排汇回车    getchar();    for (int i = 0; i < N; ++i) {        getline(cin, current);        int d = stoi(current);        // 标记以后节点非法        isExist[d] = true;        // 应用字符串的长度代表层数，越小的层数越低        int size = current.size();        // 为以后层节点增加d        level[size].push_back(d);        // 记录每一个节点的前缀和根节点root        if (i == 0) {            pre[d] = -1;            root = d;        } else {            // 每一个节点的前缀就是上一层节点的最初一个节点            pre[d] = level[size - 1][level[size - 1].size() - 1];        }    }    int K;    scanf("%d", &K);    for (int i = 0; i < K; ++i) {        int a;        scanf("%d", &a);        if (!isExist[a]) {            printf("Error: %04d is not found.\n", a);        } else {            DFS(a);            printf("\n");        }    }    return 0;}