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

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

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

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

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

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

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

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

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

9、存儲(chǔ)器中的實(shí)現(xiàn),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?chǔ),h,數(shù)據(jù)結(jié)構(gòu)的抽象描述,數(shù)據(jù)結(jié)構(gòu)可用二元組D=(K,R)的形式來(lái)描述。其中，K=a1,a2,an為元素集合，R=r1,r2,rm為關(guān)系的集合。 例1 設(shè)有一個(gè)線(xiàn)性表(a1,a2,a3,a4,a5)，它的抽象描述可表示為D=(K,R),其中K=a1,a2,a3,a4,a5,R=,，則它的邏輯結(jié)構(gòu)用圖描述見(jiàn)圖：,例2 設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的抽象描述為D=(K,R),其中K=a,b,c,d,e,f,g,h,r=,則它的邏輯結(jié)構(gòu)用圖描述見(jiàn)圖1-5。,例3 設(shè)一個(gè)數(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)用圖描述見(jiàn)圖,是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。,一個(gè)含抽象數(shù)據(jù)類(lèi)型的軟件模塊通常應(yīng)包含定義、表示和實(shí)現(xiàn)3個(gè)部分。 抽象數(shù)據(jù)類(lèi)型可用三元組表示： (D，S，P）,6.抽象數(shù)據(jù)類(lèi)型,采用以下格式定義抽象數(shù)據(jù)類(lèi)型： ADT抽象數(shù)據(jù)類(lèi)型名 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作： ADT抽象數(shù)據(jù)類(lèi)型名,基本操作的定義格式為 基本操作名（參數(shù)表） 初始條件： 操作結(jié)果： 基本操作有兩種參數(shù)： 賦值參數(shù)：只為操作提供輸入值 引用參數(shù)：以/由InitTriplet 分配3個(gè)元素存儲(chǔ)空間 /-基

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

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

13、機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開(kāi)銷(xiāo)規(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; ,基本操作: 乘法,基本操作重復(fù)執(zhí)行次數(shù)是 n3 時(shí)間復(fù)雜度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”的語(yǔ)句的頻度是1， 則T(n)=O(1)，稱(chēng)為常量階。,含基本操作“x自

14、增1”的語(yǔ)句的頻度是n， 則T(n)=O(n)，稱(chēng)為線(xiàn)性階。,含基本操作“x自增1”的語(yǔ)句的頻度是n2， 則T(n)=O(n2) ，稱(chēng)為平方階。,補(bǔ)充：求時(shí)間復(fù)雜度的方法 選擇基本操作 計(jì)算基本操作的重復(fù)執(zhí)行次數(shù) 寫(xiě)出T(n)=O(f(n),若計(jì)算出的基本操作的重復(fù)執(zhí)行次數(shù)是： aknk + ak-1nk-1+ a1n+a0 （其中，ak a0是常數(shù)，n是問(wè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 基本操作: 交換序列中相鄰兩個(gè)整數(shù),最壞時(shí)間復(fù)雜度T(n)=O(n2),最好情況下，即a中初始序列為自小至大有序，基本操作的執(zhí)行次數(shù)為0。,最壞情況下，即a中初始序列為自大至小有序，基本操作的執(zhí)行次數(shù)為(n-1)+(n-2)+1=n(n-1)/2,例3 分析下列算法段的時(shí)間頻度及時(shí)間復(fù)雜度 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) = = = + = + 故時(shí)間復(fù)雜度為(n3)。,在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)

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