VR開發(fā)入門教程45：數據結構簡述

　　一般將數據結構分為兩大類： 線性數據結構和非線性數據結構。

　　線性數據結構有: 線性表、棧、隊列、串、數組和文件;

　　非線性數據結構有: 散列表、樹和圖。

　　線性表

　　線性表的邏輯結構是n個數據元素的有限序列:

　　(a1, a2 ,a3,…an)

　　n為線性表的長度(n≥0)，n=0的表稱為空表。

　　數據元素呈線性關系。必存在唯一的稱為“第一個”的數據元素;必存在唯一的稱為“最后一個”的數據元素;除第一個元素外，每個元素都有且只有一個前驅元素; 除最后一個元素外，每個元素都有且只有一個后繼元素。

　　所有數據元素在同一個線性表中必須是相同的數據類型。

　　線性表按其存儲結構可分為順序表和鏈表。用順序存儲結構存儲的線性表稱為順序表;用鏈式存儲結構存儲的線性表稱為鏈表。

　　將線性表中的數據元素依次存放在某個存儲區(qū)域中,所形成的表稱為順序表。一維數組就是用順序方式存儲的線性表。

　　鏈表

　　棧(Stack)也是一種特殊的線性表，是一種后進先出(LIFO)的結構。

　　棧是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂(top)，表頭稱為棧底(bottom)。

　　棧的物理存儲可以用順序存儲結構，也可以用鏈式存儲結構。

　　隊列(Queue)是限定所有的插入只能在表的一端進行，而所有的刪除都在表的另一端進行的線性表。

　　表中允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)。

　　隊列的操作是按先進先出(FIFO)的原則進行的。

　　隊列的物理存儲可以用順序存儲結構，也可以用鏈式存儲結構。

　　散列表又稱為哈希表。散列表算法的基本思想是：

　　以結點的關鍵字為自變量，通過一定的函數關系(散列函數)計算出對應的函數值，以這個值作為該結點存儲在散列表中的地址。

　　當散列表中的元素存放太滿，就必須進行再散列，將產生一個新的散列表，所有元素存放到新的散列表中，原先的散列表將被刪除。在C#語言中，通過負載因子(load factor)來決定何時對散列表進行再散列。例如：如果負載因子是0.75，當散列表中已經有75%的位置已經放滿，那么將進行再散列。

　　負載因子越高(越接近1.0)，內存的使用效率越高，元素的尋找時間越長。負載因子越低(越接近0.0)，元素的尋找時間越短，內存浪費越多。