关于算法-数据结构:PAT甲级2020年冬季考试-73-File-Path

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:

14
0000
 1234
  2234
   3234
    4234
    4235
    2333
   5234
   6234
    7234
     9999
  0001
   8234
 0002
4 9999 8234 0002 6666

Sample Output:

0000->1234->2234->6234->7234->9999
0000->1234->0001->8234
0000->0002
Error: 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;
}