軟件復(fù)習(xí)指導(dǎo)-第2章基本數(shù)據(jù)結(jié)構(gòu)

2第二章

基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.1數(shù)據(jù)結(jié)構(gòu)的基本概念結(jié)構(gòu)2.2線性表及其順序2.3線性鏈表及其運(yùn)算2.4樹與二叉樹本次課主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容——基本概念和術(shù)語——數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)的物理結(jié)構(gòu)——數(shù)據(jù)的運(yùn)算計(jì)算機(jī)解題的基本方法是：分析問題，確定數(shù)據(jù)模型；設(shè)計(jì)相應(yīng)的算法；編寫程序；反復(fù)調(diào)試程序直至得到正確的結(jié)果。有些問題的數(shù)據(jù)模型可以用具體代數(shù)方程、矩陣等表示。然而，的實(shí)際問題是無法用數(shù)學(xué)方程表示的。下面給出三個(gè)簡(jiǎn)單的例子加以說明。舉例1表2-1是一個(gè)學(xué)生基本情況表。表中有30個(gè)記錄，按學(xué)號(hào)順序排列，它們之間存在一對(duì)一的關(guān)系，這是一種線性結(jié)構(gòu)，主要操作有查找、修改、或刪除等。2.1.1

數(shù)據(jù)結(jié)構(gòu)學(xué)

號(hào)姓

名性

別班級(jí)......1200302001男電氣（1）......1200302002男電氣（1）.......1200302003男電氣（1）......…………......1200302030巨園園女電氣（1）......表2-12.1.1數(shù)據(jù)結(jié)構(gòu)作是遍歷、查找、

或刪除等。2.1.1舉例2圖2-1表示的是我院的專業(yè)設(shè)置情況。在圖2-1中可以把一所學(xué)院名稱看成樹根，把下設(shè)的若干個(gè)教育類別名看成它的樹枝中間結(jié)點(diǎn)，把每個(gè)教育類別的若干個(gè)專業(yè)方向看成樹葉，這就形成一個(gè)樹形結(jié)構(gòu)。樹形結(jié)構(gòu)通常用表示結(jié)點(diǎn)的分層組織，結(jié)點(diǎn)之間是一對(duì)多的關(guān)系。對(duì)于樹形結(jié)構(gòu)的主要操數(shù)據(jù)結(jié)構(gòu)水利水電學(xué)院水利水電工程教育本科教育電氣工程及其自動(dòng)化水利工程水文學(xué)與水資源圖2-12.1.1數(shù)據(jù)結(jié)構(gòu)2.1.1

數(shù)據(jù)結(jié)構(gòu)舉例3圖2-2是一個(gè)描述若干個(gè)城鎮(zhèn)之間的公路網(wǎng)。圖中每個(gè)頂點(diǎn)代表一個(gè)城鎮(zhèn)，邊表示城鎮(zhèn)之間的道路。顯然在圖2-2中各個(gè)頂點(diǎn)之間的關(guān)系更加復(fù)雜，它們是一種多對(duì)多的關(guān)系。具有這種關(guān)系的結(jié)構(gòu)稱之為圖形結(jié)構(gòu)。在實(shí)際應(yīng)用中，假設(shè)從某個(gè)原料產(chǎn)地把原料運(yùn)往各加工地，需要制定一個(gè)方案使得費(fèi)用最省。DCABE圖3-50302.1.1數(shù)據(jù)結(jié)構(gòu)2.1.1數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：（數(shù)值或非數(shù)值）Data_Structure=（D,

R）——是指同一種數(shù)據(jù)元素類型中各元

間存在的關(guān)系。——針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。元素有限集關(guān)系有限集2.1.2

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是，針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的一門學(xué)科。程序設(shè)計(jì)＝好算法＋好結(jié)構(gòu)同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能有明顯的差異。2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容基本概念和術(shù)語數(shù)據(jù)(data)——所有能被計(jì)算機(jī)識(shí)別、和處理的符號(hào)的集合（包括數(shù)字、字符、聲音、圖像等信息）。數(shù)據(jù)元素(data element)——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義(又稱元素、結(jié)點(diǎn)，頂點(diǎn)、記錄等）。數(shù)據(jù)對(duì)象(dataobject)——由性質(zhì)相同(類型相同)的數(shù)據(jù)元素組成的集合。數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集。2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容基本概念和術(shù)語例1由4個(gè)整數(shù)組成的數(shù)據(jù)對(duì)象D1={20,-30,88,45}例2由正整數(shù)組成的數(shù)據(jù)對(duì)象D2={1,2,3,...}例3由26個(gè)字母組成的數(shù)據(jù)對(duì)象D3={A,B,C,...,Z}其中：D1，D3是有窮集，D2是無窮集。集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)基本概念和術(shù)語4.數(shù)據(jù)結(jié)構(gòu)(data

structure)——相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元

間的關(guān)系稱為結(jié)構(gòu)。四類基本結(jié)構(gòu)：2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容集合結(jié)構(gòu)：僅同屬一個(gè)集合線性結(jié)構(gòu):

一對(duì)一（1:1)樹

結(jié)構(gòu):

一對(duì)多（1:n)圖

結(jié)

構(gòu):

多對(duì)多

(m:n)非線性線性邏輯結(jié)構(gòu)可細(xì)分為4類：指數(shù)據(jù)元據(jù)，它與數(shù)據(jù)的間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容線性表?xiàng)ｊ?duì)列,雙隊(duì)列數(shù)組字符串線性結(jié)構(gòu)邏輯結(jié)構(gòu)非

線

性結(jié)

構(gòu)樹,二叉樹圖數(shù)據(jù)的邏輯結(jié)構(gòu)分類2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)——線性結(jié)構(gòu)（1）

S=(D,

R)D={

a,

b,

c,

d,

e,

f

}R={(a,e),(b,c),

(c,a),

(e,f),

(f,d)}f解：上述表達(dá)式可用圖形表示為：b

c

a

e此結(jié)構(gòu)為線性的。d例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并性結(jié)構(gòu)還是非線性結(jié)構(gòu)。它們是屬于線2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容數(shù)據(jù)的邏輯結(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)該結(jié)構(gòu)是非線性的。數(shù)據(jù)的邏輯結(jié)構(gòu)——非線性結(jié)構(gòu)（2）

S=(D,

R)D={di

|1≤i≤5}R={(di

,

dj

),

i<j}解：上述表達(dá)式可用圖形表示為：d1d2d3d4d52.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容前后件關(guān)系是數(shù)據(jù)元

間的一個(gè)基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義是隨具體對(duì)象的不同而不同。為了反映數(shù)據(jù)對(duì)象D中各數(shù)據(jù)元

間的前后件關(guān)系，一般用二元組來表示。設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組（a，b）表示a是b的前件（前驅(qū)），b是a的后件（后繼）。間的關(guān)系描述2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)元例如

四季的數(shù)據(jù)結(jié)構(gòu)B＝（D，R）D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}“夏”是“秋”的前件；“秋”是“夏”的后件。家庭成員數(shù)據(jù)結(jié)構(gòu)B＝（D，R）D＝{父親，兒兒}R＝{(父親，兒子），(父親，女兒）}“父親”是“兒子”、“女兒”的前件；“兒子”、“女兒”是“父親”的后件。2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)元

間的關(guān)系描述在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)（也稱為葉子結(jié)點(diǎn)）；除了根結(jié)點(diǎn)與終端結(jié)點(diǎn)外的其他結(jié)點(diǎn)一般稱為結(jié)點(diǎn)。根結(jié)點(diǎn)葉子結(jié)點(diǎn)結(jié)點(diǎn)終端結(jié)點(diǎn)2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)元

間的關(guān)系描述結(jié)構(gòu)可分為4大類：物理結(jié)構(gòu)亦稱

結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)

器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。順序、鏈?zhǔn)?、索引、散列例：?-1（學(xué)生信息表）的兩種

方式：記錄2方式1：地址03000301記錄10415記錄10415記錄2方式2：地址03000301內(nèi)容內(nèi)容數(shù)據(jù)的物理結(jié)構(gòu)2.1.3

數(shù)據(jù)結(jié)構(gòu)主要涵蓋內(nèi)容在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。它在數(shù)據(jù)的

結(jié)構(gòu)上實(shí)現(xiàn)。最常用的數(shù)據(jù)運(yùn)算有5

種：、刪除、修改