题目：1635 Directory Listing（列出目录）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=635
看描述好像是chenyue姐姐出的题目。这道题的大意是，给出一个UNIX文件系统的树，以及树节点的自身size，按要求列出它们，保持适当的缩进，并统计每个节点的总的size。输入的第一行代表根结点，每一个节点由name size或者*name size的形式组成（如果包含*表示这是一个文件夹，它包含的子节点将在下一行中列出，并用圆括号包含，size是一个表示节点自身属性的正整数）。在输出节点时，需要输出该节点自身size和所有子节点size的和。
深度为d的节点前面应该有8d的前导（由空格或竖线组成）；
示范输入：
*/usr 1(*mark 1 *alex 1)(hw.c 3 *course 1) (hw.c 5)(aa.txt 12)
示范输出：
|_*/usr[24] |_*mark[17] | |_hw.c[3] | |_*course[13] | |_aa.txt[12] |_*alex[6] |_hw.c[5]
--------------------------------------------------------------------------------------- 题目属于按固定格式输出的题目，但本质上是属于对“树”这种数据结构的考察。不难看出，在读取输入时，输入方式实际上是一种类似树的“按层次遍历”，即按照节点深度从小到大的顺序给出每一层次的节点，第k行即代表了该深度（depth=k）的所有节点。同时，如果节点不包含*，表示是叶子节点，如果包含*，则属于“文件夹”，因此一定会有下一行。如果某一行不包含任何*，则一棵树输入完毕。
而对于输出，容易看出，输出实际上是对树的前序遍历。
在我的此前的一篇博客中，已经详细讲解过如何通过栈来前序遍历树，以及如何通过队列来层次遍历树，因此这里不再详细介绍了。输出的时候完全是前序遍历，无须多做解释。唯一有点特别的是读取输入的过程就是组装这颗树的过程，组装过程中我们先把根结点（一定包含*）入列，然后依次读取下一行，下一行中假设包含n组子节点（即含有n组圆括号），则针对每一组子节点，从队列中出列一个节点作为这些子节点的父节点即可。直到队列为空，一棵树的读取和组装完毕。
这里我们还要注意的第一个细节问题是，在组装过程中，我们还要把该节点的最终size统计出来。因此我们给每个树节点增加了一个父节点指针，这样每挂接一个子节点，从该节点向根结点追溯，对所有父辈节点累加该size。此外我们还需要一个属性记录该节点的所在深度，这个属性在后面的输出时被利用。因此，我们把节点定义如下：
typedef struct tnode{ char text[11];/*节点名称*/ int depth; /*该节点所在层次*/ int size; /*该节点的当前值，最终值=自身值+所有子节点值*/ struct tnode *child[10]; /*根结点*/ struct tnode *parent; /*父节点，用于向根结点累加size*/} TNODE;
下面我们即可给出读取并组装树的代码。值得注意的是，我们每次读取一行，而该行中包含的子节点组的个数n是未知的，因此我们需要对读取进来的这一行通过ParseLine函数进行解析，即根据'('和')'字符，把圆括号内部的文本提取出来，再传递给AddChildNodes函数进行处理。
Code_InputTreeTNODE *queue[100];/*队列，用于输入*/TNODE *stack[100];/*栈，用于输出*/int head, tail; /*队列的全局指针*/int top; /*栈的全局指针*/TNODE* InputTree();void ParseLine(char*, int);void AddChildNodes(char*, int);void OutputTree(TNODE *head);/*读入并组装为一棵树，返回根结点指针*/TNODE* InputTree(){ int size, depth=0;/*队列的指针*/ char buf[11], line[1024]; TNODE *node=NULL, *root=NULL; /*是否读到了文件尾部，如果读到空字符串也返回null*/ if(scanf("%s %d", buf, &size)==EOF || size<0) return NULL; head=tail=0; /*申请首个节点空间，赋值，入列*/ root=(TNODE*)malloc(sizeof(TNODE)); memset(root, 0, sizeof(TNODE)); root->size=size; strcpy(root->text, buf); queue[tail++]=root; /*首个节点入队列*/ /*循环读入后续的每一行*/ while(head!=tail) { gets(line); ParseLine(line, depth++); /*解析这一行！实际就是装配树的过程！*/ /*如果这一行中没有星号，说明树已经输入完毕！*/ } return root; }/*解析当前输入的一行，depth为节点所在深度*/void ParseLine(char *line, int depth){ char *begin, *s; int flag=0; begin=s=line; while(*s) { switch(*s) { case '(': begin=s+1; break; case ')': *s='/0'; AddChildNodes(begin, depth); break; } s++; } }/*添加子节点, depth为节点所在深度*/void AddChildNodes(char *str, int depth){ TNODE *parent, *node, *temp; char *token; int i=0;/*子节点索引*/ token=strtok(str, " "); /*出列一个节点！*/ parent=queue[head++]; while(token!=NULL) { node=(TNODE*)malloc(sizeof(TNODE)); memset(node, 0 ,sizeof(TNODE)); node->depth=depth; strcpy(node->text, token); /*看该节点是否应该入列，如果是文件夹，则入列！*/ if(token[0]=='*') queue[tail++]=node; /*读入size*/ token=strtok(NULL, " "); node->size=atoi(token); /*添加该子节点！*/ parent->child[i++]=node; node->parent=parent; /*累加父节点的size！*/ temp=parent; while(temp!=NULL) { temp->size+=node->size; temp=temp->parent; } token=strtok(NULL, " "); }}
注意在上面的代码中，我们在AddChildNodes函数的最后面对节点的size进行向根结点方向的追踪累加，这样树组装完毕后，每个节点的size就是最终要输出的值。
当树读取进来并且组装以后，我们只需要对这个树进行前序遍历，依次打印节点即可，这部分的内容比较简单。但显然在输出中存在很关键的打印技巧，即如何准确打印出树的形状，每一个节点前面的前导字符串是关键！每一行由下面的格式组成：
[前缀字符串] |_ [节点名称] [size]
这里唯一有难度和技巧性的是前缀字符串的确定，每一深度的缩进由8个空格组成，但有时第一个空格实际上是竖线。那么竖线是否出现的规律是什么呢？仔细观察我们可以发现，当该节点的父节点是祖父节点的最后一个子节点（即老幺）时，父节点下方将不包含竖线。否则这8个空格中的第一个被替换为'|'。这样我们就不难写出下面的代码，提供一个缓冲区，然后我们把它设置为正确的前缀字符串：
Code_设置前缀字符串/*很关键的一个函数，设置某个节点的前导部分*/void SetPrefix(TNODE *node, char *buffer){ int i, depth=node->depth; TNODE *temp, *parent=NULL; if(node->depth>0) memset(buffer, ' ', node->depth * 8); buffer[node->depth * 8]='/0'; /*结尾*/ /*从下向上去判断！注意depth=0时无需要判断，因为根结点是“独子”，注定是“老幺”*/ temp=node->parent; while(temp!=NULL && (temp->depth > 0)) { parent=temp->parent; /*从父节点的子节点集合中最后向前找，如果不是最后一个节点，则把空格改为竖线*/ for(i=9;i>=0;i--) { /*如果temp不是父节点的最后一个子节点（老幺）*/ if(parent->child[i]!=NULL && parent->child[i]!=temp) { buffer[temp->depth*8]='|'; break; } if(parent->child[i]==temp) /*是最后一个节点*/ break; } temp=parent; }}
最后我们就可以用常规的栈前序遍历输出结果：
Code_用栈辅助来前序遍历输出/*借助栈的辅助，前序输出，并输出后释放相应节点！*/void OutputTree(TNODE *head){ TNODE *node; char prefix[80];/*该节点的前导字符串*/ int i; if(head==NULL) return; top=0; /*栈顶指针*/ /*根结点入栈*/ stack[top++]=head; /*当栈不为空时*/ while(top>0) { node=stack[--top]; /*pop a node*/ /*在这里我们设置节点的前导！非常关键的一个地方！！！*/ SetPrefix(node, prefix); /*打印该节点*/ printf("%s|_%s[%d]/n", prefix, node->text, node->size); /*node的子节点从右到左入栈！*/ for(i=9;i>=0;i--) { if(node->child[i]!=NULL) stack[top++]=node->child[i]; } }}
同时我们在输出完一棵树以后，在读取下一颗树之前，应当把当前的树说申请的内存还给系统。由于刚刚使用栈输出过这棵树，因此这棵树的所有节点实际上都位于辅助栈内。因此我们只需要把栈里所有节点释放即可：
Code_释放树占用的内存/*此时应该是刚刚输出完毕树，只要清空堆栈里的所有节点即可*/void DeleteTree(){ int i=0; for(i=0;i<100;i++) { if(stack[i]==NULL) break; free(stack[i]); stack[i]=NULL; } }/*入口点*/int main(){ TNODE *tree; while((tree=InputTree())!=NULL) { OutputTree(tree); DeleteTree();/*释放栈中的所有节点！*/ } return 0;}
最后，我们再关注一下需要注意的事项：
（1）我们在输出所有节点以后，才统一的一次性释放所有节点。而不是每输出一个节点就当即释放一个节点。这样做的原因是我们需要用节点关系去推导前缀字符串，因此我们没有立即就释放已经遍历过的节点。
（2）我们使用malloc申请了一个节点以后，请注意这样的内存是“原始”的，也就是未经过任何初始化的，因此如果里面包含指针（例如节点的父节点指针，所有子节点指针），则这些指针全部属于“野指针”状态。如果不对这些指针进行初始化，将会导致灾难性后果。所以每次申请到一个节点后我们必须要做的第一步是初始化它：即memset( node, 0, sizeof(TNODE)); 这一条语句将保证节点中所有指针被设置为NULL，切不可忘记！！！
（3）实际上由于输入和输出是完全顺序的操作，因此这里的辅助栈和辅助队列可以合并为一个，它是queue还是stack完全取决于我们如何使用它。但为了清晰起见，我们的代码还是保留为独立的queue和stack空间。
（4）此题看似容易，但实际上包含了相当的技巧性，并不是很容易在短时间内写好，从它较低的AC率（24%）来看说明它也不是一道简单的送分题。我仔细调试和检查了代码，直到全部正确才提交，然后一次性AC了，运行时间和内存占用都和解排行榜上的数据一致。
