VR開發(fā)入門教程45：數(shù)據(jù)結(jié)構(gòu)簡述

　　一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類： 線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。

　　線性數(shù)據(jù)結(jié)構(gòu)有: 線性表、棧、隊列、串、數(shù)組和文件;

　　非線性數(shù)據(jù)結(jié)構(gòu)有: 散列表、樹和圖。

　　線性表

　　線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列:

　　(a1, a2 ,a3,…an)

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

　　數(shù)據(jù)元素呈線性關(guān)系。必存在唯一的稱為“第一個”的數(shù)據(jù)元素;必存在唯一的稱為“最后一個”的數(shù)據(jù)元素;除第一個元素外，每個元素都有且只有一個前驅(qū)元素; 除最后一個元素外，每個元素都有且只有一個后繼元素。

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

　　線性表按其存儲結(jié)構(gòu)可分為順序表和鏈表。用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表;用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表稱為鏈表。

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

　　鏈表

　　棧(Stack)也是一種特殊的線性表，是一種后進(jìn)先出(LIFO)的結(jié)構(gòu)。

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

　　棧的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

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

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

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

　　隊列的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

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

　　以結(jié)點(diǎn)的關(guān)鍵字為自變量，通過一定的函數(shù)關(guān)系(散列函數(shù))計算出對應(yīng)的函數(shù)值，以這個值作為該結(jié)點(diǎn)存儲在散列表中的地址。

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

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