數(shù)據(jù)機構第1章

1、第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 教材 數(shù)據(jù)結構（數(shù)據(jù)結構（C語言版）嚴蔚敏，吳偉民語言版）嚴蔚敏，吳偉民 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 作業(yè)及考核 作業(yè)： 時間：周二 數(shù)量：每次交三分之一 考核： 期末筆試：50% 期末機試：30% 上機實驗：10% 作業(yè)：10% 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 課件 courseware_ 帳號：courseware_ds 密碼：123abc 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 C語言語言 數(shù)據(jù)結構數(shù)據(jù)結構 軟件工程軟件工程 掌握基本編掌握基本編 程方法程方法 掌握數(shù)據(jù)組掌握數(shù)據(jù)組 織和數(shù)據(jù)處織和數(shù)據(jù)處

2、理的方法理的方法 掌握大型軟掌握大型軟 件開發(fā)方法件開發(fā)方法 學習識字學習識字學習寫作文學習寫作文學習寫小說學習寫小說 基本 要求 課程 關系 與語文 學習過 程類比 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 前期課程前期課程 數(shù)據(jù)結構數(shù)據(jù)結構 計算機基礎計算機基礎 C語言語言 離散數(shù)學離散數(shù)學 后期課程后期課程 操作系統(tǒng)操作系統(tǒng) 編譯原理編譯原理 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 軟件工程軟件工程 承上承上 啟下啟下 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 第第1章章 緒論緒論 1.1 什么是數(shù)據(jù)結構（定義）什么是數(shù)據(jù)結構（定義） 1.2 數(shù)據(jù)結構的內(nèi)容數(shù)據(jù)結構的內(nèi)容 1.3 算法算法 1.4

3、 算法描述的工具算法描述的工具 1.5 對算法作性能評價對算法作性能評價 1.6 關于學習數(shù)據(jù)結構關于學習數(shù)據(jù)結構 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 第一章第一章 緒論緒論 計算機的應用計算機的應用: 科學計算；科學計算； 控制、管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作；控制、管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作； 計算機加工的對象計算機加工的對象: 純粹的數(shù)值；純粹的數(shù)值； 文本、表格和圖像數(shù)據(jù)；文本、表格和圖像數(shù)據(jù)； 如何表示、處理這些如何表示、處理這些新的新的、具有一定、具有一定結構結構的數(shù)據(jù)？的數(shù)據(jù)？ 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 數(shù)據(jù)結構數(shù)據(jù)結構是一門什么課程

4、是一門什么課程 數(shù)據(jù)結構是一門研究數(shù)據(jù)結構是一門研究非數(shù)值計算非數(shù)值計算的程序設計問題時處理的程序設計問題時處理 的的操作對象操作對象以及它們之間的以及它們之間的關系和操作關系和操作等等的學科。等等的學科。 解決數(shù)值計算問題的中心解決數(shù)值計算問題的中心: 建立適當?shù)臄?shù)學模型。建立適當?shù)臄?shù)學模型。 解決非數(shù)值計算問題的中心解決非數(shù)值計算問題的中心: 尋找適當?shù)臄?shù)據(jù)結構。尋找適當?shù)臄?shù)據(jù)結構。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 數(shù)值問題數(shù)值問題: 例例1，求解梁架結構中的應力。，求解梁架結構中的應力。 數(shù)學模型數(shù)學模型: K U = M a11 ann x1 xn b1 bn 例例2，預

5、報人口增長情況。，預報人口增長情況。 數(shù)學模型數(shù)學模型: dN(t) d t r N(t) N(t)| |t=t N0 0 N(t) N0 e r t 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 非數(shù)值問題非數(shù)值問題: 例例1，圖書館的書目檢索系統(tǒng)自動化問題。，圖書館的書目檢索系統(tǒng)自動化問題。 通過提供書名、作者或分類信息，你就可以從圖書館通過提供書名、作者或分類信息，你就可以從圖書館 中檢索某一本書。中檢索某一本書。 數(shù)據(jù)結構數(shù)據(jù)結構:線性表。線性表。 D01曲守寧曲守寧數(shù)據(jù)庫數(shù)據(jù)庫004 S01王永燕王永燕數(shù)據(jù)結構數(shù)據(jù)結構003 L01潘玉奇潘玉奇程序設計程序設計002 S01周勁周勁數(shù)

6、據(jù)結構數(shù)據(jù)結構001 004數(shù)據(jù)庫數(shù)據(jù)庫 002程序設計程序設計 001,003數(shù)據(jù)結構數(shù)據(jù)結構 004曲守寧曲守寧 003王永燕王永燕 002潘玉奇潘玉奇 001周勁周勁 004D 002L 001,003S 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例例2，計算機和人對奕問題。，計算機和人對奕問題。 計算機可以根據(jù)當前棋盤格局，來預測棋局發(fā)展的趨計算機可以根據(jù)當前棋盤格局，來預測棋局發(fā)展的趨 勢，甚至最后結局。勢，甚至最后結局。 數(shù)據(jù)結構數(shù)據(jù)結構:對弈樹。對弈樹。 O O 當前格局當前格局 派生格局派生格局 O O O O O O O O O O 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第

7、1章章 例例3，地圖的著色問題。，地圖的著色問題。 對地圖上的每個區(qū)域染一種顏色，并且要求相鄰的兩對地圖上的每個區(qū)域染一種顏色，并且要求相鄰的兩 個區(qū)域不能具有相同顏色。個區(qū)域不能具有相同顏色。 數(shù)據(jù)結構數(shù)據(jù)結構:圖。圖。 1 2 4 3 5 6 7 12 34 567 紅紅綠綠 綠綠藍藍 紅紅 黑黑 綠綠 1 2 4 3 5 6 7 用最少的顏色染色用最少的顏色染色 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 數(shù)學數(shù)學 計算機計算機 硬件硬件 計算機計算機 軟件軟件 數(shù)據(jù)數(shù)據(jù) 結構結構 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 1. 數(shù)據(jù)（數(shù)據(jù)（Data） 對客觀事物的符號描述，能輸入

8、到計算機中并被對客觀事物的符號描述，能輸入到計算機中并被 計算機程序處理的符號的總稱；計算機程序處理的符號的總稱； 能被計算機識別、存儲和加工處理的信息的載體。能被計算機識別、存儲和加工處理的信息的載體。 例，例，數(shù)字：自然數(shù)、整數(shù) 字母：a z, 單詞 圖像： 視頻、音頻信號等 表格： 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 2. 數(shù)據(jù)元素（數(shù)據(jù)元素（Data Element） 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位, 是數(shù)據(jù)集合的個體，在計是數(shù)據(jù)集合的個體，在計 算機中通常作為一個整體進行考慮和處理。算機中通常作為一個整體進行考慮和處理。 例，例，“對弈樹對弈樹”中

9、的一個格局中的一個格局 書目信息中的一條書目書目信息中的一條書目 數(shù)據(jù)項數(shù)據(jù)項: 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。 例，一條書目信息是由書名、作者名、分類等多個數(shù)據(jù)例，一條書目信息是由書名、作者名、分類等多個數(shù)據(jù) 項組成的項組成的 數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例如例如 有一個學生表如下所示。這個表中的數(shù)據(jù)元素是學有一個學生表如下所示。這個表中的數(shù)據(jù)元素是學 生記錄生記錄,每個數(shù)據(jù)元素由四個數(shù)據(jù)項每個數(shù)據(jù)元素由四個數(shù)據(jù)項(即學號、姓名、性別即學號、姓名、性別 和班號和班號)

10、組成。組成。 學號學號姓名姓名性別性別班號班號 1張斌張斌男男9901 8劉麗劉麗女女9902 34李英李英女女9901 20陳華陳華男男9902 12王奇王奇男男9901 26董強董強男男9902 5王萍王萍女女9901 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 3. 數(shù)據(jù)結構（數(shù)據(jù)結構（Data Structure） 數(shù)據(jù)結構是指相互之間存在一種或多種特定關系數(shù)據(jù)結構是指相互之間存在一種或多種特定關系 的數(shù)據(jù)元素集合，的數(shù)據(jù)元素集合， 結構（結構（Structure） 數(shù)據(jù)元素相互之間的關系。數(shù)據(jù)元素相互之間的關系。 在形式上可用二元組表示：在形式上可用二元組表示： Data_Stru

11、cture = ( D,S) D: 數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集 S: D上關系的有限集上關系的有限集 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 D = ki | 1in, n0 ki表示集合表示集合D中的第中的第i個結點或數(shù)據(jù)元素個結點或數(shù)據(jù)元素 n為為D中結點的個數(shù)中結點的個數(shù) 若若n=0, 則則D是一個空集是一個空集, 表示表示D無結構可言無結構可言, 有時有時 也可以認為它具有任意的結構也可以認為它具有任意的結構 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 S=rj| 1jm, m0 rj 表示集合表示集合S中的第中的第j個二元關系個二元關系(簡稱關系簡稱關系) m為為S中關

12、系的個數(shù)中關系的個數(shù) 若若m=0, 則則S是一個空集是一個空集, 表明集合表明集合D中的元結點中的元結點 間不存在任何關系間不存在任何關系, 彼此是獨立的彼此是獨立的 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 D D上的一個關系上的一個關系r是序偶的集合是序偶的集合, 對于對于r中的任一序偶中的任一序偶 (x,yD),我們稱序偶的第一結點為第二結點的直我們稱序偶的第一結點為第二結點的直 接前驅結點接前驅結點(通常簡稱前驅結點通常簡稱前驅結點),稱第二結點為第一結稱第二結點為第一結 點的直接后繼結點點的直接后繼結點(通常簡稱后繼結點通常簡稱后繼結點)。如在。如在的的 序偶中序偶中,x為為y的

13、前驅結點的前驅結點,而而y為為x的后繼結點。的后繼結點。 若某個結點沒有前驅若某個結點沒有前驅,則稱該結點為開始結點；若則稱該結點為開始結點；若 某個結點沒有后繼某個結點沒有后繼,則稱該結點為終端結點；除此之外則稱該結點為終端結點；除此之外 的節(jié)點稱為內(nèi)部節(jié)點。的節(jié)點稱為內(nèi)部節(jié)點。 “尖括號尖括號”表示有向關系，表示有向關系，“圓括號圓括號”表示無向關表示無向關 系。系。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例如例如,用二元組表示學生表，學生表中共有用二元組表示學生表，學生表中共有7個結點個結點, 依次用依次用k1k7表示表示,則對應的二元組表示為則對應的二元組表示為 Data_St

14、ructure=(D,S) 其中：其中： D=k1, k2, k3, k4, k5, k6, k7 S= , , , , , 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 邏輯結構圖：邏輯結構圖：可以將數(shù)據(jù)結構用圖形形象地表示可以將數(shù)據(jù)結構用圖形形象地表示 出來出來, ,圖形中的每個結點對應著一個數(shù)據(jù)元素圖形中的每個結點對應著一個數(shù)據(jù)元素, ,兩結點兩結點 之間的連線對應著關系中的一個序偶。之間的連線對應著關系中的一個序偶。 上述上述“學生表學生表”數(shù)據(jù)結構用下圖的圖形表示。數(shù)據(jù)結構用下圖的圖形表示。 k1 k2 k3 k4 k5 k6 k7 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例例

15、1，內(nèi)部關系，復數(shù)，內(nèi)部關系，復數(shù)Complex = ( C，R ) 其中其中: C是含兩個實數(shù)的集合是含兩個實數(shù)的集合c1 1,c2；R = P，而，而P是定義在集是定義在集 合合C上的一種關系上的一種關系，其中有序偶，其中有序偶表示表示c1 1是復數(shù)是復數(shù) 的實部，的實部，c2是復數(shù)的虛部。是復數(shù)的虛部。 其中其中: C是數(shù)據(jù)記錄的集合是數(shù)據(jù)記錄的集合ai；R = P，而，而P是定義在集合是定義在集合C上上 的一種關系的一種關系，其中有序偶，其中有序偶表示表示ai-1 1是是ai的直接的直接 前驅元素，前驅元素，ai是是ai-1 1的直接后繼元素。的直接后繼元素。 例例2，外部關系，線性表

16、，外部關系，線性表List = ( C，R ) OOOOO 線性線性 a1a2a3a4a5 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例例3、設數(shù)據(jù)的結構描述如下： Tree = (D, R) D = 1,2,3,4,5,6 R = , , , , 畫出其邏輯結構圖？ 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 1.2 數(shù)據(jù)結構的內(nèi)容數(shù)據(jù)結構的內(nèi)容 邏輯結構邏輯結構 數(shù)據(jù)元素之間的關系數(shù)據(jù)元素之間的關系 。 邏輯結構可看作是從具體問題抽象出來的數(shù)學模型。邏輯結構可看作是從具體問題抽象出來的數(shù)學模型。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 按照邏輯關系的不同特性分類：按照邏輯關系的

17、不同特性分類： 集合：（同屬于一個集合）集合：（同屬于一個集合） 線性結構：（一對一）線性結構：（一對一） 非線性結構：非線性結構： 樹型結構：（一對多）樹型結構：（一對多） 圖形結構：（多對多）圖形結構：（多對多） 邏輯結構類型的分類邏輯結構類型的分類 集合 線性表 樹 圖 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 (1)(1)線性結構線性結構 所謂線性結構所謂線性結構, ,該結構中的結點之間存在一對一的該結構中的結點之間存在一對一的 關系。關系。 其特點是：其特點是：開始結點開始結點和和終端結點終端結點都是惟一的都是惟一的, ,除了除了 開始結點和終端結點以外開始結點和終端結點以外,

18、,其余結點都其余結點都有且僅有有且僅有一個一個前前 驅結點驅結點, ,有且僅有有且僅有一個一個后繼結點后繼結點。 順序表就是典型的線性結構。順序表就是典型的線性結構。 邏輯結構類型邏輯結構類型 k1 k2 k3 k4 k5 k6 k7 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 (2)非線性結構非線性結構 所謂非線性結構所謂非線性結構,該結構中的結點之間存在該結構中的結點之間存在 一對多或多對多的關系。它又可以細分為樹形一對多或多對多的關系。它又可以細分為樹形 結構和圖形結構兩類。結構和圖形結構兩類。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 所謂樹形結構所謂樹形結構, ,該結構中的結點

19、之間存在一對多的該結構中的結點之間存在一對多的 關系。其特點是關系。其特點是每個結點最多只有一個前驅每個結點最多只有一個前驅, ,但可以有但可以有 多個后繼多個后繼, ,可以有多個終端結點。非線性結構樹形結構可以有多個終端結點。非線性結構樹形結構 簡稱為樹。簡稱為樹。 A C G J B E D F I H M K L 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 所謂圖形結構所謂圖形結構, ,該結構中的結點之間存在多對多的該結構中的結點之間存在多對多的 關系。其特點是關系。其特點是每個結點的前驅和后繼的個數(shù)都可以每個結點的前驅和后繼的個數(shù)都可以

20、是任意的是任意的。因此。因此, ,可能沒有開始結點和終端結點可能沒有開始結點和終端結點, ,也可也可 能有多個開始結點、多個終端結點。圖形結構簡稱為能有多個開始結點、多個終端結點。圖形結構簡稱為 圖。圖。 1 02 3 1 02 3 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 2. 存儲結構（物理結構）存儲結構（物理結構） 邏輯結構在計算機中的存儲映象，是邏邏輯結構在計算機中的存儲映象，是邏 輯結構在計算機中的實現(xiàn)，它包括數(shù)據(jù)輯結構在計算機中的實現(xiàn)，它包括數(shù)據(jù) 元素的表示和關系的表示。元素的表示和關系的表示。 l順序存儲結構順序存儲結構 l非順序存儲結構（鏈式存儲結構）非順序存儲結構（鏈式存

21、儲結構） l 索引存儲結構索引存儲結構 l散列存儲結構散列存儲結構 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例如例如 用順序存儲法和鏈式存儲法表示下面的學用順序存儲法和鏈式存儲法表示下面的學 生表。生表。 學號學號姓名姓名性別性別班號班號 1張斌張斌男男9901 8劉麗劉麗女女9902 34李英李英女女9901 20陳華陳華男男9902 12王奇王奇男男9901 26董強董強男男9902 5王萍王萍女女9901 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 用順序存儲法存放學生表的結構體定義為：用順序存儲法存放學生表的結構體定義為： struct Stud int no; /*學號學號*

22、/ char name8; /*姓名姓名*/ char sex2; /*性別性別*/ char class4; /*班號班號*/ Studs7= 1,“張斌張斌”,“男男”,“9901”, , 5,王萍王萍,女女,9901 ; 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 結構體數(shù)組結構體數(shù)組Studs各元素在內(nèi)各元素在內(nèi) 存中存中按順序存放按順序存放,即第即第i(1i6)個個 學生對應的元素學生對應的元素Studsi存放在存放在 第第i+1個學生對應的元素個學生對應的元素 Studsi+1之前之前,Studsi+1正好正好 在在Studsi之后。之后。 1張斌張斌男男 9901 8劉麗劉麗女

23、女 9902 34李英李英女女 9901 20陳華陳華男男 9902 12王奇王奇男男 9901 26董強董強男男 9902 5王萍王萍女女 9901 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 用鏈式存儲法存放學生表的結構體定義為：用鏈式存儲法存放學生表的結構體定義為： typedef struct node int no; /*學號學號*/ char name8; /*姓名姓名*/ char sex2; /*性別性別*/ char class4; /*班號班號*/ struct node *next; /*指向下個學生的指針指向下個學生的指針*/ StudType； 第 1章 緒 論 數(shù)

24、據(jù)機構第數(shù)據(jù)機構第1章章 head 1張斌張斌男男 9901 8劉麗劉麗女女 9902 34李英李英女女 9901 20陳華陳華男男 9902 12王奇王奇男男 9901 26董強董強男男 9902 5王萍王萍女女 9901 學生表構成的鏈表學生表構成的鏈表 如右圖所示。其中如右圖所示。其中 的的head為第一個數(shù)為第一個數(shù) 據(jù)元素的指針。據(jù)元素的指針。 學生表構成的鏈表學生表構成的鏈表 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 鏈式存儲法的缺點：鏈式存儲法的缺點： 存儲空間占用大存儲空間占用大 無法隨機訪問無法隨機訪問 鏈式存儲法的優(yōu)點：鏈式存儲法的優(yōu)點： 便于修改（插入、刪除便于修改（

25、插入、刪除、移動）移動） 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 邏輯結構與存儲結構的關系邏輯結構與存儲結構的關系 l存儲結構是邏輯結構用計算機語言的實現(xiàn)；存儲結構是邏輯結構用計算機語言的實現(xiàn)； l如何用計算機語言表示數(shù)據(jù)元素之間的各種關系。如何用計算機語言表示數(shù)據(jù)元素之間的各種關系。 存儲結構是邏輯關系的映象與元素本身的映象。邏輯結構是數(shù)存儲結構是邏輯關系的映象與元素本身的映象。邏輯結構是數(shù) 據(jù)結構的抽象，存儲結構是數(shù)據(jù)結構的實現(xiàn)，兩者綜合起來建據(jù)結構的抽象，存儲結構是數(shù)據(jù)結構的實現(xiàn)，兩者綜合起來建 立了數(shù)據(jù)元素之間的結構關系。立了數(shù)據(jù)元素之間的結構關系。 第 1章 緒 論 數(shù)據(jù)機構第

26、數(shù)據(jù)機構第1章章 3. 數(shù)據(jù)的運算數(shù)據(jù)的運算 就是施加于數(shù)據(jù)的操作，如查找、添加、 修改、刪除等。在數(shù)據(jù)結構中運算不僅僅 實加減乘除這些算術運算，它的范圍更為 廣泛，常常涉及算法問題。 舉例：線性表的初始化、查找、插入、刪 除操作等 算法的設計取決于選定的數(shù)據(jù)（邏輯）結構，算法的設計取決于選定的數(shù)據(jù)（邏輯）結構， 而算法的實現(xiàn)依賴于采用的存儲結構。而算法的實現(xiàn)依賴于采用的存儲結構。 抽象運算定義在邏輯結構上，而實現(xiàn)在存儲抽象運算定義在邏輯結構上，而實現(xiàn)在存儲 結構上。結構上。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 數(shù)據(jù)結構的內(nèi)容可歸納為三個部分：邏輯結構、數(shù)據(jù)結構的內(nèi)容可歸納為三個部分

27、：邏輯結構、 存儲結構和運算集合。按某種邏輯關系組織起存儲結構和運算集合。按某種邏輯關系組織起 來的一批數(shù)據(jù)，按一定的映象方式把它存放在來的一批數(shù)據(jù)，按一定的映象方式把它存放在 計算機的存儲器中，并在這些數(shù)據(jù)上定義了一計算機的存儲器中，并在這些數(shù)據(jù)上定義了一 個運算的集合，個運算的集合， 就叫做數(shù)據(jù)結構。就叫做數(shù)據(jù)結構。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 數(shù)據(jù)類型數(shù)據(jù)類型 在用高級程序語言編寫的程序中在用高級程序語言編寫的程序中, ,必須對程序中必須對程序中 出現(xiàn)的每個出現(xiàn)的每個變量變量、常量常量或或表達式表達式, ,明確說明它們所屬明確說明它們所屬 的數(shù)據(jù)類型。的數(shù)據(jù)類型。 不同

28、類型的變量不同類型的變量, ,其所能取的值的范圍不同其所能取的值的范圍不同, ,所所 能進行的操作不同。數(shù)據(jù)類型是一個能進行的操作不同。數(shù)據(jù)類型是一個值的集合值的集合和和定定 義在此集合上的一組操作義在此集合上的一組操作的總稱。的總稱。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 如如C/C+中的中的int就是整型數(shù)據(jù)類型。它是所有整就是整型數(shù)據(jù)類型。它是所有整 數(shù)的集合數(shù)的集合(在在16位計算機中為位計算機中為32768到到32767的全體的全體 整數(shù)整數(shù))和相關的整數(shù)運算和相關的整數(shù)運算(如、等如、等)。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 (2)抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 抽象

29、數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type簡寫為簡寫為ADT)指指 的是用戶進行軟件系統(tǒng)設計時從問題的數(shù)學模型中的是用戶進行軟件系統(tǒng)設計時從問題的數(shù)學模型中 抽象出來的邏輯數(shù)據(jù)結構和邏輯數(shù)據(jù)結構上的運算抽象出來的邏輯數(shù)據(jù)結構和邏輯數(shù)據(jù)結構上的運算, 而不考慮計算機的而不考慮計算機的具體存儲結構具體存儲結構和運算的和運算的具體實現(xiàn)具體實現(xiàn) 算法算法。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 一個抽象數(shù)據(jù)類型的模塊通常應包含定義、表示和實一個抽象數(shù)據(jù)類型的模塊通常應包含定義、表示和實 現(xiàn)三部分。現(xiàn)三部分。 抽象數(shù)據(jù)類型的形式定義抽象數(shù)據(jù)類型的形式定義: 抽象數(shù)據(jù)類型是一個三元

30、組抽象數(shù)據(jù)類型是一個三元組 ( D，S ，P) 其中其中: D是數(shù)據(jù)對象是數(shù)據(jù)對象 S是是D上數(shù)據(jù)關系的有限集上數(shù)據(jù)關系的有限集 P是對是對D的基本操作的有限集的基本操作的有限集 數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義 數(shù)據(jù)關系的定義數(shù)據(jù)關系的定義 基本操作的定義基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 其中其中,數(shù)據(jù)對象、數(shù)據(jù)關系用偽碼描述；數(shù)據(jù)對象、數(shù)據(jù)關系用偽碼描述； 基本操作定義格式為基本操作定義格式為 基本操作名（參數(shù)表）基本操作名（參數(shù)表） 初始條件：初始條件：初始條件描述初始條件描述 操作結果：

31、操作結果：操作結果描述操作結果描述 基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值； 引用參數(shù)以引用參數(shù)以 float RealPart,ImagPart; AssignComplex(z1,8.0,6.0); AssignComplex(z2,4.0,3.0); Add(z1,z2,z3); Multiply(z1,z2,z4); if (Division (z4,z3,z) GetReal (z, RealPart); GetImag (z, ImagPart); /if 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 ADT 有兩個重要特征:

32、 數(shù)據(jù)抽象數(shù)據(jù)抽象 用ADT描述程序處理的實體時， 強調(diào)的是其本質的特征本質的特征、其所能完成的其所能完成的 功能功能以及它和外部用戶的接口外部用戶的接口（即外界外界 使用它的方法使用它的方法） 數(shù)據(jù)封裝數(shù)據(jù)封裝 將實體的外部特性和其內(nèi)部外部特性和其內(nèi)部 實現(xiàn)細節(jié)分離實現(xiàn)細節(jié)分離，并且對外部用戶隱藏對外部用戶隱藏 其內(nèi)部實現(xiàn)細節(jié)其內(nèi)部實現(xiàn)細節(jié) 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 抽象數(shù)據(jù)類型的表示和實現(xiàn)抽象數(shù)據(jù)類型的表示和實現(xiàn) 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)固有數(shù)據(jù) 類型類型(高級編程語言中已實現(xiàn)的數(shù)據(jù) 類型)來實現(xiàn)。 例如，對以上定義的復數(shù) 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章

33、章 typedef struct float realpart； float imagpart； complex； / -存儲結構的定義存儲結構的定義 / -基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明 void AssignComplex( complex sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 1.3 算算 法法 1. 算法（算法（Algorithm）的定義）的定義 Algorithm is a finite set of rules which gives a sequence of op

34、eration for solving a specific type of problem. (算法是規(guī)則的算法是規(guī)則的 有限集合，有限集合， 是為解決特定問題而規(guī)定的一系列操作。是為解決特定問題而規(guī)定的一系列操作。 ) 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 2. 算法的特性算法的特性 (1)有窮性：有限步驟之內(nèi)正常結束，不能形成無窮循環(huán)。有窮性：有限步驟之內(nèi)正常結束，不能形成無窮循環(huán)。 (2)確定性：確定性： 算法中的每一個步驟必須有確定含義，無二算法中的每一個步驟必須有確定含義，無二 義性。義性。 (3) 可行性：可行性： 原則上能精確進行，操作可通過已實現(xiàn)的基原則上能精確進行，

35、操作可通過已實現(xiàn)的基 本運算執(zhí)行有限次而完成。本運算執(zhí)行有限次而完成。 (4) 輸入：輸入： 有多個或有多個或0個輸入。個輸入。 (5) 輸出：輸出： 至少有一個或多個輸出。至少有一個或多個輸出。 在算法的五大特性中，在算法的五大特性中， 最基本的是有限性、最基本的是有限性、 確定性和可確定性和可 行性。行性。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 void exam1() n=2; while(n%2=0) n=n+2; printf(“%dn”,n); void exam2() y=0; x=3/y; printf(“%d,%dn” ,x,y); 違反了有窮性。違反了有窮性。 違反

36、了可行性。違反了可行性。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 算法和數(shù)據(jù)結構是兩個不可分割的統(tǒng)一體算法和數(shù)據(jù)結構是兩個不可分割的統(tǒng)一體 程序程序 = 數(shù)據(jù)結構數(shù)據(jù)結構 + 算法算法 數(shù)據(jù)結構通過算法實現(xiàn)操作數(shù)據(jù)結構通過算法實現(xiàn)操作 算法根據(jù)數(shù)據(jù)結構設計程序算法根據(jù)數(shù)據(jù)結構設計程序 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 算法設計的要求算法設計的要求: 正確性正確性 正確反映需求正確反映需求(通過測試通過測試) 可讀性可讀性 有助于理解、調(diào)試和維護有助于理解、調(diào)試和維護 健壯性健壯性 完備的異常和出錯處理完備的異常和出錯處理 高效率與低存儲的需求高效率與低存儲的需求 時間、空間的

37、要求時間、空間的要求 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 描述算法的方法 自然語言：優(yōu)點簡單。缺點有歧異，表達 復雜思想不明晰，不能和實現(xiàn)方式很好結合 高級程序設計語言，如Pascal, C/C+, Java等。優(yōu) 點克服了自然語言的缺點，可直接執(zhí)行。缺 點對部分問題的描述比較煩雜，啰嗦 *類語言。和高級程序設計語言類似，但是對其中 一些比較煩雜的部分進行簡化（原因：算法主要目 的是為了清晰的表述思想） *舉例：兩個數(shù)據(jù)a, b交換空間 自然語言：交換a, b的存儲空間； 高級語言： x = a; a = b; b = x; 類語言：ab; /交換空間 1.4 算法描述的工具算法描述

38、的工具 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 衡量算法效率的方法主要有兩大類：衡量算法效率的方法主要有兩大類： 事后統(tǒng)計：利用計算機的時鐘； 事前分析估算：用高級語言編寫的程序 運行的時間主要取決于如下因素： 算法； 問題規(guī)模； 使用語言：級別越高，效率越低； 編譯程序； 機器； 1.5 對算法作性能評價對算法作性能評價 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 通常，從算法中選取一種對于研究的問題來說是基本通常，從算法中選取一種對于研究的問題來說是基本 操作的原操作，以該基本操作重復執(zhí)行的次數(shù)作為算操作的原操作，以該基本操作重復執(zhí)行的次數(shù)作為算 法執(zhí)行的時間度量。法執(zhí)行的時間度量

39、。 例，例， for ( j = 1 1 ；j=n ；j+ ) X = X + 1 1 ； for ( i = 1 1 ；i=n ；i+ ) (c) for ( i = 1 1 ；i=n ；i+ ) X = X + 1 1 ； (b) X = X + 1 1 ； (a) 基本操作重復執(zhí)行的次數(shù)分別為基本操作重復執(zhí)行的次數(shù)分別為 1，n，n2 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 頻度頻度: 語句重復執(zhí)行的次數(shù)稱為該語句的頻度，記語句重復執(zhí)行的次數(shù)稱為該語句的頻度，記f(n)。 設算法的問題規(guī)模為設算法的問題規(guī)模為n； 時間復雜度時間復雜度: 算法執(zhí)行時間度量算法執(zhí)行時間度量, ,記記T

40、(n)=O( maxlevel(f(n) )。 對算法各基本操作的頻度求和，便可得算法的時間復雜度。對算法各基本操作的頻度求和，便可得算法的時間復雜度。 但實際中我們所關心的主要是一個算法所花時間的數(shù)量但實際中我們所關心的主要是一個算法所花時間的數(shù)量 級，即取算法各基本操作的最大頻度數(shù)量級。級，即取算法各基本操作的最大頻度數(shù)量級。 f(n) = 1 + n + n2 + n3 T(n) = O( n3 ) 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 O的數(shù)學定義: 若T(n)和f(n)是定義在正整數(shù)集合上的兩 個函數(shù)，則如果存在正常數(shù)C和n0,使得當 nn0時，總滿足0T(n)Cf(n),則

41、記做 T(n)=O(f(n) 也就是只求出T(n)的最高階（數(shù)量級）,忽略 其低階項和常系數(shù),這樣既可簡化T(n)的計算, 又能比較客觀地反映出當n很大時,算法的時 間性能。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 2個個N*N矩陣相乘矩陣相乘 for (i= 1; i=n; +i) for (j= 1; j=n; +j) cij = 0; for (k= 1; k=n; +k) cij += aik * bkj; n+1 n(n+1) n2 n2(n+1) n3 1232)( 23 nnnnf T(n) = O( n3 ) 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 （1） x=x+

42、1 ； 其時間復雜度為其時間復雜度為O(1)， 我們稱之為常量階；我們稱之為常量階； （2） for (i=1; i= n; i+) x=x+1; 其時間復雜度為其時間復雜度為O(n)， 我我 們稱之為線性階；們稱之為線性階； （3） for (i=1; i= n; i+) for (j=1; j= n; j+) x=x+1; 其時間復雜度為其時間復雜度為O(n2), 我我 們稱之為平方階。們稱之為平方階。 此外算法還能呈現(xiàn)的時間復雜度有對數(shù)階此外算法還能呈現(xiàn)的時間復雜度有對數(shù)階O(log2n), 指數(shù)階指數(shù)階 O(2n)等。等。 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 ) 1 (O )(log2nO )(nO )log( 2 nnO )( 2 nO )( 3 nO )( k nO )2( n O 第 1章 緒 論 數(shù)據(jù)機構第數(shù)據(jù)機構第1章章 例如：例如： 下列程序段：下列程序段： for (i=1; i= n; i+) for (j=i; j= n; j+) x+; l語句語句x+的執(zhí)行頻度為的執(zhí)行頻度為 n+(n-1)+(n-2)+3+2+1 =