點(diǎn)擊進(jìn)入:2011計(jì)算機(jī)等考二級(jí)公共基礎(chǔ)知識(shí)講義匯總>>
1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念
1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。
2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題:
(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu)。
數(shù)據(jù)的邏輯結(jié)構(gòu)包含:1)表示數(shù)據(jù)元素的信息;2)表示各數(shù)據(jù)元素之間的前后件關(guān)系[wx1] 。
(2)在對(duì)數(shù)據(jù)進(jìn)行處理時(shí),各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系,即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。
1)順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里,結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。
2)鏈接存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰,結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
3)索引存儲(chǔ):除建立存儲(chǔ)結(jié)點(diǎn)信息外,還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。
*:數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu))是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu),但影響數(shù)據(jù)處理效率。
(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。
3、數(shù)據(jù)結(jié)構(gòu)的圖形表示
一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外,還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中,對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示,一般稱之為數(shù)據(jù)結(jié)點(diǎn),并簡(jiǎn)稱為結(jié)點(diǎn);為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系,對(duì)于關(guān)系R中的每一個(gè)二元組,用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。
4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。
(1)線性結(jié)構(gòu)(非空的數(shù)據(jù)結(jié)構(gòu))條件:1)有且只有一個(gè)根結(jié)點(diǎn)[wx2] ;2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件。
*:常見的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。
(2)非線性結(jié)構(gòu):不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。
*:常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。
注釋1:前后件關(guān)系:一般情況下,在具有相同特征的數(shù)據(jù)元素集合中,各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系(即聯(lián)系),這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中,通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系(即直接前驅(qū)與直接后繼關(guān)系)來描述。
注釋2:在數(shù)據(jù)結(jié)構(gòu)中,沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。
相關(guān)推薦:
2011計(jì)算機(jī)等考二級(jí)公共基礎(chǔ)知識(shí)要點(diǎn)匯總
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |