數(shù)據(jù)結(jié)構(gòu)耿國(guó)華課件

本演示文稿可能包含觀眾討論和即席反應(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)。

數(shù)據(jù)結(jié)構(gòu)課件用C語(yǔ)言描述11/15/20221數(shù)據(jù)結(jié)構(gòu)課件用C語(yǔ)言描述11/10/20221第1章緒論●1.7

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1.1

數(shù)據(jù)結(jié)構(gòu)的基本概念(定義)1.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究范圍）1.3

算法設(shè)計(jì)1.4

算法描述工具

1.5

對(duì)算法作性能評(píng)價(jià)1.6

數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示11/15/20222第1章緒論●1.7

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1.1

數(shù)據(jù)1.1數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：數(shù)據(jù)（Data）數(shù)據(jù)元素（DataElement）數(shù)據(jù)對(duì)象（DataObject）數(shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)類型(DataType)數(shù)據(jù)抽象與抽象數(shù)據(jù)類型11/15/202231.1數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：11數(shù)據(jù)（Data）定義：數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。C編譯程序源程序（.c）目標(biāo)程序（.obj）可執(zhí)行程序（.exe）C鏈接程序例如對(duì)C源程序11/15/20224數(shù)據(jù)（Data）定義：C編譯程序源程序目標(biāo)程序可執(zhí)行程序C鏈數(shù)據(jù)元素（DataElement）定義：

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：..................北京1983.11河北女

趙虹玲101住

址

出生年月

籍

貫性

別

姓

名

學(xué)

號(hào)

數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)11/15/20225數(shù)據(jù)元素（DataElement）定義：.......數(shù)據(jù)對(duì)象（DataObject）

定義：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。整數(shù)集合：N={0，±1，±2，…}無(wú)限集字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集例如：11/15/20226數(shù)據(jù)對(duì)象（DataObject）定義：整數(shù)集合：N={0數(shù)據(jù)結(jié)構(gòu)（DataStructure）

定義：

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。例如表結(jié)構(gòu)：..................北京1983.11河北女

趙虹玲101住

址

出生年月

籍

貫性

別

姓

名

學(xué)

號(hào)

11/15/20227數(shù)據(jù)結(jié)構(gòu)（DataStructure）定義：.....數(shù)據(jù)結(jié)構(gòu)（DataStructure）樹型結(jié)構(gòu)圖結(jié)構(gòu)1254311/15/20228數(shù)據(jù)結(jié)構(gòu)（DataStructure）樹型結(jié)構(gòu)圖結(jié)構(gòu)1數(shù)據(jù)類型(DataType)

定義：

數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。如在高級(jí)語(yǔ)言中，整型類型的取值范圍為：-32768~+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。11/15/20229數(shù)據(jù)類型(DataType)定義：如在高級(jí)語(yǔ)言中，整型類數(shù)據(jù)類型(DataType)高級(jí)語(yǔ)言中的數(shù)據(jù)類型分為兩大類：1.原子類型，其值不可分解。如C語(yǔ)言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。指針類型屬于哪種類型？11/15/202210數(shù)據(jù)類型(DataType)高級(jí)語(yǔ)言中的數(shù)據(jù)類型分為兩大類數(shù)據(jù)抽象與抽象數(shù)據(jù)類型數(shù)據(jù)的抽象抽象數(shù)據(jù)類型(AbstractDataType)抽象數(shù)據(jù)類型實(shí)現(xiàn)

ADT的表示與實(shí)現(xiàn)面向?qū)ο蟮母拍罱Y(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點(diǎn)11/15/202211數(shù)據(jù)抽象與抽象數(shù)據(jù)類型數(shù)據(jù)的抽象11/10/2022111.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

運(yùn)算集合

11/15/2022121.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容邏輯結(jié)構(gòu)11/10/202212邏輯結(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)

集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)。11/15/202213邏輯結(jié)構(gòu)定義：形式化描述：四類基本的結(jié)構(gòu)11/10/2022集合結(jié)構(gòu)定義：

結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無(wú)任何其它關(guān)系。

集合例如：11/15/202214集合結(jié)構(gòu)定義：集合例如：11/10/202214線性結(jié)構(gòu)定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系。

例如：線性表11/15/202215線性結(jié)構(gòu)定義：例如：線性表11/10/202215樹型結(jié)構(gòu)定義：

結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系。

例如：

樹11/15/202216樹型結(jié)構(gòu)定義：例如：樹11/10/202216圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。例如：

圖11/15/202217圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)定義：例如：圖11/10/2綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)——線性表、棧、隊(duì)、字符串?dāng)?shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)——樹、圖邏輯結(jié)構(gòu)11/15/202218綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)——線性表、棧、隊(duì)存儲(chǔ)結(jié)構(gòu)

定義：

存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。

形式化描述：D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲(chǔ)空間M單元的映像S，D→M，即對(duì)于每一個(gè)d，d∈D,都有唯一的z∈M使S（D）=Z,同時(shí)這個(gè)映像必須明顯或隱含地體現(xiàn)關(guān)系R。11/15/202219存儲(chǔ)結(jié)構(gòu)定義：形式化描述：11/10/202219邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映像與元素本身映像，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示方法：順序映像（順序存儲(chǔ)結(jié)構(gòu)）非順序映像（非順序存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)

11/15/202220邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映像與元素本運(yùn)算集合例如工資表：編號(hào)姓名性別基本工資工齡工資應(yīng)扣工資實(shí)發(fā)工資100001張愛芬女345．67145．4530．00451．12100002李

林

男

445．90185．6045．00586．50100003劉曉峰

男

345．00130．0025．00450．00100004趙

俊

女

560．90225．9065．00721．80100005孫

濤

男

450．60190．8050．00591．80……

……………100121張興強(qiáng)

男

1025．98365．53100．001291.5111/15/202221運(yùn)算集合例如工資表：編號(hào)姓名性別基本工資工齡工資應(yīng)扣數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合：按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的映像方式把它們存放在計(jì)算機(jī)存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。

11/15/202222數(shù)據(jù)結(jié)構(gòu)的內(nèi)容綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，11.3算法

算法（Algorithm）定義

算法的特性

算法設(shè)計(jì)的要求

11/15/2022231.3算法算法（Algorithm）定義11/10/算法（Algorithm）定義定義： Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.

算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。

11/15/202224算法（Algorithm）定義定義：11/10/202224算法的特性1.有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)2.確定性：算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性得以實(shí)現(xiàn)。

3.輸入：有多個(gè)或0個(gè)輸入

4.輸出：至少有一個(gè)或多個(gè)輸出。5.可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)基本運(yùn)算執(zhí)行有限次而完成。

11/15/202225算法的特性1.有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循算法設(shè)計(jì)的要求

算法的正確性

算法特征：

可讀性

健壯性

高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問(wèn)題給出算法如下：max=0;for（i=1；i<=n;i++）{scanf("%f",x);if(x>max)max=x;}11/15/202226算法設(shè)計(jì)的要求算法的正確性算法特征：可讀性健壯性1.4算法描述的工具

概述：

算法+數(shù)據(jù)結(jié)構(gòu)=程序

算法、語(yǔ)言、程序的關(guān)系

設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟類描述算法的語(yǔ)言選擇11/15/2022271.4算法描述的工具概述：11/10/202227算法、語(yǔ)言、程序的關(guān)系1.算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存儲(chǔ)關(guān)系描述）。2.描述算法的工具：算法可用自然語(yǔ)言、框圖或高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行描述。3.程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。11/15/202228算法、語(yǔ)言、程序的關(guān)系1.算法：描述了數(shù)據(jù)對(duì)象的元素之間的設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟1.找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系2.確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算3.考慮數(shù)據(jù)元素的存儲(chǔ)表示4.選擇描述算法的語(yǔ)言5.設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語(yǔ)言加以描述。11/15/202229設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟1.找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系類描述算法的語(yǔ)言選擇類語(yǔ)言：類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，具有高級(jí)語(yǔ)言的一般語(yǔ)句設(shè)施，撇掉語(yǔ)言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。11/15/202230類描述算法的語(yǔ)言選擇類語(yǔ)言：類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)3.賦值語(yǔ)句對(duì)C語(yǔ)言作以下描述：（1）簡(jiǎn)單賦值

1）〈變量名〉=〈表達(dá)式〉2）〈變量〉++，3）〈變量〉--，（2）串聯(lián)賦值〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉

11/15/2022313.賦值語(yǔ)句對(duì)C語(yǔ)言作以下描述：（1）簡(jiǎn)單賦值對(duì)C語(yǔ)言作以下描述：（4）條件賦值〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉:〈表達(dá)式2〉

（3）成組賦值(<變量>,<變量2>,<變量3>,…<變量k〉=(<表達(dá)式1>,<表達(dá)式2>,<表達(dá)式3>,…<表達(dá)式k>)〈數(shù)組名1〉[下標(biāo)1][下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1][下標(biāo)2]

11/15/202232對(duì)C語(yǔ)言作以下描述：（4）條件賦值〈變量名〉=〈條件表達(dá)式〉4.條件選擇語(yǔ)句對(duì)C語(yǔ)言作以下描述：if(<表達(dá)式>)語(yǔ)句;if(<表達(dá)式>)語(yǔ)句1;else語(yǔ)句2;11/15/2022334.條件選擇語(yǔ)句對(duì)C語(yǔ)言作以下描述：if(<表達(dá)式>)情況語(yǔ)句switch(<表達(dá)式>）{case判斷值1:語(yǔ)句組1；break;case判斷值2:語(yǔ)句組2；break;……case判斷值n:語(yǔ)句組n;break;[default:語(yǔ)句組；break;]}對(duì)C語(yǔ)言作以下描述：11/15/202234情況語(yǔ)句switch(<表達(dá)式>）case判斷值n對(duì)C語(yǔ)言作以下描述：5.循環(huán)語(yǔ)句for語(yǔ)句for(<表達(dá)式1>；<表達(dá)式2>；<表達(dá)式3>）{循環(huán)體語(yǔ)句；}11/15/202235對(duì)C語(yǔ)言作以下描述：5.循環(huán)語(yǔ)句for語(yǔ)句for(<表達(dá)while語(yǔ)句while(<條件表達(dá)式>）{循環(huán)體語(yǔ)句；}對(duì)C語(yǔ)言作以下描述：do–while語(yǔ)句do{循環(huán)體語(yǔ)句}while(<條件表達(dá)式>）

11/15/202236while語(yǔ)句while(<條件表達(dá)式>）對(duì)C語(yǔ)言作以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ǔ)空間來(lái)判斷一個(gè)算法的優(yōu)劣。

性能評(píng)價(jià)有關(guān)數(shù)量關(guān)系計(jì)算

11/15/2022371.5對(duì)算法作性能評(píng)價(jià)評(píng)價(jià)算法的標(biāo)準(zhǔn)：11/10/20性能評(píng)價(jià)定義：

對(duì)問(wèn)題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。問(wèn)題規(guī)模N—對(duì)不同的問(wèn)題其含義不同：

對(duì)矩陣是階數(shù)；

對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)；對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。11/15/202238性能評(píng)價(jià)定義：?jiǎn)栴}規(guī)模N—對(duì)不同的問(wèn)題其含義不同：11/10有關(guān)數(shù)量關(guān)系計(jì)算

數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間——算法在機(jī)器中所耗費(fèi)時(shí)間。數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間——算法在機(jī)器中所占存儲(chǔ)量。關(guān)于算法執(zhí)行時(shí)間語(yǔ)句頻度

算法的時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)

最壞時(shí)間復(fù)雜度

算法的空間復(fù)雜度

11/15/202239有關(guān)數(shù)量關(guān)系計(jì)算數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間——算法在機(jī)器中所耗關(guān)于算法執(zhí)行時(shí)間定義：

一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。分析：

不是針對(duì)實(shí)際執(zhí)行時(shí)間精確算出算法執(zhí)行的具體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。11/15/202240關(guān)于算法執(zhí)行時(shí)間定義：分析：11/10/202240語(yǔ)句頻度

定義： 語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個(gè)矩陣相乘算法語(yǔ)句對(duì)應(yīng)的語(yǔ)句頻度1 for（i=0；i<n;i++）n+12 for（j=0；j<n;j++）n(n+1)3{c[i][j]=0;n24for(k=0;k<n;k++)n2(n+1)c[i][j]=c[i][j]+a[i][k]*b[k][j];n3

}

總執(zhí)行次數(shù)：Tn=2n3+3n2+2n+111/15/202241語(yǔ)句頻度定義：例如：算法語(yǔ)句算法的時(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;時(shí)間復(fù)雜度為O(n2),稱為平方階。11/15/202242算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：常用的時(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ù)雜度由小到大排列的頻率表：11/15/202243常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率表：log2nnnlog2nn2n32n一般講：前3種可實(shí)現(xiàn)，后3種雖理論上是可實(shí)現(xiàn)的，實(shí)際上只有對(duì)N限制在很小范圍才有意義，當(dāng)N較大時(shí)，不可能實(shí)現(xiàn)。

01011212248424816641638246451225641664256509665536532160102432768214748364811/15/202244常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率表：log2nn最壞時(shí)間復(fù)雜度

定義：

討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。例如冒泡排序算法11/15/202245最壞時(shí)間復(fù)雜度定義：例如冒泡排序算法11/10/20224voidbubble(inta[],intlength){將a中整數(shù)數(shù)組重新排序，達(dá)到遞增有序}inti=0,j,temp;intchange;do{ change=false; for(j=1;j<length-i;j++) if(a[j]>a[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ù)雜度

11/15/202246voidbubble(inta[],intlengt算法的空間復(fù)雜度

定義：

用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記做：S(n)=O(f(n))。11/15/202247算法的空間復(fù)雜度定義：用空間復(fù)雜度作為算法所需存儲(chǔ)1.6數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示

1.6.1數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的關(guān)聯(lián)性

問(wèn)題描述：欲求1名學(xué)生10次C語(yǔ)言程序設(shè)計(jì)的測(cè)試成績(jī)總分與平均分。其中10次測(cè)驗(yàn)的成績(jī)分別為：80，85，77，56，68，83，90，92，80，98。

11/15/2022481.6數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示1.6.1數(shù)據(jù)結(jié)構(gòu)與程序程序示例1-1：main(){intsum，verage；/*總分，平均分*/intt1,t2,t3,t4,t5,t6,t7,t8,t9,t10；/*10個(gè)變量存10次成績(jī)*/t1=80；t2=85；t3=77；t4=56；t5=68；/*分別賦值*/t6=83；t7=90；t8=92；t9=80；t10=98;sum=t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;/*計(jì)算總分*/average=sum/10;/*計(jì)算平均分*/printf(“總分=%d\n”,sum);printf(“平均分=%d\n”,average);}11/15/202249程序示例1-1：main()11/10/202249根據(jù)測(cè)試次數(shù)與測(cè)試成績(jī)的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲(chǔ)測(cè)驗(yàn)成績(jī)，提高了程序的適用范圍。main(){intsum，erage；inti;intt[10]=80，85，77，56，68，83，90，92，80，98}/*分別賦值*/sum=0;/*總分置初值*/for(i=0;i<10;i++)sum=sum+t[i];average=sum/10;/*計(jì)算平均分*/printf(“總分=%d\n”,sum);printf(“平均分=%d\n”,average);}程序示例1-2：11/15/202250根據(jù)測(cè)試次數(shù)與測(cè)試成績(jī)的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲(chǔ)測(cè)驗(yàn)成績(jī)，提高1.6.2結(jié)構(gòu)化程序設(shè)計(jì)與函數(shù)的模塊化

結(jié)構(gòu)化程序設(shè)計(jì)：是為使程序具有合理的結(jié)構(gòu)，以保證程序正確性而規(guī)定的一套程序設(shè)計(jì)的方法。程序設(shè)計(jì)的實(shí)質(zhì)：算法+數(shù)據(jù)結(jié)構(gòu)=程序

即“程序是在數(shù)據(jù)的特定表示方式的基礎(chǔ)上，對(duì)抽象算法的具體描述”。程序結(jié)構(gòu)=控制結(jié)構(gòu)+數(shù)據(jù)結(jié)構(gòu)

11/15/2022511.6.2結(jié)構(gòu)化程序設(shè)計(jì)與函數(shù)的模塊化結(jié)構(gòu)化程序設(shè)計(jì)：①

結(jié)構(gòu)化程序設(shè)計(jì)目的通過(guò)設(shè)計(jì)結(jié)構(gòu)良好的程序，以程序的靜態(tài)良好結(jié)構(gòu)保證程序動(dòng)態(tài)執(zhí)行的正確性，使程序易理解、易調(diào)試、易維護(hù)，以提高軟件開發(fā)的效率，減少出錯(cuò)率。②結(jié)構(gòu)化程序設(shè)計(jì)的構(gòu)成單元任何程序都可由順序、選擇、重復(fù)三種基本控制結(jié)構(gòu)來(lái)組成。③結(jié)構(gòu)化程序設(shè)計(jì)方法

其一：“自頂向下，逐步求精”的設(shè)計(jì)思想；其二：“獨(dú)立功能，一個(gè)入口，一個(gè)出口“的模塊化結(jié)構(gòu)；其三：“僅用三種基本控制結(jié)構(gòu)”的設(shè)計(jì)原則

11/15/202252①

結(jié)構(gòu)化程序設(shè)計(jì)目的通過(guò)設(shè)計(jì)結(jié)構(gòu)良好的程序，以1.6.3面向?qū)ο笈c抽象數(shù)據(jù)類型1.面向?qū)ο蟮母拍睿好嫦驅(qū)ο?對(duì)象+類+繼承+通信對(duì)象：指在應(yīng)用問(wèn)題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說(shuō)明等。類：具有相同屬性和服務(wù)的對(duì)象

繼承：是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?/p>

11/15/2022531.6.3面向?qū)ο笈c抽象數(shù)據(jù)類型1.面向?qū)ο蟮母拍睿好嫦驅(qū)γ嫦驅(qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)是封裝性、繼承性和多態(tài)性

與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的是定義在數(shù)據(jù)結(jié)構(gòu)上的一組操作。

基本操作主要有：⑴插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素；⑵刪除：刪去數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定數(shù)據(jù)元素；⑶更新：改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)元素的值，在概念上等價(jià)于刪除和插入操作的組合；⑷查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素（的位置和值）；⑸排序：（在線性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。

11/15/202254面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)是封裝性、繼承性和多態(tài)性與數(shù)據(jù)結(jié)構(gòu)密結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn)

結(jié)構(gòu)化的開發(fā)方法：是面向過(guò)程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。面向?qū)ο蟮拈_發(fā)方法：首先著眼于應(yīng)用問(wèn)題所涉及的對(duì)象，包括對(duì)象、對(duì)象屬性和要求的操作，從而建立對(duì)象結(jié)構(gòu)和為解決問(wèn)題需要執(zhí)行的時(shí)間序列。11/15/202255結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn)結(jié)構(gòu)化的開發(fā)方法：是面向過(guò)數(shù)學(xué)模型抽象數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)非形式算法偽語(yǔ)言程序可執(zhí)行程序用抽象數(shù)據(jù)類型的概念來(lái)指導(dǎo)問(wèn)題的求解過(guò)程：2．抽象數(shù)據(jù)類型與問(wèn)題求解方法

定義：

抽象數(shù)據(jù)類型（簡(jiǎn)稱ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來(lái)；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過(guò)程隱藏起來(lái)。11/15/202256數(shù)學(xué)模型抽象數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)非形式算法偽語(yǔ)言程序可執(zhí)行程序用數(shù)據(jù)的抽象匯編語(yǔ)言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等,它們是二進(jìn)制數(shù)據(jù)的抽象;高級(jí)語(yǔ)言中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。11/15/202257數(shù)據(jù)的抽象匯編語(yǔ)言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型的描述：ADTLinear_list數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對(duì)象，i=1，2，……，nn≥0；邏輯結(jié)構(gòu)所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關(guān)系<ai，ai+1>，ai無(wú)前趨，an無(wú)后繼；操作設(shè)L為L(zhǎng)inear_list Initial(L)初始化空線性表； Length(L)求線性表的表長(zhǎng)； Get(L,i)取線性表的第i個(gè)元素； Insert(L,i,b)在線性表的第i個(gè)位置插入元素b； Delete(L,i)刪除線性表的第i個(gè)元素；

11/15/202258抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型的描述：ADTLinear抽象數(shù)據(jù)類型實(shí)現(xiàn)傳統(tǒng)的面向過(guò)程的程序設(shè)計(jì)實(shí)現(xiàn)的三種方法：“包”、“模型”的設(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)（ObjectOrientedProgramming，簡(jiǎn)稱OOP）11/15/202259抽象數(shù)據(jù)類型實(shí)現(xiàn)傳統(tǒng)的面向過(guò)程的程序設(shè)計(jì)實(shí)現(xiàn)的三種方法：“包ADT的表示與實(shí)現(xiàn)

ADT的定義：ADT<ADT名>{數(shù)據(jù)對(duì)象:<數(shù)據(jù)對(duì)象的定義>結(jié)構(gòu)關(guān)系:<結(jié)構(gòu)關(guān)系的定義>基本操作:<基本操作的定義>

}ADT<ADT名>

基本操作的定義格式為：<操作名稱>(參數(shù)表)操作前提:<操作前提描述>操作結(jié)果:<操作結(jié)果描述>11/15/202260ADT的表示與實(shí)現(xiàn)ADT的定義：ADT<ADT名>基本關(guān)于參數(shù)傳遞：參數(shù)表中的參數(shù)有值參和變參兩種。用標(biāo)準(zhǔn)C語(yǔ)言表示和實(shí)現(xiàn)ADT描述時(shí)，主要有兩個(gè)方面：

二、用C語(yǔ)言函數(shù)實(shí)現(xiàn)各操作。一、通過(guò)結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。ADT的表示與實(shí)現(xiàn)

11/15/202261關(guān)于參數(shù)傳遞：參數(shù)表中的參數(shù)有值參和變參兩種。用標(biāo)準(zhǔn)C語(yǔ)言表1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格

1.算法表示格式與函數(shù)模塊化

[函數(shù)返回值類型]函數(shù)名（[形式參數(shù)及說(shuō)明]）{內(nèi)部數(shù)據(jù)說(shuō)明；執(zhí)行語(yǔ)句組；}/*函數(shù)名*/算法表示格式11/15/2022621.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格1.算法表示格式與函數(shù)1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格

函數(shù)的模塊化

1.算法表示格式與函數(shù)模塊化

[包含文件語(yǔ)句][宏定義語(yǔ)句][自定義類型語(yǔ)句][所有子函數(shù)的原型說(shuō)明][子函數(shù)1定義]...[子函數(shù)n定義][主函數(shù)定義]

11/15/2022631.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格函數(shù)的模塊化1.算法2.算法描述要點(diǎn)

1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格

加上必要的注釋

注釋形式可以用/*字符串*/避免函數(shù)返回值隱含說(shuō)明

預(yù)定義常量和類型

#defineTRUE1#defineFALSE0#defineMAXSIZE100#defineOK1#defineERROR011/15/2022642.算法描述要點(diǎn)1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格加上避免可能出現(xiàn)的二義性表達(dá)

注意不同的退出語(yǔ)句區(qū)別

return<表達(dá)式>或return：用于函數(shù)結(jié)束。break語(yǔ)句：可用在循環(huán)語(yǔ)句或switch語(yǔ)句中結(jié)束循環(huán)過(guò)程或跳出情況語(yǔ)句。continue語(yǔ)句：可用在循環(huán)語(yǔ)句中結(jié)束本次循環(huán)過(guò)程，進(jìn)入下一次循環(huán)過(guò)程。exit語(yǔ)句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。

使用有意義的函數(shù)名與變量名

2.算法描述要點(diǎn)

1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格

簡(jiǎn)化輸入、輸出表述規(guī)范多分支轉(zhuǎn)向11/15/202265避免可能出現(xiàn)的二義性表達(dá)注意不同的退出語(yǔ)句區(qū)別retur3.與參數(shù)傳遞的相關(guān)技術(shù)

1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格

變量的作用域

全局變量：程序中所有函數(shù)都可以訪問(wèn)的量

局部變量：只能在該函數(shù)中訪問(wèn)的量。

參數(shù)傳遞方式

參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù),又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。

11/15/2022663.與參數(shù)傳遞的相關(guān)技術(shù)1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)#include<stdio.h>viodswap1(inta,intb){intc;c=a;a=b;b=c;printf(“swap1中的a=%d,b=%d”,a,b);}viodswap2(int*a,int*b){intc;c=*a,*a=*b,*b=c;}關(guān)于參數(shù)傳遞示例源程序：11/15/202267#include<stdio.h>關(guān)于參數(shù)傳遞示例源程序：voidmain(){intx=100,y=800;swap1(x,y);/*調(diào)用函數(shù)swap1()*/printf(“\n調(diào)用swap1后x=%d,y=%d”,x,y);/*輸出調(diào)用swap1后的數(shù)據(jù)*/x=100;y=800;swap2(&x,&y);/*調(diào)用函數(shù)swap2()*/printf(“\n調(diào)用swap2后x=%d,y=%d”,x,y);/*輸出調(diào)用swap2后的數(shù)據(jù)*/}關(guān)于參數(shù)傳遞示例源程序：11/15/202268voidmain()關(guān)于參數(shù)傳遞示例源程序：11/10/24.函數(shù)結(jié)果的帶出方式

1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格

三種帶出方式:全程量、函數(shù)返回值、傳址參數(shù)若函數(shù)結(jié)果需要帶出多個(gè)值，該怎樣實(shí)現(xiàn)?可以采用①全局變量方式帶出，②通過(guò)地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體方式、指針?lè)绞剑﹥深惙绞街粊?lái)實(shí)現(xiàn)。

通過(guò)參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過(guò)全局變量是一種隱式參數(shù)傳遞，一個(gè)函數(shù)中對(duì)全局變量的改變會(huì)影響其它程序的調(diào)用，使用全局變量必須注意這個(gè)問(wèn)題。

11/15/2022694.函數(shù)結(jié)果的帶出方式1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格①全局變量方式：intMIN;/*全局變量*/

intfun1(inta[],intn)/*通過(guò)函數(shù)return返回最大值，通過(guò)全局變量MIN帶回最小值*/{ inti,max;max=MIN=a[0];//給最大值最小值賦初值for(i=0;i<n;i++){if(a[i]>max)max=a[i];if(a[i]<MIN)MIN=a[i];}return(max);}一個(gè)全局變量方式帶出的例子

11/15/202270①全局變量方式：intMIN;/*全局變量int*fun2(inta[],intn)/*將最大、最小值放到數(shù)組b中，通過(guò)return返回*/{ staticintb[2];b[0]=b[1]=a[0];//給最大值最小值賦初值 inti;for(i=1;i<n;i++){ if(a[i]>b[0]) b[0]=a[i]; if(a[i]<b[1]) b[1]=a[i];}return(b);}數(shù)組方式帶出的例子11/15/202271int*fun2(inta[],intn)數(shù)組方式帶出Data*fun3(inta[],intn)/*將最大、最小值放到結(jié)構(gòu)體指針p中，通過(guò)return返回*/{ Data*p; inti; p=(Data*)malloc(sizeof(Data*));//指針初始化 p->max=p->min=a[0];//給最大值最小值賦初值 for(i=1;i<n;i++) { if(a[i]>p->max) p->max=a[i]; if(a[i]<p->min) p->min=a[i]; } return(p);}結(jié)構(gòu)體方式帶出的例子11/15/202272Data*fun3(inta[],intn)結(jié)構(gòu)體方式Datafun4(inta[],intn)/*將最大、最小值放到結(jié)構(gòu)體p中，通過(guò)結(jié)構(gòu)體p帶回返回值*/{ Datap; inti; p.max=p.min=a[0];//給最大值最小值賦初值 for(i=1;i<n;i++) { if(a[i]>p.max) p.max=a[i]; if(a[i]<p.min) p.min=a[i]; } return(p);}指針?lè)绞綆С龅睦?1/15/202273Datafun4(inta[],intn)指針?lè)绞綆?.7關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)課程地位

數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)

關(guān)于本書內(nèi)容編寫說(shuō)明11/15/2022741.7關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程地位11/10/2數(shù)據(jù)結(jié)構(gòu)課程地位

數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫(kù)人工智能專業(yè)基礎(chǔ)課操作系統(tǒng)編譯原理非線性程序設(shè)計(jì)離散數(shù)學(xué)語(yǔ)言程序設(shè)計(jì)計(jì)算機(jī)原理設(shè)計(jì)11/15/202275數(shù)據(jù)結(jié)構(gòu)課程地位數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫(kù)人數(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í)間空間分析的技巧，培養(yǎng)良好的程序設(shè)計(jì)技能。

學(xué)習(xí)方法：

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，必須經(jīng)過(guò)大量的實(shí)踐，在實(shí)踐中體會(huì)構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計(jì)的技術(shù)。

11/15/202276數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)教學(xué)目標(biāo)：11/10/202276關(guān)于本書內(nèi)容編寫說(shuō)明

本書基本結(jié)構(gòu)

第一部分：數(shù)據(jù)結(jié)構(gòu)的基本概念（第1章） 第二部分：基本的數(shù)據(jù)結(jié)構(gòu) 包括：線性結(jié)構(gòu)—線性表、棧和隊(duì)列、串、數(shù)組與廣義表（第2—5章） 非線性結(jié)構(gòu)—樹、圖（第6、7章） 第三部分：基本技術(shù)

包括：查找技術(shù)與排序技術(shù)（第8、9、10章）

11/15/202277關(guān)于本書內(nèi)容編寫說(shuō)明本書基本結(jié)構(gòu)11/10/202277要點(diǎn)小結(jié)

1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)定義其上的運(yùn)算集合線性結(jié)構(gòu)（線性表、棧、隊(duì)列、字符串、數(shù)組、廣義表）

非線性結(jié)構(gòu)

順序存儲(chǔ)

非順序存儲(chǔ)

數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合這三個(gè)部分

11/15/202278要點(diǎn)小結(jié)1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)2.注意邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)別要點(diǎn)小結(jié)

邏輯結(jié)構(gòu)定義了數(shù)據(jù)元素之間的邏輯關(guān)系。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中實(shí)現(xiàn)。一種邏輯結(jié)構(gòu)可以采用不同存儲(chǔ)方式存放在計(jì)算機(jī)中，但都必須反映出要求的邏輯關(guān)系。11/15/2022792.注意邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)別要點(diǎn)小結(jié)邏輯結(jié)構(gòu)定義了數(shù)要點(diǎn)小結(jié)

3．面向?qū)ο蟾拍睿豪斫馐裁词菙?shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽規(guī)則。了解什么是面向?qū)ο?。抽象?shù)據(jù)類型的封裝性；Coad與Yourdon定義：面向?qū)ο?對(duì)象+類+繼承+通信；面向?qū)ο蠓椒ㄖ埸c(diǎn)在于應(yīng)用問(wèn)題所涉及的對(duì)象。

11/15/202280要點(diǎn)小結(jié)3．面向?qū)ο蟾拍睿豪斫馐裁词菙?shù)據(jù)類型、抽象數(shù)據(jù)類型4．算法與算法分析：理解算法的定義、算法的特性、算法的時(shí)間代價(jià)、算法的空間代價(jià)。

要點(diǎn)小結(jié)

算法與程序的不同之處需要從算法的特性來(lái)解釋；算法的正確性是最重要的要求，理解正確性的層次；算法的可讀性是必須考慮的，算法描述的格式與方法；算法的時(shí)間代價(jià)是指算法的漸進(jìn)時(shí)間復(fù)雜性度量。11/15/2022814．算法與算法分析：理解算法的定義、算法的特性、算法的時(shí)間代本演示文稿可能包含觀眾討論和即席反應(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)。

數(shù)據(jù)結(jié)構(gòu)課件用C語(yǔ)言描述11/15/202282數(shù)據(jù)結(jié)構(gòu)課件用C語(yǔ)言描述11/10/20221第1章緒論●1.7

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1.1

數(shù)據(jù)結(jié)構(gòu)的基本概念(定義)1.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究范圍）1.3

算法設(shè)計(jì)1.4

算法描述工具

1.5

對(duì)算法作性能評(píng)價(jià)1.6

數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示11/15/202283第1章緒論●1.7

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1.1

數(shù)據(jù)1.1數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：數(shù)據(jù)（Data）數(shù)據(jù)元素（DataElement）數(shù)據(jù)對(duì)象（DataObject）數(shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)類型(DataType)數(shù)據(jù)抽象與抽象數(shù)據(jù)類型11/15/2022841.1數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：11數(shù)據(jù)（Data）定義：數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。C編譯程序源程序（.c）目標(biāo)程序（.obj）可執(zhí)行程序（.exe）C鏈接程序例如對(duì)C源程序11/15/202285數(shù)據(jù)（Data）定義：C編譯程序源程序目標(biāo)程序可執(zhí)行程序C鏈數(shù)據(jù)元素（DataElement）定義：

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：..................北京1983.11河北女

趙虹玲101住

址

出生年月

籍

貫性

別

姓

名

學(xué)

號(hào)

數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)11/15/202286數(shù)據(jù)元素（DataElement）定義：.......數(shù)據(jù)對(duì)象（DataObject）

定義：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。整數(shù)集合：N={0，±1，±2，…}無(wú)限集字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集例如：11/15/202287數(shù)據(jù)對(duì)象（DataObject）定義：整數(shù)集合：N={0數(shù)據(jù)結(jié)構(gòu)（DataStructure）

定義：

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。例如表結(jié)構(gòu)：..................北京1983.11河北女

趙虹玲101住

址

出生年月

籍

貫性

別

姓

名

學(xué)

號(hào)

11/15/202288數(shù)據(jù)結(jié)構(gòu)（DataStructure）定義：.....數(shù)據(jù)結(jié)構(gòu)（DataStructure）樹型結(jié)構(gòu)圖結(jié)構(gòu)1254311/15/202289數(shù)據(jù)結(jié)構(gòu)（DataStructure）樹型結(jié)構(gòu)圖結(jié)構(gòu)1數(shù)據(jù)類型(DataType)

定義：

數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。如在高級(jí)語(yǔ)言中，整型類型的取值范圍為：-32768~+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。11/15/202290數(shù)據(jù)類型(DataType)定義：如在高級(jí)語(yǔ)言中，整型類數(shù)據(jù)類型(DataType)高級(jí)語(yǔ)言中的數(shù)據(jù)類型分為兩大類：1.原子類型，其值不可分解。如C語(yǔ)言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。指針類型屬于哪種類型？11/15/202291數(shù)據(jù)類型(DataType)高級(jí)語(yǔ)言中的數(shù)據(jù)類型分為兩大類數(shù)據(jù)抽象與抽象數(shù)據(jù)類型數(shù)據(jù)的抽象抽象數(shù)據(jù)類型(AbstractDataType)抽象數(shù)據(jù)類型實(shí)現(xiàn)

ADT的表示與實(shí)現(xiàn)面向?qū)ο蟮母拍罱Y(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點(diǎn)11/15/202292數(shù)據(jù)抽象與抽象數(shù)據(jù)類型數(shù)據(jù)的抽象11/10/2022111.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

運(yùn)算集合

11/15/2022931.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容邏輯結(jié)構(gòu)11/10/202212邏輯結(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)

集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)。11/15/202294邏輯結(jié)構(gòu)定義：形式化描述：四類基本的結(jié)構(gòu)11/10/2022集合結(jié)構(gòu)定義：

結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無(wú)任何其它關(guān)系。

集合例如：11/15/202295集合結(jié)構(gòu)定義：集合例如：11/10/202214線性結(jié)構(gòu)定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系。

例如：線性表11/15/202296線性結(jié)構(gòu)定義：例如：線性表11/10/202215樹型結(jié)構(gòu)定義：

結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系。

例如：

樹11/15/202297樹型結(jié)構(gòu)定義：例如：樹11/10/202216圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。例如：

圖11/15/202298圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)定義：例如：圖11/10/2綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)——線性表、棧、隊(duì)、字符串?dāng)?shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)——樹、圖邏輯結(jié)構(gòu)11/15/202299綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)——線性表、棧、隊(duì)存儲(chǔ)結(jié)構(gòu)

定義：

存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。

形式化描述：D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲(chǔ)空間M單元的映像S，D→M，即對(duì)于每一個(gè)d，d∈D,都有唯一的z∈M使S（D）=Z,同時(shí)這個(gè)映像必須明顯或隱含地體現(xiàn)關(guān)系R。11/15/2022100存儲(chǔ)結(jié)構(gòu)定義：形式化描述：11/10/202219邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映像與元素本身映像，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示方法：順序映像（順序存儲(chǔ)結(jié)構(gòu)）非順序映像（非順序存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)

11/15/2022101邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映像與元素本運(yùn)算集合例如工資表：編號(hào)姓名性別基本工資工齡工資應(yīng)扣工資實(shí)發(fā)工資100001張愛芬女345．67145．4530．00451．12100002李

林

男

445．90185．6045．00586．50100003劉曉峰

男

345．00130．0025．00450．00100004趙

俊

女

560．90225．9065．00721．80100005孫

濤

男

450．60190．8050．00591．80……

……………100121張興強(qiáng)

男

1025．98365．53100．001291.5111/15/2022102運(yùn)算集合例如工資表：編號(hào)姓名性別基本工資工齡工資應(yīng)扣數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合：按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的映像方式把它們存放在計(jì)算機(jī)存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。

11/15/2022103數(shù)據(jù)結(jié)構(gòu)的內(nèi)容綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，11.3算法

算法（Algorithm）定義

算法的特性

算法設(shè)計(jì)的要求

11/15/20221041.3算法算法（Algorithm）定義11/10/算法（Algorithm）定義定義： Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.

算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。

11/15/2022105算法（Algorithm）定義定義：11/10/202224算法的特性1.有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)2.確定性：算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性得以實(shí)現(xiàn)。

3.輸入：有多個(gè)或0個(gè)輸入

4.輸出：至少有一個(gè)或多個(gè)輸出。5.可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)基本運(yùn)算執(zhí)行有限次而完成。

11/15/2022106算法的特性1.有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循算法設(shè)計(jì)的要求

算法的正確性

算法特征：

可讀性

健壯性

高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問(wèn)題給出算法如下：max=0;for（i=1；i<=n;i++）{scanf("%f",x);if(x>max)max=x;}11/15/2022107算法設(shè)計(jì)的要求算法的正確性算法特征：可讀性健壯性1.4算法描述的工具

概述：

算法+數(shù)據(jù)結(jié)構(gòu)=程序

算法、語(yǔ)言、程序的關(guān)系

設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟類描述算法的語(yǔ)言選擇11/15/20221081.4算法描述的工具概述：11/10/202227算法、語(yǔ)言、程序的關(guān)系1.算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存儲(chǔ)關(guān)系描述）。2.描述算法的工具：算法可用自然語(yǔ)言、框圖或高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行描述。3.程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。11/15/2022109算法、語(yǔ)言、程序的關(guān)系1.算法：描述了數(shù)據(jù)對(duì)象的元素之間的設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟1.找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系2.確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算3.考慮數(shù)據(jù)元素的存儲(chǔ)表示4.選擇描述算法的語(yǔ)言5.設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語(yǔ)言加以描述。11/15/2022110設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟1.找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系類描述算法的語(yǔ)言選擇類語(yǔ)言：類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，具有高級(jí)語(yǔ)言的一般語(yǔ)句設(shè)施，撇掉語(yǔ)言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。11/15/2022111類描述算法的語(yǔ)言選擇類語(yǔ)言：類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)3.賦值語(yǔ)句對(duì)C語(yǔ)言作以下描述：（1）簡(jiǎn)單賦值

1）〈變量名〉=〈表達(dá)式〉2）〈變量〉++，3）〈變量〉--，（2）串聯(lián)賦值〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉

11/15/20221123.賦值語(yǔ)句對(duì)C語(yǔ)言作以下描述：（1）簡(jiǎn)單賦值對(duì)C語(yǔ)言作以下描述：（4）條件賦值〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉:〈表達(dá)式2〉

（3）成組賦值(<變量>,<變量2>,<變量3>,…<變量k〉=(<表達(dá)式1>,<表達(dá)式2>,<表達(dá)式3>,…<表達(dá)式k>)〈數(shù)組名1〉[下標(biāo)1][下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1][下標(biāo)2]

11/15/2022113對(duì)C語(yǔ)言作以下描述：（4）條件賦值〈變量名〉=〈條件表達(dá)式〉4.條件選擇語(yǔ)句對(duì)C語(yǔ)言作以下描述：if(<表達(dá)式>)語(yǔ)句;if(<表達(dá)式>)語(yǔ)句1;else語(yǔ)句2;11/15/20221144.條件選擇語(yǔ)句對(duì)C語(yǔ)言作以下描述：if(<表達(dá)式>)情況語(yǔ)句switch(<表達(dá)式>）{case判斷值1:語(yǔ)句組1；break;case判斷值2:語(yǔ)句組2；break;……case判斷值n:語(yǔ)句組n;break;[default:語(yǔ)句組；break;]}對(duì)C語(yǔ)言作以下描述：11/15/2022115情況語(yǔ)句switch(<表達(dá)式>）case判斷值n對(duì)C語(yǔ)言作以下描述：5.循環(huán)語(yǔ)句for語(yǔ)句for(<表達(dá)式1>；<表達(dá)式2>；<表達(dá)式3>）{循環(huán)體語(yǔ)句；}11/15/2022116對(duì)C語(yǔ)言作以下描述：5.循環(huán)語(yǔ)句for語(yǔ)句for(<表達(dá)while語(yǔ)句while(<條件表達(dá)式>）{循環(huán)體語(yǔ)句；}對(duì)C語(yǔ)言作以下描述：do–while語(yǔ)句do{循環(huán)體語(yǔ)句}while(<條件表達(dá)式>）

11/15/2022117while語(yǔ)句while(<條件表達(dá)式>）對(duì)C語(yǔ)言作以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ǔ)空間來(lái)判斷一個(gè)算法的優(yōu)劣。

性能評(píng)價(jià)有關(guān)數(shù)量關(guān)系計(jì)算

11/15/20221181.5對(duì)算法作性能評(píng)價(jià)評(píng)價(jià)算法的標(biāo)準(zhǔn)：11/10/20性能評(píng)價(jià)定義：

對(duì)問(wèn)題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。問(wèn)題規(guī)模N—對(duì)不同的問(wèn)題其含義不同：

對(duì)矩陣是階數(shù)；

對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)；對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。11/15/2022119性能評(píng)價(jià)定義：?jiǎn)栴}規(guī)模N—對(duì)不同的問(wèn)題其含義不同：11/10有關(guān)數(shù)量關(guān)系計(jì)算

數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間——算法在機(jī)器中所耗費(fèi)時(shí)間。數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間——算法在機(jī)器中所占存儲(chǔ)量。關(guān)于算法執(zhí)行時(shí)間語(yǔ)句頻度

算法的時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)

最壞時(shí)間復(fù)雜度

算法的空間復(fù)雜度

11/15/2022120有關(guān)數(shù)量關(guān)系計(jì)算數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間——算法在機(jī)器中所耗關(guān)于算法執(zhí)行時(shí)間定義：

一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。分析：

不是針對(duì)實(shí)際執(zhí)行時(shí)間精確算出算法執(zhí)行的具體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。11/15/2022121關(guān)于算法執(zhí)行時(shí)間定義：分析：11/10/202240語(yǔ)句頻度

定義： 語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個(gè)矩陣相乘算法語(yǔ)句對(duì)應(yīng)的語(yǔ)句頻度1 for（i=0；i<n;i++）n+12 for（j=0；j<n;j++）n(n+1)3{c[i][j]=0;n24for(k=0;k<n;k++)n2(n+1)c[i][j]=c[i][j]+a[i][k]*b[k][j];n3

}

總執(zhí)行次數(shù)：Tn=2n3+3n2+2n+111/15/2022122語(yǔ)句頻度定義：例如：算法語(yǔ)句算法的時(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;時(shí)間復(fù)雜度為O(n2),稱為平方階。11/15/2022123算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：常用的時(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ù)雜度由小到大排列的頻率表：11/15/2022124常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率表：log2nnnlog2nn2n32n一般講：前3種可實(shí)現(xiàn)，后3種雖理論上是可實(shí)現(xiàn)的，實(shí)際上只有對(duì)N限制在很小范圍才有意義，當(dāng)N較大時(shí)，不可能實(shí)現(xiàn)。

01011212248424816641638246451225641664256509665536532160102432768214748364811/15/2022125常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率表：log2nn最壞時(shí)間復(fù)雜度

定義：

討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。例如冒泡排序算法11/15/2022126最壞時(shí)間復(fù)雜度定義：例如冒泡排序算法11/10/20224voidbubble(inta[],intlength){將a中整數(shù)數(shù)組重新排序，達(dá)到遞增有序}inti=0,j,temp;intchange;do{ change=false; for(j=1;j<length-i;j++) if(a[j]>a[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ù)雜度

11/15/2022127voidbubble(inta[],intlengt算法的空間復(fù)雜度

定義：

用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記做：S(n)=O(f(n))。11/15/2022128算法的空間復(fù)雜度定義：用空間復(fù)雜度作為算法所需存儲(chǔ)1.6數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示

1.6.1數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的關(guān)聯(lián)性

問(wèn)題描述：欲求1名學(xué)生10次C語(yǔ)言程序設(shè)計(jì)的測(cè)試成績(jī)總分與平均分。其中10次測(cè)驗(yàn)的成績(jī)分別為：80，85，77，56，68，83，90，92，80，98。

11/15/20221291.6數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示1.6.1數(shù)據(jù)結(jié)構(gòu)與程序程序示例1-1：main(){intsum，verage；/*總分，平均分*/intt1,t2,t3,t4,t5,t6,t7,t8,t9,t10；/*10個(gè)變量存10次成績(jī)*/t1=80；t2=85；t3=77；t4=56；t5=68；/*分別賦值*/t6=83；t7=90；t8=92；t9=80；t10=98;sum=t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;/*計(jì)算總分*/average=sum/10;/*計(jì)算平均分*/printf(“總分=%d\n”,sum);printf(“平均分=%d\n”,average);}11/15/2022130程序示例1-1：main()11/10/202249根據(jù)測(cè)試次數(shù)與測(cè)試成績(jī)的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲(chǔ)測(cè)驗(yàn)成績(jī)，提高了程序的適用范圍。main(){intsum，erage；inti;intt[10]=80，85，77，56，68，83，90，92，80，98}/*分別賦值*/sum=0;/*總分置初值*/for(i=0;i<10;i++)sum=sum+t[i];average=sum/10;/*計(jì)算平均分*/printf(“總分=%d\n”,sum);printf(“平均分=%d\n”,average);