1、1算法與數據結構算法與數據結構主主 講：講： 高高 慧慧電電 話：話： 1360645719413606457194E_mailE_mail： 2課程的重要性課程的重要性 數據結構是介于數學、計算機硬件和計算機軟件數據結構是介于數學、計算機硬件和計算機軟件之間的一門計算機科學與技術專業的核心課程，之間的一門計算機科學與技術專業的核心課程，是編譯原理、操作系統、數據庫、人工智能等課是編譯原理、操作系統、數據庫、人工智能等課程的基礎；程的基礎； 數據結構技術也廣泛應用于信息科學、系統工程、數據結構技術也廣泛應用于信息科學、系統工程、應用數學以及各種工程技術領域；應用數學以及各種工程技術領域； 計算

2、機程序設計的重要理論基礎計算機程序設計的重要理論基礎 程序程序 = = 算法算法 + + 數據結構數據結構為計算機處理為計算機處理問題編制的一問題編制的一組指令集組指令集處理問題的策略處理問題的策略問題的數學模型問題的數學模型計算機科學與技術專業綜合考試內容計算機科學與技術專業綜合考試內容34C語言語言 數據結構數據結構 軟件工程軟件工程掌握基本掌握基本編程方法編程方法掌握數據組掌握數據組織和數據處織和數據處理的方法理的方法掌握大型軟掌握大型軟件開發方法件開發方法學習識字學習識字學習寫作文學習寫作文學習寫小說學習寫小說與語文學習過程類似動手能力（上機）動手能力（上機）與相關課程的關系與相關課程

3、的關系5課程目的課程目的 能夠分析研究計算機加工的對象的特性，獲得能夠分析研究計算機加工的對象的特性，獲得其其邏輯結構邏輯結構，根據需求，選擇合適的，根據需求，選擇合適的存儲結構存儲結構及其相應的及其相應的算法算法 學習并掌握一些常用的算法學習并掌握一些常用的算法 復雜程序設計的訓練過程，要求編寫的程序結復雜程序設計的訓練過程，要求編寫的程序結構清楚和正確易讀構清楚和正確易讀 初步掌握初步掌握算法的時間分析和空間分析的技術算法的時間分析和空間分析的技術6基本設想基本設想 學時：學時： 8080學時，理論學時，理論6464 + + 上機上機1616； 基本要求：基本要求： 上課認真聽講；上課認真

4、聽講； 課下閱讀教材，課下閱讀教材，認真、獨立認真、獨立完成書面作業；完成書面作業； 多寫算法，多練習多寫算法，多練習，重視上機實踐；，重視上機實踐； 考試：考試： 平時成績平時成績30% + 30% + 卷面成績卷面成績70%70%； 平時成績包括考勤、作業、平時成績包括考勤、作業、隨堂測驗隨堂測驗和上機；和上機； 理論和上機課共缺席理論和上機課共缺席3 3次及以上者次及以上者取消考試資格；取消考試資格；7教教 材材 必修書必修書: : 數據結構教程數據結構教程( (第第4 4版版) ) 李春葆等李春葆等 清華大學出版社清華大學出版社 數據結構教程數據結構教程( (第第4 4版版) )上機實

5、驗指導上機實驗指導 李春葆等李春葆等 清華大學清華大學出版社出版社 參考書參考書: : 數據結構教程數據結構教程( (第第4 4版版) )學習指導學習指導 李春葆等李春葆等 清華大學出版清華大學出版社社 數據結構（數據結構（C C語言版）語言版）( (嚴蔚敏嚴蔚敏) ) 清華大學出版社清華大學出版社 算法與數據結構（陳守孔）機械工業出版社算法與數據結構（陳守孔）機械工業出版社 C C程序設計程序設計( (譚浩強譚浩強) ) 清華大學出版社清華大學出版社-上機必備上機必備 網絡資源：網絡資源： 煙臺大學計算機學院精品課程煙臺大學計算機學院精品課程 等等8課時設置課時設置 第第1 1章章 緒論緒論

6、 5 5學時學時第第2 2章章 線性表線性表 1010學時學時第第3 3章章 棧和隊列棧和隊列 6 6學時學時第第4 4章章 串串 4 4學時學時第第5 5章章 遞歸遞歸 2 2學時學時第第6 6章章 數組和廣義表數組和廣義表 4 4學時學時第第7 7章章 樹和二叉樹樹和二叉樹 1010學時學時第第8 8章章 圖圖 9 9學時學時第第9 9章章 查找查找 7 7學時學時第第1010章章 內排序內排序 7 7學時學時第第1111章章 外排序外排序 不不 講講第第1 12 2章章 文件文件 不不 講講第第1 13 3章章 采用面向對象的方法描述算法采用面向對象的方法描述算法 不不 講講9第第1章章

7、 緒論緒論 1.1 什么是數據結構什么是數據結構 1.2 算法及其描述算法及其描述 1.3 算法分析算法分析 1.4 數據結構算法程序數據結構算法程序（略）（略）101.1 什么是數據結構什么是數據結構 1.1.1 數據結構的定義數據結構的定義 1.1.2 邏輯結構類型邏輯結構類型 1.1.3 存儲結構類型存儲結構類型 1.1.4 數據結構和數據類型數據結構和數據類型11 1.1.1 數據結構的定義數據結構的定義 三個層次三個層次的概念：數據、數據元素、數據項的概念：數據、數據元素、數據項 數據：數據：是所有能被輸入到計算機中，且能被計算是所有能被輸入到計算機中，且能被計算機處理的符號的集合。

8、機處理的符號的集合。 數據元素：數據元素：是數據是數據(集合集合)中的一個中的一個“個體個體”，是數，是數據的據的基本單位基本單位。不同的條件下可稱為元素、結點、。不同的條件下可稱為元素、結點、頂點、記錄等，通常作為一個整體考慮和處理。頂點、記錄等，通常作為一個整體考慮和處理。 數據項：數據項：組成數據元素的有特定意義的組成數據元素的有特定意義的最小單位最小單位，不可分割。不可分割。 數據對象：數據對象：是具有是具有相同性質相同性質的若干個數據元素的的若干個數據元素的集合。集合。12例例1.1 有一個學生表如下所示，這個表中的數據元有一個學生表如下所示，這個表中的數據元素是學生記錄素是學生記錄

9、,每個數據元素由四個數據項每個數據元素由四個數據項(即學號、即學號、姓名、性別和班號姓名、性別和班號)組成。組成。學號學號姓名姓名性別性別班號班號1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強董強男男99025王萍王萍女女9901表表1.1 學生表學生表 數據元素數據元素數據項數據項13例例1.1 學生檔案管理系統學生檔案管理系統 計算機處理的對象：計算機處理的對象：表表 元素間的關系：元素間的關系：一對一對一的線性關系一的線性關系 施加于對象上的操作：施加于對象上的操作：查詢、插入、刪除等查詢、插入、刪除等 u數學

10、模型：數學模型：各種表格各種表格u數據結構：數據結構：線性結構線性結構u算法：算法：如何進行各種如何進行各種查詢查詢14其他例其他例 人人-機博奕機博奕.格局格局15人人-機博奕機博奕 計算機處理的對象：計算機處理的對象：格局樹格局樹 元素間的關系：元素間的關系：一一對多的層次關系對多的層次關系 施加于對象上的操施加于對象上的操作：查詢、插入、作：查詢、插入、刪除等刪除等 u數學模型：數學模型：棋盤棋盤u數據結構：數據結構：樹形結構樹形結構u算法：算法：博弈的規則和博弈的規則和策略策略16其他例其他例 快速送達疫苗快速送達疫苗 已知有鄰近的五個村子發生了疫情，我們要已知有鄰近的五個村子發生了疫

11、情，我們要用汽車快速地將疫苗送達到用汽車快速地將疫苗送達到5個村子。目標是個村子。目標是尋找一條消耗時間最少的路線。尋找一條消耗時間最少的路線。 勝利勝利 發生疫情的五個村子發生疫情的五個村子河源河源長利長利太華太華樺南樺南1275344123 村子聯系網絡村子聯系網絡v1v5v2v4v31275413432抽象抽象 17快速送達疫苗快速送達疫苗 計算機處理的對象：計算機處理的對象：圖圖 元素間的關系：元素間的關系：多多對多的網狀關系對多的網狀關系 施加于對象上的操施加于對象上的操作：查詢、插入、作：查詢、插入、刪除等刪除等 u數學模型：數學模型：圖圖u數據結構：數據結構：圖形結構圖形結構u算

12、法：算法：如何求距離、如何求距離、最短路徑等最短路徑等18結結 論論 數據結構數據結構是一門研究是一門研究非數值計算非數值計算的程序的程序設計問題中計算機的設計問題中計算機的操作對象操作對象以及它們以及它們之間的之間的關系關系和和操作操作的學科。的學科。 三要素：三要素：對象、關系及操作對象、關系及操作 學習數據結構的目的之一是，將實際問學習數據結構的目的之一是，將實際問題中涉及的處理對象在計算機中表示出題中涉及的處理對象在計算機中表示出來并對它們進行處理。來并對它們進行處理。19數據結構的定義數據結構的定義（P2） 數據以及數據元素相互之間的聯系數據以及數據元素相互之間的聯系 相互之間存在著

13、某種特定關系的數據相互之間存在著某種特定關系的數據元素的集合元素的集合 帶結構的數據元素的集合帶結構的數據元素的集合20數據結構（邏輯結構）的描述或表示數據結構（邏輯結構）的描述或表示 為了更確切地描述一種數據結構，通常采用為了更確切地描述一種數據結構，通常采用二元組表示：二元組表示： B=(D,R) 其中，其中，B是一種數據結構，它由數據元素的是一種數據結構，它由數據元素的集合集合D和和D上二元關系的集合上二元關系的集合R所組成。所組成。 D=di| 1in,n0 R=rj| 1jm,m0 21 D上的一個關系上的一個關系r是是序偶的集合序偶的集合； 對于對于r中的任一序偶中的任一序偶(x,

14、yD),我們稱序偶的我們稱序偶的第一結點為第二結點的第一結點為第二結點的直接前驅直接前驅結點結點(簡稱前驅結簡稱前驅結點點),稱第二結點為第一結點的稱第二結點為第一結點的直接后繼直接后繼結點結點(簡稱簡稱后繼結點后繼結點)。 若某個結點沒有前驅若某個結點沒有前驅,則稱該結點為則稱該結點為開始結點開始結點；若；若某個結點沒有后繼某個結點沒有后繼,則稱該結點為則稱該結點為終端結點終端結點；除此；除此之外的結點稱為之外的結點稱為內部結點內部結點。 說明：說明：表示有向關系，表示有向關系，(x,y)表示無向關系。表示無向關系。邏輯關系的表示邏輯關系的表示22 表表1.11.1中的記錄順序反映了數據元素

15、之間的邏輯關系中的記錄順序反映了數據元素之間的邏輯關系, , 用學號標識每個學生記錄用學號標識每個學生記錄, ,這種邏輯關系可以表示為：這種邏輯關系可以表示為： ,學號學號姓名姓名性別性別班號班號1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強董強男男99025王萍王萍女女9901舉例：邏輯關系的表示舉例：邏輯關系的表示P3忽略不看忽略不看23【例】【例】用二元組表示例用二元組表示例1.1的學生表，表中共的學生表，表中共有有7個結點，依次用個結點，依次用k1k7表示，則對應的表示，則對應的二元組表示為二元組表示為 B=

16、(D,R) 其中：其中： D=k1, k2, k3, k4, k5, k6, k7 R=r r=, , , , , 24 還還可以可以利用圖形形象地表示邏輯結構利用圖形形象地表示邏輯結構 例如，例如，“學生表學生表”數據結構用下圖的圖形表示數據結構用下圖的圖形表示 k1 k2 k3 k4 k5 k6 k7 251.1.2 邏輯結構類型邏輯結構類型 (1) 線性結構線性結構【例【例1.3】 結點之間關系：結點之間關系：一對一一對一 特點：特點： 開始結點和終端結點都是唯一的；開始結點和終端結點都是唯一的； 除了開始結點和終端結點以外，其余結點都有且除了開始結點和終端結點以外，其余結點都有且僅有一

17、個前驅結點，有且僅有一個后繼結點。僅有一個前驅結點，有且僅有一個后繼結點。26 結點之間關系：結點之間關系：一對多一對多 特點：特點： 開始結點開始結點唯一，唯一，終端結點不終端結點不唯一；唯一； 除終端結點以外除終端結點以外，每個結點有一個或多個后每個結點有一個或多個后繼繼結點；除開始結點外，每個結點有且僅有結點；除開始結點外，每個結點有且僅有一個前驅結點。一個前驅結點。 (2) 樹形結構樹形結構【例【例1.4】27 結點之間關系：結點之間關系：多對多多對多 特點：特點： 沒有開始結點和終端結點沒有開始結點和終端結點； 所有結點都可能有多個前驅結點和多個后繼結點。所有結點都可能有多個前驅結點

18、和多個后繼結點。 (3) 圖形結構圖形結構【例【例1.5】28集合結構：集合結構： 線性結構：線性結構：樹形結構：樹形結構： 圖形結構：圖形結構：291.1.3 存儲結構類型存儲結構類型 (1) 順序存儲結構順序存儲結構 (2) 鏈式存儲結構鏈式存儲結構 (3) 索引存儲結構索引存儲結構 (4) 散列存儲結構散列存儲結構 存儲結構存儲結構(即物理結構即物理結構)： 是數據結構在計算機中的表示。是數據結構在計算機中的表示。30 存儲結構存儲結構(物理結構物理結構)：數據結構在計算機中的表示。數據結構在計算機中的表示。順序存儲結構：順序存儲結構：借助元素在存儲器中的相對位置表示數據借助元素在存儲器

19、中的相對位置表示數據元素之間的關系（邏輯相鄰，物理位置也相鄰）元素之間的關系（邏輯相鄰，物理位置也相鄰）鏈式存儲結構：鏈式存儲結構：借助指示元素存儲地址的指針（借助指示元素存儲地址的指針（Pointer）表示數據元素之間的邏輯關系（邏輯相鄰，物理位置不一表示數據元素之間的邏輯關系（邏輯相鄰，物理位置不一定相鄰）定相鄰）【例例】 a1,a2, ana1an1000a2a310021004a1a3a4a2300020001000311.1.4 數據類型和數據結構數據類型和數據結構 (1) 數據類型數據類型 一個一個值的集合值的集合和定義在此集合上的和定義在此集合上的一組操作一組操作的總稱的總稱 規

20、定了在程序執行期間變量或表達式規定了在程序執行期間變量或表達式所有可能取所有可能取值的范圍值的范圍以及在這些值上以及在這些值上允許進行的操作允許進行的操作。 如：如：int整型數據類型整型數據類型所有整數的集合所有整數的集合(在在16位計算機中為位計算機中為3276832767的全的全體整數體整數)和相關的整數運算和相關的整數運算(如、等如、等)。 引入數據類型的目的：引入數據類型的目的：使用與實現分離使用與實現分離 數據類型是已經實現的數據結構數據類型是已經實現的數據結構（P8）32數據對象數據對象D上的上的關系集關系集對對D的基本的基本操作集操作集 (2) 抽象數據類型抽象數據類型 抽象數

21、據類型抽象數據類型(Abstract Data Type簡寫為簡寫為ADT) 用戶進行軟件系統設計時從問題的數學模型中抽用戶進行軟件系統設計時從問題的數學模型中抽象出來的象出來的邏輯數據結構和邏輯數據結構上的運算邏輯數據結構和邏輯數據結構上的運算,而而不考慮不考慮計算機的具體存儲結構和運算的具體實計算機的具體存儲結構和運算的具體實現算法。現算法。 一個數學模型以及定義在該模型上的一組操作一個數學模型以及定義在該模型上的一組操作 抽象數據類型的三元組表示：（抽象數據類型的三元組表示：（D，R，P）33ADT Complex 數據對象：數據對象： D=e1,e2|e1,e2均為實數均為實數數據關系

22、：數據關系： R=| e1是復數的實數部分，是復數的實數部分，e2 是復數的虛數部分是復數的虛數部分 e1e2i例如，抽象數據類型例如，抽象數據類型復數復數的定義：的定義：34基本運算：基本運算： AssignComplex(&Z,v1,v2):構造復數構造復數Z。 DestroyComplex(&Z):復數復數Z被銷毀。被銷毀。 GetReal(Z,&real):返回復數返回復數Z的實部值。的實部值。 GetImag(Z,&Imag):返回復數返回復數Z的虛部值。的虛部值。 Add(z1,z2,&sum):返回兩個復數返回兩個復數z1,z2的和。的和。

23、 ADT Complex351.2 算法及其描述算法及其描述 1.2.1 什么是算法什么是算法 1.2.2 算法描述算法描述361.2.1 什么是算法什么是算法 算法算法 對特定問題求解步驟的一種描述，是指令的有限序列。對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。其中每一條指令表示一個或多個操作。 算法的五個重要的特性算法的五個重要的特性 (1) 有窮性有窮性：在有窮步之后結束：在有窮步之后結束 (2) 確定性確定性：無二義性：無二義性 (3) 可行性可行性：算法中描述的操作都可以通過已經實現的算法中描述的操作都可以通過已經實現的基本操作執行有限次來實現基

24、本操作執行有限次來實現 (4) 有輸入：有輸入：零個或多個零個或多個 (5) 有輸出：有輸出：一個或多個一個或多個37算法與程序的區別算法與程序的區別 程序不一定滿足有窮性程序不一定滿足有窮性。如操作系統，只要整個系。如操作系統，只要整個系統不遭破壞，它將永遠不會停止。因此，操作系統統不遭破壞，它將永遠不會停止。因此，操作系統不是一個算法。不是一個算法。 程序是用機器可執行的語言書寫的程序是用機器可執行的語言書寫的，程序中的指令，程序中的指令必須是機器可執行的，而算法中的指令則無此限制。必須是機器可執行的，而算法中的指令則無此限制。 算法代表了對問題的解，而算法代表了對問題的解，而程序則是算法

25、在計算機程序則是算法在計算機上的特定的實現上的特定的實現。一個算法若用程序設計語言來描。一個算法若用程序設計語言來描述，則它就是一個程序。述，則它就是一個程序。38(1) 描述一描述一void exam1() n2; while (n%20) nn+2; printf(%dn,n); (2) 描述二描述二void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 以下兩段描述均不能滿足算法的特征以下兩段描述均不能滿足算法的特征,試問它們違反了哪些特征？試問它們違反了哪些特征？ 解：解：(1)算法是一個算法是一個死循環死循環，違反了算法的，違反了算法的有窮性有窮

26、性特征。特征。 (2)算法包含算法包含除零錯誤除零錯誤，違反了算法的，違反了算法的可行性可行性特征。特征。39 1.2.2 算法描述算法描述 算法可用文字描述（算法可用文字描述（P11P11例例1.71.7），也可用語言、圖），也可用語言、圖形和表格等形和表格等 本書中采用本書中采用C/C+C/C+語言語言描述算法描述算法 C+C+語言中提供了一種引用運算符語言中提供了一種引用運算符“& &”（P9P9） 引用是個引用是個別名別名, ,當建立引用時當建立引用時, ,程序用另一個已定義程序用另一個已定義的變量或對象的變量或對象( (目標目標) )的名字的名字初始化初始化它它, ,

27、從那時起從那時起, ,引用引用作為目標的別名而使用作為目標的別名而使用, ,對引用的改動實際就是對目對引用的改動實際就是對目標的改動標的改動 例如：例如：int &b=a; /*b是是a的引用變量的引用變量*/40 引用引用常用于函數形參中，采用引用型形參時，在常用于函數形參中，采用引用型形參時，在函數調用結束時函數調用結束時將形參的改變回傳給實參。將形參的改變回傳給實參。 【例】例】有如下函數有如下函數(其中的形參均為其中的形參均為引用型形參引用型形參) void swap(int &x, int &y) /*形參前的形參前的“&”符號不是取地址運算符符號不是

28、取地址運算符*/ int tmp=x; x=y; y=tmp; 當用執行語句當用執行語句swap(a,b)時，時，a和和b的值發生了交換。的值發生了交換。41 void swap1(int x,int y) int tmp; tmp=x; x=y; y=tmp; 注意：注意：a a和和b b的值不會發生交換。的值不會發生交換。形參形參實參實參 10 10a x形參形參實參實參編寫一個函數編寫一個函數swap1(x,y)，當執行語句，當執行語句swap1(a,b)時時,交換交換a和和b的值。的值。值傳遞值傳遞42 為此，為此，采用指針的方式來回傳形參的值采用指針的方式來回傳形參的值。 將上述函數

29、改為：將上述函數改為： void swap2(int *x,int *y) int tmp; tmp=*x;/*將將x的值放在的值放在tmp中中*/ *x=*y; /*將將x所指的值改為所指的值改為*y*/ *y=tmp； /*將將y所指的值改為所指的值改為tmp*/ 上述函數的調用改為上述函數的調用改為swap2(&a,&b)，顯然，顯然遠不如采用引用方式簡潔。遠不如采用引用方式簡潔。 所以本書后面很多算法都采用引用形參。所以本書后面很多算法都采用引用形參。 10&a x形參形參實參實參地址傳遞地址傳遞431.3 算法分析算法分析 1.3.2 算法效率分析算法效率分析

30、 1.3.3 算法存儲空間分析算法存儲空間分析 1.3.1 算法設計的目標算法設計的目標 441.3.1 算法設計的目標算法設計的目標 正確性正確性：CorrectnessCorrectness 可使用性可使用性：用戶友好性：用戶友好性 可讀性可讀性: Readability: Readability 健壯性健壯性: Robustness: Robustness 高效率與低存儲量需求高效率與低存儲量需求 時間復雜度時間復雜度 空間復雜度空間復雜度45 用高級語言編寫的程序，運行的時間主要用高級語言編寫的程序，運行的時間主要取決于如下因素：取決于如下因素： 硬件的速度；硬件的速度； 編寫程序的語

31、言：級別越高，效率越低；編寫程序的語言：級別越高，效率越低； 編譯程序所產生的目標代碼的質量；編譯程序所產生的目標代碼的質量； 算法選用的策略；算法選用的策略； 問題的規模；問題的規模；前三條與算前三條與算法設計無關法設計無關w排除其他影響算法效率的因素，認為一個算法的排除其他影響算法效率的因素，認為一個算法的運行代價只依賴于運行代價只依賴于問題的規模，問題的規模，或者說它是或者說它是問題問題規模的函數規模的函數w這種函數被稱為算法的這種函數被稱為算法的時間復雜度時間復雜度和和空間復雜度。空間復雜度。 衡量算法時間效率的方法主要有兩大類：衡量算法時間效率的方法主要有兩大類： 事后統計：利用計算

32、機的時鐘；事后統計：利用計算機的時鐘； 事前分析估算事前分析估算1.3.2 算法效率分析算法效率分析 46 一個算法是由一個算法是由控制結構控制結構( (順序、分支和循環三種順序、分支和循環三種) )和和原操作原操作構成的，則算法時間取決于兩者的綜合效果。構成的，則算法時間取決于兩者的綜合效果。 原操作：原操作：對于所研究的問題來說是對于所研究的問題來說是基本運算基本運算的操作。的操作。 被視為算法被視為算法基本運算基本運算的一般是的一般是最深層最深層循環內的語句。循環內的語句。 通常把算法中包含基本運算次數的多少稱為通常把算法中包含基本運算次數的多少稱為算法的算法的時間復雜度，記作時間復雜度

33、，記作T(n)T(n)。 算法中算法中基本運算次數基本運算次數T(n)T(n)是問題規模是問題規模n n的某個函數的某個函數f(n),f(n),記作：記作： T(n)=O(f(n)T(n)=O(f(n)大大O表示法：表示隨問題規模表示法：表示隨問題規模n的增大，算法執行時間的增長率的增大，算法執行時間的增長率 和和f(n)的增長率相同。的增長率相同。1.3.2 算法效率分析算法效率分析 47 大大O表示法：表示法：只求出只求出T(n)的的最高階，忽略其低階項和常系數最高階，忽略其低階項和常系數這樣既可簡化這樣既可簡化T(n)的計算，又能比較客觀地反映出的計算，又能比較客觀地反映出當當n很大時，

34、算法的時間性能。很大時，算法的時間性能。 例如，例如，T(n)=3n2-5n+10000=O(n2)48+x; s=0;時間復雜度時間復雜度 for(j=1;j=n;+j)+x; s+=x;語句的頻度為語句的頻度為1，時間復雜度為，時間復雜度為O(1)。語句的頻度為語句的頻度為n，時間復雜度為，時間復雜度為O(n)。常數階常數階線性階線性階49時間復雜度時間復雜度 for(j=1;j=n;+j)for(k=1;k=n;+k)+x; s+=x;語句頻度語句頻度為為n n，時間復雜度為，時間復雜度為O(n2)k=0;for(i=1;i=n;i+)for(j=1;j=i;j+)aij=+k;語句頻度

35、為：語句頻度為： n*(n+1)/2，時間復雜度為時間復雜度為O(n2)平方階平方階50時間復雜度時間復雜度for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;語句頻度為：語句頻度為：時間復雜度為時間復雜度為O(nlog2n)nnnnjnjnk2log1 log11log22 線性對數階線性對數階51時間復雜度時間復雜度例：矩陣乘法例：矩陣乘法 for( i = 1; i = n; i+) /(n+1) for( j = 1; j = n; j+) /n(n+1) cij = 0； /n2 for( k= 1; k= n; k+) / n2(n+1) cij = cij+ai

36、k* bkj; / n3 說明：各語句行后的數字是該語句重復執行的次數說明：各語句行后的數字是該語句重復執行的次數; 本算法時間復雜度為本算法時間復雜度為O( n3)立方階立方階52 各種不同數量級對應的值存在著如下關系：各種不同數量級對應的值存在著如下關系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)53 例例1.8 求兩個求兩個n階方陣的相加階方陣的相加C=A+B的算法如下的算法如下,分析其時間復雜度。分析其時間復雜度。 #define MAX 20 /*定義最大的方階定義最大的方階*/ void matrixadd(int n,int A

37、MAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)for (j=0;jn;j+) Cij=Aij+Bij; 54 該算法中的基本運算是兩重循環中最深層的語句該算法中的基本運算是兩重循環中最深層的語句Cij=Aij+Bij，分析它的頻度，即，分析它的頻度，即： T(n)= =O(n2) 102101010*11ninininjnnnnn55時間復雜度時間復雜度 有的情況下，算法中基本操作重復執行的次數還有的情況下，算法中基本操作重復執行的次數還隨隨問題的輸入數據集問題的輸入數據集不同而不同。不同而不同。 【例例1.9】 在這種情況下

38、，可用在這種情況下，可用最壞最壞情況下的時間復雜度作情況下的時間復雜度作為時間復雜度為時間復雜度 有時，也可計算平均情況下的時間復雜度（有時，也可計算平均情況下的時間復雜度（P16定義定義1.1）在輸入在輸入I 下執行的基下執行的基本運算的次數本運算的次數任一輸入任一輸入I出出現的概率現的概率I DnP(I)*T(I)E(n)56 （略）（略）例例1.10 有如下遞歸算法：有如下遞歸算法： void fun(int a,int n,int k) /*數組數組a共有共有n個元素個元素*/ int i;if (k=n-1) for (i=0;in;i+) printf(%dn,ai);else f

39、or (i=k;in;i+)ai=ai+i*i; fun(a,n,k+1); 調用上述算法的語句為調用上述算法的語句為fun(a,n,0)，求其時間復雜度。，求其時間復雜度。 57 解：設解：設fun(a,n,0)的時間復雜度為的時間復雜度為T(n),則則fun(a,n,k)的執行時間為的執行時間為T1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 當當k=n-1時時 T1(n,k)= (n-k)+T1(n,k+1) 其他情況其他情況 則則 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)

40、+ +2+n=O(n2) 所以調用所以調用fun(a,n,0)的時間復雜度為的時間復雜度為O(n2)。 58 算法的存儲量包括：算法的存儲量包括：輸入數據所占空間、程序本身輸入數據所占空間、程序本身所占空間和所占空間和輔助變量所占空間。輔助變量所占空間。 空間復雜度是對一個算法在運行過程中空間復雜度是對一個算法在運行過程中臨時占用的臨時占用的存儲空間存儲空間大小的量度，一般也作為問題規模大小的量度，一般也作為問題規模n的函數，的函數，以數量級形式給出，記作：以數量級形式給出，記作： S(n) = O(g(n) 若所需額外空間相對于輸入數據量來說是常數，則若所需額外空間相對于輸入數據量來說是常數

41、，則稱此算法為稱此算法為原地工作。原地工作。 若所需存儲量依賴于特定的輸入，則通常按若所需存儲量依賴于特定的輸入，則通常按最壞情最壞情況況考慮。考慮。1.3.3 算法存儲空間分析算法存儲空間分析 59 （略）（略） 例例1.10 有如下遞歸算法：有如下遞歸算法： void fun(int a,int n,int k) /*數組數組a共有共有n個元素個元素*/ int i;if (k=n-1) for (i=0;in;i+) printf(%dn,ai);else for (i=k;in;i+)ai=ai+i*i; fun(a,n,k+1); 調用上述算法的語句為調用上述算法的語句為fun(a,

42、n,0)，求其空間復雜度。，求其空間復雜度。 60 解：設解：設fun(a,n,k)的臨時空間大小為的臨時空間大小為S(k)，其中定義，其中定義了一個輔助變量了一個輔助變量i，所以，所以 S(k)=1 當當k=n-1時時 S(k)= 1+S(k+1) 其他情況其他情況 則則fun(a,n,0)的空間復雜度為的空間復雜度為S(0)，由此可得：，由此可得： S(0)=1+S(1)=1+1+S(2)=1+1+1+S(n-1)=1+1+ +1+1=O(n) 所以調用所以調用fun(a,n,0)的空間復雜度為的空間復雜度為O(n)。 611.4 數據結構算法程序數據結構算法程序（略）（略） 數據結構對算

43、法的影響主要在兩方面數據結構對算法的影響主要在兩方面 （1 1）數據結構的存儲能力）數據結構的存儲能力數據結構存儲能力強、存儲信息多算法將會較數據結構存儲能力強、存儲信息多算法將會較好設計（時間少），存儲空間大。好設計（時間少），存儲空間大。時間和空間的平衡時間和空間的平衡（2 2）定義在數據結構上的操作）定義在數據結構上的操作在數據結構上定義基本操作算法調用這些基本在數據結構上定義基本操作算法調用這些基本操作。操作。62基本操作越完整，基本操作越完整，算法設計就越容易算法設計就越容易算法算法基本操作基本操作基本算法基本算法應用程序應用程序應用程序是通過調應用程序是通過調用基本算法實現的用基本

44、算法實現的63選擇數據結構需要考慮的幾個方面：選擇數據結構需要考慮的幾個方面：（1）數據結構要適應問題的狀態描述）數據結構要適應問題的狀態描述（2）數據結構應與所選擇的算法相適應）數據結構應與所選擇的算法相適應（3）數據結構的選擇同時要兼顧程序設計的方便）數據結構的選擇同時要兼顧程序設計的方便（4）靈活應用已有知識）靈活應用已有知識64例如，有若干學生數據（學生數小于例如，有若干學生數據（學生數小于50），每），每個學生數據包含學號（每個學生學號是惟一的，個學生數據包含學號（每個學生學號是惟一的，但學生記錄不一定按學號順序存放）、姓名、班但學生記錄不一定按學號順序存放）、姓名、班號和若干門課程

45、成績（每個學生所選課程數目可號和若干門課程成績（每個學生所選課程數目可能不等，但最多不超過能不等，但最多不超過6門）。門）。要求設計一個程序輸出每個學生的學號、姓名要求設計一個程序輸出每個學生的學號、姓名和平均分以及每門課程（課程編號從和平均分以及每門課程（課程編號從16）的平）的平均分。均分。65設計方案設計方案1 1：將學生的全部數據項放在一個表中，將學生的全部數據項放在一個表中，一個學生的全部數據對應一條記錄。由于課程最多可一個學生的全部數據對應一條記錄。由于課程最多可選選6 6門，對應的成績項也應有門，對應的成績項也應有6 6個。對應的數據結構如個。對應的數據結構如下：下：struct stud int no;/*學號學號*/char name10;/*姓名姓名*/int bno;/*班號班號*/int deg1;/*課程課程1分數分數*/int deg2;/*課程課程2分數分數*/int deg3;/*課程課程3分數分數*/int deg4;/*課程課程4分數分數*/int deg5;/*課程課程5分數