关键词：文件系统，静态链式存储，二分查找

看不懂别人的代码，可以来看这个，逻辑相当简单暴力， 只是需要基础扎实， 强烈建议手搓实现以下；

相信大家第一时间能观察到：

1）如果不考虑重复与排序，仅有一条路径，正确打印十分容易，无非就是换行后多两个空格；

2）如果我们已经有一个树，用于表示文件结构，只需先序遍历，在开头额外打印2倍深度h的空格即可，h从0开始；

根据题目，我们需要有意识的练习：

1）在机考竞赛等环境下，树的构建，首选静态数组，而非动态申请空间；

2）所有题目中，一旦给出“单调”的信息，那么必须要利用，或是二分，或是提前退出等；

如果对于树的运用，和for循环一样熟练，那这题的标签确实称得上“简单”，否则还是有难度的；

为了构建这棵树，我们需要回忆：408操作系统中的目录文件；

每个目录文件需要存储：1）自身的名称；2）该目录下所有文件的地址；

因此，逻辑并不复杂，只是实操过程中需要注意一下细节：

1）输入最多10行，每行最多50个字符，至少一半是 '\\' ，因此最多250个文件，即251个索引节点（0号为根节点root）；

2）同时，某个文件夹内，最多包含10个不同名的文件，每个文件最多占满50个字符；

3）我们只用1个数 FILES 记录有效文件个数即可，小于FILES就代表已分配，大于FILES的节点无意义，文件夹内的 files 同理；

4）我们只需要用一个工作目录pwd，顺着所给路径，遍历这棵树，并在遍历的途中，顺手添加节点即可；

5）添加时，我们默认，当前状态下，目录内的文件名已然有序，我们直接插入即可，插入后仍然有序；

其他技巧性问题：

1）考虑状态间的最小变化，找到“递推关系”，是分治、动态规划等更高阶题目的核心，应当培养这种思维方式；

2）二分查找只是逻辑上的优化，对本题而言，10以内的维度，意义不大，但熟练后，也就是顺手的事；

3）用'\0'替换特定字符，是手搓split很好用的方式，熟练后，也是顺手的事；

//简洁的索引文件系统, 可简单复用, 显式的静态链式结构,
//总文件数量<=250(10*25), 单层总文件数<=10, 文件名长度<=50
//空间只递增分配, 用FILES控制视野, 只增不减, 只覆盖
//用pwd指向当前索引节点的地址
#include <stdio.h>
#include <string.h>

typedef struct TreeNode{
    char name[51];
    int files;
    struct TreeNode* idx[10];
}Tn, *Ptn;

void InitNode(char* name, Ptn node){
    node->files=0;
    strcpy(node->name, name);
}

Tn dir[251];
int FILES=1;
Ptn pwd;
char path[51];

void Find(char* name){
    //在pwd下, 尝试找到name, 并更新pwd, 不存在则创建一个name
    //idx列表内, 始终按字典序递增, 因此可以二分查找, 最后调整索引的指向即可
    int l=0, r=pwd->files, m, cmp;
    while(l<r){
        m = (l+r)>>1;
        cmp = strcmp(name, pwd->idx[m]->name);
        if(cmp==0) {//找到则直接返回
            pwd = pwd->idx[m]; return;
        }
        if(cmp<0) r=m;
        else l=m+1;
    }//退出时l=r, l左侧永远更小, 因此l是当前插入位置
    for(int i=pwd->files; i>l; --i) pwd->idx[i] = pwd->idx[i-1];
    //没出现过, 则分配, 并有效文件+1, 随后进入并初始化节点
    pwd->idx[l] = &dir[FILES++];//分配一个索引节点
    pwd->files ++;
    pwd = pwd->idx[l];
    InitNode(name, pwd);
}

void printNode(Ptn node, int h){
    for(int i=0; i<h; ++i) printf("  ");
    printf("%s\n", node->name);
    for(int i=0; i<node->files; ++i)
        printNode(node->idx[i], h+1);
}

int main() {
    int n, i;
    while (scanf("%d\n", &n) != EOF && n) {
        //初始化根节点
        InitNode("root", &dir[0]); FILES = 1;

        int l, r;
        for(i=0; i<n; ++i){
            //每次都从根节点出发, 边遍历边构建树
            pwd = &dir[0];
            scanf("%s\n", path);
            for(r=0, l=0; path[r]; ++r){
                if(path[r]=='\\'){
                    path[r] = '\0';
                    Find(path+l);
                    l = r+1;
                }
            }
            //空名不添加
            if(strlen(path+l)>0) Find(path+l);
        }

        //打印
        for(int i=0; i<dir[0].files; ++i)
            printNode(dir[0].idx[i], 0);
        printf("\n");
    }
    return 0;
}