【正文】 1 版權(quán)所有 , 1997 (c) Dale Carnegie amp。 Associates, Inc. 數(shù) 據(jù) 結(jié) 構(gòu) 面 向 對 象 語 言 描 述 朱振元 2 課程的形成背景 ? 應(yīng)用領(lǐng)域： 科學(xué)計算 管理、人工智能、文字處理 ? 加工對象： 數(shù) 值 字符、表格、圖像或其他具有一定結(jié)構(gòu)的數(shù)據(jù) 3 實例 （圖 ） （圖 ） （圖 ） 4 研究對象 主要是研究： 非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的 計算機操作對象以及它們之間的關(guān)系和操作 5 學(xué)習(xí)的目的 ? 了解計算機處理對象的特性，將現(xiàn)實世界中實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。 ? 與此同時，通過算法訓(xùn)練提高計算機思維的能力，通過程序設(shè)計的技能訓(xùn)練來促進綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。 6 課程的性質(zhì) ? 綜合性的專業(yè)基礎(chǔ)課程 ? 是計算機專業(yè)課程體系中的核心課程 7 基本術(shù)語 ? 數(shù)據(jù) （ Data） 是信息的載體 ， 它能夠被計算機識別 、 存儲和加工處理 。 例如： 數(shù)值計算中的整數(shù)和實數(shù) ， 編譯程序或文本編輯程序中的字符串 。 多媒體技術(shù)中所涉及的視頻和音頻信號 ， 經(jīng)采集轉(zhuǎn)換后都能形成被計算機所接受的數(shù)據(jù) 。 8 基本術(shù)語 ? 數(shù)據(jù)元素 （ Data Element） 是數(shù)據(jù)的基本單位 。在不同的條件下 ， 數(shù)據(jù)元素又可稱為元素 、 結(jié)點 、頂點 、 記錄 。 ? 數(shù)據(jù)元素類 （ Data Element Class） 是具有相同性質(zhì)的數(shù)據(jù)元素的集合 。 例如： 整數(shù)數(shù)據(jù)對象 N＝ ｛ 0， 11,2,2……｝ 字母數(shù)據(jù)對象 C＝ ｛ ’a’ ,’b’ ,’c’……｝ 9 數(shù)據(jù)結(jié)構(gòu)的概念 ? 數(shù)據(jù)結(jié)構(gòu)（ Data Structure） 是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 ? 四類基本的結(jié)構(gòu)： （圖 ） （ 1）集合 數(shù)據(jù)元素間的關(guān)系是 ’ 屬于同一個集合 ’ 。 （ 2） 線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對一的關(guān)系 。 （ 3） 樹形結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對多的關(guān)系 。 （ 4）圖狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對多的關(guān)系，圖狀結(jié)構(gòu)也稱網(wǎng)狀結(jié)構(gòu)。 10 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲無關(guān) 邏輯結(jié)構(gòu) 線性： 線性表、棧、隊列、數(shù)組、串 非線性： 廣義表、樹、圖 11 數(shù)據(jù)的物理結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。 ? 它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。 物理結(jié)構(gòu) 順序 使用一組連續(xù)的存儲單元 非順序 鏈?zhǔn)? 索引存儲、散列存儲 12 數(shù)據(jù)結(jié)構(gòu)形式定義 Data structrue=(D,R) 其中， D是數(shù)據(jù)元素的有限集， R是 D上關(guān)系的有限集 ? 按員工的編號來建立元素間的線性關(guān)系 LinearList =(D,R) 其中： D={01,02,03,04,05,06,07,08,09,10} R＝ {01,02,02,03,………… 09,10} 13 ? 按行政分組來建立樹形的數(shù)據(jù)結(jié)構(gòu) Tree =(D,R)其中： D={01,02,03,04,05,06,07,08,09,10} R＝ {01,05,01,06,05,02,………… 06,10} ? 按員工的愛好來建立圖狀的數(shù)據(jù)結(jié)構(gòu) Graph =(D,R) 其中： D={01,02,03,04,05,06,07,08,09,10, 網(wǎng) ， 羽 ， 乒 } R＝ {01,羽 ,01,乒 ,05,網(wǎng) ,05,乒 ,06,網(wǎng) } 14 數(shù)據(jù)類型的概念 ? 數(shù)據(jù)類型（ Data Type） 是一個值的集合和定義在這個值集上的一組操作的總稱。 ? 例如：整數(shù)類型， 其取值的范圍為 [maxint,maxint]上的整數(shù) 定義在其上的一組操作為加、減、乘、除及取模等。 15 抽象數(shù)據(jù)類型 ? 抽象數(shù)據(jù)類型（ Abstruct Data Type 簡稱 ADT） 是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。 ? 抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。 16 抽象數(shù)據(jù)類型的定義 ? 抽象數(shù)據(jù)類型的定義可以由 （元素、關(guān)系、操作）三種要素來進行定義 （由于 數(shù)據(jù)類型＝數(shù)據(jù)結(jié)構(gòu)＋操作， 而數(shù)據(jù)結(jié)構(gòu)＝數(shù)據(jù)元素＋元素間的關(guān)系） 例如棧的 ADT定義： 元素 屬于同一個數(shù)據(jù)元素類 。 關(guān)系 數(shù)據(jù)元素間呈線性關(guān)系 。 操作 PUSH（ S， X） 進棧操作 、 POP（ S） 出棧操作等等 17 實現(xiàn)方法的比較 ? 面向過程的方法 在數(shù)據(jù)與操作二者之間并沒有建立必然的聯(lián)系 順序執(zhí)行 ? 面向?qū)ο蟮姆椒? 相關(guān)的數(shù)據(jù)及操作被統(tǒng)一在一個整體 ── 對象之中 程序簡潔有利于數(shù)據(jù)保護和代碼重用 18 棧演示程序 ? 面向過程的方法 Node *top。 char ch。 void push(char ch)。 …… char pop( )。 …… top=NULL。 ch=’a’。 while (ch!= ‘E’ ) { 輸入一個字符存入 ch。 對 ch進行判別并進行相應(yīng)的處理； 輸出棧中的當(dāng)前元素 }。 ? 面向?qū)ο蟮姆椒? class LinkStack { private: Node *top。 public: LinkStack ()。 void init()。 void prnt()。 char pop()。 void push (char el)。 }。 …… LinkStack lz1。 ( )。 (el)。 ( )。 19 面向?qū)ο蟮母拍? ? 對象 是指應(yīng)用問題中所出現(xiàn)的各種實體，它是由一組屬性值和在這組值上的一組操作（方法）構(gòu)成，其中，屬性值確定了對象的狀態(tài)。例如，在程序中常用的字符串、線性表、棧、隊列等或在WINDOWS應(yīng)用程序中常見的窗體、組合框、編輯框、無線按鈕等。對于一個編輯框?qū)ο螅伤?TOP、 LEFT屬性確定了它在窗體中的位置，由它的 TEXT屬性確定了顯示在該編輯框中的字符串，可以使用 GetTextLen方法來求得該字符串的長度，也可用 Clear方法來清除這個字符串 ? 類和實例 對象在語言中是用類來定義的，類中定義了與某一種對象相關(guān)聯(lián)的一組數(shù)據(jù)以及施與該數(shù)據(jù)中的一組基本操作。在面向?qū)ο蟮某绦蛟O(shè)計中，如果某一個變量被定義成屬于某一個類，那么該變量即可成為這種對象中的一個實例。 例如，在一個窗體中可以設(shè)置多個編輯框，盡管其位置及外觀都不相同，但它們都是屬于編輯框組件（類）所派生的對象實體。 20 面向?qū)ο蟮母拍? ? 數(shù)據(jù)封裝（信息隱蔽） 是指在面向?qū)ο蟮某绦蛟O(shè)計中，對象的實現(xiàn)過程（包括數(shù)據(jù)的存儲方式、操作的執(zhí)行過程）作為私有部分被封裝在類結(jié)構(gòu)中，使用者不能看到，也不能直接操作該類型所存儲的數(shù)據(jù)，而只能根據(jù)對象提供的外部接口來訪問或操作這些數(shù)據(jù) ? 繼承與派生 繼承機制是在面向?qū)ο蠓椒ㄖ凶钣刑厣姆矫?。在面向?qū)ο蟮姆椒ㄖ校惻c類之間存在著繼承關(guān)系，這種繼承關(guān)系與客觀世界中存在的一般與特殊的關(guān)系相類似。例如：在 Windows的界面設(shè)計中，可將窗體分為一般窗體和對話框，而對話框又可分為打開對話框、確認(rèn)對話框等，這些窗體都有窗體的共同特征，但不同的窗體又有自身的不同特征。我們可以將窗體定義成基類，建立它的派生類，如對話框、打開對話框等。 21 互動環(huán)節(jié) :面向?qū)ο蟪绦蛟O(shè)計 ? 使用面向?qū)ο蟮姆椒ㄇ缶匦蔚拿娣e與周長 。 ? 1 將矩形定義成類 Rect : ? 數(shù)據(jù)成員 w、 h分別表示矩形的寬與高 。 ? 構(gòu)造函數(shù) Rect(int w0,int h0) ? 函數(shù)成員 getarea()求矩形的面積 ? getperi() 求矩形的周長 ? 2 創(chuàng)建一個矩形 rect1其寬和高分別為 6 ? 然后顯示該矩形的面積與周長 22 算法及算法分析 算法的概念： 算法是對特定問題求解步驟的一種描述 算法的特性： 有窮性、確定性 、可行性、輸入、輸出 算法的描述 自然語言。 使用流程圖、 N－ S圖等用于算法描述的工具， 直接用某種高級程序設(shè)計語言來描述算法。 使用偽碼語言 算法設(shè)計的要求 正確 、 可讀 、 健壯 、 高效 23 算法分析：時間的復(fù)雜性 表示形式 ： 一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的。從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n的某個函數(shù)，算法的時間量度記作： T(n) = o( f (n) ) 該式表示算法中原操作的執(zhí)行次數(shù)與問題規(guī)模 n的某個函數(shù)同階。 24 常數(shù)階、線性階、平方階 o(1) o(n) o(n2) x= x+1。 for (i=1。i=n。i++) x= x+1。 for (i=1。i=n。i++) for (j=1。j=n。j++) x= x+1。 for(i=1。i=n。i++) for (j=1。j=n。j++) { s=0。 for (k=1。k=n。k++) s=s+a[i][k]*b[k][j]。 c[i][j]=s。 }。 25 n階矩陣相乘運算算法的時間復(fù)雜度 for(i=1。i=n。i++) for (j=1。j=n。j++) { s=0。 //基本語句 (1) for (k=1。k=n。k++) s=s+a[i][k]*b[k][j]。 //基本語句 (2) c[i][j]=s。 //基本語句 (3) }。 在通常情況下算法的時間復(fù)雜度是指基本語句重復(fù)執(zhí)行的次數(shù)及頻度 。在上述算法中主要語句的頻度分別是： 基本語句 (1)n2 ， 基本語句 (2)n3 ， 基本語句 (3)n2 。 該算法的時間復(fù)雜度所有語句的頻度之和 T(n) = n2+ n3+ n2 = o( n3 )。 因此該算法時間復(fù)雜度為 o(n3),稱之為立方階 。 26 對數(shù)階時間復(fù)雜度 i=1。 //語句 (1) while(i=n) i=i*2。 //語句 (2) 其中語句 (1)的頻度是 1， 設(shè)語句 (2)的頻度是 f(n)， 則有 2 f(n)=n， 即： f(n)=log2n， 取最大值 f(n)=log2n， 因此該算法時間復(fù)雜度為 : T(n) =1+ log2n = o(log2n) 27 互動環(huán)節(jié)：算法及其算法分析 試寫一個算法 ， 實現(xiàn)將數(shù)組 a[n]中的 n個整數(shù)循環(huán)后移一個位置 ， 并給出它的時間復(fù)雜度和輔助空間的大小 。 28 互動環(huán)節(jié)：算法及其算法分析 int i,temp。 temp=a[n1]。 for(i=n1。i=1。i) a[i]=a[i1]。 a[0]=temp。 時間復(fù)雜度 T(n) = 1+ (n1)+1 = o( n ) 線性階 空間復(fù)雜度 S(n) = 2 = o( 1 ) 常數(shù)階 29 算法分析：空間的復(fù)雜性 表示形式 ： S(n) = o( f (n) ) 實例：將存放在一維數(shù)組 a中的 n個整數(shù)反向存放，即將a[1]存放在原 a[n]存放的位置中，將 a[2]存放在原 a[n－1]存放的位置中，依次類推，直至將 a[n]存放在原 a[1]存放的位置中。 1. 使用一組工作單元 b[n] ： for (i=1。 i=n。 i++ ) b[ni+1]= a[i]。 for (i=1。 i=n。 i++ ) a[i]= b[i]。 2. 只使用工作單元 i與 w： for (i=1。 i=n/2。 i++ ) { w= a[i]。 a[i]= b[ni+1]。 b[ni+1]= w。 }。 30 演示 ? 結(jié)束