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

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

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

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

　　線性表

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

　　(a1, a2 ,a3,…an)

　　n為線性表的長(zhǎng)度(n≥0)，n=0的表稱(chēng)為空表。

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

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

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

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

　　鏈表

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

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

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

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

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

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

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

　　散列表又稱(chēng)為哈希表。散列表算法的基本思想是：

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

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

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