教材 《數(shù)據(jù)結構》（c語言版）嚴蔚敏 吳偉民 編著 清華大

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

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

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

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

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

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

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

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

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

10、定義在這個值集上一組操作的總稱。,例：C語言中，提供int, char, float, double等基本數(shù)據(jù)類型，數(shù)組、結構體、共用體、枚舉等構造數(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),定義：指一個數(shù)學模型以及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象特性。,例：矩陣 +（求轉置、加、乘、求逆、求特征值）構成一個矩陣的抽象數(shù)據(jù)類型,數(shù)據(jù)結構 + 定義在此數(shù)據(jù)結構上的一組操作 = 抽象數(shù)據(jù)類型,描述方法形式定義：我們用一個三元組 （D，S，P）來表示一個 抽象數(shù)

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

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

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

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

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

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

18、： a．程序中不含語法錯誤； b．程序對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； c．程序對于精心選擇的、典型、苛刻切帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； d．程序對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結果；,可讀性：易于人對算法的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試；健壯性： 當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是產(chǎn)生莫名

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

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

21、度衡量準則。,例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]; },時間復雜度：程序運行從開始到結束所需要的時間。 設解決一個問題的規(guī)模為n，基本操作

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

23、句頻度相同。,語句頻度:該語句重復執(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 個最小元素 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ù)元素)操作 時間復雜度: 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 為元素進行交換標志 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平均時間復雜度為：O(n2),空間復雜度：算法所需存

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