数据结构与算法题目集7-30——目录树
我维护的数据结构与算法题库代码仓位于GitHub上的https://github.com/617076674/Data-structure-and-algorithm-topic-set
原题链接：https://pintia.cn/problem-sets/15/problems/857
题目描述：
知识点：深度优先遍历
思路：先建树，再深度优先遍历
以结构体形式定义一个名为file的数据类型用于表示树中的节点。该数据类型包含成员变量name为字符数组类型且长度固定为261字节用于存储文件名；标志位isDirectory用于区分该节点是否为目录或普通文件；标志位visited标记该文件节点在深度优先搜索过程中是否已被访问过；子向量subFiles用于存储该文件所属的子目录。
题目给出的所有字符串都表示从root节点的第一个子节点开始的不同路径方向。为此目的我们需要创建一个vector
void add(file &f, int index)函数的实现如下：
注意，这个过程中我们会改变f文件的subFile值，所以需要传递引用。
当index等于files.size时
（2）依次检查f下的每一个子目錄，在其中查找与当前索引对应的名称一致且类型相同的文件。若发现存在这样的文件，则确认当前索引位置已被包含在内；进而转向下一个待处理的位置，并将问题递归地传递给下一个层级处理。
（3）如果步骤（2）未能在文件f的子目录中找到对应的files[index]项，则将files[index]添加到文件f的子目录结构中，并进一步递归调用该函数add，并传递参数为f.subFiles[f.subFiles.size()-1]以及index+1。
以root节点为起点进行深度优先遍历该文件系统结构，并同时使用int型level变量来统计空格数量
void dfs(file &nowVisit, int level)函数的实现如下：
注意，这个过程中，我们会对f文件的subFile进行排序，所以需要传递引用。
如果当前文件尚未被访问过，则将其标记为已访问，并按照特定顺序对其中的subFile进行排列。
（2）输出当前空格数和文件名。
（3）对其subFile里的文件，递归调用dfs函数，注意level需加2。
时间复杂度和空间复杂度均与题给的数据有关，很难计算。
C++代码：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
struct file {
char name[261];
bool isDirectory, visited;
vector<file> subFiles;
};
int N;
file root;
vector<file> files;
void add(file &f, int index);
bool cmp(file f1, file f2);
void dfs(file &nowVisit, int level);
int main() {
scanf("%d", &N);
strcpy(root.name, "root");
root.isDirectory = true;
root.visited = false;
for(int i = 0; i < N; i++) {
char line[270];
scanf("%s", line);
int j = 0;
files.clear();
while(j < strlen(line)) {
char str[270];
int point = 0;
while(j < strlen(line) && line[j] != '\ ') {
str[point++] = line[j++];
}
str[point] = '\0';
file f;
if(j < strlen(line)) {
f.isDirectory = true;
} else {
f.isDirectory = false;
}
f.visited = false;
strcpy(f.name, str);
files.push_back(f);
j++;
}
add(root, 0);
}
dfs(root, 0);
return 0;
}
void add(file &f, int index) {
if(index == files.size()) {
return;
}
for(int i = 0; i < f.subFiles.size(); i++){
if(strcmp(f.subFiles[i].name, files[index].name) == 0 && f.subFiles[i].isDirectory == files[index].isDirectory) {
add(f.subFiles[i], index + 1);
return;
}
}
f.subFiles.push_back(files[index]);
add(f.subFiles[f.subFiles.size() - 1], index + 1);
}
bool cmp(file f1, file f2) {
if(f1.isDirectory && !f2.isDirectory) {
return true;
} else if(!f1.isDirectory && f2.isDirectory) {
return false;
} else {
return strcmp(f1.name, f2.name) < 0;
}
}
void dfs(file &nowVisit, int level) {
if(!nowVisit.visited) {
nowVisit.visited = true;
sort(nowVisit.subFiles.begin(), nowVisit.subFiles.end(), cmp);
}
printf("%*s%s\n", level, "", nowVisit.name);
for(vector<file>::iterator it = nowVisit.subFiles.begin(); it != nowVisit.subFiles.end(); it++) {
dfs(*it, level + 2);
}
}C++解题报告：
