1.2.2　數(shù)據(jù)結(jié)構(gòu)的分類

數(shù)據(jù)結(jié)構(gòu)常被用于描述被研究對(duì)象的空間或邏輯結(jié)構(gòu)，可分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：

（1）有且只有一個(gè)根結(jié)點(diǎn)。

（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，最多有一個(gè)后繼。

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。在一個(gè)線性結(jié)構(gòu)中，若插入或刪除任何一個(gè)結(jié)點(diǎn)后不滿足以上的兩個(gè)條件，則被操作后的數(shù)據(jù)結(jié)構(gòu)就不是線性結(jié)構(gòu)。直觀上看，線性結(jié)構(gòu)可構(gòu)成線性表，在該結(jié)構(gòu)中所有的數(shù)據(jù)元素都按某種次序排列在一個(gè)序列中，如圖1-1所示。在實(shí)際軟件設(shè)計(jì)中，線性結(jié)構(gòu)可用于描述有先后順序的事物。

根據(jù)對(duì)線性結(jié)構(gòu)中數(shù)據(jù)元素的存取方式的不同，又可將其分為直接存取結(jié)構(gòu)、順序存取結(jié)構(gòu)和廣義索引結(jié)構(gòu)。對(duì)于直接存取結(jié)構(gòu)，可以直接存取某一特定數(shù)據(jù)元素而不需先訪問其前驅(qū)。數(shù)組、記錄等都屬于這一類，只要知道數(shù)據(jù)元素的標(biāo)號(hào)就能直接訪問該元素。對(duì)于順序存取結(jié)構(gòu)，只能從數(shù)據(jù)序列中的第一個(gè)數(shù)據(jù)元素開始，按順序依次查找，直到找到指定的元素。順序表和鏈接表就屬于該類型，只有知道表的首地址才能依次訪問各元素。廣義索引與數(shù)組有類似之處，數(shù)組是依靠其下標(biāo)進(jìn)行索引的，而廣義索引是通過關(guān)鍵碼進(jìn)行索引的。廣義索引通過設(shè)定數(shù)據(jù)記錄中某一數(shù)據(jù)項(xiàng)或某一組數(shù)據(jù)項(xiàng)為關(guān)鍵碼，通過關(guān)鍵碼來索引記錄。索引表和散列表都屬于該類。在描述工程對(duì)象時(shí)，數(shù)據(jù)的線性結(jié)構(gòu)被廣泛采用。例如，在描述生產(chǎn)流程時(shí)，各工序就可以被描述為一個(gè)線性表。

在非線性結(jié)構(gòu)中，各個(gè)數(shù)據(jù)元素不必保持在一個(gè)線性序列中，每個(gè)數(shù)據(jù)元素可能與多個(gè)其他數(shù)據(jù)元素發(fā)生關(guān)聯(lián)。在非線性結(jié)構(gòu)中，各數(shù)據(jù)元素之間的前驅(qū)與后繼的關(guān)系要比線性結(jié)構(gòu)的復(fù)雜，因此對(duì)非線性結(jié)構(gòu)的存儲(chǔ)與處理比線性結(jié)構(gòu)要復(fù)雜得多。工程軟件中對(duì)工程對(duì)象結(jié)構(gòu)的描述往往可以采用一種稱為樹的非線性數(shù)據(jù)結(jié)構(gòu)進(jìn)行描述。例如，對(duì)機(jī)器的機(jī)械結(jié)構(gòu)和控制系統(tǒng)結(jié)構(gòu)的描述就是典型的樹形結(jié)構(gòu)。

線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以為空數(shù)據(jù)結(jié)構(gòu)。一個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)要根據(jù)具體情況來定。如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。

非線性數(shù)據(jù)結(jié)構(gòu)根據(jù)前驅(qū)與后繼關(guān)聯(lián)的不同，可進(jìn)一步分為層次結(jié)構(gòu)和群結(jié)構(gòu)。

層次結(jié)構(gòu)是按層次劃分的數(shù)據(jù)元素的集合，其特點(diǎn)是：每一確定層次上的元素可以有多于一個(gè)的直接下層子元素。典型的層次結(jié)構(gòu)是樹形結(jié)構(gòu)，如圖1-2所示。

群結(jié)構(gòu)中所有元素之間無順序關(guān)系，數(shù)據(jù)元素通過特定的關(guān)系聯(lián)系在一起。這類結(jié)構(gòu)中包含集合、圖結(jié)構(gòu)等，典型的圖結(jié)構(gòu)如圖1-3所示。例如，在分析機(jī)器各功能部分的相互作用關(guān)系時(shí)，就會(huì)采用群結(jié)構(gòu)。

此外，從數(shù)據(jù)的存在方式來看，數(shù)據(jù)結(jié)構(gòu)還可分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)（即物理結(jié)構(gòu)）。數(shù)據(jù)的邏輯結(jié)構(gòu)是指從解決問題的角度出發(fā)，為實(shí)現(xiàn)必要的運(yùn)算所建立的基于邏輯的數(shù)據(jù)結(jié)構(gòu)，它屬于用戶的邏輯視圖，是面向具體工程問題的。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中存放的方式，它是數(shù)據(jù)邏輯結(jié)構(gòu)向物理存儲(chǔ)結(jié)構(gòu)的映射，是屬于具體計(jì)算機(jī)存儲(chǔ)空間的物理結(jié)構(gòu)視圖。數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)問題所要實(shí)現(xiàn)的運(yùn)算來建立，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的選擇是根據(jù)解決問題所要求的響應(yīng)速度、處理效率、存儲(chǔ)空間的利用率等因素權(quán)衡的結(jié)果，是邏輯數(shù)據(jù)的實(shí)際存儲(chǔ)映像。同一種類型的數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要采用不同的存儲(chǔ)結(jié)構(gòu)。