1、2022-6-211第第1 1章章 數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)概述 數(shù)據(jù)結(jié)構(gòu)研究的問題1.11.1 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念1.21.2 算法與算法性能分析1.31.3 數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介1.41.42022-6-212本章主要內(nèi)容本章主要內(nèi)容一、數(shù)據(jù)結(jié)構(gòu)研究的問題一、數(shù)據(jù)結(jié)構(gòu)研究的問題二、數(shù)據(jù)結(jié)構(gòu)的概念及有關(guān)術(shù)語二、數(shù)據(jù)結(jié)構(gòu)的概念及有關(guān)術(shù)語三、算法的概念、特點、及其性能分析方法三、算法的概念、特點、及其性能分析方法四、數(shù)據(jù)結(jié)構(gòu)與算法的描述工具類四、數(shù)據(jù)結(jié)構(gòu)與算法的描述工具類C語言簡介語言簡介2022-6-2131.1 數(shù)據(jù)結(jié)構(gòu)研究的問題 111 計算機(jī)解決實際問題的過程與步驟計算機(jī)解決實際問題的

2、過程與步驟一、解題過程。一、解題過程。計算機(jī)解決問題的過程可以歸結(jié)為五個世界、三級抽象和表示的過程。 五個世界分別是：現(xiàn)實世界、信息世界、概念世界、數(shù)據(jù)世界、機(jī)器世界。三級抽象分別是：概念抽象、數(shù)據(jù)抽象、機(jī)器抽象。2022-6-214計算機(jī)解決實際問題的過程與步驟二、解題步驟二、解題步驟 用計算機(jī)解決實際問題一般需要經(jīng)過8個步驟：1問題定義。分析問題，理解問題是什么？明確要求做什么？2、建立模型。將實際問題抽象，建立問題的數(shù)據(jù)模型。 3、定義數(shù)據(jù)。將數(shù)據(jù)模型確切定義出來。 4、尋找算法。探求數(shù)據(jù)模型的求解算法。5、編寫代碼。將算法表示成程序代碼。6、調(diào)試運行。上機(jī)調(diào)試、查錯、糾錯，運行。7、分

3、析結(jié)果。分析結(jié)果是否符合實際問題。8、總結(jié)改進(jìn)?？偨Y(jié)經(jīng)驗，加以改進(jìn)提高。2022-6-215計算機(jī)解決實際問題的過程與步驟 上述上述8 8個步驟可能是循環(huán)的，如圖所示：個步驟可能是循環(huán)的，如圖所示：2022-6-216112 數(shù)據(jù)結(jié)構(gòu)學(xué)科概念及其所研究的內(nèi)容 數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計算的程序設(shè)計問數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作專門的學(xué)科。操作專門的學(xué)科。 三個要點： 1、非數(shù)值計算問題、非數(shù)值計算問題2、數(shù)據(jù)之間的關(guān)系：邏輯關(guān)系、存儲關(guān)系。、數(shù)據(jù)之間的關(guān)系：邏輯關(guān)系、存儲關(guān)系。 3、數(shù)據(jù)的操作、數(shù)據(jù)的操作

4、：操作定義與算法實現(xiàn)操作定義與算法實現(xiàn)2022-6-217113 數(shù)據(jù)結(jié)構(gòu)的建模舉例例例1 1、 集合結(jié)構(gòu)數(shù)據(jù)模型集合結(jié)構(gòu)數(shù)據(jù)模型例例2 2、線性結(jié)構(gòu)數(shù)據(jù)模型、線性結(jié)構(gòu)數(shù)據(jù)模型例例3 3、樹結(jié)構(gòu)數(shù)據(jù)模型、樹結(jié)構(gòu)數(shù)據(jù)模型例例4 4、圖結(jié)構(gòu)數(shù)據(jù)模型、圖結(jié)構(gòu)數(shù)據(jù)模型著重體會建模思想、掌握建模過程與方法著重體會建模思想、掌握建模過程與方法。返回首頁返回首頁2022-6-21812 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念1 12 21 1 數(shù)據(jù)的有關(guān)概念數(shù)據(jù)的有關(guān)概念 1數(shù)據(jù)（Data）。表示信息的且能被計算機(jī)存儲、處理的各種物理符號統(tǒng)稱為數(shù)據(jù)。 2數(shù)據(jù)項（Data Item）。具有獨立邏輯含義且不能再分解的數(shù)據(jù)稱為數(shù)據(jù)項

5、。 （最小單位） 3數(shù)據(jù)元素（Data Element）。數(shù)據(jù)元素是相關(guān)數(shù)據(jù)項的集合。 （基本單位） 4數(shù)據(jù)對象（Data Object）。具有相同性質(zhì)的數(shù)據(jù)元素構(gòu)成的集合稱為數(shù)據(jù)類型。 2022-6-219122 數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語 1 1數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data StructureData Structure） 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) = = 數(shù)據(jù)元素集合數(shù)據(jù)元素集合 + + 一組關(guān)系集合。一組關(guān)系集合。 形式地表示形式地表示 ： Data_StructureData_Structure = ( D , R ) = ( D , R ) 2 2數(shù)據(jù)的邏輯結(jié)構(gòu)（數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical S

6、tructureLogical Structure）集合結(jié)構(gòu)：元素之間無關(guān)系。線性結(jié)構(gòu)：元素之間存在1：1關(guān)系。樹形結(jié)構(gòu)：元素之間存在1：n關(guān)系。圖狀結(jié)構(gòu)：元素之間存在m：n關(guān)系。 邏輯結(jié)構(gòu)決定能定義那些操作。邏輯結(jié)構(gòu)決定能定義那些操作。2022-6-2110數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語3 3四種物理結(jié)構(gòu)（存儲結(jié)構(gòu)）四種物理結(jié)構(gòu)（存儲結(jié)構(gòu)）順序存儲結(jié)構(gòu)：用存儲位置相鄰表示邏輯關(guān)系。鏈接存儲結(jié)構(gòu)：用指針表示邏輯關(guān)系。索引存儲結(jié)構(gòu)：用“索引+順序”方法存儲數(shù)據(jù)。散列存儲結(jié)構(gòu)：用散列表存儲數(shù)據(jù)。存儲結(jié)構(gòu)決定操作算法的實現(xiàn)及性能。存儲結(jié)構(gòu)決定操作算法的實現(xiàn)及性能。2022-6-2111123 數(shù)據(jù)類型的概念1

7、1數(shù)據(jù)類型數(shù)據(jù)類型 數(shù)據(jù)類型數(shù)據(jù)類型 = = 數(shù)據(jù)值的集合數(shù)據(jù)值的集合 + + 一組操作一組操作2 2抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型 = 數(shù)據(jù)結(jié)構(gòu) + 數(shù)據(jù)操作。抽象數(shù)據(jù)類型分為三種：原子類型：其值不能再分解成更簡單的數(shù)據(jù)類型。靜態(tài)聚合類型。其值由固定個數(shù)的數(shù)據(jù)項組成的復(fù)合數(shù)據(jù)類型。動態(tài)聚合類型。其值由個數(shù)可變的數(shù)據(jù)項組成的復(fù)合數(shù)據(jù)類型。 2022-6-2112數(shù)據(jù)類型的概念抽象數(shù)據(jù)類型的描述格式抽象數(shù)據(jù)類型的描述格式ADT ADT 數(shù)據(jù)對象定義：數(shù)據(jù)對象定義： 數(shù)據(jù)關(guān)系定義：數(shù)據(jù)關(guān)系定義： 數(shù)據(jù)運算定義：數(shù)據(jù)運算定義： ADT ADT ；其中數(shù)據(jù)運算的定義格式為：其中數(shù)據(jù)運算的定義格

8、式為： （ 參數(shù)表參數(shù)表 ） 初始條件描述初始條件描述 ； 操作結(jié)構(gòu)描述操作結(jié)構(gòu)描述 ； 2022-6-2113數(shù)據(jù)類型的概念3 3多形數(shù)據(jù)類型多形數(shù)據(jù)類型其值的成份不確定的數(shù)據(jù)類型稱為多形數(shù)據(jù)類型。它于抽象數(shù)據(jù)類型具有相同的抽象層次，不同的是，數(shù)據(jù)的關(guān)系和運算是確定的，但數(shù)據(jù)的結(jié)構(gòu)是不確定的。 返回首頁返回首頁2022-6-211413 算法與算法性能分析1 13 31 1 算法概念及特點算法概念及特點1算法的概念對某個特定問題求解步驟的一種描述稱為算法 。2算法的5個重要特征（1）有窮性。算法的步驟是有限的。（2）確定性。每個步驟的操作含義是唯一確定的。（3）可行性。每個步驟的操作機(jī)器能夠

9、實現(xiàn)。（4）輸入性。有0或多個輸入數(shù)據(jù)。（5）輸出性。有1或多個輸入數(shù)據(jù)。2022-6-2115算法與算法性能分析3 3算法的描述方法算法的描述方法（1）自然語言描述。符合人的習(xí)慣（2）圖形描述。直觀、易懂。（3）類語言描述。方便、易實現(xiàn)（4）程序設(shè)計語言描述。 就是程序。2022-6-2116132 算法的設(shè)計要求1、正確性。算法必須正確。2、易讀性。算法易讀、易懂、便于交流。3、健壯性。算法有穩(wěn)定、容錯、可靠、適應(yīng)等性能。4、經(jīng)濟(jì)性。時間效率、空間效率高2022-6-2117133 算法的性能分析 1 1算法性能的評價指標(biāo)算法性能的評價指標(biāo)（1）算法的時間復(fù)雜度。 一個算法執(zhí)行所使用的時間

10、稱為該算法的時間復(fù)雜度。 用T=T（n）表示，n為問題的規(guī)模 。最壞時間復(fù)雜度：在最壞情況下執(zhí)行算法在所花費的時間。最好時間復(fù)雜度：在最好情況下執(zhí)行算法在所花費的時間。平均時間復(fù)雜度：在平均情況下執(zhí)行算法在所花費的時間。 （2）算法的空間復(fù)雜度執(zhí)行算法過程中所使用的額外存儲空間的開銷。不包括算法程序代碼和所處理的數(shù)據(jù)本身所占用的空間部分， 記為S=S（n）單位為字節(jié)。 2022-6-2118算法的性能分析2 2算法性能的評價方法算法性能的評價方法 （1 1） 精確計算法精確計算法 計算主要操作語句的執(zhí)行次數(shù)。 （2 2）近似估計法）近似估計法 將時間和空間復(fù)雜度用O數(shù)量級表示： T（n）= O

11、（f（n） ； S（n）= O（g（n）其中f（n）和g（n）是一個已知的函數(shù)（比較簡單的），作為比較的尺度。 2022-6-2119算法的性能分析通常使用的比較尺度有：通常使用的比較尺度有： O（1），稱為常量級，算法的時間復(fù)雜度是一個常數(shù)。 O（n），稱為線性級，時間復(fù)雜度是數(shù)據(jù)量n的線性函數(shù)。 O（n2），稱為平方級，與n的二次多項式函數(shù)屬于同一數(shù)量級。 O（n3），稱為立方級，是n的三次多項式函數(shù)。 O（log2n），稱為對數(shù)級，是n的對數(shù)函數(shù) O（n log2n），是介于線性級和平方級之間一種數(shù)量級。 O（2n），稱為指數(shù)級，時間復(fù)雜度與n的指數(shù)函數(shù)是同一個數(shù)量級。 O（n!），稱為

12、階乘級， 與n的階乘屬于同一數(shù)量級。 返回首頁返回首頁2022-6-212014 數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介 1 14 41 1 符號常量定義符號常量定義# define TRUE 1# define FALSE 0# define OK 1# define ERORR 0# define OVERFLOW -1# define INFEASIBLR -21 14 42 2 數(shù)據(jù)存儲結(jié)構(gòu)定義數(shù)據(jù)存儲結(jié)構(gòu)定義用類型定義typedef描述。如：typedef int Bool ; typedef int Status ; 2022-6-2121數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介1 14 43 3 運算符運

13、算符算術(shù)運算符：+、*、/、%（取余）比較運算符：= = 、！=、=邏輯運算符：|（或）、&（與）、?。ǚ牵?1 14 44 4 函數(shù)函數(shù) （1）自定義函數(shù)一般格式為：函數(shù)類型函數(shù)名（參數(shù)表） / 算法說明 局部變量說明 ； 語句序列 ； / 函數(shù)名 2022-6-2122數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介（2 2）標(biāo)準(zhǔn)函數(shù)）標(biāo)準(zhǔn)函數(shù) max ( 表達(dá)式1, 表達(dá)式2 , , 表達(dá)式m ) / 返回m個表達(dá)式的最大值 min ( 表達(dá)式1, 表達(dá)式2 , , 表達(dá)式m ) / 返回m個表達(dá)式的最小值 abs (表達(dá)式 ) / 返回表達(dá)式的絕對值 eof ( ) / 判斷文件結(jié)束 elon (

14、) / 判斷行結(jié)束 bof ( ) / 判斷文件開始2022-6-2123數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介1 14 45 5 語句語句1計算賦值語句 變量名 = 表達(dá)式 ； / 單個變量賦值 變量名1 = 變量名2 = = 變量名n = 表達(dá)式 ； / 串聯(lián)賦值 結(jié)構(gòu)名 = 結(jié)構(gòu)名 ； / 結(jié)構(gòu)體變量整體賦值結(jié)構(gòu)名 = 值1 , 值2, ,值m 數(shù)組名 = 表達(dá)式 ；/ 數(shù)組初始化 數(shù)組名low .high= 數(shù)組名 low .high ; / 數(shù)組整體賦值變量名 變量名; / 交換賦值 變量名 = 條件表達(dá)式？表達(dá)式1：表達(dá)式2 / 條件賦值2022-6-2124數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介2I/O

15、語句 scanf ( , &變量名1, &變量名2 , , &變量名k ) / 輸入語句 printf ( , 表達(dá)式1, 表達(dá)式2 , , 表達(dá)式m ) / 輸出語句 getchar ( ) ; / 字符輸入 putchar ( ) ; / 字符輸出2022-6-21253注釋語句 / 注釋內(nèi)容 / 單行注釋 /* 注釋內(nèi)容 */ / 多行注釋 4條件選擇語句 （1）單選擇語句 if ( 條件表達(dá)式 ) 語句 S ; / S 可以是復(fù)合語句 語句序列; （2）雙選擇語句 if ( 條件表達(dá)式 ) 語句S1; else 語句S2 ; 2022-6-2126格式一： sw

16、itch ( 表達(dá)式 ) case ：語句序列1 ; break ; case ：語句序列2 ; break ; ; case ：語句序列n ; break ; default ：語句序列n+1 ; / end switch 數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介 （5）多選擇語句（開關(guān)語句） 格式二： switch case ：語句序列1 ; break ; case ：語句序列2 ; break ; ; case ：語句序列n; break ; default ：語句序列n+1 ; / end switch2022-6-2127數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介5循環(huán)語句 （1）計數(shù)循環(huán)語句 for ( 循環(huán)變量 = 初值 ；循環(huán)變量= 終值 ；+/-循環(huán)變量+ /-) 語句序列 ; （2）當(dāng)循環(huán)語句 while ( 條件表達(dá)式 ) 語句序列 ; （3）重復(fù)循環(huán)語句 do 語句序列 ; while ( 條件表達(dá)式 )2022-6-2128數(shù)據(jù)結(jié)構(gòu)與算法描述工具簡介6其他控制語句 return ; / 返回語句 break ; / case或循環(huán)終止語句 exit ( 代碼 ) ; / 異常結(jié)束語