题解 | #路径打印#

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
struct Node{
    int n=0;
    string name;
    vector<Node*> children;
};
Node* appendNode(string name,Node *parent){
    Node* a = new Node();//不能用malloc 否则string和vector会出bug 
    a->n = 0;
    a->name = name;
    parent->n = parent->n+1;
    parent->children.push_back(a);
    return a;
}
Node* getChild(string name,Node parent){
    vector<Node*>::iterator it = parent.children.begin();
    while(it!=parent.children.end()){
        if((*it)->name==name) return *it;
        it++;
    }
    return NULL;
}
bool cmp(Node* a,Node* b){
    return a->name < b->name;
}
void DFS(Node* root,string spacing=""){
    sort(root->children.begin(),root->children.begin()+root->n,cmp);
     
    vector<Node*>::iterator child = root->children.begin();
    while(child!=root->children.end()){
        cout<<spacing<<(*child)->name<<endl;
        DFS(*child,spacing+"  ");
         
        child++;
    }
}
int main(){//习题2.10  上海交大  根据路径打印目录结构
    int n;
    while(cin>>n){
        if(n==0) break;
        Node root;
         
        string path;
        for(int k=0;k<n;k++){
            cin>>path;
            int i=0,j=0;
            int len=path.size();
            Node* current = &root;
             
            while(i<len && j< len){
                while(path[j]!='\\'&&j<len){
                    j++;
                }
                string name = path.substr(i,j-i);
                 
                Node* child = getChild(name,*current);
                if(child!=NULL){
                    current = child;
                } else {
                    current = appendNode(name,current);  
                }
                i=++j;
            }
        }
        //深度优先遍历，以打印目录
        DFS(&root);
        cout<<endl;
    } 
    return 0;
}