教材 《數(shù)據(jù)結(jié)構(gòu)》（c語言版）嚴(yán)蔚敏 吳偉民 編著 清華大

1、數(shù)據(jù)結(jié)構(gòu),教材: 《數(shù)據(jù)結(jié)構(gòu)》（C語言版） 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,本課程講述的主要內(nèi)容：分別講述數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等內(nèi)容。學(xué)習(xí)本課程的基本方法：,上課認(rèn)真聽講；仔細(xì)閱讀教材中的大量例題，從而體會(huì)并最終掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念；獨(dú)立完成每個(gè)章節(jié)的練習(xí)題和作業(yè)題。,本課程的目的

2、、任務(wù)、要求：,數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，是計(jì)算機(jī)學(xué)科的核心課程，為專業(yè)技術(shù)基礎(chǔ)課。 教學(xué)要求：1.學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)特性，以便選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法；掌握算法的時(shí)間、空間復(fù)雜度。2.鍛煉學(xué)生的變成能力。要求編寫的程序結(jié)構(gòu)清楚，易讀，符合軟件工程的要求，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。本教材特性：全書采用類C語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言?？偝煽?考試成績+實(shí)驗(yàn)

3、成績+平時(shí)成績,1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語 1.3 抽象數(shù)據(jù)類型 1.4 算法和算法分析,第一章 緒論,1.1 什么是數(shù)據(jù)結(jié)構(gòu),著名計(jì)算機(jī)科學(xué)家、Pascal語言發(fā)明者N.沃思教授提出： 程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 程序: 處理問題編制一組指令集 算法:　 處理問題的策略數(shù)據(jù)結(jié)構(gòu):　問題的數(shù)學(xué)模型也就是說，計(jì)算機(jī)按照程序所描述的算法對某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理。,數(shù)值

4、計(jì)算的程序設(shè)計(jì)問題：例如：結(jié)構(gòu)靜力分析計(jì)算─ 線性 代數(shù)方程組 預(yù)報(bào)人口增長情況─ 微分方程,例1 書目自動(dòng)檢索系統(tǒng),書目文件,算法：需要檢索的書目？如何檢索？用戶界面？ 模型：？,非數(shù)值計(jì)算的程序設(shè)計(jì)問題：,例2 人機(jī)對奕問題,,,,,,,,,,算法：對奕的規(guī)則 和策略模型：？,教學(xué)計(jì)劃編排問題,算法：如何確定課程的次序關(guān)系? 模型：？,數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容： 數(shù)據(jù)結(jié)構(gòu)是一門研究非

5、數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。,,數(shù)據(jù)（data)—所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號的集合 ，是計(jì)算機(jī)操作的對象的總稱。數(shù)據(jù)元素（data element）—是數(shù)據(jù)的基本單位，由若干個(gè)數(shù)據(jù)項(xiàng)組成，也稱結(jié)點(diǎn)、元素、頂點(diǎn)或記錄。數(shù)據(jù)項(xiàng)（data item）—是數(shù)據(jù)的不可分割的最小單位，有時(shí)也稱為域（field），即數(shù)據(jù)表中的字段。數(shù)據(jù)對象(data object)：性質(zhì)相同的數(shù)據(jù)

6、元素的集合，是數(shù)據(jù)的一個(gè)子集。如大寫字母字符數(shù)據(jù)對象是集合C={‘A’,’B’,’C’,……，’Z’} ，整數(shù)數(shù)據(jù)對象是集合 N = { 0, ±1, ±2, … },1.2 基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)(data structure)：是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。,例：一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示 3214,6587,9345 ─ a1(3214

7、),a2(6587),a3(9345)在a1、a2和a3 之間存在“次序”關(guān)系 ?a1,a2?、?a2,a3? a1 a2 a3 ≠ a3 a2 a1,,數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 Data-Structure=（D，S） 其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。,,例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu) Complex=（C，R） 其

8、中，C是含兩個(gè)實(shí)數(shù)集合{c1，c2}；R={P}，P是定義在集合C上的一種關(guān)系{}，其中有序偶表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛部。,數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系。數(shù)據(jù)的存儲（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié) 構(gòu)在計(jì)算機(jī)存儲器中的存儲形式（或稱映象）。 元素/結(jié)點(diǎn)：用于表示數(shù)據(jù)元素的二進(jìn)制位(bit)的位串。 數(shù)據(jù)域：用于表示數(shù)據(jù)項(xiàng)的二進(jìn)制位(bit)的位串。,例：（321）10＝（501）8＝（10100000

9、1）2 A＝（101）8＝（001000001）2,1536,元素2,,,,,,1400,元素1,,,,,,1346,元素3,,,,,,∧,元素4,,,,,,1345,h,鏈?zhǔn)酱鎯?,h,,,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等,,,,,線性結(jié)構(gòu),非線性結(jié)構(gòu),順序存儲,鏈?zhǔn)酱鎯?線性表,棧和隊(duì)列,串,樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：,數(shù)組和廣義表,,數(shù)據(jù)類型—一個(gè)值的集合和

10、定義在這個(gè)值集上一組操作的總稱。,例：C語言中，提供int, char, float, double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef 自己定義數(shù)據(jù)類型,typedef struct { int num; char name[20]; float score;} STUDENT;

11、STUDENT stu1,stu2, *p;,1.3 抽象數(shù)據(jù)類型,抽象數(shù)據(jù)類型ADT（Abstract Data Type),定義：指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。,例：矩陣 +（求轉(zhuǎn)置、加、乘、求逆、求特征值）構(gòu)成一個(gè)矩陣的抽象數(shù)據(jù)類型,數(shù)據(jù)結(jié)構(gòu) + 定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作 = 抽象數(shù)據(jù)類型,描述方法形式定義：我們用一個(gè)三元組 （D，S，P）來表示一個(gè) 抽象數(shù)

12、據(jù)類型 ，其中D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。 格式： ADT 抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作的定義〉 } ADT 抽象數(shù)據(jù)類型名,基本操作的定義格式：

13、 基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉 操作結(jié)果：〈操作結(jié)果描述〉,賦值參數(shù)引用參數(shù)，以“＆”打頭,例：抽象數(shù)據(jù)類型三元組的定義： ADT Triplet{ 數(shù)據(jù)對象：D={e1,e2,e3 |e1,e2,e3∈Elemset} 數(shù)據(jù)關(guān)系：R1={, } 基本操作： InitTri

14、plet(&T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三元組T， 元素e1，e2和e3分別被賦以 參數(shù)v1,v2和v3的值。,DestroyTriplet（&T） 操作結(jié)果：三元組T被銷毀。 Get（T,i,&e） 初始條件：三元組T已存在， 1<=i<=3.

15、 操作結(jié)果：用e返回T的第i元的值。 Put(&T,i,e) 初始條件：三元組T已存在，1<=i<=3. 操作結(jié)果：改變T的第i元的值為e。 IsAscending(T) 初始條件：三元組T已存在。 操作結(jié)果：如果T的3個(gè)元素按升序排列，則返回1，否則返回0。,IsDescending(T) 初始條件：三元組T已存在。 操作結(jié)果：如果T的

16、3個(gè)元素按降序排列，則 返回1，否則返回0。Max(T,&e) 初始條件：三元組T已存在。 操作結(jié)果：用e返回T的3個(gè)元素中的最大值。Min(T,&e) 初始條件：三元組T已存在。 操作結(jié)果：用e返回T的3個(gè)元素中的最小值。}ADT Triplet,1.4 算法和算法分析,有窮性：對于任意一組合法輸入值，在執(zhí)行有窮步之后結(jié)束，即算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；確定性：每條指令都有

17、確切的含義，在任何條件下算法都只有一條執(zhí)行路徑；,算法五個(gè)重要特性：,算法：是對特定問題求解步驟的描述，是指令的有限序列。,可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；有輸入：有零個(gè)或多個(gè)輸入，取自特定的對象集合有輸出：有一個(gè)或多個(gè)輸出，是算法進(jìn)行信息加工后得到的結(jié)果。,算法設(shè)計(jì)的原則正確性：在合理的數(shù)據(jù)輸入下，能在有限的運(yùn)算時(shí)間內(nèi)得到正確結(jié)果；對算法是否“正確”的理解可以有以下四個(gè)層次

18、： a．程序中不含語法錯(cuò)誤； b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c．程序?qū)τ诰倪x擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；,可讀性：易于人對算法的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試；健壯性： 當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名

19、奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。,高效率與低存儲量需求： 通常，效率指的是算法執(zhí)行時(shí)間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。,算法效率的衡量方法和準(zhǔn)則 有兩種衡量算法效率的方法: 1.事后統(tǒng)計(jì)法：利用計(jì)算機(jī)內(nèi)記時(shí)功能，用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分。 2.事前分析估計(jì)法：求出算法的

20、一個(gè)時(shí)間界限函數(shù)。,和算法執(zhí)行時(shí)間相關(guān)的因素： ?算法選用的策略 ?問題的規(guī)模 ?編寫程序的語言 ?編譯程序產(chǎn)生機(jī)器代碼質(zhì)量 ?機(jī)器執(zhí)行指令速度,算法＝控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時(shí)間＝∑原操作（i）的執(zhí)行次數(shù)╳原操作（i）執(zhí)行時(shí)間 從算法中選取一種對于所研究的問題來說是基本運(yùn)算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間

21、度衡量準(zhǔn)則。,例1：NXN矩陣相乘for(i=1; i<=n; i++) for(j=1; j<=n; j++) { c[i][j]=0; for(k=1; k<=n; k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; },時(shí)間復(fù)雜度：程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。 設(shè)解決一個(gè)問題的規(guī)模為n，基本操作

22、被重復(fù)執(zhí)行的次數(shù)是n的一個(gè)函數(shù) f（n），假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作： T (n) = O(f(n)) 其中T(n)叫算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。,顯然，被稱做問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的原操作，多數(shù)情況下是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語

23、句頻度相同。,語句頻度:該語句重復(fù)執(zhí)行的次數(shù)。,例2．{++x;s=0;}例３．for(i=1; i<=n; ++i) {++x; s+=x;}例４. for(i=2; i<=n; ++i) for(j=2; j<=i-1; ++j) {++x; a[i,j]=x;},T(n)=Ｏ(1) 常量階,T(n)= O(n) 線性階,++x語句頻度為：1+2

24、+3+…+n-2 =(n-1)(n-2)/2 =(n2-3n+2)/2 T(n)= O(n2) 平方階,Ο(1)＜Ο(log2n)＜Ο(n) ＜Ο(n2)＜Ο(n3)＜Ο(2n),選擇排序,void select_sort(int& a[], int n) { // 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 for

25、( i = 0; i< n-1; ++i ) { j = i; // 選擇第 i 個(gè)最小元素 for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k; if ( j != i ) a[j] ←→ a[i] } 基本操作: } // selec

26、t_sort 比較(數(shù)據(jù)元素)操作 時(shí)間復(fù)雜度: O(n2),例5：Void bubble-sort(int a[ ]，int n) { // 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 for( i=n-1,change=TURE; i>=1 && change; - -i)

27、 { change=false; //change 為元素進(jìn)行交換標(biāo)志 for(j=0; ja[j+1]) {a[j]←→a[j+1]; change=TURE；} } //一趟起泡 } //bubble_sort,最好情況：0次最壞情況：1+2+3+…+n-1 = n(n-1)/2平均時(shí)間復(fù)雜度為：O(n2),空間復(fù)雜度：算法所需存

28、儲空間的度量，記作： S(n)=O(f(n)) 算法的存儲量包括：（1）輸入數(shù)據(jù)所占空間； （2）程序本身所占空間； （3）輔助變量所占空間。,注意：算法的所有性能之間都存在著或多或少的相互影響，因此，