程式語言概念-資料結構

程式語言資料結構
資料結構

在討論資料結構時，必須先暸解記憶體的運作過程，首先作業系統會將記憶體(RAM)分頁，切割成特定大小的區塊，來給運作的程式使用，在程式啟動後，會先將編譯過後的程式碼載入到記憶中，並運行，而這些程式碼有些只運行一次，有些則運行多次，如程式的初始化指運行一次，如程式操作運行多次。

而在運行程式時，會運行到有變數的段落，此時就會定義一段記憶體給該變數，而其大小會隨其資料型態改變，當有相同資料型態的資料需要儲存時，通常會用陣列，把需要的資料大小告知後，把相同類型的資放在一起，而陣列是一種資料結構，其一旦宣告後，其記憶體大小就不再改變，因此有靜態的特性，所以相對的，在操作資料結構時會改變其記憶體大小的就是動態的，所以動態的資料結構，會有如何建立、如何搜尋、如何更新、如何刪除的問題，這也衍生到資料庫的CRUD(Create、Read、Update、Delete)這概念，因此在討論的時候會把時間複雜度跟空間複雜度做介紹，這樣是比較全面的做法。

而在儲存資料的時候，會有需要自訂義資料的時候，這也會影響到資料的基本大小，而自定義的型態，通常會使用struct跟class來定義，在各種語言通常struct為value type，class為refference type，兩者在意在，struct 在定義完之後可以像一般的資料型態使用，定義的變數的資料內容是存值，所以不會相互干涉，而class則會，所以class 都會使用new的宣告新的物件，不過這些東西的細部定義需要參考該官方網站的內容，此外還有point type。

---

常見的資料型態

陣列	array
堆疊	stack
佇列	queue
連結串列	linked list
樹	tree
圖	graph
堆	heap
雜湊表	hash
串列	list
字典	dict
其他

陣列

為靜態的，其記憶體大小在初始化之後，便不能在變動。

連結串列

為動態的資料結構的基本型，由struct、指標跟變數組成，用來構成其它的資料結構。
堆疊

與佇列為相似的結構，由多個連結串列組成，目的是用來儲存資料，並後存放資料先被使用，想像疊書，疊十層高，然後從上面開始拿。

佇列

由多個連結串列組成，目的是用來儲存資料，並先存放資料先被使用，排隊的概念，FIFO。
樹

常見的樹有二元樹、平衡樹、B樹等......，通常組成的樹的內容有關聯性。
圖

常見的圖有無向圖、有向圖、無環有像圖，通常用來描述點到點之間有特定關係的情況。
堆

一種特殊樹，其母節點為恆大於子節點為最大堆積，其母節點為恆ㄒㄧ於子節點為最小堆積。
雜湊表

應用雜湊函數計算儲存位置，一種自定義的函數，其沒有反函數可以計算，簡易做法可以使用質數，不過建議使用人家寫好的函數來用，可以減少搜尋的時間，但會有資料碰撞的問題。
今天如果有一字串，取其第一個字轉換成數字，並帶入雜湊函數進行計算，在存到定義好的雜湊表中。

---

非資料結構理論定義的資料結構

串列

堆疊跟佇列的組合體，可當成動態的陣列使用，通常有移除最前面資料跟最後資料的功能，所以亦可當成堆疊、佇列。
字典

為雜湊表的延伸，可以用不同資料型態當作key的值，所以在做映射的時候相當好用。