本文主要是介绍路径打印(建树,DFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给你一串路径,譬如: a\b\c a\d\e b\cst d\ 你把这些路径中蕴含的目录结构给画出来,子目录直接列在父目录下面,并比父目录向右缩一格,就像这样: a b c d e b cst d 同一级的需要按字母顺序排列,不能乱。
输入描述:
每个测试案例第一行为一个正整数n(n<=10)表示有n个路径,当n为0时,测试结束,接下来有n行,每行有一个字串表示一个路径,长度小于50。
输出描述:
输出目录结构,每一个测试样例的输出紧跟一个空行。
示例1
输入
4 a\b\c a\d\e b\cst d\ 0
输出
abcde bcst d
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define N 10
#define LEN 50typedef 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++; for (j=0; j<root->num; j++){if (strcmp(root->children[j]->name, name) == 0)//找到匹配的根节点break;} if (j < root->num)//此节点已经存在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<addLen; i++)printf(" ");printf("%s\n", root->name);}qsort(root->children, root->num, sizeof(Node *), cmp);for (i=0; i<root->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<n; i++){scanf("%s", s);create(&root, s);} DFS(&root, -1);printf("\n");}
}
这篇关于路径打印(建树,DFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!