♥ 學習筆記Learning 程式語言 Coding

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

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

childrens_highchair_b

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

ds06-01

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

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

重點是這些東西跟我的程式有什麼關係啊?沒事幹嘛跑出來亂!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];

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

b[0][0] b[1][0] b[2][0] b[3][0] b[4][0]
b[0][1] b[1][1] b[2][1] b[3][1] b[4][1]

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

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

 

   1:  Vertex VertexID[4];

Vertex VertexID[4];

 

VertexID[0] {
V_name;
V_type;
V_area;
V_power;
V_layer;
}
VertexID[1] VertexID[2] VertexID[3] VertexID[4]

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

0 1 2 3 4
V_name V_name V_name V_name V_name
V_type V_type V_type V_type V_type
V_area V_area V_area V_area V_area
V_power V_power V_power V_power V_power
V_layer V_layer V_layer V_layer V_layer

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

VertexID[0].V_name = ‘R’;

這樣使用就可了喔!因此,我們使用這個概念,先將我們的B檔案全部讀取到一個建立的表格當中了。
由於我們在最後是要將丟入表格的資料根據他們的特性整合成一個圖形(Graph),所以之後會再介紹圖形的程式表達方式的,下次再會。(光速逃~~~~)

Copyright Rami Reserved.

About the author

蕾咪

蕾咪,來自台東,卻不定期旅居歐洲的工程師女孩,身兼作家、部落客、創業家等多重身份。畢業於台大電子所,曾在義大利商與美商擔任研發工程師;走訪世界後,發現對台灣有段割捨不了的愛,讓我們一起努力成為想要的自己吧!:) 合作邀稿請聯繫:ramihaha@gmail.com

Leave a Comment