數(shù)據(jù)結(jié)構(gòu)使用c語言朱戰(zhàn)立(文件)
【正文】 (c) for(j=1。k++) x=x+1。in。inamp。 ? for(j=0。 ? } ? } ? } ? ? 分析算法復(fù)雜度： ? 最好情況： 0次 ? 最壞情況： 1+2+3+…+n 1=n(n1)/2 ? 平均時(shí)間復(fù)雜度為 :O(n2) 50 空間復(fù)雜度度量 （ Space Complexity） ?空間是指執(zhí)行算法所需用的存儲(chǔ)空間 ?存儲(chǔ)空間的固定部分 程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長成分 (如數(shù)組元素、結(jié)構(gòu)成員等 )變量所占的空間 ?可變部分 遞歸棧所用的空間、通過 malloc( )和 free( ) 等函數(shù)動(dòng)態(tài)使用的空間 ?與問題規(guī)模 n 的函數(shù)關(guān)系表示為： S（ n） = O（ f(n)） 52 本章小結(jié) 數(shù)據(jù)結(jié)構(gòu)課程 —— 數(shù)據(jù)結(jié)構(gòu)＋算法＝程序，涉及數(shù)學(xué)、計(jì)算機(jī)硬件和軟件。 算法效率 —— 時(shí)間效率和空間效率 。 。 ② 建議獨(dú)立完成輔導(dǎo)材料 —— 第 1章自測(cè)卷 。 數(shù)據(jù)結(jié)構(gòu)內(nèi)容 —— 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算 。j++) ? { ? if (a[j]a[j+1]) { ? flag=1。flag==1。 }/*sort*/ ∵ 算法中 if語句的執(zhí)行頻度為： n+(n1)+(n2)+… +3+2+1=n*(n+1)/2 ∴ T(n)= O(n2) ?加法規(guī)則 (針對(duì)并列程序段 ) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) ?乘法規(guī)則 (針對(duì)嵌套程序段 ) T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)) ?算法 又有 嵌套程序段 并列程序段 ： T(n) = O(max(n2,n))= O(n2) 嵌套程序段： T(n) = O(f (n)*g (n))= O(n2) ? 有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。 ?程序段 (a) 中頻度為 1， 則 T(n)= O(1)； ?程序段 (b)中頻度為 n， 則 T(n)= O(n)； ?程序段 (c)中頻度為 n2， 則 T(n)= O(n2)。j++) for(k=1。i=n。 ? 確定性：每條指令必須有確切的含義 ? 可行性：算法是能行得通的 ? 必有輸出 41 ? 正確性：算法應(yīng)當(dāng)滿足具體問題的需求 ? 可讀性：算法的可讀性有利于人們對(duì)算法的理解 ? 健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的結(jié)果。 QueueLength( Q ) 初始條件 ：隊(duì)列 Q已存在。Q ) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列 Q。 抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。其中 D={01， 02， 03， 04， 05， 06}； ? R={r}； ? r={01， 02， 02， 05,05,04,04,06,06,03}. ? 試 分析該數(shù)據(jù)結(jié)構(gòu)屬于哪種邏輯 結(jié)構(gòu) 。 它依賴于計(jì)算機(jī) 。 解釋 1： 什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？ 25 （ 1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 解： 上述表達(dá)式可用圖形表示為： b c a e f d 此結(jié)構(gòu)為線性的?；虬凑找欢ㄟ壿嬯P(guān)系組織，并按一定存儲(chǔ)方法存儲(chǔ)的數(shù)據(jù)的集合，且需要定義一系列運(yùn)算。 抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性 ， 而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān) 。 (3)數(shù)據(jù)項(xiàng) :構(gòu)成數(shù)據(jù)元素的項(xiàng)目 。 本書圍繞數(shù)據(jù)結(jié)構(gòu)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1