數(shù)據(jù)結(jié)構(gòu)(C語言版).ppt

1、數(shù) 據(jù) 結(jié) 構(gòu)（C語言版）,嚴蔚敏 吳偉民編著 清華大學出版社,數(shù)據(jù)結(jié)構(gòu)課程的地位和作用,“數(shù)據(jù)結(jié)構(gòu)課程”是計算機專業(yè)的專業(yè)基礎(chǔ)課。 學習“數(shù)據(jù)結(jié)構(gòu)”課程需要一些課程作為它的基礎(chǔ)，如“C語言”與“離散數(shù)學”。若沒有“C語言”或其它語言基礎(chǔ)，學生就難以理解描述數(shù)據(jù)結(jié)構(gòu)及其算法的類C或類C+，更重要的是造成學生上機環(huán)節(jié)的困難，影響該課程的學習。同樣，“離散數(shù)學”課程是“數(shù)據(jù)結(jié)構(gòu)”課程的理論基礎(chǔ)，其中集合、樹及圖等重要理論知識為“數(shù)據(jù)結(jié)構(gòu)”課程的學習提供了重要的理論基礎(chǔ)。 “數(shù)據(jù)結(jié)構(gòu)”課程為“編譯原理”、“數(shù)據(jù)庫系統(tǒng)”和“操作系統(tǒng)”等課程的學習奠定必要的基礎(chǔ)。例如：“編譯原理”的表達式求解用到“數(shù)據(jù)

2、結(jié)構(gòu)”的棧知識，符號表管理技術(shù)用到哈希查找技術(shù)；“數(shù)據(jù)庫系統(tǒng)”的存儲用到B+樹知識；“操作系統(tǒng)”的設(shè)備鏈表管理用到線性鏈表知識，最短作業(yè)優(yōu)先用到隊列知識。 計算機解決現(xiàn)實問題的方法一般經(jīng)歷下列步驟： 建立數(shù)學模型設(shè)計解此模型的算法編程、調(diào)試 而數(shù)據(jù)結(jié)構(gòu)幾乎體現(xiàn)在問題求解的各個步驟，尤其是步驟2?？梢妼W好數(shù)據(jù)結(jié)構(gòu)具有十分重要的意義。,數(shù)據(jù)結(jié)構(gòu)的教學目的,懂得“數(shù)據(jù)結(jié)構(gòu)+算法=程序” 培養(yǎng)數(shù)據(jù)抽象的能力 把數(shù)據(jù)結(jié)構(gòu)和算法理論與編程實踐相結(jié)合，能夠在實際的工程實踐中靈活地予以應用。,數(shù)據(jù)結(jié)構(gòu)的教學要求,掌握并靈活應用常用的基本數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型、各種基本存儲方法、主要的算法。 掌握并簡單應用常用

3、的排序、檢索和索引算法和方法。 掌握基本的算法設(shè)計和分析技術(shù)，并對自己設(shè)計的數(shù)據(jù)結(jié)構(gòu)和算法進行簡單的分析。 在進行程序設(shè)計、調(diào)試、測試的課程項目訓練（即上機實習訓練）過程中，要求學生綜合應用所學到的數(shù)據(jù)結(jié)構(gòu)和算法知識，學會分析研究數(shù)據(jù)對象的特性，以便選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應的算法，合理地組織數(shù)據(jù)、有效地表示數(shù)據(jù)、有效地處理數(shù)據(jù)，書寫的程序結(jié)構(gòu)清楚、正確易讀，提高程序設(shè)計的質(zhì)量。,什么是數(shù)據(jù)結(jié)構(gòu) 基本概念和術(shù)語 抽象數(shù)據(jù)類型的表示與實現(xiàn) 算法和算法分析,第1章 緒論,學習要點 1. 熟悉各名詞、術(shù)語的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性

4、質(zhì)，哪些是存儲結(jié)構(gòu)的性質(zhì)。 2. 了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。 3理解算法五個要素的確切含義：動態(tài)有窮性（能執(zhí)行結(jié)束）；確定性（對于相同的輸入執(zhí)行相同的路徑）；有輸入；有輸出；可行性（用以描述算法的操作都是足夠基本的）。 4掌握計算語句頻度和估算算法時間復雜度的方法。,1.1什么是數(shù)據(jù)結(jié)構(gòu),一般來說，用計算機解決一個具體問題時，需經(jīng)歷下列步驟： 建立數(shù)學模型設(shè)計解此模型的算法編程、調(diào)試 尋求數(shù)學模型的實質(zhì)：分析問題，從中提取操作的對象，并找出對象之間的關(guān)系，然后用數(shù)學的語言加以描述。,Niklaus Wirth: Algorithm+Data Structure=Programs

5、程序設(shè)計： 為計算機處理問題編制的一組指令集 算法：處理問題的策略 數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學模型,1.1 什么是數(shù)據(jù)結(jié)構(gòu) 程序=數(shù)據(jù)結(jié)構(gòu)+算法 例1 書目自動檢索系統(tǒng),書目文件,例2 人機對奕問題,多叉路口交通燈管理問題,數(shù)據(jù)結(jié)構(gòu)定義：,數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科。,1.2 基本概念和術(shù)語,1 數(shù)據(jù)（data） 數(shù)據(jù)是指能夠輸入到計算機中，并被計算機識別和處理的符號的集合。是計算機操作的對象的總稱。 例如：數(shù)字、字母、漢字、圖形、圖像、聲音都稱為數(shù)據(jù)。,2數(shù)據(jù)元素（data element） 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。 數(shù)據(jù)元素

6、是一個數(shù)據(jù)整體中相對獨立的單位。但它還可以分割成若干個具有不同屬性的項（字段），故不是組成數(shù)據(jù)的最小單位。,3 數(shù)據(jù)對象（data object） 是性質(zhì)相同的數(shù)據(jù)元素組成的集合，是數(shù)據(jù)的一個子集。 例如，整數(shù)數(shù)據(jù)對象的集合可表示為N0，1，2.，字母字符數(shù)據(jù)對象的集合可表示為C=A,B,Z。,4 數(shù)據(jù)類型（data type） 是一組性質(zhì)相同的值的集合以及定義于這個值集合上的一組操作的總稱。 例如，高級語言中用到的整數(shù)數(shù)據(jù)類型，是指由32768到32767中值構(gòu)成的集合及一組操作（加、減、乘、除、乘方等）的總稱。,數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合。具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏

7、輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對數(shù)據(jù)所施加的運算。這三個方面的關(guān)系為： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于計算機，是數(shù)據(jù)本身所固有的。 （2）存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存貯器中的映像，必須依賴于計算機。 （3）運算是指所施加的一組操作總稱。運算的定義直接依賴于邏輯結(jié)構(gòu)，但運算的實現(xiàn)必依賴于存貯結(jié)構(gòu)。,5. 數(shù)據(jù)結(jié)構(gòu)（data structure）,從邏輯結(jié)構(gòu)劃分數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)從邏輯結(jié)構(gòu)劃分為： （1）線性結(jié)構(gòu) 元素之間為一對一的線性關(guān)系，第一個元素無直接前驅(qū)，最后一個元素無直接后繼，其余元素都有一個直接前驅(qū)和直接后繼。 （2）非線性結(jié)構(gòu) 元素之間為一對多或多對多的非線性關(guān)系，每個元素有多個直接前驅(qū)或多個

8、直接后繼。,根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu),（集合）數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系,線性結(jié)構(gòu)一個對一個，如線性表、棧、隊列,樹形結(jié)構(gòu)一個對多個，如樹,圖狀結(jié)構(gòu)多個對多個，如圖,從存貯結(jié)構(gòu)劃分數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)從存貯結(jié)構(gòu)劃分為： (1)順序存貯（向量存貯） 所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計算機內(nèi)存仍然相鄰。 (2) 鏈式存貯 所有元素存放在可以不連續(xù)的存貯單元中，但元素之間的關(guān)系可以通過地址確定，邏輯 上相鄰的元素存放到計算機內(nèi)存后不一定是相鄰的。,數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系 數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機

9、存儲器中的實現(xiàn),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈式存儲,h,數(shù)據(jù)結(jié)構(gòu)的抽象描述,數(shù)據(jù)結(jié)構(gòu)可用二元組D=(K,R)的形式來描述。其中，K=a1,a2,an為元素集合，R=r1,r2,rm為關(guān)系的集合。 例1 設(shè)有一個線性表(a1,a2,a3,a4,a5)，它的抽象描述可表示為D=(K,R),其中K=a1,a2,a3,a4,a5,R=,，則它的邏輯結(jié)構(gòu)用圖描述見圖：,例2 設(shè)一個數(shù)據(jù)結(jié)構(gòu)的抽象描述為D=(K,R),其中K=a,b,c,d,e,f,g,h,r=,則它的邏輯結(jié)構(gòu)用圖描述見圖1-5。,例3 設(shè)一個數(shù)據(jù)結(jié)構(gòu)的抽象描述為D=(K,R),其中K=1

10、,2,3,4,而R=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), 則它的邏輯結(jié)構(gòu)用圖描述見圖,是指一個數(shù)學模型以及定義在該模型上的一組操作。,一個含抽象數(shù)據(jù)類型的軟件模塊通常應包含定義、表示和實現(xiàn)3個部分。 抽象數(shù)據(jù)類型可用三元組表示： (D，S，P）,6.抽象數(shù)據(jù)類型,采用以下格式定義抽象數(shù)據(jù)類型： ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作： ADT抽象數(shù)據(jù)類型名,基本操作的定義格式為 基本操作名（參數(shù)表） 初始條件： 操作結(jié)果： 基本操作有兩種參數(shù)： 賦值參數(shù)：只為操作提供輸入值 引用參數(shù)：以/由InitTriplet 分配3個元素存儲空間 /-基

11、本操作的函數(shù)原型說明- Status InitTriplet(Triplet /InitTriplet,1.4 算法的描述和算法分析 算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列 算法特性,1）有窮性：算法必須在有限步內(nèi)結(jié)束。2）確定性：組成算法的操作必須清晰無二義性。3）可行性：組成算法的操作必須能夠在計算機上實現(xiàn)。 4）輸入：0個或多個輸入。 5）輸出：1個或多個輸出。,算法的描述采用C語言 算法的評價衡量算法優(yōu)劣的標準 正確性(correctness) 可讀性(readability) 健壯性(robustness) 效率與低存儲量,算法效率用依據(jù)該算法編

12、制的程序在計算機上執(zhí)行所消耗的時間來度量,1.事后統(tǒng)計利用計算機內(nèi)記時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分 缺點：必須先運行依據(jù)算法編制的程序 所得時間統(tǒng)計量依賴于硬件、軟件 等環(huán)境因素，有時容易掩蓋算法本 身的優(yōu)劣,2.事前分析估計一個高級語言程序在計算機上運行所消耗的時間取決于： 依據(jù)的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產(chǎn)生機器代碼質(zhì)量 機器執(zhí)行指令速度 同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，所以使用絕對時間單位衡量算法效率不合適,時間復雜度：基本操作重復執(zhí)行的次數(shù)的階數(shù) T(n)=O(f(n) 空間復雜度：是指算法在計算

13、機內(nèi)執(zhí)行時所占用的內(nèi)存開銷規(guī)模 s(n)=O(f(n),例1：NXN矩陣相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,基本操作: 乘法,基本操作重復執(zhí)行次數(shù)是 n3 時間復雜度T(n)=O(n3),(a) +x; s=0; ,(b) for (i=1;i=n;+i) +x; s+=x; ,(c) for ( j=1; j=n; +j) for ( k=1; k=n; +k) +x; s+=x; ,含基本操作“x自增1”的語句的頻度是1， 則T(n)=O(1)，稱為常量階。,含基本操作“x自

14、增1”的語句的頻度是n， 則T(n)=O(n)，稱為線性階。,含基本操作“x自增1”的語句的頻度是n2， 則T(n)=O(n2) ，稱為平方階。,補充：求時間復雜度的方法 選擇基本操作 計算基本操作的重復執(zhí)行次數(shù) 寫出T(n)=O(f(n),若計算出的基本操作的重復執(zhí)行次數(shù)是： aknk + ak-1nk-1+ a1n+a0 （其中，ak a0是常數(shù)，n是問題規(guī)模） 則T(n)=O(nk),例2 起泡排序 void bubble_sort(int a, int n) / 將a中整數(shù)序列重新排列成自小至大 有序的整數(shù)序列。 for (i=n-1, change=TRUE; i=1 / bubbl

15、e_sort 基本操作: 交換序列中相鄰兩個整數(shù),最壞時間復雜度T(n)=O(n2),最好情況下，即a中初始序列為自小至大有序，基本操作的執(zhí)行次數(shù)為0。,最壞情況下，即a中初始序列為自大至小有序，基本操作的執(zhí)行次數(shù)為(n-1)+(n-2)+1=n(n-1)/2,例3 分析下列算法段的時間頻度及時間復雜度 for(i=1;i=n;i+) for (j=1;j=i;j+) for ( k=1;k=j;k+) x=i+j-k;,T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) = = = + = + 故時間復雜度為(n3)。,在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)，則時間復

16、雜度為O(1)。另外，在語句頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。,按數(shù)量級遞增排列，常見的時間 復雜度有： 常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),.， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復雜度不斷增大，算法的執(zhí)行效率越低。,作業(yè),基礎(chǔ)知識題 1.3 1.4 1.7 1.8中的(1)、(3)、(5)、(7)小題 算法設(shè)計題 1.16,習題集：,1.3 設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R)，其中 D=d1,d2,d3,d4，R=r，r=(d1,d2),(d2,d3),(d3,d4)。 試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。,1.4 試仿照三元組的抽象數(shù)據(jù)類型寫出抽象數(shù)據(jù)類型復數(shù)的定義。,1.7 在程序設(shè)計中，可采用下列三種方法實現(xiàn)輸出