♥ 學習筆記Learning 程式語言 Coding

[C++程式設計] 學習筆記─鏈結串列(Link List)與圖形(Graph)表示法

LINKLIST

說到鏈結串列(Link List)就代表我寫到了資料結構這一塊了,不過因為對C++語言的熟悉度偏低,所以這段還在摸索,只好老實一點,翻起了C++資料結構的書、以及C++ Primer的抽象化容器介紹;最尷尬的是,原本我想偷吃步,先宣告一個簡單的二維陣列(Array)建一個表格,硬是騰出一點空間,好直接測試與撰寫後面的演算法的。

But …又是人生最重要的But…鬼魂

我的資料量大約從10~100000個左右,所以,編譯器當然很帥氣的就給我當掉說「耍我嗎?我吃不下啦!」
因此,冷靜下來以後,我決定明查暗訪,別人是怎麼面對這麼大量的資料,又必須不能太耗時間的。

程式俱樂部討論區,就來了這麼一篇討論串,正好派上用場。《如何處理萬筆以上的資料量》
爬完討論串後,得到了一點有用的結論,來自於青衫大的具體解說。
(1) 知道總筆數資料:使用動態配置陣列,並使用Hashing搜尋,。
(2) 不知道總數量的資料:使用串連式或擴展式的方式動態配置記憶體(allocate)

你知道,其實我…有聽沒有懂。o(><;)o o 哭著跑開~
只好再針對他說的那些內容,再去尋找更多的關鍵字說明,也許哪天我就開竅了。

我幻想中的方式,比較像是第二種方式當中的串連式。
就是一開始先配置一個固定的空間,萬一不夠用的話,再多配一塊給他,直到夠用為止。
你知道的,我想到這種想法時,我還很天真的想說,用一個count去計算資料量,當達到第一個陣列空間的上限時,就在產生另一塊陣列空間,依此類推,直到while當中不再有新的資料進來,就可以停止囉!(幻想的~)

怎麼實作出來才是重點啊?孩子…                   還是沒有太多頭緒Q________Q

因此,我只好回歸到最基本的東西來,我的「資料結構」本身。
事實上,我的資料結構是一個抽象化圖形,只是為了配合演算法,需要使用Bucket List的表示方式,而為了符合IC本身的定義,所以有許多額外的細節資料,先把這些雜七雜八的細節拿掉,回到根本,就是個串列罷了。

接著,再回到最根本的,我要解決的「問題」本身,需要什麼功能?
當我為了這個圖形(Graph)創建了這樣的串列(Link List),我希望節點(Vertex)與邊(Edge)的關係可以隨時對應。
而針對每個節點串列,我要能夠知道他的大小(Size)、依大小排序(Sort)、比對(Match)、插入(Insert)、刪除(Delete)、合併(Merge)、拆解(Divide)、快速搜尋(Search)…

最後,再回頭繼續看看我的文獻,回想一下「演算法」,到底用什麼機制來解決這樣的問題?
因為一些細節資訊,我需要定義一些評估用的公式,去決定Merge的依據,將多個節點串連一起;我需要先使用DFS(深度優先搜尋)去替每一個接線接電,也就是從Library當中,擷取電量有關的訊息;我需要再串連後,重新計算大小,讓他重新又依照大小排序,方便我再做下一輪的動作;我需要再查找其他細節資料時,能夠很快的做到字串比對,找到對應資訊……

喵~所以只好硬著頭皮慢慢開始囉!Q_____________Q”
其實我學程式時,最害怕的就是一堆東西指來指去的指標了!Orz||||
但是,如果不會指標,那就是不只串列不用玩了、圖形不用玩了、連樹狀結構也沒得玩了。

在大學時,剛開始學習程式設計、資料結構、演算法等課程時,我無法體會這些東西的用處何在。
直到要實作的專案越來越大,為了有效的管理、為了資料的安全、為了程式本身的效率等,才開始成長一點。

第一點:就是個串列罷了。

 1: class Graph
 2: {
 3:       private:
 4:              list<

int

> *HeadNodes;
 5:              int n;       //n vertices
 6:       public:
 7:              Graph(const int vertices = 0):n(vertices){
 8:                          HeadNodes = new list<int> [n];
 9:                          };
 10:       };

以下,待續。XD

第二點:串列之外,還要支援許多功能。
(1) 節點(Vertex)與邊(Edge)的關係可以隨時對應
(2) 稍微來研究一下list這個STL,基本的大小(Size)、依大小排序(Sort)、插入(Insert)、刪除(Delete)似乎都有。
(3) 比對(Match)、合併(Merge)、拆解(Divide)、快速搜尋(Search)可以用一些方法做到。

第三點:支援許多功能的串列,要能符合演算法的原則。

About the author

蕾咪

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

Leave a Comment