九度OJ 1090：路径打印（树、DFS）-白红宇

九度OJ 1090：路径打印（树、DFS）

阅读量：4206 次

发布时间：2019-05-26

本文共 1766 字，大约阅读时间需要 5 分钟。

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：1704

解决：314

题目描述：

给你一串路径，譬如：

a\b\c

a\d\e

b\cst

你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右缩一格，就像这样：

cst

同一级的需要按字母顺序排列，不能乱。

输入：

每个测试案例第一行为一个正整数n（n<=10）表示有n个路径，当n为0时，测试结束，接下来有n行，每行有一个字串表示一个路径，长度小于50。

输出：

输出目录结构，每一个测试样例的输出紧跟一个空行。

样例输入：

4a\b\ca\d\eb\cstd\0

样例输出：

a  b    c  d    eb  cstd

来源：

思路：

根据输入数据建立相应的树，然后DFS输出即可。

代码：

#include 
   
    #include 
    
     #include 
     
           #define N 10#define LEN 50 typedef struct node {    char name[LEN];    int num;    struct node *children[N];} Node;     void create(Node *root, char s[LEN]){       if (s[0] == '\0')        return;    int i, j;    char name[LEN];    i = 0;    while (s[i] != '\\' && s[i] != '\0')    {        name[i] = s[i];        i ++;    }       name[i] = '\0';    if (s[i] == '\\')        i++;    //printf("s=%s, name=%s\n", s, name);    for (j=0; j
      
       num; j++)    {        if (strcmp(root->children[j]->name, name) == 0)            break;    }       if (j < root->num)//find        root = root->children[j];    else    {        Node *n1 = (Node *)malloc(sizeof(Node));        strcpy(n1->name, name);        n1->num = 0;        root->children[root->num++] = n1;        root = n1;    }    create(root, s+i);} int cmp(const void *a, const void *b){    Node **x = (Node **)a;    Node **y = (Node **)b;    return strcmp((*x)->name, (*y)->name);} void DFS(Node *root, int addLen){    int i;    if (addLen >= 0)    {        for (i=0; i
       
        name);    }    qsort(root->children, root->num, sizeof(Node *), cmp);    for (i=0; i
        
         num; i++) { DFS(root->children[i], addLen + strlen(root->name) + 1); }} int main(void){ int n; int i; char s[LEN]; Node root; while (scanf("%d", &n) != EOF && n) { root.name[0] = '\0'; root.num = 0; for (i=0; i