第1章數(shù)據(jù)結(jié)構(gòu)緒論

1、1算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)主主 講：講： 高高 慧慧電電 話：話： 1360645719413606457194E_mailE_mail： 2課程的重要性課程的重要性 數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件和計算機軟件數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件和計算機軟件之間的一門計算機科學(xué)與技術(shù)專業(yè)的核心課程，之間的一門計算機科學(xué)與技術(shù)專業(yè)的核心課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課程的基礎(chǔ)；程的基礎(chǔ)； 數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域；應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域； 計算

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

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

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

5、驗指導(dǎo)上機實驗指導(dǎo) 李春葆等李春葆等 清華大學(xué)清華大學(xué)出版社出版社 參考書參考書: : 數(shù)據(jù)結(jié)構(gòu)教程數(shù)據(jù)結(jié)構(gòu)教程( (第第4 4版版) )學(xué)習(xí)指導(dǎo)學(xué)習(xí)指導(dǎo) 李春葆等李春葆等 清華大學(xué)出版清華大學(xué)出版社社 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C C語言版）語言版）( (嚴(yán)蔚敏嚴(yán)蔚敏) ) 清華大學(xué)出版社清華大學(xué)出版社 算法與數(shù)據(jù)結(jié)構(gòu)（陳守孔）機械工業(yè)出版社算法與數(shù)據(jù)結(jié)構(gòu)（陳守孔）機械工業(yè)出版社 C C程序設(shè)計程序設(shè)計( (譚浩強譚浩強) ) 清華大學(xué)出版社清華大學(xué)出版社-上機必備上機必備 網(wǎng)絡(luò)資源：網(wǎng)絡(luò)資源： 煙臺大學(xué)計算機學(xué)院精品課程煙臺大學(xué)計算機學(xué)院精品課程 等等8課時設(shè)置課時設(shè)置 第第1 1章章 緒論緒論

6、 5 5學(xué)時學(xué)時第第2 2章章 線性表線性表 1010學(xué)時學(xué)時第第3 3章章 棧和隊列棧和隊列 6 6學(xué)時學(xué)時第第4 4章章 串串 4 4學(xué)時學(xué)時第第5 5章章 遞歸遞歸 2 2學(xué)時學(xué)時第第6 6章章 數(shù)組和廣義表數(shù)組和廣義表 4 4學(xué)時學(xué)時第第7 7章章 樹和二叉樹樹和二叉樹 1010學(xué)時學(xué)時第第8 8章章 圖圖 9 9學(xué)時學(xué)時第第9 9章章 查找查找 7 7學(xué)時學(xué)時第第1010章章 內(nèi)排序內(nèi)排序 7 7學(xué)時學(xué)時第第1111章章 外排序外排序 不不 講講第第1 12 2章章 文件文件 不不 講講第第1 13 3章章 采用面向?qū)ο蟮姆椒枋鏊惴ú捎妹嫦驅(qū)ο蟮姆椒枋鏊惴?不不 講講9第第1章章

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

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

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

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

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

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

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

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

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

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

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

18、和多個后繼結(jié)點。 (3) 圖形結(jié)構(gòu)圖形結(jié)構(gòu)【例【例1.5】28集合結(jié)構(gòu)：集合結(jié)構(gòu)： 線性結(jié)構(gòu)：線性結(jié)構(gòu)：樹形結(jié)構(gòu)：樹形結(jié)構(gòu)： 圖形結(jié)構(gòu)：圖形結(jié)構(gòu)：291.1.3 存儲結(jié)構(gòu)類型存儲結(jié)構(gòu)類型 (1) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) (2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) (3) 索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu) (4) 散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu) 存儲結(jié)構(gòu)存儲結(jié)構(gòu)(即物理結(jié)構(gòu)即物理結(jié)構(gòu))： 是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。30 存儲結(jié)構(gòu)存儲結(jié)構(gòu)(物理結(jié)構(gòu)物理結(jié)構(gòu))：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置表示數(shù)據(jù)借助元素在存儲器

19、中的相對位置表示數(shù)據(jù)元素之間的關(guān)系（邏輯相鄰，物理位置也相鄰）元素之間的關(guān)系（邏輯相鄰，物理位置也相鄰）鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針（借助指示元素存儲地址的指針（Pointer）表示數(shù)據(jù)元素之間的邏輯關(guān)系（邏輯相鄰，物理位置不一表示數(shù)據(jù)元素之間的邏輯關(guān)系（邏輯相鄰，物理位置不一定相鄰）定相鄰）【例例】 a1,a2, ana1an1000a2a310021004a1a3a4a2300020001000311.1.4 數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu) (1) 數(shù)據(jù)類型數(shù)據(jù)類型 一個一個值的集合值的集合和定義在此集合上的和定義在此集合上的一組操作一組操作的總稱的總稱 規(guī)

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

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

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

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

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

25、在計算機程序則是算法在計算機上的特定的實現(xiàn)上的特定的實現(xiàn)。一個算法若用程序設(shè)計語言來描。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。述，則它就是一個程序。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)算法是一個算法是一個死循環(huán)死循環(huán)，違反了算法的，違反了算法的有窮性有窮

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

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

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

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

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

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

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

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

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

35、為：語句頻度為： n*(n+1)/2，時間復(fù)雜度為時間復(fù)雜度為O(n2)平方階平方階50時間復(fù)雜度時間復(fù)雜度for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;語句頻度為：語句頻度為：時間復(fù)雜度為時間復(fù)雜度為O(nlog2n)nnnnjnjnk2log1 log11log22 線性對數(shù)階線性對數(shù)階51時間復(fù)雜度時間復(fù)雜度例：矩陣乘法例：矩陣乘法 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 說明：各語句行后的數(shù)字是該語句重復(fù)執(zhí)行的次數(shù)說明：各語句行后的數(shù)字是該語句重復(fù)執(zhí)行的次數(shù); 本算法時間復(fù)雜度為本算法時間復(fù)雜度為O( n3)立方階立方階52 各種不同數(shù)量級對應(yīng)的值存在著如下關(guān)系：各種不同數(shù)量級對應(yīng)的值存在著如下關(guān)系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)53 例例1.8 求兩個求兩個n階方陣的相加階方陣的相加C=A+B的算法如下的算法如下,分析其時間復(fù)雜度。分析其時間復(fù)雜度。 #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 該算法中的基本運算是兩重循環(huán)中最深層的語句該算法中的基本運算是兩重循環(huán)中最深層的語句Cij=Aij+Bij，分析它的頻度，即，分析它的頻度，即： T(n)= =O(n2) 102101010*11ninininjnnnnn55時間復(fù)雜度時間復(fù)雜度 有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨隨問題的輸入數(shù)據(jù)集問題的輸入數(shù)據(jù)集不同而不同。不同而不同。 【例例1.9】 在這種情況下

38、，可用在這種情況下，可用最壞最壞情況下的時間復(fù)雜度作情況下的時間復(fù)雜度作為時間復(fù)雜度為時間復(fù)雜度 有時，也可計算平均情況下的時間復(fù)雜度（有時，也可計算平均情況下的時間復(fù)雜度（P16定義定義1.1）在輸入在輸入I 下執(zhí)行的基下執(zhí)行的基本運算的次數(shù)本運算的次數(shù)任一輸入任一輸入I出出現(xiàn)的概率現(xiàn)的概率I DnP(I)*T(I)E(n)56 （略）（略）例例1.10 有如下遞歸算法：有如下遞歸算法： void fun(int a,int n,int k) /*數(shù)組數(shù)組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); 調(diào)用上述算法的語句為調(diào)用上述算法的語句為fun(a,n,0)，求其時間復(fù)雜度。，求其時間復(fù)雜度。 57 解：設(shè)解：設(shè)fun(a,n,0)的時間復(fù)雜度為的時間復(fù)雜度為T(n),則則fun(a,n,k)的執(zhí)行時間為的執(zhí)行時間為T1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 當(dāng)當(dāng)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) 所以調(diào)用所以調(diào)用fun(a,n,0)的時間復(fù)雜度為的時間復(fù)雜度為O(n2)。 58 算法的存儲量包括：算法的存儲量包括：輸入數(shù)據(jù)所占空間、程序本身輸入數(shù)據(jù)所占空間、程序本身所占空間和所占空間和輔助變量所占空間。輔助變量所占空間。 空間復(fù)雜度是對一個算法在運行過程中空間復(fù)雜度是對一個算法在運行過程中臨時占用的臨時占用的存儲空間存儲空間大小的量度，一般也作為問題規(guī)模大小的量度，一般也作為問題規(guī)模n的函數(shù)，的函數(shù)，以數(shù)量級形式給出，記作：以數(shù)量級形式給出，記作： S(n) = O(g(n) 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)

41、，則稱此算法為稱此算法為原地工作。原地工作。 若所需存儲量依賴于特定的輸入，則通常按若所需存儲量依賴于特定的輸入，則通常按最壞情最壞情況況考慮?？紤]。1.3.3 算法存儲空間分析算法存儲空間分析 59 （略）（略） 例例1.10 有如下遞歸算法：有如下遞歸算法： void fun(int a,int n,int k) /*數(shù)組數(shù)組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); 調(diào)用上述算法的語句為調(diào)用上述算法的語句為fun(a,

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

43、法的影響主要在兩方面數(shù)據(jù)結(jié)構(gòu)對算法的影響主要在兩方面 （1 1）數(shù)據(jù)結(jié)構(gòu)的存儲能力）數(shù)據(jù)結(jié)構(gòu)的存儲能力數(shù)據(jù)結(jié)構(gòu)存儲能力強、存儲信息多算法將會較數(shù)據(jù)結(jié)構(gòu)存儲能力強、存儲信息多算法將會較好設(shè)計（時間少），存儲空間大。好設(shè)計（時間少），存儲空間大。時間和空間的平衡時間和空間的平衡（2 2）定義在數(shù)據(jù)結(jié)構(gòu)上的操作）定義在數(shù)據(jù)結(jié)構(gòu)上的操作在數(shù)據(jù)結(jié)構(gòu)上定義基本操作算法調(diào)用這些基本在數(shù)據(jù)結(jié)構(gòu)上定義基本操作算法調(diào)用這些基本操作。操作。62基本操作越完整，基本操作越完整，算法設(shè)計就越容易算法設(shè)計就越容易算法算法基本操作基本操作基本算法基本算法應(yīng)用程序應(yīng)用程序應(yīng)用程序是通過調(diào)應(yīng)用程序是通過調(diào)用基本算法實現(xiàn)的用基本

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

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