这题是模拟一个目录，我用到字典树来做这题。
这题我是用大量stl来减少代码量，不过我对stl的功能并不是完全的熟悉，所以用起来有点别扭，代码时间也大约用了半个多小时，不过最后稳稳的1y了！～
参考代码：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 struct Node; 10 struct Cata; 11 typedef vector vc; 12 13 struct Cata { 14 char name[10]; 15 Node *next; 16 17 bool operator < (const Cata &x) const { 18 return strcmp(name, x.name) < 0; 19 } 20 } ; 21 struct Node { 22 vc child; 23 24 Node() { 25 child.clear(); 26 } 27 } *Root; 28 29 void insert(char *p) { 30 char tmp[10]; 31 char *q = tmp; 32 Node *cur = Root; 33 Cata buf; 34 vc::iterator ii; 35 36 while (true) { 37 while (*p && *p != '\\') { 38 *q = *p; 39 q++, p++; 40 } 41 *q = 0; 42 // puts(tmp); 43 44 for (ii = cur->child.begin(); ii != cur->child.end(); ii++) { 45 if (!strcmp((*ii).name, tmp)) { 46 if (!(*ii).next) { 47 (*ii).next = new Node(); 48 } 49 cur = (*ii).next; 50 break; 51 } 52 } 53 // puts("???"); 54 if (ii == cur->child.end()) { 55 buf.next = new Node(); 56 strcpy(buf.name, tmp); 57 cur->child.push_back(buf); 58 cur = buf.next; 59 // puts("yeah~"); 60 } 61 62 if (*p) { 63 q = tmp; 64 p++; 65 } else { 66 break; 67 } 68 } 69 } 70 71 void print(int depth, Node *rt) { 72 if (!rt) return ; 73 74 vc::iterator ii; 75 76 sort(rt->child.begin(), rt->child.end()); 77 for (ii = rt->child.begin(); ii != rt->child.end(); ii++) { 78 for (int i = 0; i < depth; i++) { 79 putchar(' '); 80 } 81 puts((*ii).name); 82 print(depth + 1, (*ii).next); 83 } 84 } 85 86 int main() { 87 char buf[100]; 88 int n; 89 90 // freopen("in", "r", stdin); 91 while (~scanf("%d", &n)) { 92 Root = new Node(); 93 while (n--) { 94 scanf("%s", buf); 95 insert(buf); 96 } 97 print(0, Root); 98 } 99 return 0;100 }
——written by Lyon