數(shù)據(jù)結(jié)構(gòu)C語言描述耿國華PPT課件

1、2021-11-131第第1 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語言表示語言表示第1頁/共81頁2021-11-1321.1 1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞： 數(shù)據(jù)（Data） 數(shù)據(jù)元素（Data Element） 數(shù)據(jù)對(duì)象（Data Ob

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

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

4、。 例如表結(jié)構(gòu)：. . . . . . 北京1983.11河北女 趙虹玲101 住 址 出生年月 籍 貫性 別 姓 名 學(xué) 號(hào) 第6頁/共81頁2021-11-137數(shù)據(jù)結(jié)構(gòu)（Data Structure）教研室實(shí)驗(yàn)室 系處研究機(jī)構(gòu)學(xué)校樹型結(jié)構(gòu)圖結(jié)構(gòu) 1 2 5 4 3第7頁/共81頁2021-11-138數(shù)據(jù)類型(Data Type)(Data Type) 定義： 數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。如在高級(jí)語言中，整型類型的取值范圍為：-32768+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。第8頁/共81頁2021-11-139數(shù)

5、據(jù)類型(Data Type)(Data Type) 高級(jí)語言中的數(shù)據(jù)類型分為兩大類：1.原子類型，其值不可分解。如C語言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。指針類型屬于哪種類型？第9頁/共81頁2021-11-1310數(shù)據(jù)抽象與抽象數(shù)據(jù)類型 數(shù)據(jù)的抽象 抽象數(shù)據(jù)類型(Abstract Data Type) 抽象數(shù)據(jù)類型實(shí)現(xiàn) ADT的表示與實(shí)現(xiàn) 面向?qū)ο蟮母拍?結(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點(diǎn) 第10頁/共81頁2021-11-13111.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)

6、 運(yùn)算集合 第11頁/共81頁2021-11-1312邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 定義： 數(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)。第12頁/共81頁2021-11-1313集合結(jié)構(gòu) 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無任何其它關(guān)系。 集合例如：第13頁/共81頁2021-11-1314線性結(jié)構(gòu) 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系。 例如：線性表第14頁/共81頁2021-11-1315樹型結(jié)構(gòu) 定義： 結(jié)

7、構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系。 例如： 樹第15頁/共81頁2021-11-1316圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。例如： 圖第16頁/共81頁2021-11-1317綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)線性表、棧、隊(duì)、字符串 數(shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)樹、圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)第17頁/共81頁2021-11-1318存儲(chǔ)結(jié)構(gòu)存儲(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)系的表示。 l形式化描述： D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲(chǔ)

8、空間M單元映象S ，DM，即對(duì)于每一個(gè)d， dD,都有唯一的zM使S（D）=Z, 同時(shí)這個(gè)映象必須明顯或隱含地體現(xiàn)關(guān)系R。第18頁/共81頁2021-11-1319邏輯結(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)存儲(chǔ)結(jié)構(gòu) 第19頁/共81頁2021-11-1320運(yùn)算集合運(yùn)算集合例如工資表：編編 號(hào)號(hào)姓姓 名名性別性別基本工資基本工資工齡工資工齡工資應(yīng)扣工資應(yīng)扣工資實(shí)發(fā)工資實(shí)發(fā)工資100001100001張愛芬張愛芬女女3453

9、4567671451454545303000004514511212100002100002李李 林林男男44544590901851856060454500005865865050100003100003劉曉峰劉曉峰男男34534500001301300000252500004504500000100004100004趙趙俊俊女女56056090902252259090656500007217218080100005100005孫孫濤濤男男45045060601901908080505000005915918080100121100121張興強(qiáng)張興強(qiáng)男男1025102598983653655

10、35310010000001291.511291.51第20頁/共81頁2021-11-1321數(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)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。 第21頁/共81頁2021-11-13221.3 算法 算法（算法（AlgorithmAlgorithm）定義）定義 算法的特性算法的特性 算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求 第22頁/共81頁2021-11-1323算法（算法（AlgorithmAlgorithm）定義）定義 定義： Al

11、gorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。 第23頁/共81頁2021-11-1324算法的特性算法的特性1. 有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)2. 確定性：算法中的每一個(gè)步驟必須有確定含義，無二 義性得以實(shí)現(xiàn)。 3. 輸 入： 有多個(gè)或0個(gè)輸入 4. 輸 出： 至少有一個(gè)或多個(gè)輸出。5. 可行性：原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)基本 運(yùn)算執(zhí)行有限

12、次而完成。 第24頁/共81頁2021-11-1325算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求 算法的正確性 算法特征：l 可讀性 l 健壯性 l 高效率和低存儲(chǔ)量例如要求n個(gè)數(shù)的最大值問題給出算法如下： max:=0; for（i=1 ；imax) max=x; 第25頁/共81頁2021-11-13261.4 算法描述的工具 概述：算法+數(shù)據(jù)結(jié)構(gòu)=程序 算法、語言、程序的關(guān)系 設(shè)計(jì)實(shí)現(xiàn)算法過程步驟 類描述算法的語言選擇第26頁/共81頁2021-11-1327算法、語言、程序的關(guān)系算法、語言、程序的關(guān)系1. 算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）。2. 描述算法的工具：

13、算法可用自然語言、框圖或高級(jí)程序設(shè)計(jì)語言進(jìn)行描述。3.程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。第27頁/共81頁2021-11-1328設(shè)計(jì)實(shí)現(xiàn)算法過程步驟設(shè)計(jì)實(shí)現(xiàn)算法過程步驟1. 找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系2. 確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算3. 考慮數(shù)據(jù)元素的存儲(chǔ)表示4. 選擇描述算法的語言5.設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語言加以描述。第28頁/共81頁2021-11-1329類描述算法的語言選擇類描述算法的語言選擇 類語言：類語言是接近于高級(jí)語言而又不是嚴(yán)格的高級(jí)語言，具有高級(jí)語言的一般語句設(shè)施，撇掉語言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。第29頁/共81頁2021-1

14、1-13303.賦值語句對(duì)C語言作以下描述：（1）簡單賦值 1）變量名=表達(dá)式 2） 變量+， 3） 變量- -，（2）串聯(lián)賦值變量1=變量2=變量3=變量k=表達(dá)式 第30頁/共81頁2021-11-1331對(duì)C語言作以下描述：（4）條件賦值變量名=條件表達(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頁/共81頁2021-11-13324.條件選擇語句對(duì)C語言作以下描述：if () 語句;if () 語句1; else 語句2;第32頁/共81頁2021-11-1333情況語句switch (）

15、case 判斷值1: 語句組 1； break; case 判斷值2: 語句組 2； break; case 判斷值n: 語句組n; break; default: 語句組； break; 對(duì)C語言作以下描述：第33頁/共81頁2021-11-1334對(duì)C語言作以下描述：5.循環(huán)語句for 語句for (；）循環(huán)體語句；第34頁/共81頁2021-11-1335while 語句while (） 循環(huán)體語句； 對(duì)C語言作以下描述：do while 語句do 循環(huán)體語句 while (） 第35頁/共81頁2021-11-13361.5 對(duì)算法作性能評(píng)價(jià) 評(píng)價(jià)算法的標(biāo)準(zhǔn)： 評(píng)價(jià)一個(gè)算法主要看這個(gè)算

16、法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。 性能評(píng)價(jià) 有關(guān)數(shù)量關(guān)系計(jì)算 第36頁/共81頁2021-11-1337性能評(píng)價(jià) 定義： 對(duì)問題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。問題規(guī)模N對(duì)不同的問題其含義不同： 對(duì)矩陣是階數(shù)； 對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)； 對(duì)圖是頂點(diǎn)個(gè)數(shù)； 對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。第37頁/共81頁2021-11-1338有關(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í)

17、行時(shí)間 語句頻度 算法的時(shí)間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 最壞時(shí)間復(fù)雜度 算法的空間復(fù)雜度 第38頁/共81頁2021-11-1339關(guān)于算法執(zhí)行時(shí)間 定義： 一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語句執(zhí)行時(shí)間的總和，對(duì)于語句的執(zhí)行時(shí)間是指該條語句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。l分析： 不是針對(duì)實(shí)際執(zhí)行時(shí)間的精確地算出算法執(zhí)行具體時(shí)間，而是針對(duì)算法中語句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。第39頁/共81頁2021-11-1340語句頻度 定義：語句頻度是指該語句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個(gè)矩陣相乘算法語句 對(duì)應(yīng)的語句頻度 1 1forfor（i=0i=0

18、；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=2n3+2n2 +n第40頁/共81頁2021-11-1341算法的時(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

19、; 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頁/共81頁2021-11-1342常用的時(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ù)雜度由小到大排列的頻率表：第42頁/共81頁2021-11-1343常用的時(shí)間復(fù)雜度頻率計(jì)數(shù) 常用的時(shí)間復(fù)雜度頻率表：loglog2 2n n

20、n 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í)際上只有對(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 532321601601024102432768327682147483648

21、2147483648第43頁/共81頁2021-11-1344最壞時(shí)間復(fù)雜度 定義：討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。例如冒泡排序算法第44頁/共81頁2021-11-1345void bubble(int a, int length)將a中整數(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 )

22、最壞時(shí)間復(fù)雜度 第45頁/共81頁2021-11-1346算法的空間復(fù)雜度 定義： 用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度， 記做： S(n)=O(f (n) 。第46頁/共81頁2021-11-13471.6 數(shù)據(jù)結(jié)構(gòu)與C語言表示 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的關(guān)聯(lián)性 問題描述：欲求1名學(xué)生10次C語言程序設(shè)計(jì)的測試成績總分與平均分。其中10次測驗(yàn)的成績分別為：80，85，77，56，68，83，90，92，80，98。 第47頁/共81頁2021-11-1348程序示例1-1：main() int sum，verage； /*總分，平均分*/ int t1,t2,t3,t4,t5,t6,t7,t8,

23、t9,t10； /*10個(gè)變量存10次成績*/ 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); 第48頁/共81頁2021-11-1349根據(jù)測試次數(shù)與測試成績的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲(chǔ)測驗(yàn)成績，提高了程序的適用范圍。main() int sum，erage；

24、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：第49頁/共81頁2021-11-1350結(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ù)的特定表示

25、方式的基礎(chǔ)上，對(duì)抽象算法的具體描述”。程序結(jié)構(gòu)=控制結(jié)構(gòu)+數(shù)據(jù)結(jié)構(gòu) 第50頁/共81頁2021-11-1351 結(jié)構(gòu)化程序設(shè)計(jì)目的通過設(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)來組成。結(jié)構(gòu)化程序設(shè)計(jì)方法 其一：“自頂向下，逐步求精”的設(shè)計(jì)思想 ；其二：“獨(dú)立功能，一個(gè)入口，一個(gè)出口“的模塊化結(jié)構(gòu)； 其三：“僅用三種基本控制結(jié)構(gòu)”的設(shè)計(jì)原則 第51頁/共81頁2021-11-1352面向?qū)ο笈c抽象數(shù)據(jù)類型1.1.面向?qū)ο蟮母拍睿好嫦驅(qū)ο?對(duì)

26、象+類+繼承+通信對(duì)象：指在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等 。類：具有相同屬性和服務(wù)的對(duì)象 繼承：是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?第52頁/共81頁2021-11-1353面向?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ù)元素按

27、值由小到大或由大到小的次序排列。 第53頁/共81頁2021-11-1354結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn) n結(jié)構(gòu)化的開發(fā)方法：是面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。l面向?qū)ο蟮拈_發(fā)方法：首先著眼于應(yīng)用問題所涉及的對(duì)象，包括對(duì)象、對(duì)象屬性和要求的操作，從而建立對(duì)象結(jié)構(gòu)和為解決問題需要執(zhí)行的時(shí)間序列。第54頁/共81頁2021-11-1355數(shù)學(xué)模型數(shù)學(xué)模型抽象數(shù)據(jù)模抽象數(shù)據(jù)模型型數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)非形式算非形式算法法偽語言程序偽語言程序可執(zhí)行程可執(zhí)行程序序用抽象數(shù)據(jù)類型的概念來指導(dǎo)問題的求解過程：2 2抽象數(shù)據(jù)類型與問題求解方法 n定義：抽象數(shù)據(jù)類型（簡稱ADTADT）是指基于一類

28、邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過程隱藏起來。第55頁/共81頁2021-11-1356數(shù)據(jù)的抽象數(shù)據(jù)的抽象 匯編語言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等, 它們是二進(jìn)制數(shù)據(jù)的抽象; l高級(jí)語言中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。第56頁/共81頁2021-11-1357抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 線性表的抽象數(shù)據(jù)類型的描述：ADT Linear_list數(shù)據(jù)元素 所有a

29、 ai i屬于同一數(shù)據(jù)對(duì)象，i=1i=1，2 2，n n0n n0；邏輯結(jié)構(gòu) 所有數(shù)據(jù)元素a ai i（i=1i=1，2 2，n-1n-1）存在次序關(guān)系 a ，a ai i無前趨，a an n無后繼；操作 設(shè)L L為Linear_listLinear_listInitial(L)Initial(L)初始化空線性表；Length(L)Length(L)求線性表的表長；Get(L,i)Get(L,i)取線性表的第i i個(gè)元素；Insert(L,i,b)Insert(L,i,b)在線性表的第i i個(gè)位置插入元素b b；Delete(L,i)Delete(L,i)刪除線性表的第i i個(gè)元素； 第57頁

30、/共81頁2021-11-1358抽象數(shù)據(jù)類型實(shí)現(xiàn)抽象數(shù)據(jù)類型實(shí)現(xiàn) 傳統(tǒng)的面向過程的程序設(shè)計(jì)實(shí)現(xiàn)的三種方法：l“包”、“模型”的設(shè)計(jì)方法l面向?qū)ο蟮某绦蛟O(shè)計(jì)（Object Oriented Programming，簡稱OOP）第58頁/共81頁2021-11-1359ADT的表示與實(shí)現(xiàn)的表示與實(shí)現(xiàn) ADT的定義：ADT 數(shù)據(jù)對(duì)象: 結(jié)構(gòu)關(guān)系: 基本操作: ADT 基本操作的定義格式為： (參數(shù)表) 操作前提: 操作結(jié)果:第59頁/共81頁2021-11-1360l關(guān)于參數(shù)傳遞：參數(shù)表中的參數(shù)有值參和變參兩種。用標(biāo)準(zhǔn)C語言表示和實(shí)現(xiàn)ADT描述時(shí)，主要有兩個(gè)方面： 二、用C語言函數(shù)實(shí)現(xiàn)各操作。一、

31、通過結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。ADT的表示與實(shí)現(xiàn)的表示與實(shí)現(xiàn) 第60頁/共81頁2021-11-1361算法描述規(guī)范與設(shè)計(jì)風(fēng)格 1. 算法表示格式與函數(shù)模塊化 函數(shù)返回值類型 函數(shù)名（形式參數(shù)及說明） 內(nèi)部數(shù)據(jù)說明； 執(zhí)行語句組； /*函數(shù)名*/ 算法表示格式第61頁/共81頁2021-11-1362算法描述規(guī)范與設(shè)計(jì)風(fēng)格 函數(shù)的模塊化 1. 算法表示格式與函數(shù)模塊化 包含文件語句宏定義語句自定義類型語句所有子函數(shù)的原型說明子函數(shù)1定義.子函數(shù)n定義 主函數(shù)定義 第62頁/共81頁2021-11-13

32、632. 算法描述要點(diǎn) 算法描述規(guī)范與設(shè)計(jì)風(fēng)格 加上必要的注釋 注釋形式可以用/*字符串*/ 避免函數(shù)返回值隱含說明 預(yù)定義常量和類型 # define TRUE 1 # define FALSE 0 # define MAXSIZE 100 # define OK 1 # define ERROR 0第63頁/共81頁2021-11-1364避免可能出現(xiàn)的二義性表達(dá) 注意不同的退出語句區(qū)別 return或或return：用于函數(shù)結(jié)束。：用于函數(shù)結(jié)束。break語句：可用在循環(huán)語句或語句：可用在循環(huán)語句或switch語句中結(jié)束循環(huán)過程或語句中結(jié)束循環(huán)過程或跳出情況語句。跳出情況語句。conti

33、nue語句：可用在循環(huán)語句中結(jié)束本次循環(huán)過程，進(jìn)入語句：可用在循環(huán)語句中結(jié)束本次循環(huán)過程，進(jìn)入下一次循環(huán)過程。下一次循環(huán)過程。exit語句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。語句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。使用有意義的函數(shù)名與變量名 2. 算法描述要點(diǎn) 算法描述規(guī)范與設(shè)計(jì)風(fēng)格 簡化輸入、輸出表述 規(guī)范多分支轉(zhuǎn)向 第64頁/共81頁2021-11-13653. 與參數(shù)傳遞的相關(guān)技術(shù) 算法描述規(guī)范與設(shè)計(jì)風(fēng)格 變量的作用域 全局變量：程序中所有函數(shù)都可以訪問的量 局部變量：只能在該函數(shù)中訪問的量。 參數(shù)傳遞方式 參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠

34、道。其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù)待處理數(shù)據(jù),又稱值參；第二種參數(shù)既能為操作提又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。第65頁/共81頁2021-11-1366#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(in

35、t *a,int *b) int c;c=*a, *a=*b, *b=c; 關(guān)于參數(shù)傳遞示例源程序：第66頁/共81頁2021-11-1367void main() int x=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ù)傳遞示例源程序：第67頁/共8

36、1頁2021-11-13684. 函數(shù)結(jié)果的帶出方式 算法描述規(guī)范與設(shè)計(jì)風(fēng)格 三種帶出方式: :全程量、函數(shù)返回值、傳址參數(shù)若函數(shù)結(jié)果需要帶出多個(gè)值，該怎樣實(shí)現(xiàn)?可以采用全局變量方式帶出，通過地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體方式、指針方式）兩類方式之一來實(shí)現(xiàn)。 通過參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過全局變量是一種隱式參數(shù)傳遞，一個(gè)函數(shù)中對(duì)全局變量的改變會(huì)影響其它程序的調(diào)用，使用全局變量必須注意這個(gè)問題。 第68頁/共81頁2021-11-1369全局變量方式：int MIN; /* 全局變量 */ int fun1(int a, int n) /*通過函數(shù)return返回最大值，通過

37、全局變量MIN帶回最小值*/ int i,max; max=MIN=a0; /給最大值最小值賦初值 for (i=0;imax) max=ai; if (aiMIN) MIN=ai; return(max);一個(gè)全局變量方式帶出的例子 第69頁/共81頁2021-11-1370int *fun2(int a,int n)/*將最大、最小值放到數(shù)組b中，通過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)體方式帶出的例子第71頁/共81頁2021-11-1372Data fun4(int a,int n) /*將最大、最小值放到結(jié)構(gòu)體p中，通過結(jié)構(gòu)體p帶回返回值*/Data p;int i;p.max=p.min=a0; /給最大值最小值賦初值for(i=1;ip.max) p.ma