數(shù)據(jù)結(jié)構(gòu) 緒論 什么是數(shù)據(jù)結(jié)構(gòu)

1、教材: 數(shù)據(jù)結(jié)構(gòu)（C語言版） 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院開設(shè)本課程的背景：開設(shè)本課程的背景： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)相關(guān)專業(yè)的一門是計(jì)算機(jī)相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課。它主要研究計(jì)算機(jī)加重要的專業(yè)基礎(chǔ)課。它主要研究計(jì)算機(jī)加工對(duì)象的工對(duì)象的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的、在計(jì)算機(jī)中的存儲(chǔ)結(jié)存儲(chǔ)結(jié)構(gòu)構(gòu)以及實(shí)現(xiàn)各種基本以及實(shí)現(xiàn)各種基本操作操作的算法。它是學(xué)的算法。它是學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理等計(jì)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理等計(jì)算機(jī)專業(yè)核心課程的基礎(chǔ)，掌握好這門課算機(jī)專業(yè)核心課程的基礎(chǔ)，掌握好這門課程的內(nèi)容，是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的

2、程的內(nèi)容，是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的必備條件。必備條件。本課程講述的主要內(nèi)容：本課程講述的主要內(nèi)容： 分別講述數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表分別講述數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等內(nèi)容。樹、圖、查找、排序等內(nèi)容。學(xué)習(xí)本課程的基本方法：學(xué)習(xí)本課程的基本方法：l上課認(rèn)真聽講；上課認(rèn)真聽講；l仔細(xì)閱讀教材中的大量例題，從而體會(huì)仔細(xì)閱讀教材中的大量例題，從而體會(huì)并最終掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念；并最終掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念；l獨(dú)立完成每個(gè)章節(jié)的練習(xí)題和作業(yè)題。獨(dú)立完成每個(gè)章節(jié)的練習(xí)題和作業(yè)題。學(xué)習(xí)提要： 1. 熟悉各

3、名詞術(shù)語的含義，掌握基本概熟悉各名詞術(shù)語的含義，掌握基本概念。念。 2.了解抽象數(shù)據(jù)類型的定義、表示和實(shí)了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法?，F(xiàn)方法。 3. 理解算法五個(gè)要素的確切含義，掌握理解算法五個(gè)要素的確切含義，掌握估算算法時(shí)間復(fù)雜度的方法。估算算法時(shí)間復(fù)雜度的方法。 重難點(diǎn)內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、時(shí)間數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、時(shí)間復(fù)雜度的估算方法復(fù)雜度的估算方法 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)程序設(shè)計(jì): : 為計(jì)算機(jī)處理問題編制為計(jì)算機(jī)處理問題編制 一組指令集。一組指令集。 算法算法: : 處理問題的策略。處理問題的策略。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): : 問題的

4、數(shù)學(xué)模型。問題的數(shù)學(xué)模型。 程序程序 = = 算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 數(shù)值計(jì)算數(shù)值計(jì)算的程序設(shè)計(jì)問題：的程序設(shè)計(jì)問題：例如：例如： 結(jié)構(gòu)靜力分析計(jì)算結(jié)構(gòu)靜力分析計(jì)算 線性代數(shù)方程組線性代數(shù)方程組 預(yù)報(bào)人口增長情況預(yù)報(bào)人口增長情況 微分方程微分方程非數(shù)值計(jì)算非數(shù)值計(jì)算的程序設(shè)計(jì)問題：的程序設(shè)計(jì)問題：算法: ? ?模型：？基本操作是“比較兩個(gè)數(shù)的大小比較兩個(gè)數(shù)的大小”取決于整數(shù)值的范圍整數(shù)值的范圍例例1 1：求一組(n個(gè))整數(shù)整數(shù)中的最大值。例例2 書目自動(dòng)檢索系統(tǒng)書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅

5、遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號(hào)高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表算法：算法：需要檢索的書目？如何檢索？用戶界面？需要檢索的書目？如何檢索？用戶界面？模型：模型：？例例3 3 人機(jī)對(duì)奕問題人機(jī)對(duì)奕問題樹.算法：算法：對(duì)奕的規(guī)則和策略對(duì)奕的規(guī)則和策略模型：模型：？例例4 4 教學(xué)計(jì)劃編排問題教學(xué)計(jì)劃編排問題 圖C1計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論無無C2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C1,C4C3匯編語言匯編語言C1C4C語言語言C1C5計(jì)算機(jī)圖形學(xué)計(jì)算

6、機(jī)圖形學(xué)C2,C3,C4C6接口技術(shù)接口技術(shù)C3C7數(shù)據(jù)庫原理數(shù)據(jù)庫原理C2,C9C8編譯原理編譯原理C4C9操作系統(tǒng)操作系統(tǒng)C2C1C3C4C7C6C5C2C8C9 算法：算法：如何確定課程的次序關(guān)系如何確定課程的次序關(guān)系? ?模型：模型：？概括地說：概括地說： 數(shù)據(jù)結(jié)構(gòu)是一門討論數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)描述現(xiàn)實(shí)世界實(shí)體的實(shí)世界實(shí)體的數(shù)學(xué)模型數(shù)學(xué)模型( (非數(shù)值計(jì)非數(shù)值計(jì)算算) )及其上的及其上的操作操作在計(jì)算機(jī)中如何在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)表示和實(shí)現(xiàn)”的學(xué)科。的學(xué)科。數(shù)據(jù)數(shù)據(jù)（data)：所有能被輸入到計(jì)算機(jī)：所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號(hào)的集合中，且被計(jì)算機(jī)處理的符號(hào)的集

7、合 ，是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)操作的對(duì)象的總稱。數(shù)據(jù)元素?cái)?shù)據(jù)元素（data element）：是數(shù)據(jù)）：是數(shù)據(jù)（集合）中的一個(gè)（集合）中的一個(gè)“個(gè)體個(gè)體”，是數(shù)據(jù)，是數(shù)據(jù)的的基本基本單位單位，由若干個(gè)數(shù)據(jù)項(xiàng)組成，由若干個(gè)數(shù)據(jù)項(xiàng)組成，也稱結(jié)點(diǎn)、元素、頂點(diǎn)或也稱結(jié)點(diǎn)、元素、頂點(diǎn)或記錄。記錄。 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的最小最小單位。單位。例如：例如：描述一個(gè)學(xué)生基本信息的數(shù)據(jù)描述一個(gè)學(xué)生基本信息的數(shù)據(jù)元素可以是元素可以是稱之為組合項(xiàng)稱之為組合項(xiàng)學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別專業(yè)班級(jí)專業(yè)班級(jí) 出生日期出生日期 籍貫籍貫?zāi)昴?月月 日日數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(data stru

8、cture)：是指互相之間存在著是指互相之間存在著一種或多種關(guān)一種或多種關(guān)系系的數(shù)據(jù)元素的的數(shù)據(jù)元素的集合集合?；蛘哒f，數(shù)據(jù)結(jié)構(gòu)是帶或者說，數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)的數(shù)據(jù)元素的集合。元素的集合。例：例：一個(gè)含一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以位數(shù)的十進(jìn)制數(shù)可以用三個(gè)用三個(gè)4位的十進(jìn)制數(shù)表示位的十進(jìn)制數(shù)表示 3214, 6587, 9345 a1(3214), a2(6587), a3(9345)在在a1、a2、a3 之間存在之間存在“次序次序”關(guān)關(guān)系：系： a1,a2 、 a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3又例，又例，在2行3

9、列的二維數(shù)組a1, a2, a3, a4, a5, a6 a1 a2 a3 a4 a5 a6行的次序關(guān)系行的次序關(guān)系:列的次序關(guān)系列的次序關(guān)系: :row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6再例，再例，在一維數(shù)組 a1, a2, a3, a4, a5, a6 的數(shù)據(jù)元素之間存在如下的次序關(guān)系次序關(guān)系:| i=1, 2, 3, 4, 5 可見，不同的“關(guān)系關(guān)系”構(gòu)成不同的“結(jié)構(gòu)結(jié)構(gòu)”。集合結(jié)構(gòu)：集合結(jié)構(gòu)：數(shù)據(jù)元素間數(shù)據(jù)元素間 “ “同屬于一個(gè)集合同屬于一個(gè)集合”數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)可歸結(jié)為以下四類四類: :線性結(jié)構(gòu)：線性結(jié)構(gòu)：一個(gè)對(duì)一個(gè)一

10、個(gè)對(duì)一個(gè)樹形結(jié)構(gòu)：樹形結(jié)構(gòu)：一個(gè)對(duì)多個(gè)一個(gè)對(duì)多個(gè)圖狀結(jié)構(gòu)：圖狀結(jié)構(gòu)：多個(gè)對(duì)多個(gè)多個(gè)對(duì)多個(gè)數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 Data_Structure = (D, S)其中:D 是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是 D上關(guān)系的有限集關(guān)系的有限集。例：例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義定義 Complex=（C，R） 其中，其中，C是含兩個(gè)實(shí)數(shù)集合是含兩個(gè)實(shí)數(shù)集合c1，c2； R=P，P是定義在集合是定義在集合C上的上的一種關(guān)系一種關(guān)系 。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)：只抽象反映數(shù)據(jù)：只抽象反映數(shù)據(jù)元素的邏輯關(guān)系。元素的邏

11、輯關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象。器中的映象。“數(shù)據(jù)元素”的映象 ？“關(guān)系”的映象 ？數(shù)據(jù)元素的映象方法：數(shù)據(jù)元素的映象方法： 用用二進(jìn)制位二進(jìn)制位(bit)(bit)的位串表示數(shù)的位串表示數(shù)據(jù)元素。據(jù)元素。(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2關(guān)系的映象方法：關(guān)系的映象方法：（表示x, y的方法）1 1、順序映象、順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系。以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系。例如例如: :令 y 的存儲(chǔ)位置和 x 的存儲(chǔ)位置之間差一個(gè)常量 C。 而 C 是一個(gè)隱含值

12、，整個(gè)存儲(chǔ)結(jié)整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息構(gòu)中只含數(shù)據(jù)元素本身的信息 x y2 2、鏈?zhǔn)接诚?、鏈?zhǔn)接诚笠愿郊有畔⒁愿郊有畔? (指針指針) )表示后繼關(guān)系。表示后繼關(guān)系。 需要用一個(gè)和 x 在一起的附加信附加信息息指示 y 的存儲(chǔ)位置。y x例如：例如：復(fù)數(shù)復(fù)數(shù)z1=3.0-2.3i，z2=-0.7+4.8i的存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)。結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.03.0二、數(shù)據(jù)類型二、數(shù)據(jù)類型 在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明明確說明它們所屬的數(shù)據(jù)類型數(shù)據(jù)類型。例例：C語言語言中，提供中，提供int, char, fl

13、oat等等基本數(shù)據(jù)類型基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型構(gòu)造數(shù)據(jù)類型指針、空指針、空(void)類型等。類型等。用戶也可用用戶也可用typedef 自己定義數(shù)據(jù)類型自己定義數(shù)據(jù)類型typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p; 數(shù)據(jù)類型數(shù)據(jù)類型 是一個(gè) 值的集合值的集合和定義在此集合上的 一組操作一組操作的總稱。 不同類型的變量，其所能取的值的值的范圍范圍不同，所能進(jìn)行的操作進(jìn)行的操作不同。三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型 (Abst

14、ract Data Type 簡稱簡稱ADT)vADT定義：定義： 指一個(gè)指一個(gè)數(shù)學(xué)模型數(shù)學(xué)模型以及定義在該模型以及定義在該模型上的一組上的一組操作操作。 “ “抽象抽象”的意義在于數(shù)據(jù)類型的的意義在于數(shù)據(jù)類型的數(shù)數(shù)學(xué)抽象特性學(xué)抽象特性。 例如：例如：矩陣 +（求轉(zhuǎn)置、加、乘、求逆、求特征值） 構(gòu)成一個(gè)矩陣的抽象數(shù)據(jù)類型。 vADT的描述方法：的描述方法：抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型可用三元組 （D，S，P）表示。 其中：D 是數(shù)據(jù)對(duì)象； S 是 D 上的關(guān)系集； P 是對(duì) D 的基本操作集。 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的

15、定義 基本操作：基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作基本操作的定義格式定義格式為:基本操作名基本操作名（參數(shù)表） 初始條件：初始條件：初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述 賦值參數(shù):只為操作提供輸入值。引用參數(shù):以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件初始條件: :描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果操作結(jié)果: :說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。例如，例如，抽象數(shù)據(jù)類型復(fù)數(shù)復(fù)數(shù)的定義： 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： De1,e2e1,e2

16、RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分 | e2 是復(fù)數(shù)的虛數(shù)部分 ADT Complex 基本操作：基本操作： AssignComplex( &Z, v1, v2 ) 操作結(jié)果：操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部 分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( &Z) 操作結(jié)果操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。 GetImag( Z, &ImagPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用

17、ImagPart返回復(fù)數(shù)Z的虛部值。 Add( z1,z2, &sum ) 初始條件：z1, z2是復(fù)數(shù)。 操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1, z2 的 和值。 ADT Complex假設(shè)假設(shè): :z1和z2是上述定義的復(fù)數(shù)則 Add(z1, z2, z3) 操作的結(jié)果z3 = z1 + z2即為用戶所求的結(jié)果ADT 有兩個(gè)重要特征:數(shù)據(jù)抽象：數(shù)據(jù)抽象： 用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征本質(zhì)的特征、其所能完成的其所能完成的功能功能以及它和外部用戶的接口外部用戶的接口（即外界外界使用它的方法使用它的方法）。數(shù)據(jù)封裝：數(shù)據(jù)封裝： 將實(shí)體的外部特性和其內(nèi)部外部特性和其內(nèi)部

18、實(shí)現(xiàn)細(xì)節(jié)分離實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。vADT的表示和實(shí)現(xiàn)：的表示和實(shí)現(xiàn)： 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)固有數(shù)據(jù)類型類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)。例如，對(duì)以上定義的復(fù)數(shù)。typedef struct float realpart； float imagpart；complex；/ -存儲(chǔ)結(jié)構(gòu)的定義存儲(chǔ)結(jié)構(gòu)的定義/ -基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明void Assign( complex &Z, float realval, float imagval )； / 構(gòu)造復(fù)數(shù) Z,其實(shí)部

19、和虛部分別被賦以 /參數(shù) realval 和 imagval 的值float GetReal( complex Z )； / 返回復(fù)數(shù) Z 的實(shí)部值float Getimag( complex Z )； / 返回復(fù)數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 / -基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 sum.realpar

20、t = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 算法算法是對(duì)特定問題求解步驟的描求解步驟的描述述，是指令的有限序列。1.有窮性 2.確定性 3.可行性4.有輸入 5.有輸出一、算法的定義一、算法的定義一個(gè)算法必須滿足以下五五個(gè)重要特性個(gè)重要特性：1.有窮性有窮性：對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即算法中的每個(gè)步驟都能在有限時(shí)間有限時(shí)間內(nèi)完成。 2.2.確定性：確定性：對(duì)于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能

21、明確其含義及如何執(zhí)行。并且并且在任何條件下，算法都只有一條在任何條件下，算法都只有一條執(zhí)行路徑。執(zhí)行路徑。3.可行性：可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4.有輸入：有輸入：有零個(gè)或多個(gè)輸入，取自特定的對(duì)象集合。5.有輸出：有輸出：有一個(gè)或多個(gè)輸出，是算法進(jìn)行信息加工后得到的結(jié)果。二、算法設(shè)計(jì)的原則二、算法設(shè)計(jì)的原則 設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求1.1.正確性：正確性：在在合理合理的數(shù)據(jù)輸入下，能在的數(shù)據(jù)輸入下，能在有限的運(yùn)算時(shí)間有限的運(yùn)算時(shí)間內(nèi)

22、得到內(nèi)得到正確結(jié)果正確結(jié)果。對(duì)算法是否對(duì)算法是否“正確正確”的理解可以有以下四個(gè)層次：的理解可以有以下四個(gè)層次： a a程序中不含語法錯(cuò)誤；程序中不含語法錯(cuò)誤； b b程序?qū)τ诔绦驅(qū)τ趲捉M幾組輸入數(shù)據(jù)能夠得出滿足要求輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；的結(jié)果； c c程序?qū)τ诔绦驅(qū)τ诰倪x擇的、典型、苛刻切帶有精心選擇的、典型、苛刻切帶有刁難性刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d d程序?qū)τ诔绦驅(qū)τ谝磺泻戏ㄒ磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果；足要求的結(jié)果；2.2.可讀性：可讀性：易于人對(duì)算法的理解；另一方面，晦澀難讀的程序

23、易于隱藏較多錯(cuò)誤而難以調(diào)試；3.3.健壯性：健壯性：當(dāng)輸入的數(shù)據(jù)非法非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理處理出錯(cuò)的方法出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4. .高效率與低存儲(chǔ)量需求：高效率與低存儲(chǔ)量需求： 效率效率指的是算法執(zhí)行時(shí)間。 存儲(chǔ)量存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。 兩者都與問題的規(guī)模問題的規(guī)模有關(guān)。有兩種衡量算法效率的方法有兩種衡量算法效率的方法: 1.事后統(tǒng)計(jì)法：事后統(tǒng)計(jì)法：利用計(jì)算機(jī)內(nèi)記時(shí)利用計(jì)算機(jī)內(nèi)記時(shí)功能，用

24、一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)功能，用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分。區(qū)分。 2.事前分析估計(jì)法：事前分析估計(jì)法：求出算法的一求出算法的一個(gè)時(shí)間界限函數(shù)。個(gè)時(shí)間界限函數(shù)。三三、算法效率的衡量方法和準(zhǔn)則、算法效率的衡量方法和準(zhǔn)則和算法執(zhí)行時(shí)間時(shí)間相關(guān)的因素因素：1 1算法算法選用的策略的策略2 2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言語言4 4編譯編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量的質(zhì)量5 5計(jì)算機(jī)計(jì)算機(jī)執(zhí)行指令的速度的速度 設(shè)解決一個(gè)問題的規(guī)模問題的規(guī)模為n，基本操基本操作作被重復(fù)執(zhí)行的次數(shù)是f(n)。 假如，隨著問題規(guī)模 n 的增長，算法算法執(zhí)行時(shí)間的增長率和執(zhí)行時(shí)間的增長率和 f(n) 的增長率相同的

25、增長率相同，則可記作：T (n) = O(f(n) 稱稱T (n) 為算法的為算法的漸近時(shí)間復(fù)雜度，時(shí)間復(fù)雜度，簡稱簡稱時(shí)間復(fù)雜度時(shí)間復(fù)雜度。算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 =原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間如何估算算法的時(shí)間復(fù)雜度？如何估算算法的時(shí)間復(fù)雜度？ 從算法中選取一種對(duì)于所研究的問題來說是 基本操作基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行在算法中重復(fù)執(zhí)行的次數(shù)的次數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。void mult(int a, int b, int& c ) / 以二維數(shù)組存儲(chǔ)矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作時(shí)間復(fù)