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

1、2022-3-1912022-3-192第1章 緒 論1.71.7 關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) l1.11.1 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念( (定義定義) )l1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究范圍）（研究范圍）l1.31.3 算法算法設(shè)計(jì)設(shè)計(jì)l1.41.4 算法描述工具算法描述工具 l1.51.5 對(duì)算法作性能評(píng)價(jià)對(duì)算法作性能評(píng)價(jià)l1.61.6 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與與C C語(yǔ)言表示語(yǔ)言表示2022-3-1931.1 數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：n數(shù)據(jù)（Data）n數(shù)據(jù)元素（Data Element） n數(shù)據(jù)對(duì)象（Data Object） n數(shù)據(jù)

2、結(jié)構(gòu)（Data Structure） n數(shù)據(jù)類型(Data Type) n數(shù)據(jù)抽象與抽象數(shù)據(jù)類型2022-3-194數(shù)據(jù)（Data）n定義： 數(shù)據(jù)是數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合機(jī)器且能被處理的各種符號(hào)集合。 數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。C編譯程序源程序源程序（.c）目標(biāo)程序目標(biāo)程序（.obj）可執(zhí)行程序可執(zhí)行程序（.exe）C鏈接程序例如對(duì)C源程序2022-3-195數(shù)據(jù)元素（Data Element）n定義定義： 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位組成數(shù)據(jù)的基本單位 ，是數(shù)

3、據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：. . . . . . 北京1983.11河北女 趙虹玲101 住 址 出生年月 籍 貫性 別 姓 名 學(xué) 號(hào) 數(shù)據(jù)元素?cái)?shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)2022-3-196數(shù)據(jù)對(duì)象（Data Object） n定義定義： 數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集性質(zhì)相同的數(shù)據(jù)元素的集合合，是數(shù)據(jù)的一個(gè)子集。整數(shù)集合：N=0，1，2， 無(wú)限集字符集合：C=A，B，Z 有限集例如：2022-3-197數(shù)據(jù)結(jié)構(gòu)（Data Structure） n定義： 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特?cái)?shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合定關(guān)系的數(shù)據(jù)元

4、素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。 例如表結(jié)構(gòu)：. . . . . . 北京1983.11河北女 趙虹玲101 住 址 出生年月 籍 貫性 別 姓 名 學(xué) 號(hào) 2022-3-198數(shù)據(jù)結(jié)構(gòu)（Data Structure）教研室實(shí)驗(yàn)室 系處研究機(jī)構(gòu)學(xué)校樹型結(jié)構(gòu)圖結(jié)構(gòu) 1 2 5 4 32022-3-199數(shù)據(jù)類型(Data Type) n定義： 數(shù)據(jù)類型是一組性質(zhì)相同的值集合以數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱及定義在這個(gè)值集合上的一組操作的總稱。如在高級(jí)語(yǔ)言中，整型類型的取值范圍為：-32768+32767，

5、運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。2022-3-1910數(shù)據(jù)類型(Data Type)n高級(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)的，也可以是結(jié)構(gòu)的。指針類型屬于哪種類型？指針類型屬于哪種類型？2022-3-1911數(shù)據(jù)抽象與抽象數(shù)據(jù)類型 n數(shù)據(jù)的抽象n抽象數(shù)據(jù)類型(Abstract Data Type) n抽象數(shù)據(jù)類型實(shí)現(xiàn) nADT的表示與實(shí)現(xiàn)n面向?qū)ο蟮母拍頽結(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點(diǎn)

6、2022-3-19121.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 n邏輯結(jié)構(gòu) n存儲(chǔ)結(jié)構(gòu) n運(yùn)算集合 2022-3-1913邏輯結(jié)構(gòu)n定義： 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系描述。l形式化描述：Data_Structure=（D,R）其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。l四類基本的結(jié)構(gòu) 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)。2022-3-1914集合結(jié)構(gòu)n定義定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無(wú)任何其它關(guān)系。一個(gè)集合的關(guān)系外，無(wú)任何其它關(guān)系。 集合集合例如：2022-3-1915線性結(jié)構(gòu)n定義：定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著結(jié)構(gòu)中的數(shù)據(jù)元

7、素之間存在著一對(duì)一對(duì)一的線性關(guān)系。一的線性關(guān)系。 例如：線性表線性表2022-3-1916樹型結(jié)構(gòu)n定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一對(duì)多的層次關(guān)系。多的層次關(guān)系。 例如： 樹樹2022-3-1917圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) n定義：定義： 結(jié)構(gòu)中的數(shù)據(jù)元素結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)之間存在著多對(duì)多的任意關(guān)系。多的任意關(guān)系。例如： 圖2022-3-1918綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)線性結(jié)構(gòu)線性表、棧、隊(duì)、字符串線性表、棧、隊(duì)、字符串 數(shù)組、廣義表數(shù)組、廣義表邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)樹、圖樹、圖邏輯結(jié)構(gòu)邏輯

8、結(jié)構(gòu)2022-3-1919存儲(chǔ)結(jié)構(gòu) n定義： 存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)映象算機(jī)中存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。 l形式化描述： D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲(chǔ)空間M單元的映像S ，DM，即對(duì)于每一個(gè)d， dD,都有唯一的zM使S（D）=Z, 同時(shí)這個(gè)映像必須明顯或隱含地體現(xiàn)關(guān)系R。2022-3-1920邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系關(guān)系為：為：存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映像與元素本身映像，是數(shù)是邏輯關(guān)系的映像與元素本身映像，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)邏

9、輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象是數(shù)據(jù)結(jié)構(gòu)的抽象。 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示方法：數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示方法：順序映像順序映像 （順序存儲(chǔ)結(jié)構(gòu)）（順序存儲(chǔ)結(jié)構(gòu)） 非順序映像非順序映像（非順序存儲(chǔ)結(jié)構(gòu)（非順序存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)2022-3-1921運(yùn)算集合例如工資表：編編 號(hào)號(hào)姓姓 名名性別性別基本工資基本工資工齡工資工齡工資應(yīng)扣工資應(yīng)扣工資實(shí)發(fā)工資實(shí)發(fā)工資100001100001張愛(ài)芬張愛(ài)芬女女34534567671451454545303000004514511212100002100002李李 林林 男男 44544590901851856060454500005865

10、865050100003100003劉曉峰劉曉峰 男男 34534500001301300000252500004504500000100004100004趙趙 俊俊 女女 56056090902252259090656500007217218080100005100005孫孫 濤濤 男男 45045060601901908080505000005915918080 100121100121張興強(qiáng)張興強(qiáng) 男男 102510259898365365535310010000001291.511291.512022-3-1922數(shù)據(jù)結(jié)構(gòu)的內(nèi)容數(shù)據(jù)結(jié)構(gòu)的內(nèi)容綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏

11、輯結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和和運(yùn)算集合運(yùn)算集合：按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的映像方式把它們存放在計(jì)算機(jī)存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。 2022-3-19231.3 算法 n算法（算法（AlgorithmAlgorithm）定義）定義 n算法的特性算法的特性 n算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求 2022-3-1924算法（Algorithm）定義n定義： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type

12、 of problem. 算法是規(guī)則的有限集合，是為解決算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。特定問(wèn)題而規(guī)定的一系列操作。 2022-3-1925算法的特性1. 有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)2. 確定性：算法中的每一個(gè)步驟必須有確定含義，無(wú)二算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性得以實(shí)現(xiàn)。義性得以實(shí)現(xiàn)。 3. 輸 入： 有多個(gè)或有多個(gè)或0個(gè)輸入個(gè)輸入 4. 輸 出： 至少有一個(gè)或多個(gè)輸出。至少有一個(gè)或多個(gè)輸出。5. 可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)基本原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)基本運(yùn)算執(zhí)行有限次而

13、完成。運(yùn)算執(zhí)行有限次而完成。 2022-3-1926算法設(shè)計(jì)的要求 n算法的正確性 算法特征：l 可讀性 l 健壯性 l 高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問(wèn)題給出算法如下： max=0; for（i=1 ；imax) max=x; 2022-3-19271.4 算法描述的工具 n概述：算法+數(shù)據(jù)結(jié)構(gòu)=程序 n算法、語(yǔ)言、程序的關(guān)系 n設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟n類描述算法的語(yǔ)言選擇2022-3-1928算法、語(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ī)

14、中的實(shí)現(xiàn)。2022-3-1929設(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ǔ)言加以描述。2022-3-1930類描述算法的語(yǔ)言選擇n類語(yǔ)言：類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，具有高級(jí)語(yǔ)言的一般語(yǔ)句設(shè)施，撇掉語(yǔ)言中的細(xì)節(jié)，具有高級(jí)語(yǔ)言的一般語(yǔ)句設(shè)施，撇掉語(yǔ)言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述以便把注意力主要集中在算法處理步驟本身的描述上。上。2022-3-19313.賦值語(yǔ)句賦值語(yǔ)句

15、對(duì)C語(yǔ)言作以下描述：（1）簡(jiǎn)單賦值簡(jiǎn)單賦值 1）變量名）變量名=表達(dá)式表達(dá)式 2） 變量變量+， 3） 變量變量- -，（2）串聯(lián)賦值串聯(lián)賦值變量變量1=變量變量2=變量變量3=變量變量k=表達(dá)式表達(dá)式 2022-3-1932對(duì)C語(yǔ)言作以下描述：（4）條件賦值條件賦值變量名變量名=條件表達(dá)式？表達(dá)式條件表達(dá)式？表達(dá)式1:表達(dá)式表達(dá)式2 （3）成組賦值成組賦值(, 變量變量k=(, , , )數(shù)組名數(shù)組名1 1 下標(biāo)下標(biāo)11下標(biāo)下標(biāo)2=2=數(shù)組名數(shù)組名2 2 下標(biāo)下標(biāo)11下標(biāo)下標(biāo)22 2022-3-19334.條件選擇語(yǔ)句對(duì)C語(yǔ)言作以下描述：if () 語(yǔ)句;if () 語(yǔ)句1; else 語(yǔ)句

16、2;2022-3-1934情況語(yǔ)句switch (） case 判斷值1: 語(yǔ)句組 1； break; case 判斷值2: 語(yǔ)句組 2； break; case 判斷值n: 語(yǔ)句組n; break; default: 語(yǔ)句組； break; 對(duì)C語(yǔ)言作以下描述：2022-3-1935對(duì)C語(yǔ)言作以下描述：5.循環(huán)語(yǔ)句循環(huán)語(yǔ)句for 語(yǔ)句語(yǔ)句for (；）循環(huán)體語(yǔ)句；循環(huán)體語(yǔ)句；2022-3-1936while 語(yǔ)句語(yǔ)句while (） 循環(huán)體語(yǔ)句；循環(huán)體語(yǔ)句； 對(duì)C語(yǔ)言作以下描述：do while 語(yǔ)句語(yǔ)句do 循環(huán)體語(yǔ)句循環(huán)體語(yǔ)句 while (） 2022-3-19371.5 對(duì)算法作性能

17、評(píng)價(jià) n評(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)劣。 n性能評(píng)價(jià) n有關(guān)數(shù)量關(guān)系計(jì)算有關(guān)數(shù)量關(guān)系計(jì)算 2022-3-1938性能評(píng)價(jià)性能評(píng)價(jià)n定義：定義： 對(duì)問(wèn)題規(guī)模與該算法在運(yùn)行時(shí)所占的空間對(duì)問(wèn)題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與與所耗費(fèi)的時(shí)間所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。問(wèn)題規(guī)模問(wèn)題規(guī)模N對(duì)不同的問(wèn)題其含義不同：對(duì)不同的問(wèn)題其含義不同： 對(duì)矩陣是階數(shù)；對(duì)矩陣是階數(shù)； 對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)； 對(duì)

18、圖是頂點(diǎn)個(gè)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)； 對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。2022-3-1939有關(guān)數(shù)量關(guān)系計(jì)算 數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間算法在機(jī)器中所耗算法在機(jī)器中所耗費(fèi)時(shí)間。費(fèi)時(shí)間。數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間算法在機(jī)器中所占算法在機(jī)器中所占存儲(chǔ)量。存儲(chǔ)量。n關(guān)于算法執(zhí)行時(shí)間關(guān)于算法執(zhí)行時(shí)間n語(yǔ)句頻度語(yǔ)句頻度 n算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度n數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) n最壞時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度 n算法的空間復(fù)雜度算法的空間復(fù)雜度 2022-3-1940關(guān)于算法執(zhí)行時(shí)間n定義定義： 一個(gè)算法

19、的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。l分析分析： 不是針對(duì)實(shí)際執(zhí)行時(shí)間精確算出算法執(zhí)行的具不是針對(duì)實(shí)際執(zhí)行時(shí)間精確算出算法執(zhí)行的具體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。從中得到算法執(zhí)行時(shí)間的信息。2022-3-1941語(yǔ)句頻度 n定義：定義：語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。的次數(shù)。例如：例如：兩個(gè)兩個(gè)矩陣矩陣相乘相乘算法語(yǔ)句算法語(yǔ)句 對(duì)應(yīng)的對(duì)應(yīng)的語(yǔ)句頻度語(yǔ)句頻度 1 1forfor（i=

20、0i=0；i n;i+i n;i+） n+1n+1 2 2for for （j=0j=0；jn;j+jn;j+） n n( (n+1) ) 3 cij=0; n 3 cij=0; n2 2 4 for (k=0;k n; k+) n 4 for (k=0;k n; k+) n2 2 (n+1) cij=cij+aik cij=cij+aik* *bkj; nbkj; n3 3 總執(zhí)行次數(shù)：總執(zhí)行次數(shù)：Tn=2n3+3n2 +2n+12022-3-1942算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：記做： T(n)=O(f(n)例如給出例如給出

21、X=X+1（1）x=x+1 ；時(shí)間復(fù)雜度為；時(shí)間復(fù)雜度為O(1)，稱為常量階；，稱為常量階；（2）for (i=1; i= n; i+) x=x+1; 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)，稱為線性階；，稱為線性階；（3）for (i=1; i= n; i+)for (j=1;j= n; j+) x=x+1; 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n2), 稱為平方階。稱為平方階。2022-3-1943常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) n數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè):O(1)常數(shù)型常數(shù)型O(n)線性型線性型O(n2)平方型平方型O(n3)立方型立方型O(2n)指數(shù)型指數(shù)型O(log2n)對(duì)數(shù)型對(duì)數(shù)型O(

22、nlog2n)二維型二維型按時(shí)間復(fù)雜度由小到大排列的頻率表：按時(shí)間復(fù)雜度由小到大排列的頻率表：2022-3-1944常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)n常用的時(shí)間復(fù)雜度頻率常用的時(shí)間復(fù)雜度頻率表：表：log2nnnlog2nn2n32n一般講：前3種可實(shí)現(xiàn)，后3種雖理論上是可實(shí)現(xiàn)的，實(shí)際上只有對(duì)N限制在很小范圍才有意義，當(dāng)N較大時(shí)，不可能實(shí)現(xiàn)。 0101121224842481664163824645122564166425650966553653216010243276821474836482022-3-1945最壞時(shí)間復(fù)雜度 n定義：定義：討論算法在最壞情況下的時(shí)間復(fù)雜度，即討論算法在最壞情況下的時(shí)

23、間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。界。例如冒泡排序算法例如冒泡排序算法2022-3-1946void bubble(int a, int length)將將a中整數(shù)數(shù)組重新排序，達(dá)到中整數(shù)數(shù)組重新排序，達(dá)到遞增有序遞增有序 int i=0, j, temp; int change ; do change=false ; for(j=1;jaj+1) temp= aj;aj=aj+1;aj+1=temp;change=true; i=i+1 ; while(ilength | change=true )最壞時(shí)間復(fù)雜最壞時(shí)間復(fù)雜度度2022

24、-3-1947算法的空間復(fù)雜度 n定義： 用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度， 記做：記做： S(n)=O(f(n)。2022-3-19481.6 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言表示語(yǔ)言表示 1.6.1 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的關(guān)聯(lián)性數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的關(guān)聯(lián)性 問(wèn)題描述：?jiǎ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。 2022-3-1949程序示例程序示例1-1：main() int sum，verage； /*總分，平均分*/ int t1,t2,t

25、3,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(“總分=%dn”,sum); printf(“平均分=%dn”, average); 2022-3-1950根據(jù)測(cè)試次數(shù)與測(cè)試成績(jī)的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲(chǔ)測(cè)驗(yàn)成績(jī)，提高了程序的根據(jù)測(cè)試次數(shù)與測(cè)試成績(jī)的關(guān)系，采用數(shù)組

26、結(jié)構(gòu)存儲(chǔ)測(cè)驗(yàn)成績(jī)，提高了程序的適用范圍。適用范圍。main() int sum，erage；int i; int t10 =80，85，77，56，68，83，90，92，80，98 /*分別賦值*/ sum=0; /*總分置初值*/ for (i=0; i10; i+) sum=sum+ti; average=sum/10; /*計(jì)算平均分*/ printf(“總分=%dn”,sum); printf(“平均分=%dn”, average); 程序示例程序示例1-2：2022-3-19511.6.2 結(jié)構(gòu)化程序設(shè)計(jì)與函數(shù)的模塊化結(jié)構(gòu)化程序設(shè)計(jì)與函數(shù)的模塊化 結(jié)構(gòu)化程序設(shè)計(jì) ：是為使程序具有合

27、理的結(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) 2022-3-1952 結(jié)構(gòu)化程序設(shè)計(jì)目的通過(guò)設(shè)計(jì)結(jié)構(gòu)良好的程序，以程序的靜態(tài)良好結(jié)構(gòu)保證以程序的靜態(tài)良好結(jié)構(gòu)保證程序動(dòng)態(tài)執(zhí)行的正確性程序動(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ì)思想的設(shè)計(jì)思想 ；其二：“獨(dú)立功能，

28、一個(gè)入口，一個(gè)出口獨(dú)立功能，一個(gè)入口，一個(gè)出口“的模塊化結(jié)構(gòu)的模塊化結(jié)構(gòu)； 其三：“僅用三種基本控制結(jié)構(gòu)僅用三種基本控制結(jié)構(gòu)”的設(shè)計(jì)原則的設(shè)計(jì)原則 2022-3-19531.6.3 面向?qū)ο笈c抽象數(shù)據(jù)類型1.1.面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍睿好嫦驅(qū)ο?對(duì)象+類+繼承+通信對(duì)象：指在應(yīng)用問(wèn)題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說(shuō)明等 。類：具有相同屬性和服務(wù)的對(duì)象 繼承：是是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?2022-3-1954面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)是封裝性、繼承性和多態(tài)性面向?qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)是封裝性、繼承性和多態(tài)性 與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的是定義在數(shù)據(jù)結(jié)構(gòu)上的一組操作。 基本操作主要有：基本操作主要有：

29、插入插入：在數(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ù)元素按值由小到大或由大到小的次序排列。 2022-3-1955結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn) n結(jié)構(gòu)化的開發(fā)方法：是面向過(guò)程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。l面向?qū)ο蟮拈_發(fā)方法面向?qū)ο蟮拈_發(fā)方法：首先著眼于應(yīng)用問(wèn)題所涉及的對(duì)象，包括對(duì)象、對(duì)象屬性和要求的操作，從而建立對(duì)象結(jié)構(gòu)和

30、為解決問(wèn)題需要執(zhí)行的時(shí)間序列。2022-3-1956數(shù)學(xué)模型數(shù)學(xué)模型抽象數(shù)據(jù)模型抽象數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)非形式算法非形式算法偽語(yǔ)言程序偽語(yǔ)言程序可執(zhí)行程序可執(zhí)行程序用抽象數(shù)據(jù)類型的概念來(lái)指導(dǎo)問(wèn)題的求解過(guò)程：用抽象數(shù)據(jù)類型的概念來(lái)指導(dǎo)問(wèn)題的求解過(guò)程：2 2抽象數(shù)據(jù)類型與問(wèn)題求解方法抽象數(shù)據(jù)類型與問(wèn)題求解方法 n定義：抽象數(shù)據(jù)類型（簡(jiǎn)稱抽象數(shù)據(jù)類型（簡(jiǎn)稱ADTADT）是指基于一類邏輯）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作組操作。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱

31、藏起來(lái)；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過(guò)程隱藏隱藏起來(lái)；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過(guò)程隱藏起來(lái)。起來(lái)。2022-3-1957數(shù)據(jù)的抽象n匯編語(yǔ)言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等, 它們是二進(jìn)制數(shù)據(jù)的抽象; l高級(jí)語(yǔ)言中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。2022-3-1958抽象數(shù)據(jù)類型n線性表的抽象數(shù)據(jù)類型的描述：ADT Linear_list數(shù)據(jù)元素?cái)?shù)據(jù)元素 所有所有a ai i屬于同一數(shù)據(jù)對(duì)象，屬于同一數(shù)據(jù)對(duì)象，i=1i=1，2 2，n n0n n0；邏輯結(jié)構(gòu)邏輯

32、結(jié)構(gòu) 所有數(shù)據(jù)元素所有數(shù)據(jù)元素a ai i（i=1i=1，2 2，n-1n-1）存在次序關(guān)系）存在次序關(guān)系 a ，a ai i無(wú)前趨，無(wú)前趨，a an n無(wú)后繼；無(wú)后繼；操作操作 設(shè)設(shè)L L為為L(zhǎng)inear_listLinear_listInitial(L)Initial(L)初始化空線性表；初始化空線性表；Length(L)Length(L)求線性表的表長(zhǎng)；求線性表的表長(zhǎng)；Get(L,i)Get(L,i)取線性表的第取線性表的第i i個(gè)元素；個(gè)元素；Insert(L,i,b)Insert(L,i,b)在線性表的第在線性表的第i i個(gè)位置插入元素個(gè)位置插入元素b b；Delete(L,i)De

33、lete(L,i)刪除線性表的第刪除線性表的第i i個(gè)元素；個(gè)元素； 2022-3-1959抽象數(shù)據(jù)類型實(shí)現(xiàn)n傳統(tǒng)的面向過(guò)程的程序設(shè)計(jì)傳統(tǒng)的面向過(guò)程的程序設(shè)計(jì)實(shí)現(xiàn)的三種方法：l“包包”、“模型模型”的設(shè)計(jì)方法的設(shè)計(jì)方法l面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)（Object Oriented Programming，簡(jiǎn)稱OOP）2022-3-1960ADT的表示與實(shí)現(xiàn) nADT的定義：ADT 數(shù)據(jù)對(duì)象: 結(jié)構(gòu)關(guān)系: 基本操作: ADT 基本操作的定義格式為： (參數(shù)表) 操作前提: 操作結(jié)果:2022-3-1961l關(guān)于參數(shù)傳遞：參數(shù)表中的參數(shù)有值參和變參兩種。用標(biāo)準(zhǔn)C語(yǔ)言表示和實(shí)現(xiàn)ADT描述時(shí)，

34、主要有兩個(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)的表示與實(shí)現(xiàn)2022-3-19621.6.4 算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描述規(guī)范與設(shè)計(jì)風(fēng)格 1. 算法表示格式與函數(shù)模塊化 函數(shù)返回值類型 函數(shù)名（形式參數(shù)及說(shuō)明） 內(nèi)部數(shù)據(jù)說(shuō)明； 執(zhí)行語(yǔ)句組； /*函數(shù)名*/ 算法表示格式2022-3-19631.6.4 算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描述規(guī)范與設(shè)計(jì)風(fēng)格 函數(shù)的模塊化 1. 算法表示格式與函數(shù)模塊化 包含文件語(yǔ)句包含文件語(yǔ)句宏定義語(yǔ)句宏定義語(yǔ)句自定義類型語(yǔ)句

35、自定義類型語(yǔ)句所有子函數(shù)的原型說(shuō)明所有子函數(shù)的原型說(shuō)明子函數(shù)子函數(shù)1定義定義.子函數(shù)子函數(shù)n定義定義 主函數(shù)定義主函數(shù)定義 2022-3-19642. 算法描述要點(diǎn) 1.6.4 算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描述規(guī)范與設(shè)計(jì)風(fēng)格 加上必要的注釋加上必要的注釋 注釋形式可以用/*字符串*/ 避免函數(shù)返回值隱含說(shuō)明避免函數(shù)返回值隱含說(shuō)明 預(yù)定義常量和類型預(yù)定義常量和類型 # define TRUE 1 # define FALSE 0 # define MAXSIZE 100 # define OK 1 # define ERROR 02022-3-1965避免可能出現(xiàn)的二義性表達(dá)避免可能出現(xiàn)的二義性表

36、達(dá) 注意不同的退出語(yǔ)句區(qū)別注意不同的退出語(yǔ)句區(qū)別 return 或或return：用于函數(shù)結(jié)束。：用于函數(shù)結(jié)束。break語(yǔ)句：可用在循環(huán)語(yǔ)句或語(yǔ)句：可用在循環(huán)語(yǔ)句或switch語(yǔ)句中結(jié)束循環(huán)過(guò)程或語(yǔ)句中結(jié)束循環(huán)過(guò)程或跳出情況語(yǔ)句。跳出情況語(yǔ)句。continue語(yǔ)句：可用在循環(huán)語(yǔ)句中結(jié)束本次循環(huán)過(guò)程，進(jìn)入語(yǔ)句：可用在循環(huán)語(yǔ)句中結(jié)束本次循環(huán)過(guò)程，進(jìn)入下一次循環(huán)過(guò)程。下一次循環(huán)過(guò)程。 exit語(yǔ)句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。語(yǔ)句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。 使用有意義的函數(shù)名與變量名使用有意義的函數(shù)名與變量名 2. 算法描述要點(diǎn)算法描述要點(diǎn) 1.6.4 算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描

37、述規(guī)范與設(shè)計(jì)風(fēng)格 簡(jiǎn)化輸入、輸出表述簡(jiǎn)化輸入、輸出表述 規(guī)范多分支轉(zhuǎn)向規(guī)范多分支轉(zhuǎn)向 2022-3-19663. 與參數(shù)傳遞的相關(guān)技術(shù) 1.6.4 算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描述規(guī)范與設(shè)計(jì)風(fēng)格 變量的作用域變量的作用域 全局變量：程序中所有函數(shù)都可以訪問(wèn)的量 局部變量：只能在該函數(shù)中訪問(wèn)的量。 參數(shù)傳遞方式參數(shù)傳遞方式 參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù)待處理數(shù)

38、據(jù),又稱值參；第二種參數(shù)既能為操作提又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。 2022-3-1967#include viod swap1(int a,int b) int c;c=a; a=b; b=c; printf(“swap1中的a= %d,b=%d”,a,b); viod swap2(int *a,int *b) int c;c=*a, *a=*b, *b=c; 關(guān)于參數(shù)傳遞示例源程序關(guān)于參數(shù)傳遞示例源程序：2022-3-1968void main() int x=100,y=800; swap1(x

39、,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ù)傳遞示例源程序關(guān)于參數(shù)傳遞示例源程序：2022-3-19694. 函數(shù)結(jié)果的帶出方式函數(shù)結(jié)果的帶出方式 1.6.4 算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描述規(guī)范與設(shè)計(jì)風(fēng)格 三種帶出方式三種帶出方式: :全程量、函數(shù)返回值、傳址參數(shù)全程量、函數(shù)返回值、傳址

40、參數(shù)若函數(shù)結(jié)果需要帶出多個(gè)值，該怎樣實(shí)現(xiàn)若函數(shù)結(jié)果需要帶出多個(gè)值，該怎樣實(shí)現(xiàn)?可以采用可以采用全局全局變量方式帶出，變量方式帶出，通過(guò)地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體通過(guò)地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體方式、指針?lè)绞剑﹥深惙绞街粊?lái)實(shí)現(xiàn)。方式、指針?lè)绞剑﹥深惙绞街粊?lái)實(shí)現(xiàn)。 通過(guò)參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過(guò)通過(guò)參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過(guò)全局變量是一種隱式參數(shù)傳遞，一個(gè)函數(shù)中對(duì)全局變量的全局變量是一種隱式參數(shù)傳遞，一個(gè)函數(shù)中對(duì)全局變量的改變會(huì)影響其它程序的調(diào)用，使用全局變量必須注意這個(gè)改變會(huì)影響其它程序的調(diào)用，使用全局變量必須注意這個(gè)問(wèn)題。問(wèn)題。 2022-3-

41、1970全局變量方式：int MIN; /* 全局變量 */ int fun1(int a, int n) /*通過(guò)函數(shù)return返回最大值，通過(guò)全局變量MIN帶回最小值*/ int i,max; max=MIN=a0; /給最大值最小值賦初值 for (i=0;imax) max=ai; if (aiMIN) MIN=ai; return(max);一個(gè)全局變量方式帶出的例子一個(gè)全局變量方式帶出的例子 2022-3-1971int *fun2(int a,int n)/*將最大、最小值放到數(shù)組b中，通過(guò)return返回*/ static int b2; b0=b1=a0; /給最大值最小值

42、賦初值int i; for (i=1;ib0)b0=ai;if (aimax=p-min=a0; /給最大值最小值賦初值for(i=1;ip-max) p-max=ai;if (aimin)p-min=ai;return(p);結(jié)構(gòu)體方式帶出的例子結(jié)構(gòu)體方式帶出的例子2022-3-1973Data fun4(int a,int n) /*將最大、最小值放到結(jié)構(gòu)體p中，通過(guò)結(jié)構(gòu)體p帶回返回值*/Data p;int i;p.max=p.min=a0; /給最大值最小值賦初值for(i=1;ip.max) p.max=ai;if (aip.min)p.min=ai;return(p);指針?lè)绞綆С龅睦又羔樂(lè)绞綆С龅睦?022-3-19741.7 關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) n數(shù)據(jù)結(jié)構(gòu)課程地位數(shù)據(jù)結(jié)構(gòu)課程地位 n數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn) n關(guān)于本書內(nèi)容編寫說(shuō)明關(guān)于本書內(nèi)容編寫說(shuō)明2022-3-1975數(shù)據(jù)結(jié)構(gòu)課程地位n 數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)人工智能人工智能專業(yè)基礎(chǔ)課專業(yè)基礎(chǔ)課操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理非線性程序設(shè)計(jì)非線性程序設(shè)計(jì)離散數(shù)學(xué)離散數(shù)學(xué)語(yǔ)言程序設(shè)計(jì)語(yǔ)言程序