山師附中課件-mutong在yj41上第17講數(shù)據(jù)結(jié)構(gòu)

為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)？主要掌握的數(shù)據(jù)結(jié)構(gòu)有哪些？怎樣學(xué)好數(shù)據(jù)結(jié)構(gòu)？一、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？程序=計(jì)算機(jī)語言+數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)和算法緊密聯(lián)系：

既沒有離開算法的數(shù)據(jù)結(jié)構(gòu);也沒有脫離數(shù)據(jù)結(jié)構(gòu)的算法。一個(gè)農(nóng)夫(M)，要過河，他有一棵白菜(V)，一只狼(W)和一只羊(S)。一次船上農(nóng)夫只能帶一個(gè)東西。羊和白菜，狼和羊不能在一起。你找出一種最快的過河方法。例1：農(nóng)夫過河M代表人；W代表狼；S代表羊；V代表白菜。開始時(shí)4樣?xùn)|西在左岸，這種情況用：MWSV表示。左岸可能出現(xiàn)的情況共有16種：[MWSV]

[MWS]

[MWV]

[MSV]

[WSV]

[MW]

[MS][MV][WS]

[WV]

[SV]

[M]

[W]

[S]

[V]

[

]刪除6中可能狼吃羊，羊吃白菜的情況：[WSV]

[MW]

[MV]

[WS]

[SV]

[M]還剩下10中可能發(fā)生的情況。10種情況：如果情況A經(jīng)過一次渡河可以變成情況B那么從A到B連一條邊。//岸的左邊MWSVMWSMWVMSVMSWVWSV[]12345678910邊長設(shè)為1頂點(diǎn)1到頂點(diǎn)10的最短距離構(gòu)造圖此題可以用深搜和廣搜做圖中兩點(diǎn)之間的最短距離：1、圖中每對頂點(diǎn)（任意兩點(diǎn)）之間的最短路徑（

算法：floyed）。2、圖中一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑（

算法：dijkstra）。有兩個(gè)無刻度標(biāo)志的水杯，分別可裝滿x升和y升的水。設(shè)另一個(gè)水缸，可以用來向水杯灌水或從水杯向水缸里倒水，兩個(gè)水杯之間也可以相互倒水。已知x升的水杯開始是盛滿水的，y升的

是空的，問如何通過倒水和灌水操作，用最少的步數(shù)能在y升的

里量出z升水。X

Y水缸（足夠的水,未滿）X=20

Y=15

Z=10

？Y—>10例2：倒水問題XY開始:200step1:515step2:015step3:150step4:1515step5:2010算法：廣度優(yōu)先搜索數(shù)據(jù)結(jié)構(gòu)：隊(duì)列問題：問從S到T的最大水流量是多少？4

32

57344引例3：

問題有一自來水管道輸送系統(tǒng)，起點(diǎn)是S，終點(diǎn)是T，途中經(jīng)過的管道都有一個(gè)最大的容量。算法：網(wǎng)絡(luò)流（最大流）算法數(shù)據(jù)結(jié)構(gòu)：圖數(shù)據(jù)與數(shù)據(jù)間的關(guān)系。針對數(shù)據(jù)的基本操作。數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure

=

(D,

S)式，以便對數(shù)據(jù)進(jìn)是行有效的和組織數(shù)據(jù)的和修改。二、數(shù)據(jù)結(jié)構(gòu)？方式。物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的邏輯結(jié)構(gòu)：數(shù)據(jù)元

間的邏輯關(guān)系。物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的

方式。1、順序結(jié)構(gòu)：借助元素在器中的相對位置來表示數(shù)據(jù)元間的邏輯關(guān)系。邏輯上關(guān)聯(lián)的數(shù)據(jù)元素，物理結(jié)構(gòu)中相鄰。

2、鏈?zhǔn)浇Y(jié)構(gòu)：借助元素地址的指針（pointer）表示數(shù)據(jù)元間的邏輯關(guān)系

。邏輯上關(guān)聯(lián)的數(shù)據(jù)元素，物理 結(jié)構(gòu)中不一定相鄰。幾種主要的數(shù)據(jù)結(jié)構(gòu)(邏輯邏輯)離散結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖結(jié)構(gòu)四種數(shù)據(jù)結(jié)構(gòu)類型定義：算法就是對某一類特定問題求解步驟的一種描述，是指令的有限有序系列。五個(gè)重要特征：、有窮性、確定性、可行性、輸入(0或多個(gè))、輸出（一個(gè)或多個(gè)）、算法算法的描述：、偽代碼（最常用）、流程圖、通俗語言描述算法的要求：、正確性、可讀性、健壯性、時(shí)間復(fù)雜度和空間復(fù)雜度要小（時(shí)間快，空間?。┚€性結(jié)構(gòu)：線性表、棧、隊(duì)列樹圖三、主要掌握的數(shù)據(jù)結(jié)構(gòu)有哪些？掌握數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，適用范圍該數(shù)據(jù)結(jié)構(gòu)的常用基本算法基本算法的擴(kuò)展\變形及應(yīng)用等不能參看別人的算法，不能參看程序（學(xué)習(xí)的關(guān)鍵）四、怎樣學(xué)好數(shù)據(jù)結(jié)構(gòu)？參變量是數(shù)組類型fillchar的使用Shr

shl的使用Typedata=