[C++程式設計] 學習筆記─建立資料結構(2/5)

延續我們之前提過的問題，在建立資料結構時，其實我以前常常會遇到一個觀念轉換不過來，像是當有人跟我說「你用程式把圖建出來就可以了」，這是什麼鬼？這是火星文嗎？這是中文嗎？為什麼每個字我都聽得懂，卻搞不清楚他說的是什麼意思(大哭跑開~o(# >”<)o)；因此，我就開始覺得天殺的程式語言我還只會加減乘除，別人就要我用他拿來畫出美妙的貝茲曲線了(大誤，這是完全沒關係的!)；不然就是要我寫出一棵樹，雖然我剛好也是喝克寧奶粉長大的，但是我只長成了小樹叢那樣的高，也沒跟樹很熟…。

事實上，需要先了解所謂的「圖」與「樹」這些抽象的概念；
在數學上，定義一般的圖是由點(Vertex)和線(Edge)組成的，所以他可以長成這樣。

而一般我們在論文或課本中，會看到類似這樣的定義，引述一段…
圖形 G 包含兩個集合：
一個是由頂點 ( vertices ) 所形成的有限的非空集合，另一個是由邊 (edges )所形成有限非空集合。

同理，樹的定義是由根(Root)、枝(Branch)、葉(Leaf)組成的，同樣也有類似的一般性定義。
樹狀結構是一個或多個節點的有限集合，它滿足：
1.有一個特定的節點稱為根節點 ( root )。
2.其餘的節點分成 n >= 0 個獨立的集合 T₁ , T₂,…..,T_n , 其中的各個集合是一個樹狀結構。即稱T₁ , T₂,　　　　…..,T_n 為根節點的子樹 ( Subtree ) 。

重點是這些東西跟我的程式有什麼關係啊？沒事幹嘛跑出來亂！o(= ” =+)o
而且圖那麼多種，樹那麼多種，找麻煩嘛！

你知道的，這就是我跟資料結構感情不好的時候的內心話，因為就學期間，我們大部份都只處理很小很小的程式問題，所以有時候會有殺雞用牛刀之感，卻忘了有一天我們刀總是要拿來殺牛的Orz||||。

因此，最基本的要求，就是我們得開始學會一些基本的容器，像是表格、目錄、圖、樹等，當對自己的程式有更高的要求，例如更快(Time Complexity)、更省空間(Space)等，我們再來思考演算法(Algorithm)，也就是所謂的「解決問題的方法」如何更好。

冏，越扯越遠了，我們回過頭來看看這次我們要解決的問題是如何建構圖形的吧！

※建立所需的資料結構

其實我的題目呢？是一個電路分割的問題，將電路抽象化成圖形，而因為是電路問題，所以每一個點都帶有電量與面積，因此代表的是我的圖形當中的每個點，除了她自己本身的大小以外，還需要記綠其他的資訊，因此我們會選用C++的類別(class)或C語言的結構(struct)來宣告點的樣子。

同樣的結構，我們可以運用在哪些地方呢？假設你現在需要建立一個商業網站，每一個人都有許多的基本資料，而為了讓使用者能夠比較容易獲得他們想要的資料，你會希望在背後的系統藉由她們的資料關連性，做一些簡單的分群，讓使用者被歸納到屬於他的一群，方便你做會員管理與產品行銷。

其實，兩個東西原理是一樣的，背後使用的結構也可能是類似的；因為你同樣也可以把一個人想做是一個點，就像把電子元件想做一個點一樣；同時把那些人連結的關係做為線，而電路上就是電路接線囉！

隨便先亂宣告一個這樣！

   1:  class Vertex{

   2:           char * V_name;

   3:           int V_type;

   4:           int V_area;

   5:           int V_power;

   6:           int V_layer;

   7:  };

結果會發現錯了，因為class的變數是預設為private的，所以必須宣告在public:之下。(這裡跟C不太相同喔!)

不過一開始，我們要解決我們的問題，只需要先建立一個表格，其中最常使用的是陣列(array)的形式。
例如一個表格Row，長這個樣子：

用程式怎麼把他”寫”出來呢？
你可以這樣宣告：

   1:  int a[4];

這代表的意思是，這個表格名字叫做a，有4+1格(因為電腦從0開始數)，而宣告成int是說，我要存的都是整數數字(integer)；一行表格可以作為循序的排列，那如果我要兩行呢？

可以這樣寫寫看。

   1:  int b[4][1];

那麼哪一格是指哪一格呢？

這樣就可以知道我們的東西到底是存到哪裡了。^____________^”
另外，在C++的STL(Standard Template Library)標準函式庫中，還有vector與list這些陣列的強化版容器可用，各自有各自的個性，有興趣的人可以去研究並比較看看囉！(C++ Primer 一書中有Container的比較。)

好了，介紹完表格的寫法，回到我們專題要處理的問題上吧！
因此，我們同樣也可以用這種方式宣告。

   1:  Vertex VertexID[4];

Vertex VertexID[4];

展開來看，其實就會很像一個大表格喔！^^

要能夠儲存到VertexID[0]裡頭的V_name，假設我們要將R存進去。

VertexID[0].V_name = ‘R’;

Copyright Rami Reserved.