數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 第1章 數(shù)據(jù)結(jié)構(gòu)與算法概論

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計計算機解決問題的步驟非數(shù)值數(shù)學(xué)模型1.1問題求解計算機求解現(xiàn)實問題計算機解決問題的步驟一個長75cm、寬60cm的長方形紙板，平均切割成大小相等的正方形紙板，使每個正方形紙板的面積最大，共可切割成多少個正方形紙板？人要和計算機進行有效交流，必須通過程序計算機世界機器語言現(xiàn)實世界自然語言程序計算機解決問題的步驟分析問題、設(shè)計算法、編寫程序、執(zhí)行程序人：分析問題、確定解決方案、編寫程序計算機：執(zhí)行程序最終獲得問題的解數(shù)據(jù)模型數(shù)值問題：數(shù)學(xué)方程非數(shù)值問題：線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)模型一個簡單的圖書信息檢索系統(tǒng)包括一張按索書號、條碼號和書名的順序排列的圖書信息表。圖書信息表中的順序關(guān)系可以被抽象成線性結(jié)構(gòu)圖書信息檢索系統(tǒng)——線性數(shù)據(jù)結(jié)構(gòu)書名條碼號索書號書架號什么是算法90073160TP393.92/1811-12-3數(shù)據(jù)庫原理與應(yīng)用70002001TP391.41/3141-12-1軟件測試項目實踐00777680TP311.52/8371-13-2Linux系統(tǒng)編程50010241TP316.76/4541-10-2Python程序設(shè)計90115601TP311.56/1291-14-1對弈問題——樹人機對弈問題是一個古老的人工智能問題，對弈過程是在一定規(guī)則約束下的隨機過程。其解決問題的思路是將對弈策略事先存入計算機，包括對弈過程中所有可能出現(xiàn)的情況和相應(yīng)的對策。城市道路問題——圖假設(shè)某人要從地點A騎車到地點G，使用導(dǎo)航系統(tǒng)查詢合適的騎行路線。導(dǎo)航系統(tǒng)為解決這個問題，須建設(shè)地區(qū)交通的數(shù)學(xué)模型，描述各個地點及其之間的交通情況。對于這類問題，通常采用“圖”來描述路況——將地點抽象成一個點，地點之間的路線抽象成一條線，路線的距離用線上的數(shù)字描述。這些點、線就組成了一個圖。小結(jié)1.1問題求解計算機解決問題的步驟非數(shù)值數(shù)學(xué)模型數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念抽象數(shù)據(jù)類型1.2數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)(data)信息的載體，是對客觀事物的符號表示，能夠被計算機識別、存儲和加工處理。圖像、聲音、視頻等都可通過編碼由計算機處理，因此也屬于數(shù)據(jù)的范疇數(shù)據(jù)元素(dataelement)數(shù)據(jù)的基本單位,也稱為元素、結(jié)點或記錄數(shù)據(jù)項數(shù)據(jù)元素可由若干個數(shù)據(jù)項（字段、域）構(gòu)成數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念數(shù)據(jù)對象數(shù)據(jù)的子集具有相同性質(zhì)的數(shù)據(jù)元素的集合姓名班級學(xué)號小明3020112小紅302027小方3020232姓名課程名成績小明高數(shù)85小紅高數(shù)90小紅英語88數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)對象數(shù)據(jù)項數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素的集合中，元素相互之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)集合線性結(jié)構(gòu)樹型結(jié)構(gòu)圖狀結(jié)構(gòu)數(shù)據(jù)的物理(存儲)結(jié)構(gòu)數(shù)據(jù)在存儲器中位置的關(guān)系數(shù)據(jù)邏輯結(jié)構(gòu)表示： Data_Structures=(D,S)D是數(shù)據(jù)元素的有限集S是數(shù)據(jù)元素關(guān)系的有限集GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<M,D1>,<M,D2>,<D1,E11>,<D1,E12>…<D２,E23>}D1D2E11E12E13E21E23E22M某公司有1名經(jīng)理(M)，2個部門經(jīng)理(D)，每個部門各有3名職員(E)。人員之間的關(guān)系是：經(jīng)理指導(dǎo)部門經(jīng)理的工作，部門經(jīng)理指導(dǎo)職員的工作。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<D1,M>,<M,E11>,<E11,E21>,<E21,E12>…<E22,E23>}D1D2E11E12E13E21E23E22M某公司有1名經(jīng)理，2個部門經(jīng)理，每個部門各有3名職員。人員之間的關(guān)系是：按人員年齡從大到小排列。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={(M,D1),(M,D2),(D1,D2),(D2,E12)…(D２,E22)}D1D2E11E12E13E21E23E22M某公司有1名經(jīng)理，2個部門經(jīng)理，每個部門各有3名職員。人員之間的關(guān)系是：人員之間的友好關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)元素的存儲用二進制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2‘A’=(101)8=(01000001)2關(guān)系的存儲順序存儲結(jié)構(gòu)用元素之間存儲的相對位置表示關(guān)系鏈式存儲結(jié)構(gòu)用存儲元素的引用（指針）表示關(guān)系抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具，其目的是使人們能夠獨立于程序的實現(xiàn)細節(jié)來理解數(shù)據(jù)結(jié)構(gòu)的特性。抽象數(shù)據(jù)類型一般通過數(shù)據(jù)對象、數(shù)據(jù)關(guān)系以及基本操作來定義。ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象D：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系R：<數(shù)據(jù)關(guān)系的定義>

基本操作P：<基本操作的定義>}小結(jié)1.2數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計算法及其特性算法設(shè)計的要求算法描述方法1.3算法概述算法評價算法(Algorithm)對特定問題求解步驟的一種描述是指令的有限序列算法的特性有窮性確定性可行性輸入輸出算法及其特性正確性：算法應(yīng)當滿足具體問題的需求，按算法編碼好的計算機程序的執(zhí)行結(jié)果應(yīng)當符合預(yù)先設(shè)定的功能和性能要求?？勺x性：一個算法應(yīng)當思路清晰、層次分明、易讀易懂?？勺x性好，易于理解。健壯性：指一個算法對不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也被稱為容錯性。高效性：一個算法應(yīng)當有效使用存儲空間和有較高的效率。對于同一個問題，通?？梢杂卸鄠€解決算法，其中執(zhí)行時間短、占用存儲空間少的算法即“好的算法”。算法設(shè)計的要求自然語言算法描述框圖算法描述偽代碼算法描述高級程序語言編寫的程序或函數(shù)算法描述方法事前估算法（定性分析）：對算法所消耗資源的一種估算方法算法的策略問題的規(guī)模書寫程序的語言編譯程序產(chǎn)生的機器代碼的質(zhì)量機器執(zhí)行指令的速度事后統(tǒng)計法（定量分析）：將算法實現(xiàn)，測算其時間和空間開銷評價算法算法評價指標執(zhí)行程序需要占用多少機器資源時間資源算法運行時花費的時間代價空間資源程序執(zhí)行中占用的內(nèi)存空間代價時間復(fù)雜性和空間復(fù)雜性T(n)：2n3+3n2+2n+1算法的時間復(fù)雜性分析算法中所有語句執(zhí)行時間之和語句的執(zhí)行時間：該語句的頻度(語句重復(fù)執(zhí)行的次數(shù))，與該語句執(zhí)行一次所需時間的乘積。//求兩個n階方陣的乘積C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求兩個n階方陣的乘積C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1//求兩個n階方陣的乘積C=A*BWhile(i<n){//n+1while(j<n){//n*(n+1)C[i][j]=0//n*n while(k<n){//n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

//n*n*n k+=1} j+=1}i+=1}#求兩個n階方陣的乘積C=A*Bwhilei<n:#n+1whilej<n:#n*(n+1)C[i][j]=0#n*n whilek<n:#n*n*(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]

#n*n*n k+=1 j+=1i+=1算法的時間復(fù)雜性分析算法時間取決于控制結(jié)構(gòu)和原操作的綜合效果f(n)是算法中頻度最大的語句頻度，通常是最深層循環(huán)內(nèi)的原操作執(zhí)行的次數(shù)。隨著n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同。算法時間復(fù)雜度記作：T(n)=O(f(n))O(n)：n3常見函數(shù)比較通常有如下的函數(shù)關(guān)系

c<log2n<n<nlog2n<n2<n3<2n指數(shù)時間的關(guān)系為

O(2n)<O(n!)<O(nn)算法的時間復(fù)雜度不僅是問題規(guī)模n的函數(shù)，還與所處理的數(shù)據(jù)集有關(guān) (1)1,2,3,4,5,6,7,