4月 25, 2008

【解題】樹狀結構展示 - Tree

@
台北市96學年度高中資訊學科能力競賽 - 樹狀結構展示 (Tree)


問題描述

  樹狀結構為一種程式設計者常用的資料結構,但較不容易在畫面上展示。常見的樹狀結構展示方式為「樹根在左、樹枝朝右」的橫向目錄型式,但其實若能以「樹根在上、樹枝朝下」的直向表示法,更能展現樹狀結構的精神。而要在電腦的二維螢幕上畫出美觀的樹狀結構,必須計算其中各個節點的座標位置。以下圖的樹狀結構為例,在一般文字模式的螢幕上(一個位置一個字元),其畫出來的樣子如下所示。其中名稱為N-1的節點,其起始座標為(5, 3),名稱為N-2的節點,其起始座標為(22, 3),名稱為N-1-1的節點,其起始座標為(1, 6),其餘依此類推。



  根據上例的表示方法,請寫一程式讀入如下格式的樹狀結構後,轉換為直向的樹狀結構,輸出每個節點的二維座標位置。

  在將輸入轉換成直向的樹狀圖時,為求美觀,轉換時必須符合下列規則:
   1. 節點以其名稱輸出。所有的距離、位置、寬度,都以「字元數」計算。
   2. 同一階層的節點有相同垂直位置。
   3. 同一階層的節點間必須求出最小間隔,但至少距離一個空白字元。
   4. 若某一節點有多個子節點,則其水平位置必需在所有子節點的總寬度的正中央。其計算公式為:(LS + LE + L) / 2。

  其中:
   S:本身節點的起始水平位置;當S 無法整除時,取其四捨五入值。
   LS:第一個子節點的起始水平位置。
   LE:最後一個子節點的最後水平位置。
   L:本身子節點的長度。


輸入檔格式(C:\tree\input.txt)

  1. 輸入為多行字串,每一行代表一個由根節點到本身節點的路徑,節點名稱由英文、數字與可列印符號表示,而上、下節點之間以冒號隔開。

  2. 所有的輸入依照深度優先演算法(Depth-First)列出,不會有如下情形:
   N-1
   N-1:N-1-1
   N-2
   N-1:N-1-2


  3. 輸入格式一定正確,不需考慮輸入格式錯誤情形。


輸出檔格式 (C:\tree\output.txt)

  1. 輸出時,先輸出每個節點的路徑,其順序輸入相同。

  2. 每個路徑後面,空一格後加上括號,括號內第一個值為該節點的起始水平座標位置,第二個值為其垂直座標位置。

  3. 水平與垂直座標位置均以字元數計算,由1 開始。如上例中的節點N-1,其起始水平座標位置為5,則輸出5,垂直座標為3,則輸出3。


輸入檔範例1

N-1
N-1:N-1-1
N-1:N-1-2
N-1:N-1-2:N-1-2-1
N-2
N-2:N-2-1
N-2:N-2-1:N-2-1-1
N-2:N-2-2
N-2:N-2-3


輸出檔範例1

N-1 (5,3)
N-1:N-1-1 (1,6)
N-1:N-1-2 (7,6)
N-1:N-1-2:N-1-2-1 (6,9)
N-2 (22,3)
N-2:N-2-1 (15,6)
N-2:N-2-1:N-2-1-1 (14,9)
N-2:N-2-2 (21,6)
N-2:N-2-3 (27,6)


輸入檔範例2

A
A:AB
A:AC
a
a:ab
a:ac


輸出檔範例2

A (3,3)
A:AB (1,6)
A:AC (4,6)
a (9,3)
a:ab (7,6)
a:ac (10,6)


解題思考

  這題老實說比較麻煩,我的作法是把問題分成兩個部份:儲存輸入資料,以及處理解析後的資料(也就是得出題目要求的節點座標)。

  要如何根據輸入,將必要的資料儲存在變數呢?在一次讀取檔案的一整行之後,根據題意,我們把這筆資料根據":"作字串切割。這些切割出來的內容,就是一個節點的名稱以及它的節點路徑。

  假若這一行的字串共切割成n個部份,則第1個到第n-1個部份即為節點路徑,而最後一個部份就是節點名稱了。至於資料的儲存,就只要根據切割出來的節點路徑,找到其父節點並新增節點資料就可以了。

  現在,我們已經能將資料正確的存入結構中了。接著要怎麼得知節點座標呢?

  首先,因為每一階層的節點都需要有最小間隔,且至少要距離一個空白,所以我們需要一些變數來存取每個階層的"邊界"。接著,我們就照著深度優先、遞迴的方式,來放置每個節點。

  我們舉題目的範例1來看,請看下圖:



  第一層目前的邊界為0,因此節點"N-1"暫時放置在第一格的位置,並將邊界加上L+1(節點長度+間隔的空格)。



  第二層目前的邊界為0,因此節點"N-1-1"暫時放置在第一格的位置,並將邊界加上L+1。所以"N-1-2"放置於第七格,並同樣再將邊界加上L+1。



  第三層目前的邊界為0,因此節點"N-1-2-1"暫時放置在第一格的位置,並將邊界加上L+1。



  由"N-1-2-1"節點的位置回推"N-1-2"的節點位置(利用題目給予的公式):結果小於最小間隔,故將"N-1-2-1"節點調整到配合"N-1-2"節點的位置。



  由"N-1-1"與"N-1-2"節點的位置回推"N-1"的節點位置:結果大於其目前的位置,故將"N-1"節點調整到配合"N-1-1"與"N-1-2"節點的位置。

  只要能讓程式重複以上步驟,就能夠達成題目的要求了。最後再利用深度優先的方式輸出結果,這題就完成了!


參考解答(C++)

#include <iostream>
#include <fstream>

#include <string>
#include <vector>

#define _GET_MAX_ 256

using namespace std;

struct node
{
    int s; // 座標起始點
    string name; // 節點名稱
    vector<node> childen; // 子節點
};

int move(node &, int);
void show(node &, int, string, ofstream &);

vector<int> border;

int main(void)
{
    ifstream in("C:/tree/input.txt");
    ofstream out("C:/tree/output.txt", ios_base::trunc);

    // 建立一個"虛擬根"作存取起始點
    node root;
    root.s = 0;

    cout << "讀入資料 . . ." << endl;
    char get[_GET_MAX_];
    while (in.getline(get, _GET_MAX_))
    {
        // 建立一個節點指標, 指向根節點
        node *tree = &root;

        string str = get;

        string sub;
        int start = 0, end;
        while (1)
        {
            // 根據冒號擷取資料
            end = str.find(":", start);
            sub = str.substr(start, end - start);

            // 路徑結束, 跳出
            if (end == string::npos) { break; }

            // 尋找節點路徑
            for (vector<node>::iterator it = (*tree).childen.begin();
                it < (*tree).childen.end(); it++)
            {
                if ((*it).name == sub)
                {
                    // 更新節點指標為此節點
                    tree = &(*it);
                    break;
                }
            }

            start = end + 1;
        }

        // 新增一個節點, 使之為當前節點的子節點
        node newnode;
        newnode.name = sub;
        newnode.s = 1;

        (*tree).childen.push_back(newnode);
    }

    in.close();

    // 呼叫遞迴函式處理資料並印出結果
    move(root, 0);
    show(root, 0, "", out);
    out.close();

    cout << "輸出資料在 ouput.txt" << endl;

    system("pause");
}

int move(node &tree, int level)
{
    for (vector<node>::iterator it = tree.childen.begin();
        it < tree.childen.end(); it++)
    {
        // 此層級邊界不存在就新增一個
        if (border.size() <= level) { border.push_back(0); }

        // 保持節點間隔
        (*it).s += *(border.begin() + level);
        *(border.begin() + level) += (*it).name.size() + 1;

        // 假如有子節點
        if ((*it).childen.size())
        {
            // 呼叫遞迴函式得出偏移量, 以更新起始座標及邊界
            int p = move(*it, level + 1);

            (*it).s += p;
            *(border.begin() + level) += p;
        }
    }

    int m = ((*tree.childen.begin()).s + (*(tree.childen.end() - 1)).s
            + (*(tree.childen.end() - 1)).name.size() - tree.name.size()) / 2;

    if (m < tree.s)
    {
        // 偏移量為負, 修正子節點座標及邊界
        for (vector<node>::iterator it = tree.childen.begin();
            it < tree.childen.end(); it++)
        {
            (*it).s += tree.s - m;
        }

        *(border.begin() + level) += tree.s - m;

        return 0;
    }

    // 返回父節點偏移量
    return m - tree.s;
}

void show(node &tree, int level, string str, ofstream &out)
{
    if (level)
    {
        // 印出當前節點座標
        cout << str << tree.name << " (" << tree.s << ", " << 3 * level << ")" << endl;
        out << str << tree.name << " (" << tree.s << ", " << 3 * level << ")" << endl;

        str += tree.name + ":";
    }

    // 遞迴呼叫函式顯示結果
    for (vector<node>::iterator it = tree.childen.begin();
        it < tree.childen.end(); it++)
    {
        show(*it, level + 1, str, out);
    }
}

4 回覆:

kgame 智涵 提到...

這行
tree = &(*t)
貌似多此一舉

另外呼叫指標中的成員可用->

Unknown 提到...

我知道你的意思,不過這行若以 "tree = it;" 來寫會 compile error。錯誤訊息如下:

Tree.cpp||In function `int main()':|
Tree.cpp|60|error: cannot convert `it' from type `__gnu_cxx::__normal_iterator<node*, std::vector<node, std::allocator<node> > >' to type `node*'|
||=== Build finished: 1錯誤,0警告 ===|

另外,STL中的 iterator 所指向的內容必須以 "*iterator" 提取。

若是將提取物件(結構體)的"*iterator."改成 "iterator->"仍然會發生類似的錯誤訊息。

這個就牽涉到 STL 的實做原理了,我猜大概跟 operator overloading 有關。

kgame 智涵 提到...

原來如此
沒仔細測試

但我在VC++測試iterator->可以正常運作@@

Unknown 提到...

經過與智涵於MSN討論之後,我實際做了個測試:

http://src.wtgstudio.com/?17TUN1

代表"iterator->"提取指標中的成員是可以的。

至於上面提到的錯誤,是我自己的誤解。感謝智涵的糾正。

張貼留言