數(shù)據(jù)結(jié)構(gòu)與算法講解-在線瀏覽
2025-08-06 16:28本頁(yè)面
【正文】 更適合于非數(shù)值計(jì)算。 (2)是學(xué)習(xí)、設(shè)計(jì)和實(shí)現(xiàn)操作系統(tǒng)、編譯系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)和 其它應(yīng)用系統(tǒng)的重要基礎(chǔ)。 注 : ADT是程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的進(jìn)一步 推廣和進(jìn)一步抽象。 二 .抽象數(shù)據(jù)型的實(shí)現(xiàn) 就是將 ADT轉(zhuǎn)換成程序設(shè)計(jì)語(yǔ)言的說(shuō)明語(yǔ)句，加上對(duì) 應(yīng)于該 ADT中的每個(gè)操作的函數(shù)。 (1)同一數(shù)學(xué)模型上定義不同的操作集，則它們代表不 同的ADT。 (1)各自含義 數(shù)據(jù)型是該類型變量的存儲(chǔ)格式和所有可能取值的集合 。抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型及在該模型上定義的操作集的總稱。 數(shù)組、結(jié)構(gòu)（體）和文件 一 .ADT的實(shí)現(xiàn)原則 (1)應(yīng)符合規(guī)格描述的定義； (2)應(yīng)有盡可能好的通用性； (3)應(yīng)盡可能具有良好的獨(dú)立性，在結(jié)構(gòu)上應(yīng)成為獨(dú)立 的模塊；將內(nèi)部細(xì)節(jié)屏蔽起來(lái)。 struct node{ elementtype val。 }。//棧的類型 2) 基本操作的實(shí)現(xiàn) stack NEWSTACK() { stack s。*/ snext=NULL； return s。 s=new node。 snext=stknext。 } void POP(stack stk) { stack s。 stknext=snext。 /* free(s) */ } } elementtype TOP(stack stk) { if (stknext) return (stknextval)； else return NULLELE。 else return TRUE。就是說(shuō)，用已定義的類型來(lái)表述正要定義的類型的定義域，并用前者的操作來(lái)表述后者的操作這就是所謂逐層抽象的方法。 (1)由于在定義高層數(shù)據(jù)類型時(shí)不必考慮低層數(shù)據(jù)類型及其操作的內(nèi)部細(xì)節(jié) ,因而對(duì)復(fù)雜數(shù)據(jù)類型進(jìn)行抽象可以簡(jiǎn)化許多瑣事。 3. 缺點(diǎn) 多層次抽象化的最終目的是建立最高層的數(shù)據(jù)類型，因此低層應(yīng)該服從高層的要求。 采用抽象數(shù)據(jù)型的方法進(jìn)行軟件（特別是大型軟件）系統(tǒng)的設(shè)計(jì)，具有許多明顯的優(yōu)點(diǎn)： 首先，它降低了軟件設(shè)計(jì)的復(fù)雜性。 第三，由于抽象數(shù)據(jù)型的使用降低了程序的復(fù)雜度，使程序的各部分相對(duì)分離，因而程序的正確性容易得到保證。 算法及其性能評(píng)價(jià)準(zhǔn)則 算法時(shí)間復(fù)雜性分析方法 一、算法、算法的特征和算法描述 算法（ Algorithm）：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指 令（規(guī)則）的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 算法的特征： ①有窮性、②確定性、③能行性、④輸入、⑤輸出 算法描述： ①自然語(yǔ)言；②程序設(shè)計(jì)語(yǔ)言；③類語(yǔ)言 ； 常用的算法設(shè)計(jì)方法： ①遞歸法（ Recursion）、②分治法 (Divideand Conquer)、 ③貪心法 (Greedy)、④動(dòng)態(tài)規(guī)劃 (Dynamic Programming)、 ⑤搜索與遍歷、⑥回溯（ Backtracking）、⑦解空間局部搜索 ⑧近似算法 (Approximation)、⑨在線算法（ OnLine）等 二、 好的算法的標(biāo)準(zhǔn) (Correctness) ? 正確性的含義：是指對(duì)于一切合法的輸入數(shù)據(jù)經(jīng)有限時(shí)間或有限步后均可得到正確（滿足規(guī)格說(shuō)明要求）的結(jié)果； ? 算法包括兩方面的內(nèi)容： ① 解決問(wèn)題的方法；② 實(shí)現(xiàn)這一方法的一系列指令 (語(yǔ)句、步驟 ) ? 算法的正確性證明：①需要一組相關(guān)的引理和定理，確認(rèn)一個(gè)算法所使用的方法和公式的正確性； ②在證明一系列的語(yǔ)句確實(shí)做了符合規(guī)定的動(dòng)作。只有那些比較簡(jiǎn)單的算法，其正確性才能被形式化證明。 二、 好的算法的標(biāo)準(zhǔn) ⑵事前分析 (估計(jì) )法 高級(jí)語(yǔ)言編寫(xiě)的程序在計(jì)算機(jī)上運(yùn)行時(shí)間取決于下列因素： ①依據(jù)的算法本身選擇何種策略 ②問(wèn)題的規(guī)模（輸入的規(guī)模，輸入的大?。?。它表示隨問(wèn)題規(guī)模 n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率不會(huì)超過(guò) f（ n），稱為算法的漸進(jìn)時(shí)間復(fù)雜性，簡(jiǎn)稱時(shí)間復(fù)雜性。 稱 E(n)= Σ I∈ D n {P(I)* T(I)}為該算法的期望復(fù)雜性（平均時(shí)間復(fù)雜性） 稱 W(n)=max I∈ D n { T(I)}為該算法的最壞時(shí)間復(fù)雜性 一、算法的時(shí)間復(fù)雜性 例 A是一個(gè)由 n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求其最大和最小元素的算法和時(shí)間復(fù)雜性 void SM(double A[], int n, double amp。min ) { max=min=A[0]。 kn。 if ( A[k]min ) min=A[k]。 while ( jn){ if ( A[j]==K ) break。 } return j 。令 D n={ I0, I1, …In1 , In }，其中 I j ( 0 ≤ j n ) 表示 K==A [j] 的任意輸入， In 表示 K 不是 A 中元素的任意一個(gè)輸 入，由上述說(shuō)明有：當(dāng) 0 ≤ j n 時(shí)， P(Ij)=q / n， T (Ij)=j+1， P(In)=1q ， T (In)=n 算法 SK的期望復(fù)雜性和最壞復(fù)雜性為 E(n)=Σ j∈ D n { P(Ij)* T(Ij)}= Σ j=0,…n1 [ (q /n)*(j+1)] + (1q)*n =1/2( n+1)q + (1q)n=1/2(n+1) (K在 A中， q=1) W(n)=max { T(Ij)| 0 ≤ j n } = n 二、函數(shù)階的比較 定義 設(shè) f(n)、 T(n)是整數(shù)集到實(shí)數(shù)集上的函數(shù)，稱 函數(shù) f(n )是 T(n)增長(zhǎng)率的上界，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù) C和整數(shù) n0 ，使得對(duì)任意的 n≥ n0 時(shí)，有 T (n) ≤C f(n)記作： T(n)= O( f(n)) 此時(shí)也稱 T(n)的階至多為 f(n) *一個(gè)算法的時(shí)間復(fù)雜性為 O( f(n))，表明它的基本操作次 數(shù)至多是 f(n)的某個(gè)常數(shù)倍 例 設(shè)函數(shù) T(n)=3n5+4n2+1，證明： T(n)=О(n5) 證明： f(n)= n5. 取 n0=0,
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1