考點(diǎn)2 數(shù)據(jù)結(jié)構(gòu)的基本概念

1.數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。

（1）數(shù)據(jù)的邏輯結(jié)構(gòu)。

所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系（即前后件關(guān)系）的數(shù)據(jù)結(jié)構(gòu)。它包括兩個(gè)要素，數(shù)據(jù)元素的集合和數(shù)據(jù)元素之間的關(guān)系。

（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)）。數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式包括順序存儲(chǔ)方法、鏈?zhǔn)酱鎯?chǔ)方法、索引存儲(chǔ)方法和散列存儲(chǔ)方法。而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的。

數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容主要包括3個(gè)方面：

●數(shù)據(jù)集合中各數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；

●在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；

●對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

2.數(shù)據(jù)結(jié)構(gòu)的圖形表示

數(shù)據(jù)元素之間最基本的關(guān)系是前后件關(guān)系。前后件關(guān)系，即每一個(gè)二元組，都可以用圖形來(lái)表示。用中間標(biāo)有元素值的方框表示數(shù)據(jù)元素，一般稱(chēng)為數(shù)據(jù)節(jié)點(diǎn)，簡(jiǎn)稱(chēng)為節(jié)點(diǎn)。對(duì)于每一個(gè)二元組，用一條有向線段從前件指向后件。

圖形表示數(shù)據(jù)結(jié)構(gòu)具有直觀易懂的特點(diǎn)，在不引起歧義的情況下，前件節(jié)點(diǎn)到后件節(jié)點(diǎn)連線上的箭頭可以省略。例如，樹(shù)型結(jié)構(gòu)中，通常都是用無(wú)向線段來(lái)表示前后件關(guān)系的。

3.線性結(jié)構(gòu)與非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型，即線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足有且只有一個(gè)根節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件，則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱(chēng)線性表。如果不滿(mǎn)足上述條件的數(shù)據(jù)結(jié)構(gòu)則稱(chēng)為非線性結(jié)構(gòu)。

真考鏈接

考核概率為45%。考生要熟記該考點(diǎn)的內(nèi)容，尤其是數(shù)據(jù)結(jié)構(gòu)的定義、分類(lèi)，能區(qū)分線性結(jié)構(gòu)與非線性結(jié)構(gòu)。

小提示

需要注意的是，在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)節(jié)點(diǎn)后還應(yīng)該是線性結(jié)構(gòu)。否則，不能稱(chēng)為線性結(jié)構(gòu)。

真題精選

下列敘述中正確的是______。

A）程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)

B）程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)

C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量

D）以上三種說(shuō)法都不對(duì)

【答案】A

【解析】在計(jì)算機(jī)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對(duì)數(shù)據(jù)的執(zhí)行效率有較大影響，如在有序存儲(chǔ)的表中查找某個(gè)數(shù)值比在無(wú)序存儲(chǔ)的表中查找的效率高很多。