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

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

既沒有離開算法的數(shù)據(jù)結(jié)構;也沒有脫離數(shù)據(jù)結(jié)構的算法。一個農(nóng)夫(M)，要過河，他有一棵白菜(V)，一只狼(W)和一只羊(S)。一次船上農(nóng)夫只能帶一個東西。羊和白菜，狼和羊不能在一起。你找出一種最快的過河方法。例1：農(nóng)夫過河M代表人；W代表狼；S代表羊；V代表白菜。開始時4樣東西在左岸，這種情況用：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邊長設為1頂點1到頂點10的最短距離構造圖此題可以用深搜和廣搜做圖中兩點之間的最短距離：1、圖中每對頂點（任意兩點）之間的最短路徑（

算法：floyed）。2、圖中一個頂點到其他頂點的最短路徑（

算法：dijkstra）。有兩個無刻度標志的水杯，分別可裝滿x升和y升的水。設另一個水缸，可以用來向水杯灌水或從水杯向水缸里倒水，兩個水杯之間也可以相互倒水。已知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é)構：隊列問題：問從S到T的最大水流量是多少？4

32

57344引例3：

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

=

(D,

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

間的邏輯關系。物理結(jié)構：數(shù)據(jù)在計算機中的

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

2、鏈式結(jié)構：借助元素地址的指針（pointer）表示數(shù)據(jù)元間的邏輯關系

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

shl的使用Typedata=