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

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

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

數(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ù)類(lèi)型數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)算法及其特性算法設(shè)計(jì)的要求算法描述方法1.3算法概述算法評(píng)價(jià)算法(Algorithm)對(duì)特定問(wèn)題求解步驟的一種描述是指令的有限序列算法的特性有窮性確定性可行性輸入輸出算法及其特性正確性：算法應(yīng)當(dāng)滿(mǎn)足具體問(wèn)題的需求，按算法編碼好的計(jì)算機(jī)程序的執(zhí)行結(jié)果應(yīng)當(dāng)符合預(yù)先設(shè)定的功能和性能要求?？勺x性：一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、易讀易懂?？勺x性好，易于理解。健壯性：指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也被稱(chēng)為容錯(cuò)性。高效性：一個(gè)算法應(yīng)當(dāng)有效使用存儲(chǔ)空間和有較高的效率。對(duì)于同一個(gè)問(wèn)題，通常可以有多個(gè)解決算法，其中執(zhí)行時(shí)間短、占用存儲(chǔ)空間少的算法即“好的算法”。算法設(shè)計(jì)的要求自然語(yǔ)言算法描述框圖算法描述偽代碼算法描述高級(jí)程序語(yǔ)言編寫(xiě)的程序或函數(shù)算法描述方法事前估算法（定性分析）：對(duì)算法所消耗資源的一種估算方法算法的策略問(wèn)題的規(guī)模書(shū)寫(xiě)程序的語(yǔ)言編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量機(jī)器執(zhí)行指令的速度事后統(tǒng)計(jì)法（定量分析）：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開(kāi)銷(xiāo)評(píng)價(jià)算法算法評(píng)價(jià)指標(biāo)執(zhí)行程序需要占用多少機(jī)器資源時(shí)間資源算法運(yùn)行時(shí)花費(fèi)的時(shí)間代價(jià)空間資源程序執(zhí)行中占用的內(nèi)存空間代價(jià)時(shí)間復(fù)雜性和空間復(fù)雜性T(n)：2n3+3n2+2n+1算法的時(shí)間復(fù)雜性分析算法中所有語(yǔ)句執(zhí)行時(shí)間之和語(yǔ)句的執(zhí)行時(shí)間：該語(yǔ)句的頻度(語(yǔ)句重復(fù)執(zhí)行的次數(shù))，與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。//求兩個(gè)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}#求兩個(gè)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//求兩個(gè)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}#求兩個(gè)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算法的時(shí)間復(fù)雜性分析算法時(shí)間取決于控制結(jié)構(gòu)和原操作的綜合效果f(n)是算法中頻度最大的語(yǔ)句頻度，通常是最深層循環(huán)內(nèi)的原操作執(zhí)行的次數(shù)。隨著n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。算法時(shí)間復(fù)雜度記作：T(n)=O(f(n))O(n)：n3常見(jiàn)函數(shù)比較通常有如下的函數(shù)關(guān)系

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

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