题目：输入N个文件/文件夹位置关系，输出层级关系。看题目例子就可以看懂。
解析：利用树状结构
代码缺点：该代码内存占用太多。在insert函数中，可以选择更高效的查找及插入算法，但这道题对运行时间要求没那没高，可以写的相对简单一点。Tree* child[70]这个数字70根据题目可以调整，只是越大消耗内存越大，可以存放的子节点越多，Timus这道题写70就够了。
代码优化建议：
1. 把Tree中改成vector<pair<string, Tree>> child;这样可以大大减少内存以及提供更高效的对string排序操作。
2. 把Tree中改成set<Tree> child;并对<运算符(根据string name;)进行重载。set提供了高效的insert和find函数，这种方法更高效。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<algorithm> #include<vector> using namespace std; class Tree { public: Tree() { level = 0; } Tree(const Tree& tree) { this->level = tree.level + 1; } int level; vector<pair<string, int>> name; Tree* child[70]; }; Tree * insert(Tree* tree, string word) { for (int i = 0; i < tree->name.size(); i++) if (tree->name[i].first == word) return tree->child[i]; tree->name.push_back(make_pair(word, tree->name.size())); tree->child[tree->name.size() - 1] = new Tree(*tree); return tree->child[tree->name.size() - 1]; } int f(pair<string, int>& a, pair<string, int>& b) { return a.first < b.first; } void show(Tree* tree) { for (int i = 0; i < tree->name.size(); i++) { sort(tree->name.begin(), tree->name.end(), f); for (int j = 0; j < tree->level; j++)cout << " "; cout << (tree->name[i].first) << endl; show(tree->child[tree->name[i].second]); } } int main() { int n, count = 0; cin >> n; string temp; Tree tree; Tree* tempTree; for (int i = 0; i < n; i++) { cin >> temp; string single = ""; tempTree = &tree; for (int j = 0; j < temp.size(); j++) { if (temp[j] == '\\') { tempTree = insert(tempTree, single); single = ""; } else single += temp[j]; } tempTree = insert(tempTree, single); } show(&tree); } |
浙公网安备 33010902002953号