1、數(shù)據(jù)結(jié)構(gòu),課程類別：專業(yè)選修 學(xué)時、學(xué)分數(shù)：48學(xué)時3學(xué)分 考核方式與要求：考查,課程介紹,重要性,章節(jié)介紹,緒論 4 線性表 6 棧和隊列 6 串 1 數(shù)組和廣義表 1 樹和二叉樹 9 圖 9 查找 6 內(nèi)部排序 6,數(shù)據(jù)結(jié)構(gòu),邏輯結(jié)構(gòu),物理結(jié)構(gòu),線性結(jié)構(gòu),樹形結(jié)構(gòu),圖狀結(jié)構(gòu),集合,順序?qū)崿F(xiàn),鏈式實現(xiàn),操作，算法,5數(shù)組和廣義表,4串,3棧和隊列,2線性表,7圖,6樹和二叉樹,主要內(nèi)容,10排序,9查找,幾點要求,上課請關(guān)機 不遲到，不曠課 準備筆記本 機房禁止玩游戲，上網(wǎng)，吃東西,第一章 緒 論,學(xué)習(xí)目的：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。,重點難點：數(shù)據(jù)結(jié)構(gòu)的基本概念。,1.1 什么是數(shù)據(jù)結(jié)

2、構(gòu),1.2 基本概念和術(shù)語,教學(xué)內(nèi)容,1.1 什么是數(shù)據(jù)結(jié)構(gòu),IT 計算機科學(xué)家 pascal語言的創(chuàng)始人Niklaus Wirth（尼古拉斯沃斯 ）教授在1976年出版了一本書：“Algorithms + Data Structures = Programs” 說明了算法和數(shù)據(jù)結(jié)構(gòu)是進行程序設(shè)計的兩大要素。,1.計算機是怎么解決問題的？,很多數(shù)值計算問題的數(shù)學(xué)模型通?？捎靡唤M線性或非線性的代數(shù)方程組或微分方程組來描述： 如：結(jié)構(gòu)靜力分析計算-線性代數(shù)方程組，全球天氣預(yù)報-環(huán)流模式方程,抽象模型,設(shè)計算法,調(diào)試測試,編碼,得出結(jié)果,如今計算機所處理的是大量的非數(shù)值計算的程序設(shè)計問題：,例1 *

3、數(shù)據(jù)庫管理系統(tǒng),例2 計算機對弈：,數(shù)學(xué)模型：表格和數(shù)據(jù)庫,數(shù)學(xué)模型： 樹形結(jié)構(gòu),例3 交叉路口的紅綠燈管理。如今十字路口橫豎兩個方向都有三個紅綠燈，分別控制左拐、直行和右拐，那么如何控制這些紅綠燈既使交通不堵塞，又使流量最大呢？,數(shù)學(xué)模型： 圖狀結(jié)構(gòu),例4 煤氣管道的鋪設(shè)問題。如下圖：需為城市的各小區(qū)之間鋪設(shè)煤氣管道，對 n 個小區(qū)只需鋪設(shè) n-1 條管線，由于地理環(huán)境不同等因素使各條管線所需投資不同(如圖上所標識)，如何使投資成本最低？,數(shù)學(xué)模型： 圖狀結(jié)構(gòu),綜合各種程序設(shè)計問題，抽取它具體的物理含義，就可以得到兩類數(shù)學(xué)模型： 和數(shù)值計算相關(guān)的數(shù)學(xué)模型：（非）線性代數(shù)方程，常微分方程-計算

4、數(shù)學(xué) 非數(shù)值計算問題的數(shù)學(xué)模型：數(shù)學(xué)模型的表示和求解方法-數(shù)據(jù)結(jié)構(gòu) 由以上幾個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。,2.什么是數(shù)據(jù)結(jié)構(gòu)?,數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科。 要使計算機能夠更有效地進行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點，在計算機中的表示方式以及各個操作的具體實現(xiàn)手段。這些就是數(shù)據(jù)結(jié)構(gòu)這門課程研究的主要內(nèi)容。,是所有能被輸入到計算機中，且能被計算機處理的所有符號(數(shù)字、字符等)的集合，它是計算機操作對象的總稱，是計算機處理的信息的載體，是信息的某種特定的

5、符號表示形式。 數(shù)據(jù)是個集合，如果用集合的表示方法來寫的話，就是： 數(shù)據(jù)=x|x是計算機操作的對象,是數(shù)據(jù)(集合)中的一個“個體”，在計算機中通常作為一個整體進行考慮和處理，是數(shù)據(jù)結(jié)構(gòu)中討論的“基本單位”，但不是“最小單位”。,1、數(shù)據(jù),2、數(shù)據(jù)元素,1.2 基本概念和術(shù)語,數(shù)據(jù)元素分類 一類是不可分割的“原子”型數(shù)據(jù)元素，如：整數(shù)“5”，字符 “N” 等 一類是由多個款項構(gòu)成的數(shù)據(jù)元素，其中每個款項被稱為一個“數(shù)據(jù)項”。 例如描述一個學(xué)生的信息的數(shù)據(jù)元素可由下列6個數(shù)據(jù)項組成。 數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中討論的“最小單位”。 數(shù)據(jù)元素是數(shù)據(jù)項的集合。,是性質(zhì)相同的數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個子集。

6、如：整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, 字母字符數(shù)據(jù)對象C= A,B,Z 在同一個數(shù)學(xué)模型中的數(shù)據(jù)元素必然具有相同特性。,3、數(shù)據(jù)對象,4、數(shù)據(jù)結(jié)構(gòu),1）概念：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合。 “結(jié)構(gòu)”即指數(shù)據(jù)元素之間存在的約束關(guān)系。 數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間的關(guān)系的總和。,例5 一個12位數(shù)的十進制數(shù)可以用3個4位的十進制數(shù)表示： 3214，6587，9345-a1(3214),a2(6587),a3(9345) a1,a2,a3之間存在“次序”關(guān)系, ， 意為 x 和 y 之間存在“x領(lǐng)先于y”的次序關(guān)系。 a1a2a3

7、a2a1a3,例6 可以用下述數(shù)據(jù)結(jié)構(gòu)來描述2行3列的矩陣： 它是一個含6個數(shù)據(jù)元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行關(guān)系”和“列關(guān)系”兩個次序關(guān)系，其中： 行row=， 列col=，,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,同樣的這6個數(shù)據(jù)元素組成的一維數(shù)組a1,a2,a3,a4,a5,a6的數(shù)據(jù)元素之間存在如下的次序關(guān)系: | i=1,2,5 同樣的數(shù)據(jù)元素，不同的關(guān)系構(gòu)成了不同的結(jié)構(gòu)，因此數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合?；蛘哒f，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。,2）數(shù)據(jù)結(jié)構(gòu)的形式定義,數(shù)據(jù)結(jié)構(gòu)是一個二元組

8、Data_Structures = ( D,S ) 其中：D是數(shù)據(jù)元素的有限集， S是D上關(guān)系的有限集。 例7 復(fù)數(shù)的二元組定義 復(fù)數(shù)由實部和虛部構(gòu)成（構(gòu)成元素），兩者之間存在著一種次序關(guān)系（邏輯關(guān)系）。 可以表示為： Complex=(C,R) 其中,C= c1,c2 R= 說明:表示有序數(shù)對,用圖示法表示時畫箭頭 ( )表示無序數(shù)對,用圖示法表示時畫線段,數(shù)據(jù)的邏輯結(jié)構(gòu)：描述數(shù)據(jù)元素之間的邏輯關(guān) 系，不依賴于具體表示，是抽象的。可歸結(jié)為以下四類:,線性結(jié)構(gòu),樹形結(jié)構(gòu),圖/網(wǎng)狀結(jié)構(gòu),集合結(jié)構(gòu),3）數(shù)據(jù)的“邏輯結(jié)構(gòu)”,一對一,一對多,多對多,4）數(shù)據(jù)的“存儲結(jié)構(gòu)”, 邏輯結(jié)構(gòu)在存儲器中的具體實

9、現(xiàn)表示(映象)。故又稱數(shù)據(jù)存儲結(jié)構(gòu)。 它包括數(shù)據(jù)元素的表示和關(guān)系的表示。,“數(shù)據(jù)元素”的映象 ？,“關(guān)系”的映象 ？,數(shù)據(jù)元素的映象方法：,用二進制位(bit)的位串表示數(shù)據(jù)元素,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,關(guān)系的映象方法：,順序映象,借助元素在存儲器中相對的位置來表示數(shù)據(jù)元素之間的關(guān)系。地址是連續(xù)的。如數(shù)組。,例8 存儲復(fù)數(shù) z=3.0-2.3i,順序存儲結(jié)構(gòu),鏈式映象,借助元素存儲地址的指針來表示數(shù)據(jù)元素之間的關(guān)系。地址可以是離散的。 如上復(fù)數(shù)的存儲,鏈式存儲結(jié)構(gòu),當(dāng)用高級程序設(shè)計語言進行編程時，通?？?/p>

10、用高級編程語言中提供的數(shù)據(jù)類型來描述存儲結(jié)構(gòu)。,兩種存儲的比較： 順序結(jié)構(gòu):占用最少的存儲空間，產(chǎn)生較多碎片。 非順序：不會出現(xiàn)碎片，每個結(jié)點占用較多空間。,5、數(shù)據(jù)類型 數(shù)據(jù)類型是一個“值”的集合和定義在此集合上的“一組操作”的總稱。 在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所屬的數(shù)據(jù)類型。程序中對變量或常量說明其所屬類型的作用是，對它們加上兩個約束條件：一是可取值的范圍，二是可進行的操作。 不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。,例如，C 語言中提供的基本數(shù)據(jù)類型有:,整型 int,浮點型 float,字符型 char,空類

11、型 void,雙精度型 double,實型（ C+語言）,6、抽象數(shù)據(jù)類型(Abstract Data Type 簡稱ADT),指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。 由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型 由基本的數(shù)據(jù)類型組成, 并包括一組相關(guān)的服務(wù)（或稱操作）,抽象數(shù)據(jù)類型的描述方法(P8),抽象數(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ù)類型名,其中基本操作的定義格式為: 基本操作名（

12、參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述 賦值參數(shù) 只為操作提供輸入值。 引用參數(shù) 以&打頭，除可提供輸入值外，還將返回操作結(jié)果。 初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。 操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。,例9、抽象數(shù)據(jù)類型復(fù)數(shù)的定義,ADT Complex 數(shù)據(jù)對象：D = e1,e2 | e1,e2 RealSet 數(shù)據(jù)關(guān)系：R1 = | e1是復(fù)數(shù)的實部，e2是復(fù)數(shù)的虛部 基本操作： InitComplex( &Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù)Z，其實部和虛部分別被賦以參數(shù)v1和v2的值。 DestroyComplex( &Z) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用 realPart 返回復(fù)數(shù)Z的實部值。 GetImag( Z, &ImagPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用 ImagPart 返回復(fù)數(shù)Z的虛部值。 Add(