數(shù)據(jù)結構第一章緒論課件

1、數(shù) 據(jù) 結 構主講教師陳明 教材 數(shù)據(jù)結構教程 李春葆等 清華大學出版社 參考教材數(shù)據(jù)結構 （ C+語言版） 劉清 王瓊 電子工業(yè)出版社數(shù)據(jù)結構 （ C語言版） 嚴蔚敏 吳偉民 清華大學出版社數(shù)據(jù)結構與程序設計C+語言描述（影印版）Robert L.Kruse，Alexander J.Ryba 高等教育出版社 教學內容 第一章 緒論 第二章 線性表 第三章 棧和隊列 第四章 串（最后選講） 第五章 數(shù)組和廣義表（簡 單介紹） 第六章 樹 第七章 圖 第八章 查找 第九章 排序課程特點及教學方法難度大 綜合性強 必須下苦功學習關于教學的幾個新觀念教學過程以學生為主體, 教師為主導 學生由知識技能

2、的被動接受者向知識技能的主動探求者轉變, 教師由傳授者向教學活動的設計者、組織者、指導者轉變教學目標為使學生在知識、能力、素質方面協(xié)調發(fā)展能力包括自學能力、知識運用能力、動手能力、創(chuàng)新能力、發(fā)現(xiàn)問題能力、分析問題和解決問題能力以及可持續(xù)發(fā)展能力第一章 緒論1.1 本課程研究的問題計算機的發(fā)展 軟件 硬件 應用領域數(shù)據(jù)處理的種類和能力 數(shù)據(jù)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)數(shù) (整數(shù),實數(shù)) 字符 字符串 文字 圖形 圖象 聲音數(shù)據(jù)：客觀對象的符號表示數(shù)學中的整數(shù)、實數(shù)，課程名，地名、書名程序原始數(shù)據(jù)結果數(shù)據(jù) 數(shù)值問題與非數(shù)值問題1）數(shù)值問題例1 已知：游泳池的長len和寬wide，求面積area設計 求解問題

3、的方法 編程1.1 本課程研究的問題 建模型：問題涉及的對象：游泳池的長len 寬wide，面積area；對象之間的關系：area=lenwide1.1 本課程研究的問題例 3 迷宮問題。在迷宮中，每走到一處，接下來可走的通路有三條。計算機處理的這類對象之間通常不存在線性關系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹” 入口 出口城市間交通網(wǎng)問題1.1 本課程研究的問題數(shù)據(jù)結構的研究問題： 非數(shù)值數(shù)據(jù)之間的結構關系，及如何表示，如何存儲，如何處理。本課程討論的問題： 應用中常用的幾種數(shù)據(jù)間的結構關系，及如何表示,如何存儲，如何處理。 例如對C 源程序，數(shù)據(jù)概念不僅是源

4、程序所處理的數(shù)據(jù)，相對于編譯程序來說，C編譯程序相對于源程序是一個處理程序， 它加工的數(shù)據(jù)是字符流的源程序（.c）， 輸出的結果是目標程序(.obj)； 對于鏈接程序來說，它加工的數(shù)據(jù)是目標程序(.obj)， 輸出的結果是可執(zhí)行程序(.exe)，如圖 1.1 所示。 圖1.1 編譯程序示意圖 源程序目標程度可執(zhí)行程序C編譯程序C鏈接程序 2. 數(shù)據(jù)元素（Data Element） 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位, 是數(shù)據(jù)集合的個體，在計算機中通常作為一個整體進行考慮和處理。 表1-1 學 籍 表 學號姓名性別籍貫出生年月住址101趙紅玲女河北1983.11北京 數(shù)據(jù)項記錄綜上13所述，再分析數(shù)據(jù)

5、概念： 4. 數(shù)據(jù)結構（Data Structure） 數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素集合， 圖1.2 學校組織層次結構圖 圖1.3 交通流量圖 5. 數(shù)據(jù)類型(Data Type) 數(shù)據(jù)類型是一組性質相同的值集合以及定義在這個值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個集合，即該類型的取值范圍，以及該類型中可允許使用的一組運算。例如高級語言中的數(shù)據(jù)類型就是已經(jīng)實現(xiàn)的數(shù)據(jù)結構的實例。 從這個意義上講，數(shù)據(jù)類型是高級語言中允許的變量種類， 是程序語言中已經(jīng)實現(xiàn)的數(shù)據(jù)結構（即程序中允許出現(xiàn)的數(shù)據(jù)形式）。在高級語言中，整型類型可能的取值范圍是-32 768+32 767， 可

6、用的運算符集合為加、 減、 乘、 除、 乘方、 取模（如C語言中+， -， *， /， %）。 6. 數(shù)據(jù)抽象與抽象數(shù)據(jù)類型 ） 數(shù)據(jù)的抽象 計算機中使用的是二進制數(shù)，匯編語言中則可給出各種數(shù)據(jù)的十進制表示，如98.65、 9.6E3等, 它們是二進制數(shù)據(jù)的抽象; 使用者在編程時可以直接使用, 不必考慮實現(xiàn)細節(jié)。在高級語言中，則給出更高一級的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型， 如整型、 實型、字符型等。到抽象數(shù)據(jù)類型出現(xiàn)，可以進一步定義更高級的數(shù)據(jù)抽象，如各種表、隊、棧、樹、圖、窗口、管理器等，這種數(shù)據(jù)抽象的層次為設計者提供了更有利的手段，使得設計者可以從抽象的概念出發(fā)，從整體考慮，然后自頂向下、逐步

7、展開，最后得到所需結果。可以這樣看，高級語言中提供整型、實型、字符、記錄、文件、指針等多種數(shù)據(jù)類型，可以利用這些類型構造出像棧、隊列、樹、圖等復雜的抽象數(shù)據(jù)類型。 ） 抽象數(shù)據(jù)類型 (Abstract Data Type) 抽象數(shù)據(jù)類型（簡稱ADT）是指基于一類邏輯關系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決于客觀存在的一組邏輯特性，而與其在計算機內如何表示和實現(xiàn)無關，即不論其內部結構如何變化，只要它的數(shù)學特性不變，都不影響其外部使用。從某種意義上講，抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質上是一個概念。整數(shù)類型就是一個簡單的抽象數(shù)據(jù)類型實例?！俺橄蟆钡囊饬x在于教學特性的抽象。一個

8、ADT定義了一個數(shù)據(jù)對象，數(shù)據(jù)對象中各元素間的結構關系，以及一組處理數(shù)據(jù)的操作。ADT 通常是指由用戶定義且用以表示應用問題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，并包括一組相關服務操作。 數(shù)學模型抽象數(shù)據(jù)類型數(shù)據(jù)結構，恰好反應了信息結構轉換的三個重要階段，而在這個轉換過程中，數(shù)據(jù)結構是基礎，抽象數(shù)據(jù)類型是中樞。 一個線性表的抽象數(shù)據(jù)類型的描述如下： ADT Linear-list 數(shù)據(jù)元素 所有ai屬于同一數(shù)據(jù)對象，i=1，2，n, n0； 邏輯結構 所有數(shù)據(jù)元素ai（i=1，2，n-1）存在次序關系，ai無前趨，an無后繼； 操作設L為Linear-list: Initial(L): 初始化

9、空線性表; Length(L): 求線性表的表長; Get(L, i): 取線性表的第i個元素； Insert(L, i, b): 在線性表的第i個位置插入元素b； Delete(L, i): 刪除線性表的第i個元素。 ） ADT的表示與實現(xiàn) ADT的定義 ADT的定義格式不唯一, 我們采用下述格式定義一個ADT: ADT 數(shù)據(jù)對象: 結構關系: 基本操作: ADT 其中數(shù)據(jù)對象和結構關系的定義采用數(shù)學符號和自然語言描述, 而基本操作的定義格式為: (參數(shù)表) 操作前提: 操作結果: 關于參數(shù)傳遞 參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù), 又稱值參；第二種參數(shù)既能為操作提供待處

10、理數(shù)據(jù), 又能返回操作結果，也稱變量參數(shù)。操作前提描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件, 操作結果描述操作執(zhí)行之后, 數(shù)據(jù)結構的變化狀況和應返回結果。ADT可用現(xiàn)有計算機語言中已有的數(shù)據(jù)類型, 即固有數(shù)據(jù)類型來表示和實現(xiàn)。不同語言的表示和實現(xiàn)方法不盡相同，如ADT中“返回結果的參數(shù)”， PASCAL語言用“變參” 實現(xiàn), C+語言通過“引用型參數(shù)”實現(xiàn), 而C語言用“指針參數(shù)”實現(xiàn)。 用標準C+語言表示和實現(xiàn)ADT描述時，主要包括以下兩個方面: (1) 通過結構體將int、 float等固有類型組合到一起, 構成一個結構類型, 再用typedef為該類型或該類型指針重新起一個名字。 (

11、2) 用C+語言函數(shù)實現(xiàn)各操作。 基本操作主要有以下幾種： (1) 插入： 在數(shù)據(jù)結構中的指定位置上增添新的數(shù)據(jù)元素； (2) 刪除： 刪去數(shù)據(jù)結構中某個指定數(shù)據(jù)元素； (3) 更新：改變數(shù)據(jù)結構中某個元素的值， 在概念上等價于刪除和插入操作的組合； (4) 查找：在數(shù)據(jù)結構中尋找滿足某個特定要求的數(shù)據(jù)元素（的位置和值)； (5) 排序：（在線性結構中）重新安排數(shù)據(jù)元素之間的邏輯順序關系，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。 對每種數(shù)據(jù)結構，主要討論如下兩方面的問題： 1） 數(shù)據(jù)的邏輯結構，數(shù)據(jù)結構的基本操作； 2） 數(shù)據(jù)的存儲結構，數(shù)據(jù)結構基本操作的實現(xiàn)；數(shù)據(jù)的邏輯結構： 數(shù)據(jù)之間的

12、結構關系，是具體關系的抽象。數(shù)據(jù)結構的基本操作： 指對數(shù)據(jù)結構的加工處理數(shù)據(jù)的存儲結構 (物理結構)： 數(shù)據(jù)結構在計算機內存中的表示數(shù)據(jù)結構基本操作的實現(xiàn)： 基本操作在計算機上的實現(xiàn)（方法) 1.3 數(shù)據(jù)結構的分類及表示 某班學生基本情況登記表，記錄了每個學生的學號 姓名 專業(yè) 政治 面貌 ，表中的記錄是按學生的學號順序排列的。 學號 姓名 專業(yè) 政治面藐 001 王洪 計算機 黨員 002 孫文 計算機 團員 003 謝軍 計算機 團員 004 李輝 計算機 團員 005 沈祥福 計算機 黨員 006 余斌 計算機 團員 007 鞏力 計算機 團員 008 孔令輝 計算機 團員學生基本情況登

13、記表的圖示 001003002004006005008007學生間學號順序關系是一種線性結構關系例一 常用的數(shù)據(jù)結構 1） 集合 2） 線性結構 3） 樹結構 4） 圖結構 5）其它復雜結構 家族的族譜 假設某家族有10個成員A， B， C， D， E， F， G， H，I， J，他們之間的血緣關系可以用如下圖表示。JIACBDHGFE13 數(shù)據(jù)結構的分類及表示例1. 邏輯結構 圖1.5 四類基本數(shù)據(jù)結構示意 (1) 集合結構：結構中的數(shù)據(jù)元素之間除了同屬于一個集合的關系外，無任何其它關系。 (2) 線性結構：結構中的數(shù)據(jù)元素之間存在著一對一的線性關系。 (3) 樹形結構：結構中的數(shù)據(jù)元素之間

14、存在著一對多的層次關系。 (4) 圖狀結構或網(wǎng)狀結構：結構中的數(shù)據(jù)元素之間存在著多對多的任意關系。 邏輯結構 線性結構線性表、棧、隊、字符串、數(shù)組、廣義表非線性結構樹、 圖 2. 存儲結構 存儲結構（又稱物理結構）是邏輯結構在計算機中的存儲映象，是邏輯結構在計算機中的實現(xiàn)，它包括數(shù)據(jù)元素的表示和關系的表示。 形式化描述：D要存入機器中，建立一從D的數(shù)據(jù)元素到存儲空間M單元的映象S，DM， 即對于每一個d，dD, 都有唯一的zM，使S（D）=Z, 同時這個映象必須明顯或隱含地體現(xiàn)關系R。 邏輯結構與存儲結構的關系為：存儲結構是邏輯關系的映象與元素本身的映象。邏輯結構是數(shù)據(jù)結構的抽象，存儲結構是數(shù)

15、據(jù)結構的實現(xiàn)，兩者綜合起來建立了數(shù)據(jù)元素之間的結構關系。 順序映象 （順序存儲結構） 非順序映象（非順序存儲結構） 數(shù)據(jù)結構的內容可歸納為三個部分：邏輯結構、存儲結構和運算集合。按某種邏輯關系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合， 就叫做數(shù)據(jù)結構。 數(shù)據(jù)結構的表示 圖示表示 圖示表示是由頂點和邊構成的圖，其中頂點表示數(shù)據(jù) ，邊表示數(shù)據(jù)之間的結構關系； 001003002004006005008007學生基本情況表的圖示表示JIACBDHGFE家族樹的圖示表示13 數(shù)據(jù)結構的分類及表示學生基本情況表的二元組表示（D，S） 二元組表示

16、二元組表示是用一個二元組（D，S）表示數(shù)據(jù)結構， 其中 D 是數(shù)據(jù)元素集合，S 是 D 上關系的集合。D = 001，002，003，004，005，006，007，008S = R R= , , 家族樹的二元組表示（D，S） D = A，B，C，D，E，F(xiàn)，G，H，I，J S = R R = A,B, 13 數(shù)據(jù)結構的分類及表示JIACBDHGFE 00100300200400600500800714 算法與算法分析 1.4 算法與算法分析一 算法的概念 算法是求解問題的操作序列 算法的基本特征：1）輸入：0個或多個輸入；2）輸出：1個或多個輸出；3）有窮性：算法必須在有限步內結束；4）確定

17、性：組成算法的操作必須清晰無二義性。5）可行性：組成算法的操作必須能夠在計算機上實現(xiàn)。 求兩個正整數(shù) m，n 中的最大數(shù)MAX的算法 （1）若 m n 則 max=m （2）若 m = n 則 max=n 例描述算法的書寫規(guī)則所有算法均以函數(shù)形式給出, 算法的輸入數(shù)據(jù)來自參數(shù)表參數(shù)表的參數(shù)在算法之前均進行類型說明有關結點結構的類型定義,以及全局變量的說明等均在算法之前進行說明評價算法標準 算法的正確性，可讀性，可維護性，健壯性等，1 算法時間復雜度T（n） 本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時間的度量。 14 算法與算法分析O（n3） 稱為矩陣相乘算法時間復雜度；O（n

18、3）表示矩陣相乘算法執(zhí)行時間與n3成正比, 即O（n3）與n3 同一數(shù)量級； n 階矩 陣相乘的算法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 += a i k * b k j 乘法 加法執(zhí)行次數(shù)均為 n3 例 矩陣相乘的基本運算：乘法 加法； 有些算法，基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關，這時可考慮 （1） 算法平均時間復雜度 （2） 算法在最壞情況下的時間復雜度算法的時間復雜度 一般來說，設算法中基本操作的執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間復雜度記作： T(n) = O(f(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率與f(n) 的增長率相同。 14 算法與算法分析算法的時間復雜度為O (N3) 14 算法與算法分析 100元買100支筆, 其中鋼筆 3元/支, 圓珠筆 2元/支, 鉛筆 0.5元/支. 寫算法輸出各種組合方案解法1 #define N 100void scheme() int i, j, k, count, money; for (i = 0; i=N; i+ ) for (j = 0; j=N; j+ ) for (k=0; k=N; k+) count=i+j+k;