西北農(nóng)林科技大學(xué)信息工程學(xué)院

1、2024/3/17,1,西北農(nóng)林科技大學(xué)信息工程學(xué)院,本演示文稿可能包含觀眾討論和即席反應(yīng)。使用 PowerPoint 可以跟蹤演示時(shí)的即席反應(yīng)，在幻燈片放映中，右鍵單擊鼠標(biāo)請(qǐng)選擇“會(huì)議記錄”選擇“即席反應(yīng)”選項(xiàng)卡必要時(shí)輸入即席反應(yīng)單擊“確定”撤消此框此動(dòng)作將自動(dòng)在演示文稿末尾創(chuàng)建一張即席反應(yīng)幻燈片，包括您的觀點(diǎn)。,用C語言描述,數(shù)據(jù)結(jié)構(gòu),主講教師：馮 妍,2024/3/17,2,關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)課程地位

2、數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn),,2024/3/17,3,數(shù)據(jù)結(jié)構(gòu)課程地位,數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)庫,人工智能,專業(yè)基礎(chǔ)課,操作系統(tǒng),編譯原理,非線性程序設(shè)計(jì),離散數(shù)學(xué),語言程序設(shè)計(jì),計(jì)算機(jī)原理設(shè)計(jì),,,,,,,,,,,2024/3/17,4,數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn),教學(xué)目標(biāo)：學(xué)會(huì)分析數(shù)據(jù)對(duì)象的特征，掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表示方法，以便為應(yīng)用所涉及數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時(shí)間空間分析的技巧，

3、培養(yǎng)良好的程序設(shè)計(jì)技能。 學(xué)習(xí)方法：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，必須經(jīng)過大量的實(shí)踐，在實(shí)踐中體會(huì)構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計(jì)的技術(shù)。,,2024/3/17,5,第1章 緒 論,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義1.2 基本概念和術(shù)語1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容1.4 算法1.5 對(duì)算法作性能評(píng)價(jià)1.6 本章習(xí)題,2024/3/17,6,選擇合適數(shù)據(jù)結(jié)構(gòu)解決應(yīng)用問題1． 計(jì)算機(jī)處理問題的分類,1.1 學(xué)習(xí)數(shù)

4、據(jù)結(jié)構(gòu)的意義,（1）數(shù)值計(jì)算問題    在計(jì)算機(jī)發(fā)展初期，人們使用計(jì)算機(jī)主要是處理數(shù)值計(jì)算問題。 例1：線性方程的求解   　 該類問題涉及的運(yùn)算對(duì)象是簡單的整型、實(shí)型或布爾型數(shù)據(jù)。程序設(shè)計(jì)者的主要精力集中于程序設(shè)計(jì)的技巧，無須重視數(shù)據(jù)結(jié)構(gòu)。,2024/3/17,7,選擇合適數(shù)據(jù)結(jié)構(gòu)解決應(yīng)用問題1． 計(jì)算機(jī)處理問題的分類,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,（2）非數(shù)值性問

5、題    　隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，"非數(shù)值性問題"越來越顯得重要。據(jù)統(tǒng)計(jì)，當(dāng)今處理非數(shù)值性問題占用了90%以上的機(jī)器時(shí)間，這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決此類問題的關(guān)鍵已不再是分析數(shù)學(xué)和計(jì)算方法，而是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。,2024/3/17,8,選擇合適數(shù)據(jù)結(jié)構(gòu)解決應(yīng)用問題2．

6、非數(shù)值問題求解,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,著名的瑞士計(jì)算機(jī)科學(xué)家沃思（N.Wirth）教授曾提出：,數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 算法： 是對(duì)數(shù)據(jù)運(yùn)算的描述 程序設(shè)計(jì)： 實(shí)質(zhì)是對(duì)實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。,算法+數(shù)據(jù)結(jié)構(gòu)=程序,2024/3/17,9,例2 電話號(hào)碼查詢問題。,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,編一個(gè)

7、查詢某個(gè)城市或單位的私人電話號(hào)碼的程序。要求對(duì)任意給出的一個(gè)姓名，若該人有電話號(hào)碼，則迅速找到其電話號(hào)碼；否則指出該人沒有電話號(hào)碼。,2024/3/17,10,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,例3 學(xué)校機(jī)構(gòu)管理問題問題。,編一個(gè)學(xué)校人事查詢系統(tǒng)。,2024/3/17,11,例4 田徑賽的時(shí)間安排問題。,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,假設(shè)某校的田徑選拔賽共設(shè)六個(gè)項(xiàng)目的比賽，即跳高、跳遠(yuǎn)、標(biāo)槍、鉛球、100米和200米短跑，規(guī)定每個(gè)選手至多參

8、加三個(gè)項(xiàng)目的比賽?，F(xiàn)有五名選手報(bào)名比賽，選手所選擇的項(xiàng)目如參賽選手比賽項(xiàng)目表所示?，F(xiàn)在要求設(shè)計(jì)一個(gè)競賽日程安排表，使得在盡可以短的時(shí)間內(nèi)安排完比賽。,2024/3/17,12,1.2 基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：數(shù)據(jù)（Data）數(shù)據(jù)元素（Data Element） 數(shù)據(jù)對(duì)象（Data Object） 數(shù)據(jù)結(jié)構(gòu)（Data Structure） 數(shù)據(jù)類型(Data Type) 數(shù)據(jù)抽象與抽象數(shù)據(jù)類型,,2024/3/17

9、,13,數(shù)據(jù)（Data）,定義： 數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。,,數(shù)值型數(shù)據(jù)非數(shù)值型數(shù)據(jù),1.2 基本概念和術(shù)語,數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。,2024/3/17,14,數(shù)據(jù)元素（Data Element）,定義： 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record）。是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)

10、中通常作為一個(gè)整體進(jìn)行考慮和處理。,,1.2 基本概念和術(shù)語,定義： 數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，也稱域(field) 數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合,數(shù)據(jù)項(xiàng)（Data Item）,2024/3/17,15,數(shù)據(jù)對(duì)象（Data Object）,定義： 數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。,整數(shù)數(shù)據(jù)對(duì)象：N={0，±1，±2，…} 無限集字符數(shù)據(jù)對(duì)象：C=

11、{ˊAˊ，Bˊ，…，ˊZˊ} 有限集學(xué)生數(shù)據(jù)對(duì)象：,,1.2 基本概念和術(shù)語,2024/3/17,16,數(shù)據(jù)結(jié)構(gòu)（Data Structure）,定義： 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。記為：,Data_Structure=(D,S)其中： D：是某一數(shù)據(jù)對(duì)象 S：是D對(duì)象中所有數(shù)據(jù)元素之間關(guān)系的有限集合,1.2 基本概念和術(shù)語,2024/3/17,17,,1.2 基本概念和術(shù)語,20

12、24/3/17,18,數(shù)據(jù)類型(Data Type),定義： 數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。,如在高級(jí)語言中，整型類型的取值范圍為：-32768~+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。,,1.2 基本概念和術(shù)語,2024/3/17,19,數(shù)據(jù)類型(Data Type),高級(jí)語言中的數(shù)據(jù)類型分為兩大類：,1.原子類型，其值不可分解。如C語言中的標(biāo)準(zhǔn)類型（整型

13、、實(shí)型、字符型、）。,2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。,指針類型屬于哪種類型？,,1.2 基本概念和術(shù)語,2024/3/17,20,數(shù)據(jù)抽象與抽象數(shù)據(jù)類型,數(shù)據(jù)的抽象抽象數(shù)據(jù)類型(Abstract Data Type) 抽象數(shù)據(jù)類型實(shí)現(xiàn) ADT的表示與實(shí)現(xiàn),,1.2 基本概念和術(shù)語,2024/3/17,21,數(shù)據(jù)的抽象,匯編語言中十進(jìn)制表示的數(shù)據(jù)98.6

14、5、9.6E3等, 它們是二進(jìn)制數(shù)據(jù)的抽象;,,高級(jí)語言中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí) 型、字符型等，還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù) 抽 象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù) 雜的抽象數(shù)據(jù)類型。,1.2 基本概念和術(shù)語,2024/3/17,22,抽象數(shù)據(jù)類型(Abstract Data Type),定義： 抽象數(shù)據(jù)類型（簡稱ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作

15、。,,一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過程隱藏起來。,用抽象數(shù)據(jù)類型的概念來指導(dǎo)問題的求解過程：,現(xiàn)實(shí)問題 → 數(shù)學(xué)模型 → 算法 → 程序 → 解,1.2 基本概念和術(shù)語-ADT,2024/3/17,23,ADT的表示與實(shí)現(xiàn)實(shí)現(xiàn),抽象數(shù)據(jù)類型可用以下三元組表示 ADT=（D，R，P）其中， D是數(shù)據(jù)元素有限集， R

16、是D上的關(guān)系的有限集， （D，R）構(gòu)成了一個(gè)數(shù)據(jù)結(jié)構(gòu)， P是對(duì)該數(shù)據(jù)結(jié)構(gòu)的基本操作集。,1.2 基本概念和術(shù)語-ADT,2024/3/17,24,ADT的表示與實(shí)現(xiàn)實(shí)現(xiàn),1.2 基本概念和術(shù)語-ADT,ADT的定義：,ADT 　　　　　{ 數(shù)據(jù)對(duì)象: 結(jié)構(gòu)關(guān)系: 基本操作: }ADT ,2024/3/17,25,關(guān)

17、于參數(shù)傳遞：,參數(shù)表中的參數(shù)有值參和變參兩種。,用標(biāo)準(zhǔn)C語言表示和實(shí)現(xiàn)ADT描述時(shí)，主要有兩個(gè)方面：,二、用C語言函數(shù)實(shí)現(xiàn)各操作。,一、通過結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。,,ADT的表示與實(shí)現(xiàn)實(shí)現(xiàn),1.2 基本概念和術(shù)語-ADT,2024/3/17,26,例：抽象數(shù)據(jù)類型圓（Circle）的定義。 ADT Circle { 數(shù)據(jù)對(duì)

18、象集：D={r | r∈實(shí)型數(shù)集合} 數(shù)據(jù)關(guān)系集：R={ } 基本操作集：P包括 InitCircle(& r,c) 初始條件：c為圓的半徑（c>0） 操作結(jié)果：構(gòu)造一個(gè)圓r，使其半徑為c DestroyCircle(&r) 初始條件：圓r已存在 操作結(jié)果：撤消圓r（使其半徑為0） Area

19、Circle(r，&A) 初始條件：圓r已存在 操作結(jié)果：用A返回圓的面積 CircumferenceCircle(r，&C) 初始條件：圓r已存在 操作結(jié)果：用C返回圓的周長 }ADT Circle,1.2 基本概念和術(shù)語,2024/3/17,27,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容,邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 運(yùn)算集合,,2024/3/17,28,

20、數(shù)據(jù)結(jié)構(gòu),用戶自己建立的，并呈現(xiàn)在用戶面前的結(jié)構(gòu)。（表現(xiàn)在線性、非線性）,邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映象。（表現(xiàn)為順序、非順序）,映象方式,數(shù)據(jù)對(duì)象上各種運(yùn)算的集合。,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容,2024/3/17,29,邏輯結(jié)構(gòu),定義： 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系描述。,,形式化描述：Data_Structure=（D,R）其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。,四類基本的結(jié)構(gòu)

21、 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)。,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-邏輯結(jié)構(gòu),2024/3/17,30,綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：,,存儲(chǔ)結(jié)構(gòu),1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 -存儲(chǔ)結(jié)構(gòu),2024/3/17,31,存儲(chǔ)結(jié)構(gòu),定義：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱為映像）稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。,數(shù)據(jù)元素的表示： 計(jì)算機(jī)中表示信息的最小單位是bit（比特），即二進(jìn)制數(shù)中的一位。數(shù)據(jù)元

22、素可用一個(gè)由若干個(gè)位組成的位串來表示，通常稱這個(gè)位串為結(jié)點(diǎn)（node）或元素（element）。,,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-存儲(chǔ)結(jié)構(gòu),2024/3/17,32,邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：,,存儲(chǔ)結(jié)構(gòu)分為：,存儲(chǔ)結(jié)構(gòu),1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 -存儲(chǔ)結(jié)構(gòu),2024/3/17,33,順序存儲(chǔ),1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-存儲(chǔ)結(jié)構(gòu),2024/3/17,34,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-存儲(chǔ)結(jié)構(gòu),2024/3/17,35,數(shù)據(jù)的操

23、作是定義在邏輯結(jié)構(gòu)上的，而操作的具體實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的?；镜臄?shù)據(jù)操作主要有以下幾種：,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-數(shù)據(jù)的運(yùn)算,查找 在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定條件的數(shù)據(jù)元素（的位置或值）。插入 在數(shù)據(jù)結(jié)構(gòu)中增加新的數(shù)據(jù)元素。刪除 刪去數(shù)據(jù)結(jié)構(gòu)中指定的數(shù)據(jù)元素。更新 改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)數(shù)據(jù)元素中一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的值。排序 （在線性結(jié)構(gòu)中）保持?jǐn)?shù)據(jù)元素的個(gè)數(shù)不變，重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使之按（某個(gè)

24、數(shù)據(jù)項(xiàng)的）值由?。ù螅┑酱螅ㄐ。┑拇涡蚺帕?。,2024/3/17,36,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-總結(jié),2024/3/17,37,綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合： 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。,,1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容-總結(jié),2024/3/17,38,1.4 算法,算法（Algorit

25、hm）定義 算法的特性 算法設(shè)計(jì)的要求,,2024/3/17,39,算法（Algorithm）定義,定義： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。,,2024/3/17,40,算

26、法的特性,,1. 有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)。,2. 確定性：算法中的每一個(gè)步驟必須有確定含義，無二 義性得以實(shí)現(xiàn)。,3. 輸 入：有多個(gè)或0個(gè)輸入。,4. 輸 出：至少有一個(gè)或多個(gè)輸出。,5. 可行性：原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)基本 運(yùn)算執(zhí)行有限次而完成。,2024/3/17,41,算法設(shè)計(jì)的要求,算法的正確性,,算法特征：,可讀性,健壯性,高效率和低存儲(chǔ)量,

27、例如要求n個(gè)數(shù)的最大值問題給出算法如下： max=0; for（i=1 ；imax) max=x; },2024/3/17,42,算法描述的工具,概述：算法+數(shù)據(jù)結(jié)構(gòu)=程序 算法、語言、程序的關(guān)系 設(shè)計(jì)實(shí)現(xiàn)算法過程步驟類描述算法的語言選擇,2024/3/17,43,算法、語言、程序的關(guān)系,1. 算法：描述了數(shù)據(jù)對(duì)

28、象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）。,,2. 描述算法的工具：算法可用自然語言、框圖或高級(jí)程序設(shè)計(jì)語言進(jìn)行描述。,3.程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。,2024/3/17,44,設(shè)計(jì)實(shí)現(xiàn)算法過程步驟,1. 找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系,,2. 確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算,3. 考慮數(shù)據(jù)元素的存儲(chǔ)表示,4. 選擇描述算法的語言,5. 設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語言加以描述。,2024/3/17,45,類描述算法的

29、語言選擇,類語言：,,類語言是接近于高級(jí)語言而又不是嚴(yán)格的高級(jí)語言，具有高級(jí)語言的一般語句設(shè)施，撇掉語言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。,2024/3/17,46,對(duì)C語言作以下描述：,1.預(yù)定義常量和類型,# define TRUE 1 # define FALSE 0 # define MAXSIZE 100 # define OK 1

30、 # define ERROR 0,2024/3/17,47,對(duì)C語言作以下描述：,[數(shù)據(jù)類型] 函數(shù)名（[形式參數(shù)及說明]）{ 內(nèi)部數(shù)據(jù)說明； 執(zhí)行語句組；} /*函數(shù)名*/,2.函數(shù)的表示形式：,2024/3/17,48,3.賦值語句,對(duì)C語言作以下描述：,（1）簡單賦值,1）〈變量名〉=〈表達(dá)式〉 2） 〈變量〉++，

31、 3） 〈變量〉- -，,（2）串聯(lián)賦值,〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉,2024/3/17,49,對(duì)C語言作以下描述：,,（4）條件賦值,〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉:〈表達(dá)式2〉,（3）成組賦值,(,,,…, ,,…)〈數(shù)組名1〉[下標(biāo)1][下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1][下標(biāo)2],2024/3/17,50,4.條件選擇語句,對(duì)C語言作

32、以下描述：,,if () 語句;,if () 語句1; else 語句2;,2024/3/17,51,情況語句,switch (） {case 判斷值1: 語句組 1； break; case 判斷值2: 語句組 2； break; ……,case 判斷值n: 語句組n; br

33、eak; [default: 語句組； break;] },對(duì)C語言作以下描述：,2024/3/17,52,對(duì)C語言作以下描述：,5.循環(huán)語句,for 語句,for (；；）{循環(huán)體語句；},2024/3/17,53,while 語句,while (） {循環(huán)體語句； },對(duì)C語言作以下描述：,

34、do –while 語句,do { 循環(huán)體語句 }while (）,2024/3/17,54,對(duì)C語言作以下描述：,6.輸入、輸出函數(shù),7.其它一些語句,8.注釋語句,9.一些基本的函數(shù),2024/3/17,55,1.5 對(duì)算法作性能評(píng)價(jià),評(píng)價(jià)算法的標(biāo)準(zhǔn)： 評(píng)價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算

35、法的優(yōu)劣。 性能評(píng)價(jià) 有關(guān)數(shù)量關(guān)系計(jì)算,,2024/3/17,56,性能評(píng)價(jià),定義： 對(duì)問題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。,,問題規(guī)模N—對(duì)不同的問題其含義不同： 對(duì)矩陣是階數(shù)； 對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)； 對(duì)圖是頂點(diǎn)個(gè)數(shù)； 對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。,2024/3/17,57,有關(guān)數(shù)量關(guān)系計(jì)算,數(shù)量關(guān)系評(píng)價(jià)

36、體現(xiàn)在時(shí)間——算法在機(jī)器中所耗費(fèi)時(shí)間。數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間——算法在機(jī)器中所占存儲(chǔ)量。關(guān)于算法執(zhí)行時(shí)間語句頻度 算法的時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 最壞時(shí)間復(fù)雜度 算法的空間復(fù)雜度,,2024/3/17,58,關(guān)于算法執(zhí)行時(shí)間,定義： 一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語句執(zhí)行時(shí)間的總和，對(duì)于語句的執(zhí)行時(shí)間是指該條語句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。,,分析： 不是針對(duì)實(shí)際執(zhí)

37、行時(shí)間的精確地算出算法執(zhí)行具體時(shí)間，而是針對(duì)算法中語句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。,2024/3/17,59,語句頻度,定義：語句頻度是指該語句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。,,例如：兩個(gè)矩陣相乘,算法語句 對(duì)應(yīng)的語句頻度 1for（i=0；i< n;i++） n 2for （j=0；j&l

38、t;n;j++） n2 3 {c[i][j]=0; n2 4 for (k=0;k< n; k++) n3 c[i][j]=c[i][j]+a[i][k]*b[k][j]; n3 } 總執(zhí)行次數(shù)：Tn=2n3+

39、2n2 +n,2024/3/17,60,算法的時(shí)間復(fù)雜度,算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做： T(n)=O(f(n)),,例如給出X=X+1,（1）x=x+1 ；時(shí)間復(fù)雜度為O(1)，稱為常量階；,（2）for (i=1; i<= n; i++) x=x+1; 時(shí)間復(fù)雜度為O(n)，稱為線性階；,（3）for (i=1; i<= n; i++)for (j=1;j<= n; j++) x=x+1;

40、 時(shí)間復(fù)雜度為O(n2), 稱為平方階。,2024/3/17,61,常用的時(shí)間復(fù)雜度頻率計(jì)數(shù),數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè):,,O(1) 常數(shù)型 O(n)線性型 O(n2)平方型 O(n3)立方型 O(2n)指數(shù)型 O(log2n)對(duì)數(shù)型O(nlog2n)二維型,按時(shí)間復(fù)雜度由小到大排列的頻率表：,2024/3/17,62,常用的時(shí)間復(fù)雜度頻率計(jì)數(shù),常用

41、的時(shí)間復(fù)雜度頻率表：,,2024/3/17,63,最壞時(shí)間復(fù)雜度,定義：討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。,,例如冒泡排序算法,2024/3/17,64,void bubble(int a[], int length){將a中整數(shù)數(shù)組重新排序，達(dá)到遞增有序} int i=0, j, temp; int change ; do{ change=false ;

42、 for(j=1;ja[j+1]),{temp= a[j];a[j]=a[j+1];a[j+1]=temp;change=true; } i=i+1 ; } while(i<length || change==true )},,最壞時(shí)間復(fù)雜度,2024/3/17,65,算法的空間復(fù)雜度,定義：,,用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記做： S(n)=O(f (n))

43、 。,2024/3/17,66,1.6 本章習(xí)題,一. 簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。二. 設(shè)n為正整數(shù)，利用大"O"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。,(1) i=1; k=0; 　　while(i<n) 　　　{ k=k+10*i;i++;　　　},(2) i=0; k=0; 　　do{　　　　k=k+10*i;

44、i++; 　　　}　　while(i<n);,,2024/3/17,67,,(3) i=1; j=0; 　　while(i+jj) j++;　　　　else i++;　　　},(4)x=n; // n>1 　while (x>=(y+1)*(y+1)) 　　y++;,(5) x=91; y=100;     while(y>0)