[計算機軟件及應用]數(shù)據(jù)結構第1章 緒論.ppt

1、1 1.1 什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構 1.2 基本概念和術語基本概念和術語 1.4 算法和算法分析算法和算法分析 1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn) 2 1.1 什么是數(shù)據(jù)結構 用計算機解決具體問題的步驟用計算機解決具體問題的步驟 ： 1. 抽象出一個抽象出一個數(shù)學模型數(shù)學模型； 2. 設計一個解此數(shù)學模型的設計一個解此數(shù)學模型的算法算法； 3. 編程、測試、調(diào)整。編程、測試、調(diào)整。 尋求數(shù)學模型：尋求數(shù)學模型：分析分析問題問題、提取、提取操作操作的的對象對象及其及其 對象之間的對象之間的關系關系并進行描述。并進行描述。非數(shù)值計算非數(shù)值計算 操作對象操作對象關系和操作

2、關系和操作 3 1.2 基本概念 數(shù)據(jù)數(shù)據(jù)： 指所有能被輸入到計算機中，且能被計算指所有能被輸入到計算機中，且能被計算 機處理的機處理的。 是計算機操作的是計算機操作的。 數(shù)據(jù)元素數(shù)據(jù)元素: : 是數(shù)據(jù)結構中討論的是數(shù)據(jù)結構中討論的單位。單位。 在計算機程序中作為一個在計算機程序中作為一個“”進行考進行考 慮。慮。 一一. . 數(shù)據(jù)和數(shù)據(jù)結構數(shù)據(jù)和數(shù)據(jù)結構 4 數(shù)據(jù)項：數(shù)據(jù)項： 是數(shù)據(jù)結構中討論的是數(shù)據(jù)結構中討論的的的單位。單位。 數(shù)據(jù)對象數(shù)據(jù)對象: : 是是的數(shù)據(jù)元素的集合，如的數(shù)據(jù)元素的集合，如:一個班級一個班級 的成績表可以看作一個數(shù)據(jù)對象。它是的成績表可以看作一個數(shù)據(jù)對象。它是數(shù)據(jù)數(shù)據(jù)

3、的一個的一個 子集子集。 數(shù)據(jù)結構：數(shù)據(jù)結構： 若在特性相同的數(shù)據(jù)元素若在特性相同的數(shù)據(jù)元素集合集合中的中的數(shù)據(jù)元素數(shù)據(jù)元素之間存之間存 在一種或多種在一種或多種特定的關系特定的關系，則稱該數(shù)據(jù)元素的集合，則稱該數(shù)據(jù)元素的集合 為為“數(shù)據(jù)結構數(shù)據(jù)結構“。 數(shù)據(jù)結構數(shù)據(jù)結構是帶是帶“結構結構”的的數(shù)據(jù)元素數(shù)據(jù)元素的集合。的集合。 5 數(shù)據(jù)結構是一個二元組是一個二元組 Data_Structures = (D, S) 其中其中: D 是是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是是 D上關系的有限集。上關系的有限集。 6 二二. . 數(shù)據(jù)類型數(shù)據(jù)類型 在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)

4、在用高級程序語言編寫的程序中，必須對程序中出現(xiàn) 的每個的每個變量、常量或表達式變量、常量或表達式，明確說明它們，明確說明它們所屬的數(shù)所屬的數(shù) 據(jù)類型據(jù)類型。 【例】【例】C/C+語言中提供的基本數(shù)據(jù)類型有語言中提供的基本數(shù)據(jù)類型有: 整整 型型 int浮浮 點點 型型 float 字符型字符型 char 邏輯型邏輯型 bool （ C+語言）語言） 雙精度型雙精度型 double 1.2 基本概念 7 8 三三. . 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (Abstract Data Type , ADT) 抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型：是指一個是指一個數(shù)學模型數(shù)學模型以及定義在此數(shù)以及定義在此數(shù) 學模型上

5、的學模型上的一組操作一組操作。 即：即：ADT的定義由一個的定義由一個值域值域和定義在該值域上的一和定義在該值域上的一 組組操作操作組成。組成。 ADT的定義僅取決于的定義僅取決于數(shù)據(jù)模型數(shù)據(jù)模型的的邏輯特征邏輯特征。 ADT和和數(shù)據(jù)類型數(shù)據(jù)類型實質上是一個概念。實質上是一個概念。 與其在與其在計算機內(nèi)部計算機內(nèi)部的表示和實現(xiàn)無關。的表示和實現(xiàn)無關。 “抽象抽象”的意義在于數(shù)據(jù)類型的的意義在于數(shù)據(jù)類型的數(shù)學抽象特性數(shù)學抽象特性。 不論內(nèi)部結構如何變化，都不論內(nèi)部結構如何變化，都不會影響外部使用不會影響外部使用。 9 例：線性表這樣的抽象數(shù)據(jù)類型。例：線性表這樣的抽象數(shù)據(jù)類型。 數(shù)學模型數(shù)學模型

6、：數(shù)據(jù)元素的集合；：數(shù)據(jù)元素的集合； 該集合內(nèi)的元素的該集合內(nèi)的元素的關系關系：除第一個和最后：除第一個和最后 一個外，每個元素有唯一的前趨和唯一的一個外，每個元素有唯一的前趨和唯一的 后繼；后繼； 操作操作：插入一個元素、刪除一個元素等。：插入一個元素、刪除一個元素等。 10 抽象數(shù)據(jù)類型不僅僅局限于抽象數(shù)據(jù)類型不僅僅局限于固有數(shù)據(jù)類型固有數(shù)據(jù)類型，也包括，也包括用用 戶自定義的戶自定義的數(shù)據(jù)類型。數(shù)據(jù)類型。 ADT 按照其值的不同特性，分為按照其值的不同特性，分為4種類型：種類型： 原原 子子 類類 型型：其值其值不可分解的類型；如：不可分解的類型；如：int 固定聚合類型固定聚合類型：其

7、值由確定數(shù)目的成分按某種結構組成；如：其值由確定數(shù)目的成分按某種結構組成；如： 復數(shù)；復數(shù)； 可變聚合類型可變聚合類型：其值由不固定數(shù)目的成分按某種結構組成；其值由不固定數(shù)目的成分按某種結構組成； 如：學生基本情況，有序整數(shù)序列；如：學生基本情況，有序整數(shù)序列； 多形數(shù)據(jù)類型多形數(shù)據(jù)類型：其值的成分不確定的數(shù)據(jù)類型；（元素之間其值的成分不確定的數(shù)據(jù)類型；（元素之間 的關系相同，基本操作也相同的關系相同，基本操作也相同 ） 11 2. 數(shù)據(jù)封裝：數(shù)據(jù)封裝：將實體的將實體的外部特性外部特性和其內(nèi)部和其內(nèi)部實現(xiàn)細節(jié)實現(xiàn)細節(jié) 分離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)。分離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細

8、節(jié)。 1. 數(shù)據(jù)抽象：數(shù)據(jù)抽象：用用ADT描述程序處理的實體時，強調(diào)描述程序處理的實體時，強調(diào) 的是其的是其本質的特征本質的特征、其所能完成的、其所能完成的功能功能以及它和外以及它和外 部用戶的部用戶的接口接口（即外界使用它的方法）。（即外界使用它的方法）。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的定義由一個的定義由一個值域值域和定義在該值域上和定義在該值域上 的一組的一組操作操作組成。組成。 12 抽象數(shù)據(jù)類型可用三元組表示抽象數(shù)據(jù)類型可用三元組表示: ADT =（D，S，P） 其中：其中：D 是是數(shù)據(jù)對象數(shù)據(jù)對象； S 是是 D 上的上的關系關系集；集； P 是是對對 D 的的基本操作基本操作集集。 1

9、3 數(shù)據(jù)結構是一個二元組是一個二元組 Data_Structures = (D, S) 其中其中: D 是是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是是 D上關系的有限集。上關系的有限集。 14 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義-D 數(shù)據(jù)關系：數(shù)據(jù)關系：數(shù)據(jù)關系的定義數(shù)據(jù)關系的定義-S 基本操作：基本操作：基本操作的定義基本操作的定義-P ADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 基本操作基本操作的定義格式為的定義格式為: 基本操作名基本操作名（參數(shù)表參數(shù)表） 初始條件初始條件：初始條件描述：初始條件描述 操作結果操作結果：操作結果描述操作結果描

10、述 其中，數(shù)據(jù)對象和數(shù)據(jù)關系的其中，數(shù)據(jù)對象和數(shù)據(jù)關系的 定義用定義用偽碼描述偽碼描述 15 1.1.參數(shù)表：參數(shù)表： 賦值參數(shù)賦值參數(shù): : 只為操作提供只為操作提供輸入值輸入值。 引用參數(shù)引用參數(shù): : 以以 sum.imagpart = z1.imagpart + z2.imagpart; 其它省略其它省略 23 1.3 算法和算法的衡量 一一. 算法算法 算法算法: :算法是對算法是對特定問題特定問題求解步驟求解步驟的一種描述的一種描述, , 是指是指 令的令的有限序列有限序列，其中每一條指令表示一個或多個操作。，其中每一條指令表示一個或多個操作。 一個算法必須滿足以下五個重要一個算法

11、必須滿足以下五個重要特性特性： 1有窮性有窮性 2確定性確定性 3可行性可行性 4有輸入有輸入 5有輸出有輸出 24 1 1有窮性有窮性: : 對于任意一組合法輸入值，在執(zhí)行對于任意一組合法輸入值，在執(zhí)行有窮有窮 步驟步驟之后一定能結束，且每一步驟都能在之后一定能結束，且每一步驟都能在有限時間有限時間 內(nèi)完成。內(nèi)完成。 2 2確定性確定性: : 對于對于每種情況每種情況下所應執(zhí)行的操作，在算下所應執(zhí)行的操作，在算 法中都有法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都的規(guī)定，使算法的執(zhí)行者或閱讀者都 能明確其含義及如何執(zhí)行。并且在任何條件下，算能明確其含義及如何執(zhí)行。并且在任何條件下，算 法

12、都只有一條執(zhí)行路徑。法都只有一條執(zhí)行路徑。 3 3可行性可行性: : 算法中描述的操作都是可以通過算法中描述的操作都是可以通過已經(jīng)實已經(jīng)實 現(xiàn)現(xiàn)的的基本運算基本運算執(zhí)行有限次來實現(xiàn)。執(zhí)行有限次來實現(xiàn)。 25 4 4有輸入：有輸入：零個或多個的輸入。零個或多個的輸入。作為算法加工對象作為算法加工對象 的量值，通常體現(xiàn)為算法中的一組變量。有些輸入的量值，通常體現(xiàn)為算法中的一組變量。有些輸入 量需要在算法執(zhí)行過程中輸入，而有的算法表面上量需要在算法執(zhí)行過程中輸入，而有的算法表面上 可以沒有輸入，實際上已被嵌入算法之中?？梢詻]有輸入，實際上已被嵌入算法之中。 5 5有輸出：有輸出：一個或多個的輸出。一

13、個或多個的輸出。它是一組與它是一組與“輸輸 入入”有確定關系的量值，是算法進行信息加工后得有確定關系的量值，是算法進行信息加工后得 到的結果，這種確定關系即為算法的功能。到的結果，這種確定關系即為算法的功能。 26 有窮性？有窮性？ 不是一個算法！不是一個算法！ 27 二二. 算法設計的原則算法設計的原則 設計算法時，通常應考慮達到以下目標：設計算法時，通常應考慮達到以下目標： 1正確性正確性 2. 可讀性可讀性 3健壯性健壯性 4高效率與低存儲量需求高效率與低存儲量需求 28 1 1正確性正確性 算法應當滿足以特定的算法應當滿足以特定的“規(guī)格說明規(guī)格說明”方式給出的方式給出的 需求需求。 對

14、算法是否對算法是否“正確正確”的理解可以有以下四個層次：的理解可以有以下四個層次： a程序中不含程序中不含語法錯誤語法錯誤； b程序對于程序對于幾組輸入數(shù)據(jù)幾組輸入數(shù)據(jù)能夠得出滿足要求的能夠得出滿足要求的 結果；結果； c程序對于程序對于精心選擇的、典型、苛刻且?guī)в械箅y精心選擇的、典型、苛刻且?guī)в械箅y 性的性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結果；幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； d程序對于程序對于一切合法的輸入數(shù)據(jù)一切合法的輸入數(shù)據(jù)都能得出滿足要都能得出滿足要 求的結果；求的結果； 通常以第通常以第 c 層意義的正確性作為衡量標準。層意義的正確性作為衡量標準。 29 2. 2. 可讀性可讀

15、性 算法主要是為了人的閱讀與交流，其次才是為計算算法主要是為了人的閱讀與交流，其次才是為計算 機執(zhí)行，因此算法應該機執(zhí)行，因此算法應該易于人的理解易于人的理解； 另一方面，難讀的程序易于另一方面，難讀的程序易于隱藏較多錯誤隱藏較多錯誤而難以調(diào)而難以調(diào) 試。試。 3 3健壯性健壯性 當輸入的當輸入的數(shù)據(jù)非法數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇从硶r，算法應當恰當?shù)刈鞒龇从?或進行相應處理，而不是產(chǎn)生或進行相應處理，而不是產(chǎn)生莫名奇妙的輸出結果莫名奇妙的輸出結果 處理出錯的方法不應是中斷程序的執(zhí)行，而應是處理出錯的方法不應是中斷程序的執(zhí)行，而應是 返回一個返回一個表示錯誤或錯誤性質的值表示錯誤或錯誤性質

16、的值，以便進行處理，以便進行處理 30 4 4高效率與低存儲量需求高效率與低存儲量需求 通常，效率指的是算法通常，效率指的是算法執(zhí)行時間執(zhí)行時間；存儲量指的是算；存儲量指的是算 法執(zhí)行過程中所需的法執(zhí)行過程中所需的最大存儲空間最大存儲空間，兩者都與問題，兩者都與問題 的規(guī)模有關。的規(guī)模有關。 31 算法與程序的區(qū)別算法與程序的區(qū)別 算法算法是解決問題的一種方法或一個過程，考慮是解決問題的一種方法或一個過程，考慮 如何將輸入轉換成輸出，一個問題可以有如何將輸入轉換成輸出，一個問題可以有多個多個 算法。算法。 程序程序是用某種程序設計語言對是用某種程序設計語言對算法的具體實現(xiàn)。算法的具體實現(xiàn)。 主

17、要區(qū)別：主要區(qū)別：有窮性、正確性和描述方法有窮性、正確性和描述方法 程序可以是程序可以是無窮無窮的，例如的，例如OS，算法是，算法是有窮有窮的；的； 程序可以是程序可以是錯誤錯誤的，而算法必須是的，而算法必須是正確正確的；的； 程序是用程序是用程序設計語言描述程序設計語言描述的，在機器上可以的，在機器上可以 執(zhí)行，算法還可以用執(zhí)行，算法還可以用自然語言、框圖、高級程自然語言、框圖、高級程 序語言序語言等方式描述。等方式描述。 32 三三. 算法效率的衡量方法和準則算法效率的衡量方法和準則 事后統(tǒng)計事后統(tǒng)計 缺點：缺點：1必須執(zhí)行程序必須執(zhí)行程序 2其它因素掩蓋算法本質其它因素掩蓋算法本質 33

18、 和算法執(zhí)行時間相關的和算法執(zhí)行時間相關的因素因素： 算法選用的策略算法選用的策略 問題的規(guī)模問題的規(guī)模 編寫程序的語言編寫程序的語言 編譯程序產(chǎn)生的機器代碼的質量編譯程序產(chǎn)生的機器代碼的質量 計算機執(zhí)行指令的速度計算機執(zhí)行指令的速度 事前分析事前分析 34 35 36 37 算法算法 = 控制結構控制結構 + 原操作原操作（固有數(shù)據(jù)類型的操作）（固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時間算法的執(zhí)行時間 = （原操作（原操作(i)的的執(zhí)行次數(shù)執(zhí)行次數(shù)原操作原操作(i)的的執(zhí)行時間執(zhí)行時間） 算法的執(zhí)行時間算法的執(zhí)行時間 與與 原操作執(zhí)行次數(shù)原操作執(zhí)行次數(shù)之和之和 成正比成正比 通常，從算法中選取通常

19、，從算法中選取一種一種對于所研究的問題來說對于所研究的問題來說 是是 基本操作基本操作 的原操作，以該的原操作，以該基本操作基本操作 在算法中重在算法中重 復執(zhí)行的次數(shù)復執(zhí)行的次數(shù) 作為算法運行時間的作為算法運行時間的衡量準則衡量準則。 38 例:求下列程序段各語句的頻度頻度。 (1)for(i=1; i=n;i(1)for(i=1; i=n;i+) n+1+) n+1 x+; n x+; n (2) (2) for(j=1;j=n;jfor(j=1;j=n;j+) n+) n+1+1 for(k=1;k=n;k for(k=1;k=n;k+) n+) n* *(n(n+1+1) ) x+;

20、n x+; n* *n n 39 (1) i=1; k=0; while (i=n-1) k+=10*i; i+; 語句頻度語句頻度T(n) i=1; k=0; do k+=10*i; i+; while (i=n-1) (2) 語句頻度語句頻度T(n) =n-1 =n-1 40 (3) k=0; for(i=1;i=n;i+) for(j=i;j=n;j+) k+; i=1時；時；j循環(huán)循環(huán)n次次 i=2時；時；j循環(huán)循環(huán)n-1次次 i=n時；時；j循環(huán)循環(huán)1次次 語句頻度語句頻度T(n) =n+(n-1)+1 =(n-1+1)*(n+1)/2 41 【例】兩個【例】兩個NN矩陣相乘矩陣相乘

21、 void mult(int a, int b, int i=n; +i) / n+1 for (j=1; j=n; +j) /n*(n+1) ci,j = 0; /n*n for (k=1; k1 - -i) /n-1次次 change = FALSE; / change 為元素進行交換標志為元素進行交換標志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / (n-2)*i / 一趟起泡一趟起泡 / bubble_sort 基本操作基本操作:比較操作比較操作 時間復雜度時間復雜度: O(n2) 43 1i 0j 1 1n 2 )n(T i 1n 2 )1.111( i 1n 2 )101i ( i 1n 2 i i