數(shù)據(jù)結構耿國華

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

2、結構（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）目標程序目標程序（.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 住 址 出生年月 籍 貫性 別 姓 名 學 號 數(shù)據(jù)元素數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)項2022-3-196數(shù)據(jù)對象（Data Object） n定義定義： 數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集性質相同的數(shù)據(jù)元素的集合合，是數(shù)據(jù)的一個子集。整數(shù)集合：N=0，1，2， 無限集字符集合：C=A，B，Z 有限集例如：2022-3-197數(shù)據(jù)結構（Data Structure） n定義： 數(shù)據(jù)結構是指相互之間存在一種或多種特數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素集合定關系的數(shù)據(jù)元

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

5、運算符集合為加、減、乘、除、取模，即+、-、*、/、%。2022-3-1910數(shù)據(jù)類型(Data Type)n高級語言中的數(shù)據(jù)類型分為兩大類：1.原子類型原子類型，其值不可分解。如C語言中的標準類型（整型、實型、字符型、）。2.結構類型結構類型，其值是由若干成分按某種結構組成的，因此是可以分解的，并且它的成分可以是非結構的，也可以是結構的。指針類型屬于哪種類型？指針類型屬于哪種類型？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面向對象的概念n結構化的開發(fā)方法與面向對象開發(fā)方法不同點

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

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

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

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

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

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

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

14、中的實現(xiàn)。2022-3-1929設計實現(xiàn)算法過程步驟1. 找出與求解有關的數(shù)據(jù)元素之間的關系2. 確定在某一數(shù)據(jù)對象上所施加運算3. 考慮數(shù)據(jù)元素的存儲表示4. 選擇描述算法的語言5.設計實現(xiàn)求解的算法，并用程序語言加以描述。2022-3-1930類描述算法的語言選擇n類語言：類語言是接近于高級語言而又不是嚴格的高級語言，類語言是接近于高級語言而又不是嚴格的高級語言，具有高級語言的一般語句設施，撇掉語言中的細節(jié)，具有高級語言的一般語句設施，撇掉語言中的細節(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 下標下標11下標下標2=2=數(shù)組名數(shù)組名2 2 下標下標11下標下標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評價算法的標準： 評價一個算法主要看這個算法所占用機器資源的多少，而這些資源中時間代價與空間代價是兩個主要的方面，通常是以算法執(zhí)行所需的機器時間和所占用的存儲空間來判斷一個算法的優(yōu)劣。 n性能評價 n有關數(shù)量關系計算有關數(shù)量關系計算 2022-3-1938性能評價性能評價n定義：定義： 對問題規(guī)模與該算法在運行時所占的空間對問題規(guī)模與該算法在運行時所占的空間S與與所耗費的時間所耗費的時間T給出一個數(shù)量關系的評價給出一個數(shù)量關系的評價。問題規(guī)模問題規(guī)模N對不同的問題其含義不同：對不同的問題其含義不同： 對矩陣是階數(shù)；對矩陣是階數(shù)； 對多項式運算是多項式項數(shù)；對多項式運算是多項式項數(shù)； 對

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

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

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

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

23、間復雜度，即分析最壞情況下以估計出算法執(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 )最壞時間復雜最壞時間復雜度度2022

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

26、結構存儲測驗成績，提高了程序的適用范圍。適用范圍。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 結構化程序設計與函數(shù)的模塊化結構化程序設計與函數(shù)的模塊化 結構化程序設計 ：是為使程序具有合

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

28、一個入口，一個出口獨立功能，一個入口，一個出口“的模塊化結構的模塊化結構； 其三：“僅用三種基本控制結構僅用三種基本控制結構”的設計原則的設計原則 2022-3-19531.6.3 面向對象與抽象數(shù)據(jù)類型1.1.面向對象的概念面向對象的概念：面向對象=對象+類+繼承+通信對象：指在應用問題中出現(xiàn)的各種實體、事件、規(guī)格說明等 。類：具有相同屬性和服務的對象 繼承：是是面向對象方法的最有特色的方面。 2022-3-1954面向對象程序設計的特點是封裝性、繼承性和多態(tài)性面向對象程序設計的特點是封裝性、繼承性和多態(tài)性 與數(shù)據(jù)結構密切相關的是定義在數(shù)據(jù)結構上的一組操作。 基本操作主要有：基本操作主要有：

29、插入插入：在數(shù)據(jù)結構中的指定位置上增添新的數(shù)據(jù)元素 ；刪除刪除：刪去數(shù)據(jù)結構中某個指定數(shù)據(jù)元素 ；更新更新：改變數(shù)據(jù)結構中某個元素的值，在概念上等價于刪除和插入操作的組合 ；查找查找：在數(shù)據(jù)結構中尋找滿足某個特定要求的數(shù)據(jù)元素（的位置和值）； 排序排序：（在線性結構中）重新安排數(shù)據(jù)元素之間的邏輯順序關系，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。 2022-3-1955結構化與面向對象開發(fā)方法的不同點 n結構化的開發(fā)方法：是面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實現(xiàn)的功能。l面向對象的開發(fā)方法面向對象的開發(fā)方法：首先著眼于應用問題所涉及的對象，包括對象、對象屬性和要求的操作，從而建立對象結構和

30、為解決問題需要執(zhí)行的時間序列。2022-3-1956數(shù)學模型數(shù)學模型抽象數(shù)據(jù)模型抽象數(shù)據(jù)模型數(shù)據(jù)結構數(shù)據(jù)結構非形式算法非形式算法偽語言程序偽語言程序可執(zhí)行程序可執(zhí)行程序用抽象數(shù)據(jù)類型的概念來指導問題的求解過程：用抽象數(shù)據(jù)類型的概念來指導問題的求解過程：2 2抽象數(shù)據(jù)類型與問題求解方法抽象數(shù)據(jù)類型與問題求解方法 n定義：抽象數(shù)據(jù)類型（簡稱抽象數(shù)據(jù)類型（簡稱ADTADT）是指基于一類邏輯）是指基于一類邏輯關系的數(shù)據(jù)類型以及定義在這個類型之上的一關系的數(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ù)抽象，如各種表、隊、棧、樹、圖、窗口、管理器等復雜的抽象數(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；邏輯結構邏輯

32、結構 所有數(shù)據(jù)元素所有數(shù)據(jù)元素a ai i（i=1i=1，2 2，n-1n-1）存在次序關系）存在次序關系 a ，a ai i無前趨，無前趨，a an n無后繼；無后繼；操作操作 設設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)的面向過程的程序設計傳統(tǒng)的面向過程的程序設計實現(xiàn)的三種方法：l“包包”、“模型模型”的設計方法的設計方法l面向對象的程序設計面向對象的程序設計（Object Oriented Programming，簡稱OOP）2022-3-1960ADT的表示與實現(xiàn) nADT的定義：ADT 數(shù)據(jù)對象: 結構關系: 基本操作: ADT 基本操作的定義格式為： (參數(shù)表) 操作前提: 操作結果:2022-3-1961l關于參數(shù)傳遞：參數(shù)表中的參數(shù)有值參和變參兩種。用標準C語言表示和實現(xiàn)ADT描述時，

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

35、自定義類型語句所有子函數(shù)的原型說明所有子函數(shù)的原型說明子函數(shù)子函數(shù)1定義定義.子函數(shù)子函數(shù)n定義定義 主函數(shù)定義主函數(shù)定義 2022-3-19642. 算法描述要點 1.6.4 算法描述規(guī)范與設計風格算法描述規(guī)范與設計風格 加上必要的注釋加上必要的注釋 注釋形式可以用/*字符串*/ 避免函數(shù)返回值隱含說明避免函數(shù)返回值隱含說明 預定義常量和類型預定義常量和類型 # 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ù)結束。：用于函數(shù)結束。break語句：可用在循環(huán)語句或語句：可用在循環(huán)語句或switch語句中結束循環(huán)過程或語句中結束循環(huán)過程或跳出情況語句。跳出情況語句。continue語句：可用在循環(huán)語句中結束本次循環(huán)過程，進入語句：可用在循環(huán)語句中結束本次循環(huán)過程，進入下一次循環(huán)過程。下一次循環(huán)過程。 exit語句：表示出現(xiàn)異常情況時，控制退出函數(shù)。語句：表示出現(xiàn)異常情況時，控制退出函數(shù)。 使用有意義的函數(shù)名與變量名使用有意義的函數(shù)名與變量名 2. 算法描述要點算法描述要點 1.6.4 算法描述規(guī)范與設計風格算法描

37、述規(guī)范與設計風格 簡化輸入、輸出表述簡化輸入、輸出表述 規(guī)范多分支轉向規(guī)范多分支轉向 2022-3-19663. 與參數(shù)傳遞的相關技術 1.6.4 算法描述規(guī)范與設計風格算法描述規(guī)范與設計風格 變量的作用域變量的作用域 全局變量：程序中所有函數(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ù)，又能返回操作結果，也稱變量參數(shù)。供待處理數(shù)據(jù)，又能返回操作結果，也稱變量參數(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; 關于參數(shù)傳遞示例源程序關于參數(shù)傳遞示例源程序：2022-3-1968void main() int x=100,y=800; swap1(x

39、,y); /*調用函數(shù)swap1()*/printf(“n調用swap1后x= %d,y=%d”,x,y); /*輸出調用swap1后的數(shù)據(jù)*/x=100;y=800;swap2(&x,&y); /*調用函數(shù)swap2()*/ printf(“n調用swap2后x=%d,y=%d”,x,y); /*輸出調用swap2后的數(shù)據(jù)*/ 關于參數(shù)傳遞示例源程序關于參數(shù)傳遞示例源程序：2022-3-19694. 函數(shù)結果的帶出方式函數(shù)結果的帶出方式 1.6.4 算法描述規(guī)范與設計風格算法描述規(guī)范與設計風格 三種帶出方式三種帶出方式: :全程量、函數(shù)返回值、傳址參數(shù)全程量、函數(shù)返回值、傳址

40、參數(shù)若函數(shù)結果需要帶出多個值，該怎樣實現(xiàn)若函數(shù)結果需要帶出多個值，該怎樣實現(xiàn)?可以采用可以采用全局全局變量方式帶出，變量方式帶出，通過地址傳遞帶出（數(shù)組方式、結構體通過地址傳遞帶出（數(shù)組方式、結構體方式、指針方式）兩類方式之一來實現(xiàn)。方式、指針方式）兩類方式之一來實現(xiàn)。 通過參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過通過參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過全局變量是一種隱式參數(shù)傳遞，一個函數(shù)中對全局變量的全局變量是一種隱式參數(shù)傳遞，一個函數(shù)中對全局變量的改變會影響其它程序的調用，使用全局變量必須注意這個改變會影響其它程序的調用，使用全局變量必須注意這個問題。問題。 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);結構體方式帶出的例子結構體方式帶出的例子2022-3-1973Data fun4(int a,int n) /*將最大、最小值放到結構體p中，通過結構體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 關于學習數(shù)據(jù)結構 n數(shù)據(jù)結構課程地位數(shù)據(jù)結構課程地位 n數(shù)據(jù)結構課程學習特點數(shù)據(jù)結構課程學習特點 n關于本書內容編寫說明關于本書內容編寫說明2022-3-1975數(shù)據(jù)結構課程地位n 數(shù)據(jù)結構與其它課程關系圖：數(shù)據(jù)結構與其它課程關系圖：數(shù)據(jù)結構數(shù)據(jù)庫數(shù)據(jù)庫人工智能人工智能專業(yè)基礎課專業(yè)基礎課操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理非線性程序設計非線性程序設計離散數(shù)學離散數(shù)學語言程序設計語言程序