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

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è)計設(shè)計l1.41.4 算法描述工具算法描述工具 l1.51.5 對算法作性能評價對算法作性能評價l1.61.6 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與與C C語言表示語言表示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ù)對象（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ù)值、字符以及能輸入機器且能被處理的各種符號集合機器且能被處理的各種符號集合。 數(shù)據(jù)包含整型、實型、布爾型、圖象、字符、聲音等一切可以輸入到計算機中的符號集合。C編譯程序源程序源程序（.c）目標(biāo)程序目標(biāo)程序（.obj）可執(zhí)行程序可執(zhí)行程序（.exe）C鏈接程序例如對C源程序2022-3-195數(shù)據(jù)元素（Data Element）n定義定義： 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位組成數(shù)據(jù)的基本單位 ，是數(shù)

3、據(jù)集合的個體，在計算機中通常作為一個整體進行考慮和處理。例如：. . . . . . 北京1983.11河北女 趙虹玲101 住 址 出生年月 籍 貫性 別 姓 名 學(xué) 號 數(shù)據(jù)元素數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)項2022-3-196數(shù)據(jù)對象（Data Object） n定義定義： 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集性質(zhì)相同的數(shù)據(jù)元素的集合合，是數(shù)據(jù)的一個子集。整數(shù)集合：N=0，1，2， 無限集字符集合：C=A，B，Z 有限集例如：2022-3-197數(shù)據(jù)結(jié)構(gòu)（Data Structure） n定義： 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特數(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é) 號 2022-3-198數(shù)據(jù)結(jié)構(gòu)（Data Structure）教研室實驗室 系處研究機構(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ì)相同的值集合以及定義在這個值集合上的一組操作的總稱及定義在這個值集合上的一組操作的總稱。如在高級語言中，整型類型的取值范圍為：-32768+32767，

5、運算符集合為加、減、乘、除、取模，即+、-、*、/、%。2022-3-1910數(shù)據(jù)類型(Data Type)n高級語言中的數(shù)據(jù)類型分為兩大類：1.原子類型原子類型，其值不可分解。如C語言中的標(biāo)準(zhǔn)類型（整型、實型、字符型、）。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ù)類型實現(xiàn) nADT的表示與實現(xiàn)n面向?qū)ο蟮母拍頽結(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點

6、2022-3-19121.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 n邏輯結(jié)構(gòu) n存儲結(jié)構(gòu) 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ù)元素之間除了同屬于一個集合的關(guān)系外，無任何其它關(guān)系。一個集合的關(guān)系外，無任何其它關(guān)系。 集合集合例如：2022-3-1915線性結(jié)構(gòu)n定義：定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著結(jié)構(gòu)中的數(shù)據(jù)元

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

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

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

10、865050100003100003劉曉峰劉曉峰 男男 34534500001301300000252500004504500000100004100004趙趙 俊俊 女女 56056090902252259090656500007217218080100005100005孫孫 濤濤 男男 45045060601901908080505000005915918080 100121100121張興強張興強 男男 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)容可歸納為三個部分，邏

11、輯結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)存儲結(jié)構(gòu)和和運算集合運算集合：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映像方式把它們存放在計算機存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。 2022-3-19231.3 算法 n算法（算法（AlgorithmAlgorithm）定義）定義 n算法的特性算法的特性 n算法設(shè)計的要求算法設(shè)計的要求 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ī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。特定問題而規(guī)定的一系列操作。 2022-3-1925算法的特性1. 有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)2. 確定性：算法中的每一個步驟必須有確定含義，無二算法中的每一個步驟必須有確定含義，無二義性得以實現(xiàn)。義性得以實現(xiàn)。 3. 輸 入： 有多個或有多個或0個輸入個輸入 4. 輸 出： 至少有一個或多個輸出。至少有一個或多個輸出。5. 可行性：原則上能精確進行，操作可通過已實現(xiàn)基本原則上能精確進行，操作可通過已實現(xiàn)基本運算執(zhí)行有限次而

13、完成。運算執(zhí)行有限次而完成。 2022-3-1926算法設(shè)計的要求 n算法的正確性 算法特征：l 可讀性 l 健壯性 l 高效率和低存儲量例如要求n個數(shù)的最大值問題給出算法如下： max=0; for（i=1 ；imax) max=x; 2022-3-19271.4 算法描述的工具 n概述：算法+數(shù)據(jù)結(jié)構(gòu)=程序 n算法、語言、程序的關(guān)系 n設(shè)計實現(xiàn)算法過程步驟n類描述算法的語言選擇2022-3-1928算法、語言、程序的關(guān)系1. 算法：描述了數(shù)據(jù)對象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存儲關(guān)系描述）。2. 描述算法的工具：算法可用自然語言、框圖或高級程序設(shè)計語言進行描述。3.程序是算法在計算機

14、中的實現(xiàn)。2022-3-1929設(shè)計實現(xiàn)算法過程步驟1. 找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系2. 確定在某一數(shù)據(jù)對象上所施加運算3. 考慮數(shù)據(jù)元素的存儲表示4. 選擇描述算法的語言5.設(shè)計實現(xiàn)求解的算法，并用程序語言加以描述。2022-3-1930類描述算法的語言選擇n類語言：類語言是接近于高級語言而又不是嚴格的高級語言，類語言是接近于高級語言而又不是嚴格的高級語言，具有高級語言的一般語句設(shè)施，撇掉語言中的細節(jié)，具有高級語言的一般語句設(shè)施，撇掉語言中的細節(jié)，以便把注意力主要集中在算法處理步驟本身的描述以便把注意力主要集中在算法處理步驟本身的描述上。上。2022-3-19313.賦值語句賦值語句

15、對C語言作以下描述：（1）簡單賦值簡單賦值 1）變量名）變量名=表達式表達式 2） 變量變量+， 3） 變量變量- -，（2）串聯(lián)賦值串聯(lián)賦值變量變量1=變量變量2=變量變量3=變量變量k=表達式表達式 2022-3-1932對C語言作以下描述：（4）條件賦值條件賦值變量名變量名=條件表達式？表達式條件表達式？表達式1:表達式表達式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.條件選擇語句對C語言作以下描述：if () 語句;if () 語句1; else 語句

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

17、評價 n評價算法的標(biāo)準(zhǔn)： 評價一個算法主要看這個算法所占用機器資源的多少，而這些資源中時間代價與空間代價是兩個主要的方面，通常是以算法執(zhí)行所需的機器時間和所占用的存儲空間來判斷一個算法的優(yōu)劣。 n性能評價 n有關(guān)數(shù)量關(guān)系計算有關(guān)數(shù)量關(guān)系計算 2022-3-1938性能評價性能評價n定義：定義： 對問題規(guī)模與該算法在運行時所占的空間對問題規(guī)模與該算法在運行時所占的空間S與與所耗費的時間所耗費的時間T給出一個數(shù)量關(guān)系的評價給出一個數(shù)量關(guān)系的評價。問題規(guī)模問題規(guī)模N對不同的問題其含義不同：對不同的問題其含義不同： 對矩陣是階數(shù)；對矩陣是階數(shù)； 對多項式運算是多項式項數(shù)；對多項式運算是多項式項數(shù)； 對

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

19、的執(zhí)行時間大致上等于其所有語句執(zhí)行時間的總和，對于語句的執(zhí)行時間是指該條語句的執(zhí)行次數(shù)和執(zhí)行一次所需時間的乘積。l分析分析： 不是針對實際執(zhí)行時間精確算出算法執(zhí)行的具不是針對實際執(zhí)行時間精確算出算法執(zhí)行的具體時間，而是針對算法中語句的執(zhí)行次數(shù)做出估計，體時間，而是針對算法中語句的執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。從中得到算法執(zhí)行時間的信息。2022-3-1941語句頻度 n定義：定義：語句頻度是指該語句在一個算法中重復(fù)執(zhí)行語句頻度是指該語句在一個算法中重復(fù)執(zhí)行的次數(shù)。的次數(shù)。例如：例如：兩個兩個矩陣矩陣相乘相乘算法語句算法語句 對應(yīng)的對應(yīng)的語句頻度語句頻度 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算法的時間復(fù)雜度 算法的時間復(fù)雜度，即是算法的時間量度算法的時間復(fù)雜度，即是算法的時間量度記做：記做： T(n)=O(f(n)例如給出例如給出

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

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

23、間復(fù)雜度，即分析最壞情況下以估計出算法執(zhí)行時間的上分析最壞情況下以估計出算法執(zhí)行時間的上界。界。例如冒泡排序算法例如冒泡排序算法2022-3-1946void bubble(int a, int length)將將a中整數(shù)數(shù)組重新排序，達到中整數(shù)數(shù)組重新排序，達到遞增有序遞增有序 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 )最壞時間復(fù)雜最壞時間復(fù)雜度度2022

24、-3-1947算法的空間復(fù)雜度 n定義： 用空間復(fù)雜度作為算法所需存儲空間的量度，用空間復(fù)雜度作為算法所需存儲空間的量度， 記做：記做： S(n)=O(f(n)。2022-3-19481.6 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)與C語言表示語言表示 1.6.1 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計的關(guān)聯(lián)性數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計的關(guān)聯(lián)性 問題描述：問題描述：欲求1名學(xué)生10次C語言程序設(shè)計的測試成績總分與平均分。其中10次測驗的成績分別為：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個變量存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; /*計算總分*/ average=sum/10; /*計算平均分*/ printf(“總分=%dn”,sum); printf(“平均分=%dn”, average); 2022-3-1950根據(jù)測試次數(shù)與測試成績的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲測驗成績，提高了程序的根據(jù)測試次數(shù)與測試成績的關(guān)系，采用數(shù)組

26、結(jié)構(gòu)存儲測驗成績，提高了程序的適用范圍。適用范圍。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; /*計算平均分*/ printf(“總分=%dn”,sum); printf(“平均分=%dn”, average); 程序示例程序示例1-2：2022-3-19511.6.2 結(jié)構(gòu)化程序設(shè)計與函數(shù)的模塊化結(jié)構(gòu)化程序設(shè)計與函數(shù)的模塊化 結(jié)構(gòu)化程序設(shè)計 ：是為使程序具有合

27、理的結(jié)構(gòu)，以保證程序正確性而規(guī)定的一套程序設(shè)計的方法 。程序設(shè)計的實質(zhì)：算法+數(shù)據(jù)結(jié)構(gòu)=程序 即“程序是在數(shù)據(jù)的特定表示方式的基礎(chǔ)上，對抽象算法的具體描述”。程序結(jié)構(gòu)=控制結(jié)構(gòu)+數(shù)據(jù)結(jié)構(gòu) 2022-3-1952 結(jié)構(gòu)化程序設(shè)計目的通過設(shè)計結(jié)構(gòu)良好的程序，以程序的靜態(tài)良好結(jié)構(gòu)保證以程序的靜態(tài)良好結(jié)構(gòu)保證程序動態(tài)執(zhí)行的正確性程序動態(tài)執(zhí)行的正確性，使程序易理解、易調(diào)試、易維護，以提高軟件開發(fā)的效率，減少出錯率。結(jié)構(gòu)化程序設(shè)計的構(gòu)成單元任何程序都可由順序、選擇、重復(fù)三種基本控制結(jié)構(gòu)來組成。結(jié)構(gòu)化程序設(shè)計方法 其一：其一：“自頂向下，逐步求精自頂向下，逐步求精”的設(shè)計思想的設(shè)計思想 ；其二：“獨立功能，

28、一個入口，一個出口獨立功能，一個入口，一個出口“的模塊化結(jié)構(gòu)的模塊化結(jié)構(gòu)； 其三：“僅用三種基本控制結(jié)構(gòu)僅用三種基本控制結(jié)構(gòu)”的設(shè)計原則的設(shè)計原則 2022-3-19531.6.3 面向?qū)ο笈c抽象數(shù)據(jù)類型1.1.面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍睿好嫦驅(qū)ο?對象+類+繼承+通信對象：指在應(yīng)用問題中出現(xiàn)的各種實體、事件、規(guī)格說明等 。類：具有相同屬性和服務(wù)的對象 繼承：是是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?2022-3-1954面向?qū)ο蟪绦蛟O(shè)計的特點是封裝性、繼承性和多態(tài)性面向?qū)ο蟪绦蛟O(shè)計的特點是封裝性、繼承性和多態(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)中某個指定數(shù)據(jù)元素 ；更新更新：改變數(shù)據(jù)結(jié)構(gòu)中某個元素的值，在概念上等價于刪除和插入操作的組合 ；查找查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個特定要求的數(shù)據(jù)元素（的位置和值）； 排序排序：（在線性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。 2022-3-1955結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點 n結(jié)構(gòu)化的開發(fā)方法：是面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實現(xiàn)的功能。l面向?qū)ο蟮拈_發(fā)方法面向?qū)ο蟮拈_發(fā)方法：首先著眼于應(yīng)用問題所涉及的對象，包括對象、對象屬性和要求的操作，從而建立對象結(jié)構(gòu)和

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

31、藏起來；它定義了一組運算，但將運算的實現(xiàn)過程隱藏隱藏起來；它定義了一組運算，但將運算的實現(xiàn)過程隱藏起來。起來。2022-3-1957數(shù)據(jù)的抽象n匯編語言中十進制表示的數(shù)據(jù)98.65、9.6E3等, 它們是二進制數(shù)據(jù)的抽象; l高級語言中，給出更高一級的數(shù)據(jù)抽象，如整型、實型、字符型等，還可以進一步定義更高級的數(shù)據(jù)抽象，如各種表、隊、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。2022-3-1958抽象數(shù)據(jù)類型n線性表的抽象數(shù)據(jù)類型的描述：ADT Linear_list數(shù)據(jù)元素數(shù)據(jù)元素 所有所有a ai i屬于同一數(shù)據(jù)對象，屬于同一數(shù)據(jù)對象，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無前趨，無前趨，a an n無后繼；無后繼；操作操作 設(shè)設(shè)L L為為Linear_listLinear_listInitial(L)Initial(L)初始化空線性表；初始化空線性表；Length(L)Length(L)求線性表的表長；求線性表的表長；Get(L,i)Get(L,i)取線性表的第取線性表的第i i個元素；個元素；Insert(L,i,b)Insert(L,i,b)在線性表的第在線性表的第i i個位置插入元素個位置插入元素b b；Delete(L,i)De

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

34、主要有兩個方面： 二、用C語言函數(shù)實現(xiàn)各操作。一、通過結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個名字。ADT的表示與實現(xiàn)的表示與實現(xiàn)2022-3-19621.6.4 算法描述規(guī)范與設(shè)計風(fēng)格算法描述規(guī)范與設(shè)計風(fēng)格 1. 算法表示格式與函數(shù)模塊化 函數(shù)返回值類型 函數(shù)名（形式參數(shù)及說明） 內(nèi)部數(shù)據(jù)說明； 執(zhí)行語句組； /*函數(shù)名*/ 算法表示格式2022-3-19631.6.4 算法描述規(guī)范與設(shè)計風(fēng)格算法描述規(guī)范與設(shè)計風(fēng)格 函數(shù)的模塊化 1. 算法表示格式與函數(shù)模塊化 包含文件語句包含文件語句宏定義語句宏定義語句自定義類型語句

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

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

37、述規(guī)范與設(shè)計風(fēng)格 簡化輸入、輸出表述簡化輸入、輸出表述 規(guī)范多分支轉(zhuǎn)向規(guī)范多分支轉(zhuǎn)向 2022-3-19663. 與參數(shù)傳遞的相關(guān)技術(shù) 1.6.4 算法描述規(guī)范與設(shè)計風(fēng)格算法描述規(guī)范與設(shè)計風(fēng)格 變量的作用域變量的作用域 全局變量：程序中所有函數(shù)都可以訪問的量 局部變量：只能在該函數(shù)中訪問的量。 參數(shù)傳遞方式參數(shù)傳遞方式 參數(shù)傳遞是函數(shù)之間進行信息通訊的重要渠道。參數(shù)傳遞是函數(shù)之間進行信息通訊的重要渠道。其參數(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è)計風(fēng)格算法描述規(guī)范與設(shè)計風(fēng)格 三種帶出方式三種帶出方式: :全程量、函數(shù)返回值、傳址參數(shù)全程量、函數(shù)返回值、傳址

40、參數(shù)若函數(shù)結(jié)果需要帶出多個值，該怎樣實現(xiàn)若函數(shù)結(jié)果需要帶出多個值，該怎樣實現(xiàn)?可以采用可以采用全局全局變量方式帶出，變量方式帶出，通過地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體通過地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體方式、指針方式）兩類方式之一來實現(xiàn)。方式、指針方式）兩類方式之一來實現(xiàn)。 通過參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過通過參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過全局變量是一種隱式參數(shù)傳遞，一個函數(shù)中對全局變量的全局變量是一種隱式參數(shù)傳遞，一個函數(shù)中對全局變量的改變會影響其它程序的調(diào)用，使用全局變量必須注意這個改變會影響其它程序的調(diào)用，使用全局變量必須注意這個問題。問題。 2022-3-

41、1970全局變量方式：int MIN; /* 全局變量 */ int fun1(int a, int n) /*通過函數(shù)return返回最大值，通過全局變量MIN帶回最小值*/ int i,max; max=MIN=a0; /給最大值最小值賦初值 for (i=0;imax) max=ai; if (aiMIN) MIN=ai; return(max);一個全局變量方式帶出的例子一個全局變量方式帶出的例子 2022-3-1971int *fun2(int a,int n)/*將最大、最小值放到數(shù)組b中，通過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中，通過結(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);指針方式帶出的例子指針方式帶出的例子2022-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í)特點數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點 n關(guān)于本書內(nèi)容編寫說明關(guān)于本書內(nèi)容編寫說明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ù)庫數(shù)據(jù)庫人工智能人工智能專業(yè)基礎(chǔ)課專業(yè)基礎(chǔ)課操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理非線性程序設(shè)計非線性程序設(shè)計離散數(shù)學(xué)離散數(shù)學(xué)語言程序設(shè)計語言程序