數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述耿國(guó)華實(shí)用教案

1、2022-6-231第第1 1章章 緒緒 論論1.7 1.7 關(guān)于關(guān)于(guny)(guny)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) l1.11.1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)(sh j ji u)的的基本概念基本概念( (定義定義) )l1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究(ynji)(ynji)范圍）范圍）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ǔ)言表示第1頁(yè)/共81頁(yè)第一頁(yè)，共81頁(yè)。2022-6-2321.1 1.1 數(shù)據(jù)結(jié)構(gòu)(sh j

2、ji u)(sh j ji u)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞(mng c)：數(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ù)類型第2頁(yè)/共81頁(yè)第二頁(yè)，共81頁(yè)。2022-6-233數(shù)據(jù)(shj)(shj)（DataData） 定義： 數(shù)據(jù)是描述客觀事物(k un sh w)的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。 數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。C編譯程序源程序（.c）目標(biāo)程序（.obj）可執(zhí)

3、行程序（.exe）C鏈接程序例如(lr)對(duì)C源程序第3頁(yè)/共81頁(yè)第三頁(yè)，共81頁(yè)。2022-6-234數(shù)據(jù)(shj)(shj)元素（Data ElementData Element） 定義： 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位 ，是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常(tngchng)作為一個(gè)整體進(jìn)行考慮和處理。例如：. . . . . . 北京1983.11河北女 趙虹玲101 住 址 出生年月 籍 貫性 別 姓 名 學(xué) 號(hào) 數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)第4頁(yè)/共81頁(yè)第四頁(yè)，共81頁(yè)。2022-6-235數(shù)據(jù)(shj)(shj)對(duì)象（Data ObjectData Object） 定義： 數(shù)據(jù)對(duì)象是性質(zhì)相同(xi

4、n tn)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。整數(shù)集合：N=0，1，2， 無(wú)限(wxin)集字符集合：C=A，B，Z 有限集例如：第5頁(yè)/共81頁(yè)第五頁(yè)，共81頁(yè)。2022-6-236數(shù)據(jù)結(jié)構(gòu)(sh j ji u)(sh j ji u)（Data StructureData Structure） 定義： 數(shù)據(jù)結(jié)構(gòu)(sh j ji 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) 第6頁(yè)/共

5、81頁(yè)第六頁(yè)，共81頁(yè)。2022-6-237數(shù)據(jù)結(jié)構(gòu)(sh j ji u)(sh j ji u)（Data StructureData Structure）教研室實(shí)驗(yàn)室 系處研究機(jī)構(gòu)學(xué)校樹(shù)型結(jié)構(gòu)(jigu)圖結(jié)構(gòu)(jigu) 1 2 5 4 3第7頁(yè)/共81頁(yè)第七頁(yè)，共81頁(yè)。2022-6-238數(shù)據(jù)類型(Data Type)(Data Type) 定義(dngy)： 數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義(dngy)在這個(gè)值集合上的一組操作的總稱。如在高級(jí)(goj)語(yǔ)言中，整型類型的取值范圍為：-32768+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。第8頁(yè)/共81頁(yè)

6、第八頁(yè)，共81頁(yè)。2022-6-239數(shù)據(jù)類型(Data Type)(Data Type) 高級(jí)(goj)語(yǔ)言中的數(shù)據(jù)類型分為兩大類：1.原子類型，其值不可分解(fnji)。如C語(yǔ)言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以(ky)分解的，并且它的成分可以(ky)是非結(jié)構(gòu)的，也可以(ky)是結(jié)構(gòu)的。指針類型屬于哪種類型？第9頁(yè)/共81頁(yè)第九頁(yè)，共81頁(yè)。2022-6-2310數(shù)據(jù)抽象與抽象數(shù)據(jù)類型 數(shù)據(jù)(shj)的抽象 抽象數(shù)據(jù)(shj)類型(Abstract Data Type) 抽象數(shù)據(jù)(shj)類型實(shí)現(xiàn) ADT的表示與實(shí)現(xiàn) 面向?qū)ο蟮?/p>

7、概念 結(jié)構(gòu)化的開(kāi)發(fā)方法與面向?qū)ο箝_(kāi)發(fā)方法不同點(diǎn) 第10頁(yè)/共81頁(yè)第十頁(yè)，共81頁(yè)。2022-6-23111.2 數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的內(nèi)容 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 運(yùn)算(yn sun)集合 第11頁(yè)/共81頁(yè)第十一頁(yè)，共81頁(yè)。2022-6-2312邏輯邏輯(lu j)結(jié)構(gòu)結(jié)構(gòu) 定義： 數(shù)據(jù)(shj)的邏輯結(jié)構(gòu)是指數(shù)據(jù)(shj)元素之間邏輯關(guān)系描述。l形式化描述(mio sh)：lData_Structure=（D,R）其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。l四類基本的結(jié)構(gòu) 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)。第12頁(yè)/共81頁(yè)第十二頁(yè)，共81頁(yè)。2022-6-2313集

8、合(jh)結(jié)構(gòu) 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系(gun x)外，無(wú)任何其它關(guān)系(gun x)。 集合例如(lr)：第13頁(yè)/共81頁(yè)第十三頁(yè)，共81頁(yè)。2022-6-2314線性結(jié)構(gòu)(jigu)(jigu) 定義(dngy)： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系。 例如(lr)：線性表第14頁(yè)/共81頁(yè)第十四頁(yè)，共81頁(yè)。2022-6-2315樹(shù)型結(jié)構(gòu)(jigu) 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素(yun s)之間存在著一對(duì)多的層次關(guān)系。 例如(lr)： 樹(shù)第15頁(yè)/共81頁(yè)第十五頁(yè)，共81頁(yè)。2022-6-2316圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)(jigu)(jigu)或網(wǎng)狀結(jié)構(gòu)或網(wǎng)狀

9、結(jié)構(gòu)(jigu) (jigu) 定義： 結(jié)構(gòu)中的數(shù)據(jù)(shj)元素之間存在著多對(duì)多的任意關(guān)系。例如(lr)： 圖第16頁(yè)/共81頁(yè)第十六頁(yè)，共81頁(yè)。2022-6-2317綜上所述，數(shù)據(jù)(shj)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)線性表、棧、隊(duì)、字符串?dāng)?shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)樹(shù)、圖邏輯邏輯(luj)結(jié)構(gòu)結(jié)構(gòu)第17頁(yè)/共81頁(yè)第十七頁(yè)，共81頁(yè)。2022-6-2318存儲(chǔ)存儲(chǔ)(cn ch)結(jié)構(gòu)結(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ù)元素的表示(biosh)和關(guān)系的表示(biosh)。 l形式化描述：l D要存入機(jī)器中，建立一從D的

10、數(shù)據(jù)元素到存儲(chǔ)空間M單元映象S ，DM，即對(duì)于每一個(gè)(y )d， dD,都有唯一的zM使S（D）=Z, 同時(shí)這個(gè)映象必須明顯或隱含地體現(xiàn)關(guān)系R。第18頁(yè)/共81頁(yè)第十八頁(yè)，共81頁(yè)。2022-6-2319邏輯(luj)結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映象與元素(yuns)本身映象，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象。數(shù)據(jù)元素之間關(guān)系在計(jì)算機(jī)中的表示(biosh)方法：順序映象（順序存儲(chǔ)結(jié)構(gòu)）非順序映象（非順序存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)第19頁(yè)/共81頁(yè)第十九頁(yè)，共81頁(yè)。2022-6-2320運(yùn)算運(yùn)算(yn sun)集合集合例如(lr)工資表：編編 號(hào)號(hào)姓姓 名名性別性別基

11、本工資基本工資工齡工資工齡工資應(yīng)扣工資應(yīng)扣工資實(shí)發(fā)工資實(shí)發(fā)工資100001100001張愛(ài)芬張愛(ài)芬女女34534567671451454545303000004514511212100002100002李李 林林男男44544590901851856060454500005865865050100003100003劉曉峰劉曉峰男男34534500001301300000252500004504500000100004100004趙趙俊俊女女56056090902252259090656500007217218080100005100005孫孫濤濤男男4504506060190190808050

12、5000005915918080100121100121張興強(qiáng)張興強(qiáng)男男102510259898365365535310010000001291.511291.51第20頁(yè)/共81頁(yè)第二十頁(yè)，共81頁(yè)。2022-6-2321數(shù)據(jù)結(jié)構(gòu)(sh j ji u)(sh j ji u)的內(nèi)容 綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合(jh)：按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合(jh)，就叫做數(shù)據(jù)結(jié)構(gòu)。 第21頁(yè)/共81頁(yè)第二十一頁(yè)，共81頁(yè)。2022-6-23221.3 算法(sun f) 算法（算

13、法（Algorithm）定義）定義 算法的特性算法的特性 算法設(shè)計(jì)算法設(shè)計(jì)(shj)的要求的要求 第22頁(yè)/共81頁(yè)第二十二頁(yè)，共81頁(yè)。2022-6-2323算法算法(sun f)（Algorithm）定義）定義 定義： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是規(guī)則的有限(yuxin)集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。 第23頁(yè)/共81頁(yè)第二十三頁(yè)，共81頁(yè)。2022-6-2324算法算法(sun

14、f)的特性的特性1. 有限(yuxin)性：有限(yuxin)步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)2. 確定(qudng)性：算法中的每一個(gè)步驟必須有確定(qudng)含義，無(wú)二 義性得以實(shí)現(xiàn)。 3. 輸 入： 有多個(gè)或0個(gè)輸入 4. 輸 出： 至少有一個(gè)或多個(gè)輸出。5. 可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)基本 運(yùn)算執(zhí)行有限次而完成。 第24頁(yè)/共81頁(yè)第二十四頁(yè)，共81頁(yè)。2022-6-2325算法算法(sun f)設(shè)計(jì)的要求設(shè)計(jì)的要求 算法(sun f)的正確性 算法(sun f)特征：l 可讀性 l 健壯性 l 高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問(wèn)題給出算法如下： max:=0

15、; for（i=1 ；imax) max=x; 第25頁(yè)/共81頁(yè)第二十五頁(yè)，共81頁(yè)。2022-6-23261.4 算法(sun f)描述的工具 概述：算法+數(shù)據(jù)結(jié)構(gòu)=程序 算法、語(yǔ)言、程序的關(guān)系 設(shè)計(jì)(shj)實(shí)現(xiàn)算法過(guò)程步驟 類描述算法的語(yǔ)言選擇第26頁(yè)/共81頁(yè)第二十六頁(yè)，共81頁(yè)。2022-6-2327算法、語(yǔ)言算法、語(yǔ)言(yyn)、程序的關(guān)系、程序的關(guān)系1. 算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系(gun x)（包括數(shù)據(jù)邏輯關(guān)系(gun x)、存貯關(guān)系(gun x)描述）。2. 描述算法的工具：算法可用自然語(yǔ)言、框圖(kungt)或高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行描述。3.程序是算法在計(jì)算機(jī)中的

16、實(shí)現(xiàn)。第27頁(yè)/共81頁(yè)第二十七頁(yè)，共81頁(yè)。2022-6-2328設(shè)計(jì)設(shè)計(jì)(shj)實(shí)現(xiàn)算法過(guò)程步驟實(shí)現(xiàn)算法過(guò)程步驟1. 找出與求解有關(guān)的數(shù)據(jù)(shj)元素之間的關(guān)系2. 確定在某一數(shù)據(jù)對(duì)象(duxing)上所施加運(yùn)算3. 考慮數(shù)據(jù)元素的存儲(chǔ)表示4. 選擇描述算法的語(yǔ)言5.設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語(yǔ)言加以描述。第28頁(yè)/共81頁(yè)第二十八頁(yè)，共81頁(yè)。2022-6-2329類描述類描述(mio sh)算法的語(yǔ)言選擇算法的語(yǔ)言選擇 類語(yǔ)言(yyn)：類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，具有高級(jí)語(yǔ)言的一般語(yǔ)句設(shè)施，撇掉語(yǔ)言中的細(xì)節(jié)，以便把注意力主要(zhyo)(zhyo)集中在算法處

17、理步驟本身的描述上。第29頁(yè)/共81頁(yè)第二十九頁(yè)，共81頁(yè)。2022-6-23303.賦值語(yǔ)句(yj)對(duì)C語(yǔ)言作以下(yxi)描述：（1）簡(jiǎn)單(jindn)賦值 1）變量名=表達(dá)式2）變量+，3）變量-，（2）串聯(lián)賦值變量1=變量2=變量3=變量k=表達(dá)式 第30頁(yè)/共81頁(yè)第三十頁(yè)，共81頁(yè)。2022-6-2331對(duì)C語(yǔ)言作以下(yxi)描述：（4）條件(tiojin)賦值變量名=條件(tiojin)表達(dá)式？表達(dá)式1:表達(dá)式2 （3）成組賦值(, 變量k=(, , , )數(shù)組名1 1 下標(biāo)11下標(biāo)2=2=數(shù)組名2 2 下標(biāo)11下標(biāo)22 第31頁(yè)/共81頁(yè)第三十一頁(yè)，共81頁(yè)。2022-6-2

18、3324.條件選擇(xunz)語(yǔ)句對(duì)C語(yǔ)言作以下(yxi)描述：if () 語(yǔ)句(yj);if () 語(yǔ)句1; else 語(yǔ)句2;第32頁(yè)/共81頁(yè)第三十二頁(yè)，共81頁(yè)。2022-6-2333情況(qngkung)語(yǔ)句switch (） case 判斷(pndun)值1: 語(yǔ)句組 1； break; case 判斷(pndun)值2: 語(yǔ)句組 2； break; case 判斷(pndun)值n: 語(yǔ)句組n; break; default: 語(yǔ)句組； break; 對(duì)C語(yǔ)言作以下描述：第33頁(yè)/共81頁(yè)第三十三頁(yè)，共81頁(yè)。2022-6-2334對(duì)C語(yǔ)言作以下(yxi)描述：5.循環(huán)(xnhu

19、n)語(yǔ)句for語(yǔ)句(yj)for(；）循環(huán)體語(yǔ)句；第34頁(yè)/共81頁(yè)第三十四頁(yè)，共81頁(yè)。2022-6-2335while語(yǔ)句(yj)while(）循環(huán)體語(yǔ)句；對(duì)C語(yǔ)言作以下(yxi)描述：dowhile語(yǔ)句do循環(huán)體語(yǔ)句while(） 第35頁(yè)/共81頁(yè)第三十五頁(yè)，共81頁(yè)。2022-6-23361.5 對(duì)算法作性能(xngnng)評(píng)價(jià) 評(píng)價(jià)(pngji)算法的標(biāo)準(zhǔn)： 評(píng)價(jià)(pngji)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來(lái)判斷一個(gè)算法的優(yōu)劣。 性能評(píng)價(jià)(pngji) 有關(guān)數(shù)量關(guān)系計(jì)算 第

20、36頁(yè)/共81頁(yè)第三十六頁(yè)，共81頁(yè)。2022-6-2337性能(xngnng)(xngnng)評(píng)價(jià) 定義： 對(duì)問(wèn)題規(guī)模(gum)與該算法在運(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)算(ynsun)是多項(xiàng)式項(xiàng)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)；對(duì)集合運(yùn)算(ynsun)是集合中元素個(gè)數(shù)。第37頁(yè)/共81頁(yè)第三十七頁(yè)，共81頁(yè)。2022-6-2338有關(guān)數(shù)量(shling)(shling)關(guān)系計(jì)算 數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間算法(sun f)(sun f)在機(jī)器中所耗費(fèi)時(shí)間。數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間算法(sun f)(sun f)在機(jī)器中所占存儲(chǔ)

21、量。關(guān)于算法(sun f)(sun f)執(zhí)行時(shí)間語(yǔ)句頻度 算法(sun f)(sun f)的時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 最壞時(shí)間復(fù)雜度 算法(sun f)(sun f)的空間復(fù)雜度 第38頁(yè)/共81頁(yè)第三十八頁(yè)，共81頁(yè)。2022-6-2339關(guān)于算法(sun f)(sun f)執(zhí)行時(shí)間 定義： 一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和(zngh)(zngh)，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。l分析：l不是針對(duì)實(shí)際執(zhí)行時(shí)間的精確地算出算法執(zhí)行具體(jt)時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。第39

22、頁(yè)/共81頁(yè)第三十九頁(yè)，共81頁(yè)。2022-6-2340語(yǔ)句(yj)(yj)頻度 定義：語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行(zhxng)的次數(shù)。例如：兩個(gè)矩陣(jzhn)相乘算法語(yǔ)句 對(duì)應(yīng)的語(yǔ)句頻度 1 1forfor（i=0i=0；i n;i+i n;i+） n n 2 2for for （j=0j=0；jn;j+jn;j+） n n2 2 3 cij=0; n 3 cij=0; n2 2 4 for (k=0;k n; k+) n 4 for (k=0;k n; k+) n3 3 cij=cij+aik cij=cij+aik* *bkj; nbkj; n3 3 總執(zhí)行次數(shù)：Tn=2n

23、3+2n2+n第40頁(yè)/共81頁(yè)第四十頁(yè)，共81頁(yè)。2022-6-2341算法(sun f)(sun f)的時(shí)間復(fù)雜度 算法的時(shí)間(shjin)復(fù)雜度，即是算法的時(shí)間(shjin)量度記做： T(n)=O(f(n)例如(lr)給出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), 稱為平方階。第41頁(yè)/共81頁(yè)第四十一頁(yè)，共81頁(yè)。2022-6-2342常用(chn yn)(chn yn)的時(shí)間復(fù)雜度

24、頻率計(jì)數(shù) 數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間(shjin)復(fù)雜度頻率計(jì)數(shù)有7個(gè):O(1)常數(shù)型O(n)線性型O(n2)平方(pngfng)型O(n3)立方型O(2n)指數(shù)型O(log2n)對(duì)數(shù)型O(nlog2n)二維型按時(shí)間復(fù)雜度由小到大排列的頻率表：第42頁(yè)/共81頁(yè)第四十二頁(yè)，共81頁(yè)。2022-6-2343常用的時(shí)間復(fù)雜度頻率(pnl)(pnl)計(jì)數(shù) 常用(chn yn)(chn yn)的時(shí)間復(fù)雜度頻率表：loglog2 2n nn nnlognlog2 2n nn n2 2n n3 32 2n n一般講：前一般講：前3種可實(shí)現(xiàn)，種可實(shí)現(xiàn)，后后3種雖理種雖理論上是可實(shí)論上是可實(shí)現(xiàn)的，實(shí)際現(xiàn)的，實(shí)際上只

25、有對(duì)上只有對(duì)N限制在很小限制在很小范圍才有意范圍才有意義，當(dāng)義，當(dāng)N較較大時(shí)，不可大時(shí)，不可能實(shí)現(xiàn)。能實(shí)現(xiàn)。0 01 10 01 11 12 21 12 22 24 48 84 42 24 48 81616646416163 38 8242464645125122562564 4161664642562565096509665536655365 5323216016010241024327683276821474836482147483648第43頁(yè)/共81頁(yè)第四十三頁(yè)，共81頁(yè)。2022-6-2344最壞時(shí)間(shjin)(shjin)復(fù)雜度 定義：討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析(

26、fnx)最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。例如(lr)冒泡排序算法第44頁(yè)/共81頁(yè)第四十四頁(yè)，共81頁(yè)。2022-6-2345voidbubble(inta,intlength)將a中整數(shù)(zhngsh)數(shù)組重新排序，達(dá)到遞增有序inti=0,j,temp;intchange;dochange=false;for(j=1;jaj+1)temp=aj;aj=aj+1;aj+1=temp;change=true;i=i+1;while(ilength|change=true)最壞時(shí)間(shjin)(shjin)復(fù)雜度 第45頁(yè)/共81頁(yè)第四十五頁(yè)，共81頁(yè)。2022-6-2346算法(sun

27、 f)(sun f)的空間復(fù)雜度 定義(dngy)： 用空間(kngjin)復(fù)雜度作為算法所需存儲(chǔ)空間(kngjin)的量度， 記做： S(n)=O(f (n) 。第46頁(yè)/共81頁(yè)第四十六頁(yè)，共81頁(yè)。2022-6-23471.6數(shù)據(jù)結(jié)構(gòu)(shjjiu)與C語(yǔ)言表示數(shù)據(jù)結(jié)構(gòu)(sh j ji u)(sh j ji u)與程序設(shè)計(jì)的關(guān)聯(lián)性 問(wèn)題描述：欲求1 1名學(xué)生1010次C C語(yǔ)言程序設(shè)計(jì)的測(cè)試成績(jī)總分與平均分。其中(qzhng)10(qzhng)10次測(cè)驗(yàn)的成績(jī)分別為：8080，8585，7777，5656，6868，8383，9090，9292，8080，9898。 第47頁(yè)/共81頁(yè)第

28、四十七頁(yè)，共81頁(yè)。2022-6-2348程序(chngx)示例1-1：main() int sum，verage； /*總分，平均分*/ int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10； /*10個(gè)變量存10次成績(jī)*/ t1=80；t2=85；t3=77；t4=56； t5=68； /*分別(fnbi)賦值*/ 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); print

29、f(“平均分=%dn”, average); 第48頁(yè)/共81頁(yè)第四十八頁(yè)，共81頁(yè)。2022-6-2349根據(jù)測(cè)試次數(shù)與測(cè)試成績(jī)的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲(chǔ)測(cè)驗(yàn)成績(jī)，提高了程序(chngx)的適用范圍。main()intsum，erage；inti;intt10=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);程序(chngx)示例1-2：第49頁(yè)/

30、共81頁(yè)第四十九頁(yè)，共81頁(yè)。2022-6-2350結(jié)構(gòu)化程序設(shè)計(jì)(shj)(shj)與函數(shù)的模塊化 結(jié)構(gòu)化程序設(shè)計(jì) ：是為使程序具有合理的結(jié)構(gòu)，以保證程序正確性而規(guī)定(gudng)的一套程序設(shè)計(jì)的方法 。程序設(shè)計(jì)的實(shí)質(zhì)：算法+數(shù)據(jù)(shj)結(jié)構(gòu)=程序 即“程序是在數(shù)據(jù)(shj)的特定表示方式的基礎(chǔ)上，對(duì)抽象算法的具體描述”。程序結(jié)構(gòu)=控制結(jié)構(gòu)+數(shù)據(jù)(shj)結(jié)構(gòu) 第50頁(yè)/共81頁(yè)第五十頁(yè)，共81頁(yè)。2022-6-2351 結(jié)構(gòu)化程序設(shè)計(jì)(shj)目的通過(guò)設(shè)計(jì)結(jié)構(gòu)良好的程序(chngx)，以程序(chngx)的靜態(tài)良好結(jié)構(gòu)保證程序(chngx)動(dòng)態(tài)執(zhí)行的正確性，使程序(chngx)易理解、易

31、調(diào)試、易維護(hù)，以提高軟件開(kāi)發(fā)的效率，減少出錯(cuò)率。結(jié)構(gòu)化程序設(shè)計(jì)的構(gòu)成(guchng)單元任何程序都可由順序、選擇、重復(fù)三種基本控制結(jié)構(gòu)來(lái)組成。結(jié)構(gòu)化程序設(shè)計(jì)方法 其一：“自頂向下，逐步求精”的設(shè)計(jì)思想 ；其二：“獨(dú)立功能，一個(gè)入口，一個(gè)出口“的模塊化結(jié)構(gòu)； 其三：“僅用三種基本控制結(jié)構(gòu)”的設(shè)計(jì)原則 第51頁(yè)/共81頁(yè)第五十一頁(yè)，共81頁(yè)。2022-6-2352面向?qū)ο笈c抽象數(shù)據(jù)類型1.1.面向?qū)ο蟮母拍?ginin)(ginin)：面向?qū)ο?duxing)=對(duì)象(duxing)+類+繼承+通信對(duì)象：指在應(yīng)用問(wèn)題中出現(xiàn)的各種實(shí)體、事件、規(guī)格(gug)說(shuō)明等 。類：具有相同屬性和服務(wù)的對(duì)象 繼承：

32、是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?第52頁(yè)/共81頁(yè)第五十二頁(yè)，共81頁(yè)。2022-6-2353面向?qū)ο蟪绦蛟O(shè)計(jì)(chn x sh j)(chn x sh j)的特點(diǎn)是封裝性、繼承性和多態(tài)性 與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的是定義(dngy)在數(shù)據(jù)結(jié)構(gòu)上的一組操作。 基本操作主要有：插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素；刪除：刪去數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定數(shù)據(jù)元素；更新：改變(gibin)數(shù)據(jù)結(jié)構(gòu)中某個(gè)元素的值，在概念上等價(jià)于刪除和插入操作的組合；查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素（的位置和值）；排序：（在線性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使數(shù)據(jù)元素按值由小到大或由大到小的次

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

34、類型與問(wèn)題(wnt)(wnt)求解方法 n定義(dngy)：n抽象數(shù)據(jù)類型（簡(jiǎn)稱ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義(dngy)在這個(gè)類型之上的一組操作。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來(lái)；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過(guò)程隱藏起來(lái)。第55頁(yè)/共81頁(yè)第五十五頁(yè)，共81頁(yè)。2022-6-2356數(shù)據(jù)數(shù)據(jù)(shj)(shj)的抽象的抽象 匯編語(yǔ)言中十進(jìn)制表示的數(shù)據(jù)(shj)98.65、9.6E3等, 它們是二進(jìn)制數(shù)據(jù)(shj)的抽象; l高級(jí)語(yǔ)言(yyn)中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，l還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、

35、樹(shù)、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。第56頁(yè)/共81頁(yè)第五十六頁(yè)，共81頁(yè)。2022-6-2357抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 線性表的抽象數(shù)據(jù)類型的描述(mio sh)：ADT Linear_list數(shù)據(jù)元素 所有ai屬于同一數(shù)據(jù)對(duì)象，i=1，2，n n0；邏輯結(jié)構(gòu) 所有數(shù)據(jù)元素ai（i=1，2，n-1）存在次序關(guān)系 ，ai無(wú)前趨，an無(wú)后繼；操作 設(shè)L為L(zhǎng)inear_listInitial(L)初始化空線性表；Length(L)求線性表的表長(zhǎng)；Get(L,i)取線性表的第i個(gè)元素；Insert(L,i,b)在線性表的第i個(gè)位置(wi zhi)插入元素b；Delete(L,i)刪除線性表的

36、第i個(gè)元素； 第57頁(yè)/共81頁(yè)第五十七頁(yè)，共81頁(yè)。2022-6-2358抽象數(shù)據(jù)類型實(shí)現(xiàn)抽象數(shù)據(jù)類型實(shí)現(xiàn)(shxin) 傳統(tǒng)的面向過(guò)程(guchng)(guchng)的程序設(shè)計(jì)實(shí)現(xiàn)(shxin)的三種方法：l“包”、“模型”的設(shè)計(jì)方法l面向?qū)ο蟮某绦蛟O(shè)計(jì)（Object Oriented Programming，簡(jiǎn)稱OOP）第58頁(yè)/共81頁(yè)第五十八頁(yè)，共81頁(yè)。2022-6-2359ADT的表示的表示(biosh)與實(shí)現(xiàn)與實(shí)現(xiàn) ADT的定義(dngy)：ADT 數(shù)據(jù)對(duì)象: 結(jié)構(gòu)關(guān)系: 基本操作: ADT 基本操作的定義格式為： (參數(shù)表) 操作前提: 操作結(jié)果:第59頁(yè)/共81頁(yè)第五十九頁(yè)

37、，共81頁(yè)。2022-6-2360l關(guān)于(guny)參數(shù)傳遞：參數(shù)(cnsh)表中的參數(shù)(cnsh)有值參和變參兩種。用標(biāo)準(zhǔn)C語(yǔ)言表示和實(shí)現(xiàn)(shxin)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)的表示與實(shí)現(xiàn)第60頁(yè)/共81頁(yè)第六十頁(yè)，共81頁(yè)。2022-6-2361算法描述(mio sh)(mio sh)規(guī)范與設(shè)計(jì)風(fēng)格 1. 算法表示格式(g shi)與函數(shù)模塊化 函數(shù)(hnsh)返回值類型 函數(shù)(hnsh)名（形式參數(shù)及說(shuō)明）

38、內(nèi)部數(shù)據(jù)說(shuō)明； 執(zhí)行語(yǔ)句組； /*函數(shù)(hnsh)名*/ 算法表示格式第61頁(yè)/共81頁(yè)第六十一頁(yè)，共81頁(yè)。2022-6-2362算法(sun f)(sun f)描述規(guī)范與設(shè)計(jì)風(fēng)格 函數(shù)(hnsh)的模塊化 1. 算法(sun f)表示格式與函數(shù)模塊化 包含文件語(yǔ)句宏定義語(yǔ)句自定義類型語(yǔ)句所有子函數(shù)的原型說(shuō)明子函數(shù)1定義.子函數(shù)n定義主函數(shù)定義 第62頁(yè)/共81頁(yè)第六十二頁(yè)，共81頁(yè)。2022-6-23632. 算法描述(mio sh)要點(diǎn) 算法描述(mio sh)(mio sh)規(guī)范與設(shè)計(jì)風(fēng)格 加上必要(byo)(byo)的注釋 注釋形式可以用/*字符串*/ 避免函數(shù)返回值隱含說(shuō)明 預(yù)定義

39、常量和類型 # define TRUE 1 # define FALSE 0 # define MAXSIZE 100 # define OK 1 # define ERROR 0第63頁(yè)/共81頁(yè)第六十三頁(yè)，共81頁(yè)。2022-6-2364避免(bmin)(bmin)可能出現(xiàn)的二義性表達(dá) 注意不同(b tn)(b tn)的退出語(yǔ)句區(qū)別 return或或return：用于函數(shù)結(jié)束。：用于函數(shù)結(jié)束。break語(yǔ)句語(yǔ)句(yj)：可用在循環(huán)語(yǔ)句：可用在循環(huán)語(yǔ)句(yj)或或switch語(yǔ)句語(yǔ)句(yj)中結(jié)束中結(jié)束循環(huán)過(guò)程或跳出情況語(yǔ)句循環(huán)過(guò)程或跳出情況語(yǔ)句(yj)。continue語(yǔ)句語(yǔ)句(yj)：可

40、用在循環(huán)語(yǔ)句：可用在循環(huán)語(yǔ)句(yj)中結(jié)束本次循環(huán)過(guò)程，中結(jié)束本次循環(huán)過(guò)程，進(jìn)入下一次循環(huán)過(guò)程。進(jìn)入下一次循環(huán)過(guò)程。exit語(yǔ)句語(yǔ)句(yj)：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。使用有意義的函數(shù)名與變量名 2.算法描述要點(diǎn) 算法描述規(guī)范與設(shè)計(jì)風(fēng)格 簡(jiǎn)化輸入、輸出表述 規(guī)范多分支轉(zhuǎn)向 第64頁(yè)/共81頁(yè)第六十四頁(yè)，共81頁(yè)。2022-6-23653. 與參數(shù)傳遞的相關(guān)(xinggun)技術(shù) 算法(sun f)(sun f)描述規(guī)范與設(shè)計(jì)風(fēng)格 變量(binling)(binling)的作用域 全局變量：程序中所有函數(shù)都可以訪問(wèn)的量 局部變量：只能在該函數(shù)中訪問(wèn)的量

41、。 參數(shù)傳遞方式 參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。其參數(shù)參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)參數(shù)表中的參傳遞的主要方式有傳值和傳地址兩類。函數(shù)參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù)數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù),又稱值又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù)，又能參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。返回操作結(jié)果，也稱變量參數(shù)。 第65頁(yè)/共81頁(yè)第六十五頁(yè)，共81頁(yè)。2022-6-2366#include viod swap1(int a,int b) int c;c

42、=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)于(guny)參數(shù)傳遞示例源程序：第66頁(yè)/共81頁(yè)第六十六頁(yè)，共81頁(yè)。2022-6-2367void main() int x=100,y=800; swap1(x,y); /*調(diào)用函數(shù)swap1()*/printf(“n調(diào)用swap1后x= %d,y=%d”,x,y); /*輸出(shch)調(diào)用swap1后的數(shù)據(jù)*/x=100;y=800;swap2(&x,&y); /*調(diào)用函數(shù)swap2()

43、*/ printf(“n調(diào)用swap2后x=%d,y=%d”,x,y); /*輸出(shch)調(diào)用swap2后的數(shù)據(jù)*/ 關(guān)于(guny)參數(shù)傳遞示例源程序：第67頁(yè)/共81頁(yè)第六十七頁(yè)，共81頁(yè)。2022-6-23684.函數(shù)結(jié)果(jigu)的帶出方式算法描述規(guī)范(gufn)(gufn)與設(shè)計(jì)風(fēng)格 三種(sn zhn)(sn zhn)帶出方式: :全程量、函數(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è)函

44、數(shù)中對(duì)全局變量的改變會(huì)影響其它程序的調(diào)用，使用全局變量必須注意這個(gè)問(wèn)題。 第68頁(yè)/共81頁(yè)第六十八頁(yè)，共81頁(yè)。2022-6-2369全局變量方式(fngsh)：int MIN; /* 全局變量 */ int fun1(int a, int n) /*通過(guò)函數(shù)(hnsh)return返回最大值，通過(guò)全局變量MIN帶回最小值*/ int i,max; max=MIN=a0; /給最大值最小值賦初值 for (i=0;imax) max=ai; if (aiMIN) MIN=ai; return(max);一個(gè)(y )(y )全局變量方式帶出的例子 第69頁(yè)/共81頁(yè)第六十九頁(yè)，共81頁(yè)。202

45、2-6-2370int *fun2(int a,int n)/*將最大、最小值放到數(shù)組b中，通過(guò)(tnggu)return返回*/ static int b2; b0=b1=a0; /給最大值最小值賦初值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)(jigu)(jigu)體方式帶出的例子第71頁(yè)/共81頁(yè)第七十一頁(yè)，共81頁(yè)。2022-6-2372Data fun4(int a,int n) /*將最大、最小值放到結(jié)構(gòu)(jigu)體p中，通過(guò)結(jié)構(gòu)(jigu)體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è)绞?fngsh)(fngsh)帶出的例子第72頁(yè)/共81頁(yè)第七十二頁(yè)，共81頁(yè)。2022-6-237