题解 | #路径打印#

#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;
}