1、數據結構及算法數據結構及算法b課程名稱：課程名稱：數據結構及算法數據結構及算法b預修課程預修課程: C語言語言, 高等數學高等數學b教材教材：1.數據結構數據結構(C語言版語言版)清華大學出版社清華大學出版社 1997 2.數據結構題集數據結構題集(C語言版語言版)清華大學出版社清華大學出版社 1999教材中習題放在每章結束教材中習題放在每章結束,但學生在每周都應該完成與上但學生在每周都應該完成與上課內容相應的部分小題課內容相應的部分小題有精力的同學應該思考數據結構題集中未列為必做有精力的同學應該思考數據結構題集中未列為必做的練習的練習,這會有助于理解課程內容這會有助于理解課程內容習題包括理論

2、習題和上機實驗題習題包括理論習題和上機實驗題實驗題要求用實驗題要求用C語言編寫語言編寫,并在計算機上調試通過并在計算機上調試通過緒論緒論11什么是數據結構12基本概念和術語13抽象數據類型的表示與實現14算法和算法分析 141 算法 142 算法設計的要求 143 算法效率的度量 144 算法的存儲空間需求1.1 什么是什么是數據結構數據結構計算機解決問題的步驟 實際問題 - 數學模型-算法-程序- 結果 工程師 數學家 程序員計算機的用途科學計算(數值運算): 解方程(組), 函數求值, 概率統計等非數值運算: 字符, 表格, 圖象, 聲音等計算機的用途-數值運算水庫大壩的應力計算預報人口增

3、長天氣預報計算機的用途-非數值運算書目檢索系統001高等數學劉金明S01002線性代數華羅庚X01003高等數學徐漢洋S01004普通物理羅志高W01高等數學001,003線性代數002普通物理004劉 金 明001華 羅 庚002羅 志 高004X002S001,003多叉路口的交通燈管理問題有連線的節點用不同的顏色標記, 表示不能同時通行.要求使用的顏色數盡可能少, 以使減少等待時間.圖論中的四色問題.多叉路口的交通燈管理問題 不能同時通行的通路用連線把它們連起來, 它們有: A-B 通路: CA, BD, BC A-D 通路: CB, BC B-C 通路: AB, AD B-D 通路:

4、AB, CB C-A 通路: AB C-B 通路: BD, AD計算機的用途-非數值運算計算機與人對奕問題數據結構的定義描述非數值計算問題的模型是- 如表、樹、圖之類的數據結構數據結構是- 研究計算機的操作對象(數據)以及它們之間的關系和操作等的學科.學科數據結構在計算機科學中所處的地位綜合性的專業基礎課1.2 基本概念和術語基本概念和術語數據：數據：計算機程序處理的符號的總稱。數據元素：數據元素：數據的基本單位。 通常作為一個整體進行處理。數據項：數據項：數據的不可分割的最小單位。 一個數據元素可以由若干個數據項構成。數據對象：數據對象：性質相同的數據元素的集合。數據結構：數據結構：相互間存

5、在一種或多種關系的數據元素的集合。 集合集合 線性結構線性結構 樹型結構樹型結構 圖狀結構（網狀結構）圖狀結構（網狀結構）數據結構的數學定義數據結構的數學定義數據結構是一個二元組數據結構是一個二元組 Data_Structure = (D,S)Data_Structure = (D,S)D D 數據元素的有限集合S S 定義在D上的關系的有限集合邏輯結構和物理結構邏輯結構和物理結構邏輯結構邏輯結構: 數據元素之間的邏輯關系數據元素之間的邏輯關系物理結構物理結構: 數據結構在計算機中的表示數據結構在計算機中的表示,又稱存儲結構又稱存儲結構算法的設計取決于選定的邏輯結構算法的設計取決于選定的邏輯結

6、構算法的實現依賴于采用的存儲結構算法的實現依賴于采用的存儲結構數據類型（數據類型（Data Type）：）： 值的集合以及定義在這個集合上的一組操作。 例如例如: C語言中的整數類型抽象數據類型抽象數據類型(ADT) 數學模型以及定義在該模型上的一組操作。 與其在計算機中的表示和實現無關。 ADT可用三元組表示：（D,S,P） D 數據對象; S D上的關系; P 對D的基本操作集抽象數據類型的定義格式：抽象數據類型的定義格式：ADT抽象數據類型名抽象數據類型名 數據對象：數據對象的定義 數據關系：數據關系的定義 基本操作：基本操作的定義ADT抽象的數據類型名基本操作的定義格式為：基本操作的定

7、義格式為：基本操作名（參數表）初始條件：初始條件描述操作結果：操作結果描述ADT Triplet 數據對象數據對象：D = e1,e2,e3 | e1,e2,e3屬于Elemset(定義了關系的某個集合) 數據關系數據關系：R1 = e1,e2|e2,e3 基本操作基本操作： InitTriplet(&T,v1,v2,v3) 初始條件: 操作結果: 構造三元組T,元素e1,e2和e3分別被賦予參數v1,v2和v3的值。 DestroyTriplet(&T) 初始條件: 三元組T已經存在。 操作結果: 銷毀三元組T。 Get(T,i,&e) 初始條件: 三元組T已經存在,

8、1=i=3。 操作結果: 用e返回三元組T的第i個元素。 Put(&T,i,e) 初始條件: 三元組T已經存在,1=i=3。 操作結果: 用e值取代三元組T的第i個元素。 IsAscending(T) 初始條件: 三元組T已經存在。 操作結果: 如果三元組T的三個元素按升序排列,則返回TRUE; 否則返回FALSE。 IsDescending(T) 初始條件: 三元組T已經存在。 操作結果: 如果三元組T的三個元素按降序排列,則返回TRUE; 否則返回FALSE。 Max(T,&e) 初始條件: 三元組T已經存在,。 操作結果: 用e返回三元組T的最大值。 Min(T,&

9、;e) 初始條件: 三元組T已經存在,。 操作結果: 用e返回三元組T的最小值。ADT Triplet抽象數據類型的表示與實現抽象數據類型的表示與實現類C語言（作了擴充和修改）的表示如：預定義常量和類型 define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASIBLE -1define OVERFLOW -2 typedef int Status三元組基本操作實現三元組基本操作實現-舉例舉例Status Get(Triple T, int i, Elemtype *e)/ 初始條件: 三元組T已經存在,1=i=3。/ 操

10、作結果: 用e返回三元組T的第i個元素。 if (i3) return ERROR; *e=Ti-1; return OK;1.4 算法和算法分析算法和算法分析, 1.4.1 算法算法算法（算法（Algorithm）:對特定問題求解步對特定問題求解步驟的一種描述驟的一種描述算法的五個重要特性：算法的五個重要特性：有窮性有窮性確定性確定性可行性可行性輸入輸入輸出輸出算法舉例算法舉例-氣泡排序算法氣泡排序算法初始條件：初始條件：n個待排序的數個待排序的數a0-an-1結果：排序后結果：排序后a0-an-1從小到大排列從小到大排列i 從從n-1直到直到i=2做（做（3）-（6）步）步change =

11、 FALSE;j從從0直到直到j=i-1做（做（5）（5）若）若ajaj+1則交換它們并置則交換它們并置change=TRUE（6) 若若change = FALSE則結束則結束（7）算法結束）算法結束i 從從n-1直到直到i=2做（做（2）-（3）步）步j從從0直到直到j=i-1做（做（3）3）若）若ajaj+1則交換它們則交換它們4）算法結束）算法結束void bb_sort(int a, int n) for (i=n-1; i1; -i) for (j= 0; j aj+1) aj aj+1; /bb_sort1.4.2 算法設計的要求算法設計的要求算法應達到的目標算法應達到的目標正確

12、性正確性可讀性可讀性健壯性健壯性效率與低存貯量效率與低存貯量1.4.3 算法效率的度量算法效率的度量（1) 事后統計法事后統計法事前分析估算法事前分析估算法 算法的時間復雜度時間復雜度：基本操作重復執行的次數。 它是問題規模n的某個函數f(n)： T(n) = O(f(n)例如：兩個nxn矩陣相乘兩個nxn矩陣相乘的算法中乘法運算是基本操作，其重復執行的次數為n3。該算法的時間復雜度為時間復雜度為:T(n) = O(n3)。for (i=1; i=n;+i) for(j=1;j=n;+j) ci,j=0; for(k=1;k1&change; -i) change = false; for (j= 0; j aj+1) aj aj+1; change=TURE; /bubble_sort 漸近時間復雜度漸近時間復雜度(階階) )與與語句頻語句頻度度時間復雜度時間復雜度只考慮對于問題規模的增長率增