1、數(shù)據(jù)結(jié)構(gòu),教材: 數(shù)據(jù)結(jié)構(gòu)（C語言版） 嚴蔚敏 吳偉民 編著 清華大學出版社,計算機科學與技術(shù)學院,開設(shè)本課程的背景： 數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課。它主要研究計算機加工對象的邏輯結(jié)構(gòu)、在計算機中的存儲結(jié)構(gòu)以及實現(xiàn)各種基本操作的算法。它是學習操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理等計算機專業(yè)核心課程的基礎(chǔ)，掌握好這門課程的內(nèi)容，是學習計算機其他相關(guān)課程的必備條件。,本課程講述的主要內(nèi)容： 分別講述數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等內(nèi)容。 學習本課程的基本方法：,上課認真聽講； 仔細閱讀教材中的大量例題，從而體會并最終掌握數(shù)據(jù)結(jié)構(gòu)中的基

2、本概念； 獨立完成每個章節(jié)的練習題和作業(yè)題。,1.1 什么是數(shù)據(jù)結(jié)構(gòu),第一章 緒論,1.3 算法和算法分析,1.2 基本概念和術(shù)語,學習提要： 1. 熟悉各名詞術(shù)語的含義，掌握基本概念。 2.了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。 3. 理解算法五個要素的確切含義，掌握估算算法時間復雜度的方法。 重難點內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、時間復雜度的估算方法,1.1 什么是數(shù)據(jù)結(jié)構(gòu),程序設(shè)計: 為計算機處理問題編制 一組指令集。 算法: 處理問題的策略。 數(shù)據(jù)結(jié)構(gòu): 問題的數(shù)學模型。,程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu),數(shù)值計算的程序設(shè)計問題： 例如： 結(jié)構(gòu)靜力分析計算 線性代數(shù)方程組 預報人口

3、增長情況 微分方程,非數(shù)值計算的程序設(shè)計問題：,算法: ? 模型：？,基本操作是“比較兩個數(shù)的大小”,取決于整數(shù)值的范圍,例1：求一組(n個)整數(shù)中的最大值。,例2 書目自動檢索系統(tǒng),書目文件,算法：需要檢索的書目？如何檢索？用戶界面？ 模型：？,例3 人機對奕問題,算法：對奕的規(guī)則和策略 模型：？,例4 教學計劃編排問題,算法：如何確定課程的次序關(guān)系? 模型：？,概括地說：,數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學科。,1.2 基本概念和術(shù)語,一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu),二、數(shù)據(jù)類型,三、抽象數(shù)據(jù)類型,數(shù)據(jù)（data)：所有能被輸入到計算

4、機中，且被計算機處理的符號的集合 ，是計算機操作的對象的總稱。 數(shù)據(jù)元素（data element）：是數(shù)據(jù)（集合）中的一個“個體”，是數(shù)據(jù)的基本單位，由若干個數(shù)據(jù)項組成，也稱結(jié)點、元素、頂點或記錄。,一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)項：,是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。,例如：,描述一個學生基本信息的數(shù)據(jù)元素可以是,稱之為組合項,數(shù)據(jù)結(jié)構(gòu)(data structure)： 是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 或者說，數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。,例：一個含12位數(shù)的十進制數(shù)可以用三個4位的十進制數(shù)表示 3214, 6587, 9345 a1(3214), a2(6587), a3(

5、9345) 在a1、a2、a3 之間存在“次序”關(guān)系： a1,a2、a2,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,又例，在2行3列的二維數(shù)組a1, a2, a3, a4, a5, a6,行的次序關(guān)系: 列的次序關(guān)系:,row = ,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,再例，在一維數(shù)組 a1, a2, a3, a4, a5, a6 的數(shù)據(jù)元素之間存在如下的次序關(guān)系:,| i=1, 2, 3, 4, 5,可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”。,集合結(jié)構(gòu)：數(shù)據(jù)元素間 “同屬于一個集合”,

6、數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:,線性結(jié)構(gòu)：一個對一個,樹形結(jié)構(gòu)：一個對多個,圖狀結(jié)構(gòu)：多個對多個,數(shù)據(jù)結(jié)構(gòu)的形式定義為:,數(shù)據(jù)結(jié)構(gòu)是一個二元組,Data_Structure = (D, S),其中:D 是數(shù)據(jù)元素的有限集， S 是 D上關(guān)系的有限集。,例：在計算機科學中，復數(shù)可取如下定義 Complex=（C，R） 其中，C是含兩個實數(shù)集合c1，c2； R=P，P是定義在集合C上的一種關(guān)系 。,數(shù)據(jù)的邏輯結(jié)構(gòu)：只抽象反映數(shù)據(jù)元素的邏輯關(guān)系。,數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器中的映象。,“數(shù)據(jù)元素”的映象 ？,“關(guān)系”的映象 ？,數(shù)據(jù)元素的映象方法：,用二進制位(bit)的位串表示數(shù)據(jù)元素。,

7、(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,關(guān)系的映象方法：,（表示x, y的方法）,1、順序映象,以相對的存儲位置表示后繼關(guān)系。,例如:令 y 的存儲位置和 x 的存儲位置之間差一個常量 C。,而 C 是一個隱含值，整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息,x y,2、鏈式映象,以附加信息(指針)表示后繼關(guān)系。,需要用一個和 x 在一起的附加信息指示 y 的存儲位置。,y x,例如：復數(shù)z1=3.0-2.3i，z2=-0.7+4.8i的存儲結(jié)構(gòu)。,順序存儲結(jié)構(gòu),鏈式存儲結(jié)構(gòu),二、數(shù)據(jù)類型,在用高級程序語言編寫的程序中，必須對

8、程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所屬的數(shù)據(jù)類型。,例：C語言中，提供 int, char, float等基本數(shù)據(jù)類型， 數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型 指針、空(void)類型等。 用戶也可用typedef 自己定義數(shù)據(jù)類型,typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p;,數(shù)據(jù)類型 是一個 值的集合 和定義在此集合上的 一組操作 的總稱。,不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。,三、抽象數(shù)據(jù)類型 (Abstract Data Typ

9、e 簡稱ADT),ADT定義： 指一個數(shù)學模型以及定義在該模型上的一組操作。 “抽象”的意義在于數(shù)據(jù)類型的數(shù)學抽象特性。,例如： 矩陣 +（求轉(zhuǎn)置、加、乘、求逆、求特征值） 構(gòu)成一個矩陣的抽象數(shù)據(jù)類型。,ADT的描述方法：,抽象數(shù)據(jù)類型可用三元組 （D，S，P） 表示。 其中：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ù)類型名,其中基本操作的定義格式為:,基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述,賦值參數(shù):只為操作提供輸

10、入值。 引用參數(shù):以 s=0;,T(n)=(1),T(n)= O(n),(1)(log2n)(n)(n2)(n3)(2n),例3 for (i=1; i=n; +i) +x; s+=x;,例4 for( i=2; i=n; +i ) for( j=2; j=i-1; +j ) +x; ai,j=x; ,T(n)= O(n2), change = FALSE; / change 為元素進行交換標志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡,void bubble_sort(int -i) / bubble_sort,基本操作: 交換操作,時間復雜度