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

1、 第一章第一章 緒緒 論論 上課前需要說明的幾個(gè)問題：上課前需要說明的幾個(gè)問題： 任課教師：王歲花任課教師：王歲花 聯(lián)系電話：聯(lián)系電話：13663901273136639012732.2.交流信箱：交流信箱：3.3.公共信箱：公共信箱： 公共信箱：公共信箱： 密碼：密碼： dsggxx2008dsggxx20084.4.關(guān)于數(shù)據(jù)結(jié)構(gòu)課程：關(guān)于數(shù)據(jù)結(jié)構(gòu)課程： 教材、重要性、時(shí)間按排（教材、重要性、時(shí)間按排（54+3654+36） 考試成績考試成績= =期末考試期末考試* *70%+70%+平時(shí)成績平時(shí)成績* *30%30%5.5.平時(shí)成績主要是實(shí)驗(yàn)作業(yè)完成情況，實(shí)驗(yàn)每次平時(shí)成績主要是實(shí)驗(yàn)作業(yè)完成

2、情況，實(shí)驗(yàn)每次點(diǎn)名，隨機(jī)抽查驗(yàn)收，查看程序運(yùn)行。點(diǎn)名，隨機(jī)抽查驗(yàn)收，查看程序運(yùn)行。 第一章第一章 緒緒 論論 1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1.2 1.2 基本概念和術(shù)語基本概念和術(shù)語1.4 1.4 算法和算法分析算法和算法分析1.3 1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型本章小結(jié)、本章小結(jié)、教材、參考文獻(xiàn)教材、參考文獻(xiàn)作作 業(yè)業(yè) 第一章第一章 緒緒 論論 1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1) 1) 數(shù)據(jù)結(jié)構(gòu)討論的范疇數(shù)據(jù)結(jié)構(gòu)討論的范疇Niklaus WirthNiklaus Wirth 程序程序= =數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +算法算法 用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過

3、下列用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟幾個(gè)步驟:（1）抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型）抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型（2）設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法）設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（3）編出程序進(jìn)行測試、修改直至得到最終結(jié)果。）編出程序進(jìn)行測試、修改直至得到最終結(jié)果。 第一章第一章 緒緒 論論 例例1. 1. 田徑賽的時(shí)間安排問題田徑賽的時(shí)間安排問題 設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示），設(shè)計(jì)比項(xiàng)目，有五人報(bào)名參加比賽（如下表所示），設(shè)計(jì)比賽日程表，使得用盡可能少的時(shí)間段完成比賽。賽日程表，使得用盡可能

4、少的時(shí)間段完成比賽。姓姓 名名項(xiàng)項(xiàng) 目目1項(xiàng)項(xiàng) 目目2項(xiàng)項(xiàng) 目目3丁丁 一一馬馬 二二張張 三三李李 四四王王 五五跳跳 高高標(biāo)標(biāo) 槍槍標(biāo)標(biāo) 槍槍鉛鉛 球球跳跳 遠(yuǎn)遠(yuǎn)跳跳 遠(yuǎn)遠(yuǎn)100米米鉛鉛 球球100米米200米米200米米跳跳 高高200米米用無向圖的用無向圖的著色問題解著色問題解決！決！ 第一章第一章 緒緒 論論 （1 1）設(shè)用如下六個(gè)不同的代號代表不同的項(xiàng)目：）設(shè)用如下六個(gè)不同的代號代表不同的項(xiàng)目： 跳高跳高 跳遠(yuǎn)跳遠(yuǎn) 標(biāo)槍標(biāo)槍 鉛球鉛球 100100米米 200200米米 A A B B C D E C D E F F （2 2）用頂點(diǎn)代表比賽項(xiàng)目）用頂點(diǎn)代表比賽項(xiàng)目 （3 3）用邊

5、連接不能同時(shí)進(jìn)行比賽的項(xiàng)目）用邊連接不能同時(shí)進(jìn)行比賽的項(xiàng)目 如下圖所示：如下圖所示：姓姓 名名項(xiàng)目項(xiàng)目1項(xiàng)目項(xiàng)目2項(xiàng)目項(xiàng)目3丁丁 一一馬馬 二二張張 三三李李 四四王王 五五ACCDBBEDEFFAF 第一章第一章 緒緒 論論 韋爾奇韋爾奇. .鮑威爾（鮑威爾（Welch Powell)Welch Powell)方法：方法： 1.1.將圖將圖G G中的結(jié)點(diǎn)按中的結(jié)點(diǎn)按度度遞減的順序排列。遞減的順序排列。 2.2.用沒有用過的顏色對第一個(gè)點(diǎn)著色，并且按排列用沒有用過的顏色對第一個(gè)點(diǎn)著色，并且按排列次序，對與前面著色點(diǎn)不相鄰的點(diǎn)著相同顏色。次序，對與前面著色點(diǎn)不相鄰的點(diǎn)著相同顏色。 3.3.從序列

6、中刪除第從序列中刪除第2 2步著過色的點(diǎn)。步著過色的點(diǎn)。 4.4.重復(fù)第重復(fù)第2 2、3 3步，直到序列為空。步，直到序列為空。 第一章第一章 緒緒 論論 例例: :對上例，執(zhí)行算法第對上例，執(zhí)行算法第1 1步結(jié)果為：步結(jié)果為： F ,A , E ,B , C ,D F ,A , E ,B , C ,D 重復(fù)執(zhí)行第重復(fù)執(zhí)行第2,32,3步序列變化為：步序列變化為： A,E,B,C,D E,B,D B A,E,B,C,D E,B,D B 圖的變化為：圖的變化為： 第一章第一章 緒緒 論論 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)操作對象以及它們之間

7、關(guān)系和操問題中計(jì)算機(jī)操作對象以及它們之間關(guān)系和操作等的學(xué)科。作等的學(xué)科。2) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 對研究對研究對象對象及其之間及其之間關(guān)系關(guān)系的描述。的描述。結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為數(shù)據(jù)結(jié)構(gòu)的形式定義為: : 數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 Data_Structures = (D, S)Data_Structures = (D, S)其中其中:D :D ：是數(shù)據(jù)元素的有限集：是數(shù)據(jù)元素的有限集 S S ：是：是 D D上關(guān)系的有限集上關(guān)系的有限集。（邏輯結(jié)構(gòu)）（邏輯結(jié)構(gòu)） 第一章第一章 緒緒 論論 1.2 1.2 基本概念和術(shù)語基本概念和術(shù)語 數(shù)據(jù)數(shù)據(jù)(Data):(Data):

8、是對信息的一種符號表示。在計(jì)算機(jī)科是對信息的一種符號表示。在計(jì)算機(jī)科學(xué)中是指所有能被輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處學(xué)中是指所有能被輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。理的符號的總稱。數(shù)據(jù)元素?cái)?shù)據(jù)元素(Data Element(Data Element):):是數(shù)據(jù)的基本單位，在計(jì)是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(Data Item(Data Item）: :一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象

9、數(shù)據(jù)對象(Data Object)(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。集合。是數(shù)據(jù)的一個(gè)子集。 第一章第一章 緒緒 論論 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): :是相互之間存在一種或多種特定關(guān)系的數(shù)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。據(jù)元素的集合。根據(jù)數(shù)據(jù)元素間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)或分為根據(jù)數(shù)據(jù)元素間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)或分為四種：四種：線性結(jié)構(gòu)：線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間結(jié)構(gòu)中的數(shù)據(jù)元素之間 存在一對一的關(guān)系。存在一對一的關(guān)系。樹型結(jié)構(gòu)（層次結(jié)構(gòu)）：樹型結(jié)構(gòu)（層次結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。據(jù)元素之間存

10、在一對多的關(guān)系。圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的（網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。數(shù)據(jù)元素之間存在多對多的關(guān)系。集集 合：合：結(jié)構(gòu)中的數(shù)據(jù)元素除了結(jié)構(gòu)中的數(shù)據(jù)元素除了 同屬于一個(gè)集合外，別無其它關(guān)系。同屬于一個(gè)集合外，別無其它關(guān)系。Data_Structures = (D, S)Data_Structures = (D, S)（邏輯結(jié)構(gòu)）（邏輯結(jié)構(gòu)） 第一章第一章 緒緒 論論 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素?cái)?shù)據(jù)元素”的映象的映象 ？“關(guān)系關(guān)系”的映象的映象 ？數(shù)據(jù)元素的映象方法：數(shù)據(jù)元素的映象方法：用二進(jìn)制位用二

11、進(jìn)制位(bit)(bit)的位串表示數(shù)據(jù)元素的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2 第一章第一章 緒緒 論論 1 1. .順序映象順序映象 ：借助于元素在計(jì)算機(jī)存儲(chǔ)器中的存借助于元素在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)位置來描述元素之間的邏輯關(guān)系。儲(chǔ)位置來描述元素之間的邏輯關(guān)系。 例：關(guān)系的映象方法（表示例：關(guān)系的映象方法（表示 的方法）的方法） xyz2.2.鏈?zhǔn)接诚箧準(zhǔn)接诚?借助于指示元素存儲(chǔ)地址的指針表示借助于指示元素存儲(chǔ)地址的指針表示元素之間的邏輯關(guān)系元素之間的邏輯關(guān)系 。 xyz 第一章第一章 緒緒 論論

12、 在不同的編程環(huán)境中，在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。 當(dāng)用高級程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒壆?dāng)用高級程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通常可用高級編程語言中提供的數(shù)據(jù)類型描述之。編程語言中提供的數(shù)據(jù)類型描述之。 第一章第一章 緒緒 論論 數(shù)據(jù)類型：數(shù)據(jù)類型：數(shù)據(jù)類型是一個(gè)值的集合和定義在這組值數(shù)據(jù)類型是一個(gè)值的集合和定義在這組值 集上的一組操作的總稱。集上的一組操作的總稱。例如：例如：C-語言中的語言中的int , float , char等等抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type 簡稱簡稱ADT) ：是指一個(gè)是指一個(gè)數(shù)學(xué)模型以

13、及定義在此數(shù)學(xué)模型上的一組操作。數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 第一章第一章 緒緒 論論 抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法: : 抽象數(shù)據(jù)類型可用（抽象數(shù)據(jù)類型可用（D D，S S，P P）三元組表示）三元組表示, ,其其中，中，D D是數(shù)據(jù)對象，是數(shù)據(jù)對象，S S是是D D上的關(guān)系集，上的關(guān)系集，P P是對是對D D的基本的基本操作集。操作集。 本門課采用下面格式表示抽象數(shù)據(jù)類型：本門課采用下面格式表示抽象數(shù)據(jù)類型：ADT ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義基本操作：基

14、本操作：基本操作的定義基本操作的定義 ADT ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 第一章第一章 緒緒 論論 其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為：操作的定義格式為：基本操作名（參數(shù)表）基本操作名（參數(shù)表）初始條件：初始條件：初始條件描述初始條件描述操作結(jié)果：操作結(jié)果：操作結(jié)果描述操作結(jié)果描述基本操作有兩種參數(shù)基本操作有兩種參數(shù)：賦值參數(shù)：賦值參數(shù)只為操作提供輸入值；只為操作提供輸入值；引用參數(shù)引用參數(shù)以以& &打頭，打頭， 除可提供輸入值外，還將帶回操作除可提供輸入值外，還將帶回操作結(jié)果。結(jié)果。引用變量和

15、引用參數(shù)引用變量和引用參數(shù) 第一章第一章 緒緒 論論 “ “初始條件初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?；叵鄳?yīng)出錯(cuò)信息。若初始條件為空，則省略之。若初始條件為空，則省略之。 “操作結(jié)果操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程高級編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。來實(shí)現(xiàn)。例如：抽象

16、數(shù)據(jù)類型三元組的定義：例如：抽象數(shù)據(jù)類型三元組的定義：P9 第一章第一章 緒緒 論論 #includestdio.hvoid main( ) int x=3, y=4, &z=x; printf(x=%d, y=%d, z=%dn,x,y,z); z=x+y; printf(x=%d, y=%d, z=%dn,x,y,z); 運(yùn)行結(jié)果運(yùn)行結(jié)果:x=3, y=4, z=3x=7, y=4, z=7 第一章第一章 緒緒 論論 void sum1(int a,int b,int c) c=a+b; return;void sum2(int a,int b,int &c) c=a+b;

17、 return;void main( )void main( ) int x=3,y=4,z=5; int x=3,y=4,z=5; printf(x=%d,y=%d,z=%dn,x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); sum1(x,y,z); sum1(x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); sum2(x,y,z); sum2(x,y,z); printf(x=%d,y=%d,z=%dn,x,y,z); printf(x=%d,y=%d,z=%dn,x,y

18、,z); 運(yùn)行結(jié)果運(yùn)行結(jié)果x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=5x=3,y=4,z=7x=3,y=4,z=7 第一章第一章 緒緒 論論 - / - 采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)- typedef ElemType typedef ElemType * *Triplet;Triplet;/ / 由由InitTripletInitTriplet分配三個(gè)元素存儲(chǔ)空間分配三個(gè)元素存儲(chǔ)空間/ Triplet/ Triplet類型是類型是ElemTypeElemType類型的指針類型的指針/存放存放ElemTypeElemType類

19、型的地址類型的地址例如：抽象數(shù)據(jù)類型三元組的定義：例如：抽象數(shù)據(jù)類型三元組的定義：P9 第一章第一章 緒緒 論論 bo1_1.cpp / bo1_1.cpp 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型TripletTriplet和和ElemTypeElemType/(/(由由c1_1.hc1_1.h定義定義) )的基本操作的基本操作(8(8個(gè)個(gè)) )Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3) /操作結(jié)果操作結(jié)果: :構(gòu)造三元組構(gòu)造三元組T,T,依次置依次置T T的三個(gè)元素的初的三個(gè)元素的初 /值為值為v1,v2v1

20、,v2和和v3v3 if(!(T=(ElemType *)malloc(3*sizeof(ElemType) exit(OVERFLOW); T0=v1,T1=v2,T2=v3; return OK; 第一章第一章 緒緒 論論 Status Get(Triplet T,int i, ElemType &e) /初始條件：三元組初始條件：三元組T T已存在，已存在，1i31i3。 /操作結(jié)果：用操作結(jié)果：用e e返回返回T T的第的第i i元的值元的值 if(i3) return ERROR; e=Ti-1; return OK; Status Put(Triplet T,int i,E

21、lemType e) /初始條件：三元組初始條件：三元組T T已存在，已存在，1i31i3。 /操作結(jié)果：改變操作結(jié)果：改變T T的第的第i i元的值為元的值為e e if(i3) return ERROR; Ti-1=e; return OK; 第一章第一章 緒緒 論論 Status IsAscending(Triplet T) / / 初始條件：三元組初始條件：三元組T T已存在。操作結(jié)果：如果已存在。操作結(jié)果：如果 /T/T的三個(gè)元素按升序排列，返回的三個(gè)元素按升序排列，返回1 1，否則返回，否則返回0 0 return(T0=T1&T1=T1&T1=T2); 第一章第一

22、章 緒緒 論論 Status Max(Triplet T,ElemType &e)Status Max(Triplet T,ElemType &e) / / 初始條件：三元組初始條件：三元組T T已存在。已存在。 / / 操作結(jié)果：用操作結(jié)果：用e e返回返回T T的三個(gè)元素中的最大值的三個(gè)元素中的最大值 e=(T0=T1)?(T0=T2)?T0:T2):e=(T0=T1)?(T0=T2)?T0:T2): (T1 =T2)?T1:T2);T1 =T2)?T1:T2); return OK; return OK; Status Min(Triplet T,ElemType &am

23、p;e)Status Min(Triplet T,ElemType &e) / / 初始條件：三元組初始條件：三元組T T已存在。已存在。 /操作結(jié)果：用操作結(jié)果：用e e返回返回T T的三個(gè)元素中的最小值的三個(gè)元素中的最小值 e=(T0=T1)?(T0=T2)?T0:T2)e=(T0=T1)?(T0=T2)?T0:T2): : ( (T1=T2)?T1:T2);T1=0)n=0)個(gè)初始數(shù)據(jù)的輸入。個(gè)初始數(shù)據(jù)的輸入。 （5 5）輸出：）輸出：一個(gè)算法有一個(gè)或多個(gè)與輸入有某種關(guān)系一個(gè)算法有一個(gè)或多個(gè)與輸入有某種關(guān)系的有效信息的輸出。的有效信息的輸出。 第一章第一章 緒緒 論論 3 3）算

24、法設(shè)計(jì)的要求）算法設(shè)計(jì)的要求 正確性、可讀性、健壯性和效率與存儲(chǔ)量要求。正確性、可讀性、健壯性和效率與存儲(chǔ)量要求。 第一章第一章 緒緒 論論 程序正確性的五個(gè)層面：程序正確性的五個(gè)層面： （1 1）不含語法錯(cuò)誤）不含語法錯(cuò)誤 （2 2）程序?qū)τ冢┏绦驅(qū)τ趎 n組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果。求的結(jié)果。 （3 3）程序?qū)τ诰倪x擇的典型、邊界性的）程序?qū)τ诰倪x擇的典型、邊界性的n n組輸入數(shù)組輸入數(shù)據(jù)能得出滿足規(guī)格說明要求的結(jié)果。據(jù)能得出滿足規(guī)格說明要求的結(jié)果。 （4 4）程序?qū)τ谝磺泻线m的輸入數(shù)據(jù)都能得出滿足規(guī)）程序?qū)τ谝磺泻线m的輸入數(shù)據(jù)都能得出滿足

25、規(guī)格說明要求的結(jié)果（窮舉）。格說明要求的結(jié)果（窮舉）。 （5 5）用數(shù)學(xué)方法證明程序的正確性用數(shù)學(xué)方法證明程序的正確性 第一章第一章 緒緒 論論 嫦娥一號：嫦娥一號：98.8萬行源代碼，萬行源代碼， 421萬份文件，萬份文件， 打印打印出來有出來有23000頁。用了頁。用了160多萬行程序證明它的正確多萬行程序證明它的正確 性。性。可讀性、健壯性和效率與存儲(chǔ)量要求?？勺x性、健壯性和效率與存儲(chǔ)量要求。 第一章第一章 緒緒 論論 4 4）高效率與低存儲(chǔ)量需求）高效率與低存儲(chǔ)量需求通常，效率指的是通常，效率指的是算法執(zhí)行時(shí)間算法執(zhí)行時(shí)間；存儲(chǔ)量指的是；存儲(chǔ)量指的是算法執(zhí)行過程中算法執(zhí)行過程中所需的最

26、大存儲(chǔ)空間所需的最大存儲(chǔ)空間，兩者都與問題的，兩者都與問題的規(guī)模有關(guān)。規(guī)模有關(guān)。算法效率的衡量方法和準(zhǔn)則算法效率的衡量方法和準(zhǔn)則衡量算法效率的方法衡量算法效率的方法: :缺點(diǎn)：缺點(diǎn)：1 1必須執(zhí)行程序必須執(zhí)行程序 2 2其它因素掩蓋算法本質(zhì)其它因素掩蓋算法本質(zhì)事后統(tǒng)計(jì)法：事后統(tǒng)計(jì)法：事前分析估算法事前分析估算法 第一章第一章 緒緒 論論 和算法執(zhí)行時(shí)間有關(guān)的因素：和算法執(zhí)行時(shí)間有關(guān)的因素：1 1算法選用的策略算法選用的策略2 2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言編寫程序的語言4 4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5 5計(jì)算機(jī)執(zhí)行指令的速度計(jì)算機(jī)執(zhí)行指令的速度 一個(gè)

27、特定一個(gè)特定算法的算法的“運(yùn)行工作量運(yùn)行工作量” 的大小，只的大小，只依賴于依賴于問題的規(guī)模問題的規(guī)模（通常用整數(shù)量（通常用整數(shù)量n表示），或表示），或者說，者說，它是問題規(guī)模的函數(shù)它是問題規(guī)模的函數(shù)f(n) f(n) 。 第一章第一章 緒緒 論論 算法算法 = = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 /基本操作基本操作 （固有數(shù)據(jù)類型的操作）（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 = =原操作原操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 從算法中選取一

28、種對于所研究的問題來說是從算法中選取一種對于所研究的問題來說是 基基本操作本操作 的原操作，以該基本操作的原操作，以該基本操作 在算法中重復(fù)執(zhí)在算法中重復(fù)執(zhí)行的次數(shù)行的次數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。 第一章第一章 緒緒 論論 表示隨著問題規(guī)模的增大，算法執(zhí)行時(shí)間增長增表示隨著問題規(guī)模的增大，算法執(zhí)行時(shí)間增長增長率和長率和 f(n)f(n)相同，稱作算法的漸近時(shí)間復(fù)雜度，簡相同，稱作算法的漸近時(shí)間復(fù)雜度，簡稱為時(shí)間復(fù)雜度。稱為時(shí)間復(fù)雜度。一般情況下，算法中基本操作執(zhí)行的次數(shù)是問題一般情況下，算法中基本操作執(zhí)行的次數(shù)是問題規(guī)模規(guī)模n n的某個(gè)函數(shù)的某個(gè)函數(shù)f(n),

29、f(n),算法的時(shí)間量度記作：算法的時(shí)間量度記作：T (n) = O(f(n)T (n) = O(f(n)= MnT (n)limf(n) ( M M 是是00的常數(shù)的常數(shù)) ) 也可以用：也可以用： 第一章第一章 緒緒 論論 如何估算算法的時(shí)間復(fù)雜度？如何估算算法的時(shí)間復(fù)雜度？例：例：2n2n3 3+1000n+1000n2 2+1=O(n+1=O(n3 3) ) 1000n 1000n2 2+n+1000000= O(n+n+1000000= O(n2 2) ) 第一章第一章 緒緒 論論 例例一一兩兩個(gè)個(gè)矩矩陣陣相相乘乘void mult(int a, int b, int c )void

30、 mult(int a, int b, int c ) / / 以二維數(shù)組存儲(chǔ)矩陣元素，以二維數(shù)組存儲(chǔ)矩陣元素，c c 為為 a a 和和 b b 的乘積的乘積 for (i=1; i=n; +i)for (i=1; i=n; +i) for (j=1; j=n; +j) for (j=1; j=n; +j) cij = 0; cij = 0; for (k=1; k=n; +k) for (k=1; k=1 & change; for (i=n-1, change=TRUE; i=1 & change; -i)i) / bubble_sort / bubble_sort ch

31、ange = FALSE; change = FALSE; / change / change 為元素進(jìn)行交換標(biāo)志為元素進(jìn)行交換標(biāo)志 for (j=0; ji; +j)for (j=0; j aj+1) if (aj aj+1) aj aj aj+1; change = TRUE ; aj+1; change = TRUE ; / / 一趟冒泡一趟冒泡交換次數(shù)：交換次數(shù)：最好情況：最好情況：0 0最壞情況：最壞情況：n(n-1)/2n(n-1)/2 第一章第一章 緒緒 論論 最壞情況下的時(shí)間復(fù)雜度最壞情況下的時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度若不特別說明，以后我們所說的都是最壞情若不特別說

32、明，以后我們所說的都是最壞情況下的時(shí)間復(fù)雜度況下的時(shí)間復(fù)雜度 第一章第一章 緒緒 論論 常見函數(shù)的時(shí)間復(fù)雜度常見函數(shù)的時(shí)間復(fù)雜度按數(shù)量遞增排列及增長按數(shù)量遞增排列及增長率。率。 常數(shù)階常數(shù)階O(1)O(1) 對數(shù)階對數(shù)階O(logO(log2 2n)n) 線性階線性階O(n)O(n) 線性對數(shù)階線性對數(shù)階O(nlogO(nlog2 2n)n) 平方階平方階O(nO(n2 2) ) 立方階立方階O(nO(n3 3) ) 多項(xiàng)式多項(xiàng)式階階O(nO(nk k) ) 指數(shù)階指數(shù)階O(2O(2n n） 第一章第一章 緒緒 論論 1.10 按增長率由小到大的排列順序是：按增長率由小到大的排列順序是： (2

33、/3)n , 2100, log2(log2n) , log2n , (log2n)2, ,n2/3, n/log2n , n , nlog2n , n3/2, (4/3)n , (3/2)n ,n log2n , n! , nn解題依據(jù)為：解題依據(jù)為： n 122lim0 (1)mxxxmm 2limlogxxx 第一章第一章 緒緒 論論 4) 4) 算法的存儲(chǔ)空間需求算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為算法的空間復(fù)雜度定義為: : 表示隨著問題規(guī)模表示隨著問題規(guī)模 n n 的增大，算法運(yùn)行的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與所需存儲(chǔ)量的增長率與 g(n) g(n) 的增長率相同。的增長

34、率相同。S(n) = O(g(n)S(n) = O(g(n)算法的存儲(chǔ)量包括算法的存儲(chǔ)量包括: :輸入數(shù)據(jù)所占空間輸入數(shù)據(jù)所占空間程序本身所占空間程序本身所占空間輔助變量所占空間輔助變量所占空間 第一章第一章 緒緒 論論 若輸入數(shù)據(jù)所占空間只取決于問題本身，和算若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析法無關(guān)，則只需要分析除輸入和程序之外的輔助變除輸入和程序之外的輔助變量所占額外空間。量所占額外空間。 若需存儲(chǔ)量依賴于特定的輸入，則通常按最壞若需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。情況考慮。 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，若所需額外空間相對于輸入數(shù)據(jù)量來

35、說是常數(shù)，則稱此算法為則稱此算法為原地工作原地工作。例如在進(jìn)行冒泡排序時(shí)所。例如在進(jìn)行冒泡排序時(shí)所需的額外的空間就是一個(gè)常數(shù)需的額外的空間就是一個(gè)常數(shù), ,空間復(fù)雜度為空間復(fù)雜度為O(1)O(1)。 第一章第一章 緒緒 論論 本章小結(jié)本章小結(jié)1.1.基本概念和術(shù)語基本概念和術(shù)語 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)對象、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算）、多形數(shù)數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算）、多形數(shù)據(jù)類型、抽象數(shù)據(jù)類型（定義、表示和實(shí)現(xiàn)）據(jù)類型、抽象數(shù)據(jù)類型（定義、表示和實(shí)現(xiàn)）2.2.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：描述、類：描述、類-C-C中的

36、基本語句和函數(shù)中的基本語句和函數(shù)3.3.算法：算法：算法的時(shí)間復(fù)雜度（漸近時(shí)間復(fù)雜度、最壞算法的時(shí)間復(fù)雜度（漸近時(shí)間復(fù)雜度、最壞情況下的時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度），算法的情況下的時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度），算法的空間復(fù)雜度（原地工作、額外空間）。對空間復(fù)雜度（原地工作、額外空間）。對O O的理解的理解 第一章第一章 緒緒 論論 4.4.編程常用頭文件：編程常用頭文件： #include #include #include / malloc( ),alloc( ),realloc( )等等 #include / INT_MAX等等 #include / EOF(=Z或或F6),NULL #i

37、nclude / srand( ) ,rand( ),exit(n) #include / eof( ) #include / floor(),ceil( ),abs( ) #include / exit(n) #include / cout,cin 第一章第一章 緒緒 論論 5. 5. 函數(shù)結(jié)果狀態(tài)代碼函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; / Status是函數(shù)的類型是函

38、數(shù)的類型,/其值是函數(shù)結(jié)果狀態(tài)代碼，如其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等等 typedef int Boolean; / Boolean是布爾類型是布爾類型,其其/值是值是TRUE或或FALSE 第一章第一章 緒緒 論論 6. 6.上機(jī)環(huán)境及注意事項(xiàng)上機(jī)環(huán)境及注意事項(xiàng) 上機(jī)環(huán)境上機(jī)環(huán)境VC+6.0 ,VC+6.0 ,但我們不用面象對象的思想；但我們不用面象對象的思想；除了使用除了使用VCVC中提供的中提供的引用參數(shù)引用參數(shù)的概念外，全用的是標(biāo)的概念外，全用的是標(biāo)準(zhǔn)準(zhǔn)C C。 所有用戶定義的類型，必須先定義后使用！所有用戶定義的類型，必須先定義后使用！例如：例如：ElemType ElemType 在使用時(shí)，應(yīng)根據(jù)情況定義它的具在使用