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

1、2024/3/17,1,西北農(nóng)林科技大學(xué)信息工程學(xué)院,本演示文稿可能包含觀眾討論和即席反應(yīng)。使用 PowerPoint 可以跟蹤演示時的即席反應(yīng)，在幻燈片放映中，右鍵單擊鼠標(biāo)請選擇“會議記錄”選擇“即席反應(yīng)”選項卡必要時輸入即席反應(yīng)單擊“確定”撤消此框此動作將自動在演示文稿末尾創(chuàng)建一張即席反應(yīng)幻燈片，包括您的觀點。,用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í)特點,,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è)計,離散數(shù)學(xué),語言程序設(shè)計,計算機原理設(shè)計,,,,,,,,,,,2024/3/17,4,數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點,教學(xué)目標(biāo)：學(xué)會分析數(shù)據(jù)對象的特征，掌握數(shù)據(jù)組織方法和計算機的表示方法，以便為應(yīng)用所涉及數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時間空間分析的技巧，

3、培養(yǎng)良好的程序設(shè)計技能。 學(xué)習(xí)方法：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，必須經(jīng)過大量的實踐，在實踐中體會構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計的技術(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 對算法作性能評價1.6 本章習(xí)題,2024/3/17,6,選擇合適數(shù)據(jù)結(jié)構(gòu)解決應(yīng)用問題1． 計算機處理問題的分類,1.1 學(xué)習(xí)數(shù)

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

5、題    　隨著計算機應(yīng)用領(lǐng)域的擴大和軟、硬件的發(fā)展，"非數(shù)值性問題"越來越顯得重要。據(jù)統(tǒng)計，當(dāng)今處理非數(shù)值性問題占用了90%以上的機器時間，這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決此類問題的關(guān)鍵已不再是分析數(shù)學(xué)和計算方法，而是要設(shè)計出合適的數(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)的意義,著名的瑞士計算機科學(xué)家沃思（N.Wirth）教授曾提出：,數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 算法： 是對數(shù)據(jù)運算的描述 程序設(shè)計： 實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。,算法+數(shù)據(jù)結(jié)構(gòu)=程序,2024/3/17,9,例2 電話號碼查詢問題。,1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,編一個

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

8、加三個項目的比賽?，F(xiàn)有五名選手報名比賽，選手所選擇的項目如參賽選手比賽項目表所示?，F(xiàn)在要求設(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ù)對象（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ù)值、字符以及能輸入機器且能被處理的各種符號集合。,,數(shù)值型數(shù)據(jù)非數(shù)值型數(shù)據(jù),1.2 基本概念和術(shù)語,數(shù)據(jù)包含整型、實型、布爾型、圖象、字符、聲音等一切可以輸入到計算機中的符號集合。,2024/3/17,14,數(shù)據(jù)元素（Data Element）,定義： 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，也稱節(jié)點（node）或記錄（record）。是數(shù)據(jù)集合的個體，在計算機

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

11、{ˊAˊ，Bˊ，…，ˊZˊ} 有限集學(xué)生數(shù)據(jù)對象：,,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ù)對象 S：是D對象中所有數(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ì)相同的值集合以及定義在這個值集合上的一組操作的總稱。,如在高級語言中，整型類型的取值范圍為：-32768~+32767，運算符集合為加、減、乘、除、取模，即+、-、*、/、%。,,1.2 基本概念和術(shù)語,2024/3/17,19,數(shù)據(jù)類型(Data Type),高級語言中的數(shù)據(jù)類型分為兩大類：,1.原子類型，其值不可分解。如C語言中的標(biāo)準(zhǔn)類型（整型

13、、實型、字符型、）。,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ù)類型實現(xiàn) ADT的表示與實現(xiàn),,1.2 基本概念和術(shù)語,2024/3/17,21,數(shù)據(jù)的抽象,匯編語言中十進制表示的數(shù)據(jù)98.6

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

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

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

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

18、象集：D={r | r∈實型數(shù)集合} 數(shù)據(jù)關(guān)系集：R={ } 基本操作集：P包括 InitCircle(& r,c) 初始條件：c為圓的半徑（c>0） 操作結(jié)果：構(gòu)造一個圓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) 存儲結(jié)構(gòu) 運算集合,,2024/3/17,28,

20、數(shù)據(jù)結(jié)構(gòu),用戶自己建立的，并呈現(xiàn)在用戶面前的結(jié)構(gòu)。（表現(xiàn)在線性、非線性）,邏輯結(jié)構(gòu)在計算機存儲器中的映象。（表現(xiàn)為順序、非順序）,映象方式,數(shù)據(jù)對象上各種運算的集合。,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)可概括為：,,存儲結(jié)構(gòu),1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 -存儲結(jié)構(gòu),2024/3/17,31,存儲結(jié)構(gòu),定義：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱為映像）稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。,數(shù)據(jù)元素的表示： 計算機中表示信息的最小單位是bit（比特），即二進制數(shù)中的一位。數(shù)據(jù)元

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

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

24、數(shù)據(jù)項的）值由?。ù螅┑酱螅ㄐ。┑拇涡蚺帕?。,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)容可歸納為三個部分，邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合： 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計算機存貯器中，并在這些數(shù)據(jù)上定義了一個運算的集合，就叫做數(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è)計的要求,,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. 確定性：算法中的每一個步驟必須有確定含義，無二 義性得以實現(xiàn)。,3. 輸 入：有多個或0個輸入。,4. 輸 出：至少有一個或多個輸出。,5. 可行性：原則上能精確進行，操作可通過已實現(xiàn)基本 運算執(zhí)行有限次而完成。,2024/3/17,41,算法設(shè)計的要求,算法的正確性,,算法特征：,可讀性,健壯性,高效率和低存儲量,

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

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

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

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

31、 3） 〈變量〉- -，,（2）串聯(lián)賦值,〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達式〉,2024/3/17,49,對C語言作以下描述：,,（4）條件賦值,〈變量名〉=〈條件表達式〉？〈表達式1〉:〈表達式2〉,（3）成組賦值,(,,,…, ,,…)〈數(shù)組名1〉[下標(biāo)1][下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1][下標(biāo)2],2024/3/17,50,4.條件選擇語句,對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;] },對C語言作以下描述：,2024/3/17,52,對C語言作以下描述：,5.循環(huán)語句,for 語句,for (；；）{循環(huán)體語句；},2024/3/17,53,while 語句,while (） {循環(huán)體語句； },對C語言作以下描述：,

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

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

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

37、行時間的精確地算出算法執(zhí)行具體時間，而是針對算法中語句的執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。,2024/3/17,59,語句頻度,定義：語句頻度是指該語句在一個算法中重復(fù)執(zhí)行的次數(shù)。,,例如：兩個矩陣相乘,算法語句 對應(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,算法的時間復(fù)雜度,算法的時間復(fù)雜度，即是算法的時間量度記做： T(n)=O(f(n)),,例如給出X=X+1,（1）x=x+1 ；時間復(fù)雜度為O(1)，稱為常量階；,（2）for (i=1; i<= n; i++) x=x+1; 時間復(fù)雜度為O(n)，稱為線性階；,（3）for (i=1; i<= n; i++)for (j=1;j<= n; j++) x=x+1;

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

41、的時間復(fù)雜度頻率表：,,2024/3/17,63,最壞時間復(fù)雜度,定義：討論算法在最壞情況下的時間復(fù)雜度，即分析最壞情況下以估計出算法執(zhí)行時間的上界。,,例如冒泡排序算法,2024/3/17,64,void bubble(int a[], int length){將a中整數(shù)數(shù)組重新排序，達到遞增有序} 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 )},,最壞時間復(fù)雜度,2024/3/17,65,算法的空間復(fù)雜度,定義：,,用空間復(fù)雜度作為算法所需存儲空間的量度，記做： 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)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。二. 設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時間表示為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)