數(shù)據(jù)結(jié)構(gòu)ppt教案(清華大學(xué))ds-文庫吧資料
2024-10-25 19:45本頁面
【正文】 當(dāng) n?? 時的時間復(fù)雜性，稱為 漸進(jìn)時間復(fù)雜性 。 51 算法的事前估計 ? 算法的事前估計主要包括時間復(fù)雜性和空間復(fù)雜性的分析： ? 問題的規(guī)模： 如：矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)等。 cout n runTime endl。stop)。 int k = seqsearch (a, n, x)。 time(amp。 return i。 a[i] != x ) i++。 while ( i n amp。 49 例如，給出順序搜索 (Sequenial Search)算法 int seqsearch ( int a[ ], int n, int x ) { //在 a[0],…,a[n 1]中搜索與給定值 x 相等的元 //素，函數(shù)返回其位置，失敗返回 1。 ? 事后測試 則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分析。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。通常這兩者與問題的規(guī)模有關(guān)。以有利于閱讀者對程序的理解。 } 定義對象時，代入實際數(shù)據(jù)類型 重載友元操作 標(biāo)準(zhǔn) I／ O操作 消息通信 46 算法簡單性能分析與度量 ? 算法的性能標(biāo)準(zhǔn) ? 算法的后期測試 ? 算法的事前估計 47 算法的性能標(biāo)準(zhǔn) ? 正確性 (Correctness ) 算法應(yīng)滿足具體問題的需求。 cout TestList endl。 cout TestList endl。 45 dataList int, sick TestList (SZ)。 bool operator (sick x) { return key 。 int age。 int main ( ) { struct sick { //患者 int key。 if (j != i) swap (j, i)。 i = listSize2。 } return inStream。 i++) { cout “元素 ” i “:” 。 for (int i = 0。 instream 。 operator (istreamamp。 return outStream。 outStream endl。 i 。 outStream, dataListK, E outList) { outStream “輸出數(shù)組內(nèi)容 : \n”。 定義的重載操作 41 template class K, class E ostreamamp。 return min。 40 template class K, class E int dataListK, E::minKey (int low, int high) { //查找數(shù)組 Element[low]到 Element[high]中具 //有最小關(guān)鍵碼值的表項，函數(shù)返回其位置 int min = low。 element [m2] = temp。 endif 39 類中所有操作作為模板函數(shù)的實現(xiàn) template class K, class E void dataList K,E :: swap (int m1, int m2) { //交換由 m1, m2為下標(biāo)的數(shù)組元素的值 E temp = element [m1]。 inList)。 operator (istreamamp。 outList)。 operator (ostreamamp。} void sort ( )。 int minKey (int low, int high)。 int listSize。 } } 36 模板 (template) 定義 適合 多種數(shù)據(jù)類型 的 類定義 或 算法 ，在特定環(huán)境下通過簡單地代換，變成 針對具體某種數(shù)據(jù)類型 的 類定義 或 算法。 a[i] = a[k]。 j++) if (a[j] a[k]) k = j。 //從 a[i]查到 a[n1], 找最小整數(shù) , 在 a[k] for (int j = i+1。 i n1。 若最小整數(shù)在 a[k], 交換 a[i]與 a[k]。 i n1。 – 使用： move(p, x, y)。 ? C中則不同，需使用函數(shù)調(diào)用方式： – 定義： Point p。 void move(int Δx, intΔy)。 ? 同一類的實例 ? 共享類的屬性和類的操作； ? 通過繼承共享其父類的公共的和保護(hù)性的屬性和操作； ? 同一類的不同實例有不同的屬性值。 28 ? 類 (class)，實例 (instance) ? 具有相同屬性和服務(wù)的對象歸于同一類，形成類。 ? 由一組 屬性值 和在這組值上的一組 服務(wù)（或稱操作）構(gòu)成。 False, True ? Boolean, +、 、 、 ==、 = 等都是可用的服務(wù)。 24 自然數(shù)的抽象數(shù)據(jù)類型定義 ADT NaturalNumber is objects: 一個整數(shù)的有序子集合 ,它開始于 0, 結(jié)束于機(jī)器能表示的最大整數(shù) (MaxInt)。 ? “ 后置條件 ” 說明了操作正常完成之后 ，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果 。打頭 ， 除可提供輸入值外 ， 還將返回操作結(jié)果 。 ? 抽象數(shù)據(jù)類型可用 （ D, S, P） 三元組表示，其中， D 是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象）， S 是 D上的關(guān)系集合， P 是對 D 的基本操作集合。 20 抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types) ? 抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。 ? 數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。 ? 構(gòu)造數(shù)據(jù)類型由 不同成分類型 構(gòu)成。 13 數(shù)據(jù)的邏輯結(jié)構(gòu)分類 ? 線性結(jié)構(gòu) ? 線性表 ? 非線性結(jié)構(gòu) ? 樹 ? 圖（或網(wǎng)絡(luò)） 14 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 樹 二叉樹 二叉搜索樹 bin dev etc lib user 14 13 12 11 2 3 4 5 6 7 8 9 10 3 1 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1