程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1556 - Disk Tree(字典樹)

uva 1556 - Disk Tree(字典樹)

編輯：C++入門知識

uva 1556 - Disk Tree(字典樹)

題目連接：uva 1556 - Disk Tree

題目大意：給出N個目錄關系，然後按照字典序輸出整個文件目錄。

解題思路：以每個目錄名作為字符建立一個字典樹即可，每個節點的關系可以用map優化。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 50005;
typedef map::iterator iter;

struct Tire {
    int sz;
    map g[maxn];

    void init();
    void insert(string s);
    void put(int u, int d);
}tree;

int main () {
    int n;
    string s;
    while (cin >> n && n) {
        tree.init();
        for (int i = 0; i < n; i++) {
            cin >> s;
            s += '\\';
            tree.insert(s);
        }
        tree.put(0, 0);
        cout << endl;
    }
    return 0;
}

void Tire::init() {
    sz = 1;
    g[0].clear();
}

void Tire::insert(string s) {

    int u = 0;
    string word = "";

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '\\') {

            if (!g[u].count(word)) {
                g[sz].clear();
                g[u][word] = sz++;
            }

            u = g[u][word];
            word = "";
        } else
            word += s[i];
    }
}

void Tire::put (int u, int d) {

    for (iter i = g[u].begin(); i != g[u].end(); i++) {
        for (int j = 0; j < d; j++)
            cout << " ";
        cout << i->first << endl;
        put(i->second, d + 1);
    }
}