數(shù)據(jù)結(jié)構(gòu)使用c語言朱戰(zhàn)立-預(yù)覽頁
【正文】 程序、軟件？ （ Niklaus Wirth)教授提出： 程序 =算法 +數(shù)據(jù)結(jié)構(gòu) 以上公式說明了如下兩個問題： （ 1）數(shù)據(jù)上的算法決定如何構(gòu)造和組織數(shù)據(jù)（算法 → 數(shù)據(jù)結(jié)構(gòu)）。 ?數(shù)值計算解決問題的一般步驟： 數(shù)學(xué)模型 → 選擇計算機語言 → 編出程序 →測試 → 最終解答。 ?非數(shù)值計算問題： 11 例 田徑賽的時間安排問題（無向圖的著色問題） ： 設(shè)有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）設(shè)計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。 即：首先要考慮 對相關(guān)的各種信息如何表示、組織和存儲？ 因此，可以認(rèn)為： 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科。 70年代后期，我國高校陸續(xù)開設(shè)該課程。 18 ?《 數(shù)據(jù)結(jié)構(gòu)課程 》 所處的地位： 19 數(shù)據(jù)結(jié)構(gòu)的核心研究內(nèi)容 數(shù)據(jù)的邏輯結(jié)構(gòu) 、 存儲結(jié)構(gòu)及它們之間的關(guān)系和相應(yīng)的基本操作運算的定義和實現(xiàn) 。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成 。 例：C語言 （ 基本類型：整型 、 浮點型 、 字符型等構(gòu)造類型：數(shù)組 、結(jié)構(gòu) 、 聯(lián)合 、 指針 、 枚舉等 ） (5)抽象數(shù)據(jù)類型 （ Abstruct Data Type，簡稱 ADT） ：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作 。 21 22 基本術(shù)語 (續(xù)） (7)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。即從邏輯關(guān)系上描述數(shù)據(jù)，它 與數(shù)據(jù)的存儲無關(guān) ，是 獨立于計算機 的。 解：上述表達(dá)式可用圖形表示為： （ 2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), ij} 27 答：物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu) ， 是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示 （ 或映像 ） 。 最常用的數(shù)據(jù)運算有 5 種： 插入、刪除、修改、查找、排序 解釋 3：什么是數(shù)據(jù)的運算？ 練習(xí) ? 設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為： line=(D,R)。其中D={a， b， c， d， e， f,g}； R={r}； r={a， b， b， c,c,d,d,e,e,f,f,g}.試畫出對應(yīng)的圖形并說明屬于哪種邏輯結(jié)構(gòu) . 32 ? 將上述關(guān)系改為 r={a， b， a，c,b,d,b,e,c,f,c,g}.試畫出對應(yīng)的圖形并說明屬于哪種邏輯結(jié)構(gòu) . 33 34 什么是抽象數(shù)據(jù)類型 1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？ 2 抽象數(shù)據(jù)類型如何定義？ 3 抽象數(shù)據(jù)類型如何表示和實現(xiàn)？ 討論： 35 1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別 數(shù)據(jù)類型：是一個值的集合和定義在該值上的一組操作的總稱。 ? 基本操作： InitQueue( amp。 操作結(jié)果：銷毀隊列 Q。 ? 有窮性：一個算法必須總是 (對任何合法的輸入值 )在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。 ?時間復(fù)雜度往往不是精確的執(zhí)行次數(shù) ， 而是估算的數(shù)量級 ， 它著重體現(xiàn)的是隨著問題規(guī)模 n的增大 ， 算法執(zhí)行時間的變化趨勢 ?時間復(fù)雜度的數(shù)量級 O (1) O (log2n) O (n ) O( nlog2n) O (n2) O (n3) O (2n) O (3n) O (n!) ?例如在下列三個程序段中： (a) x=x+1； (b) for(i=1。j=n。 基本語句均為 x=x+1。i++) for(j=i； j=n； j++) if( S[i]． score＜ S[j]． score) { t=S[i]； S[i]=S[j]； S[j]=t； } for(i=1； i=n； i++) printf(“%8d%8d%8d\n”,i,S[i].no,S[i].score)。amp。jni。 數(shù)據(jù)結(jié)構(gòu)定義 —— 指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，可用 data_Structure=(D,R)表示。 53 作業(yè)： ① 課本 P25 ， ， ， ， ，
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1