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

1、第 1章 緒 論 教材數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴蔚敏，吳偉民語言版）嚴蔚敏，吳偉民第 1章 緒 論 作業(yè)及考核 作業(yè)： 時間：周二 數(shù)量：每次交三分之一 考核： 期末筆試：50% 期末機試：30% 上機實驗：10% 作業(yè)：10%第 1章 緒 論 課件 courseware_ http:/ 帳號：courseware_ds 密碼：123abc第 1章 緒 論 C語言語言 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 軟件工程軟件工程掌握基本編掌握基本編程方法程方法掌握數(shù)據(jù)組掌握數(shù)據(jù)組織和數(shù)據(jù)處織和數(shù)據(jù)處理的方法理的方法掌握大型軟掌握大型軟件開發(fā)方法件開發(fā)方法學習識字學習識字學習寫作文學習寫作文學習寫小說學習寫小說基本

2、要求課程關(guān)系與語文學習過程類比第 1章 緒 論 前期課程前期課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計算機基礎(chǔ)計算機基礎(chǔ)C語言語言離散數(shù)學離散數(shù)學后期課程后期課程操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理數(shù)據(jù)庫原理數(shù)據(jù)庫原理軟件工程軟件工程承上承上啟下啟下第 1章 緒 論 第第1章章 緒論緒論 1.1 什么是數(shù)據(jù)結(jié)構(gòu)（定義）什么是數(shù)據(jù)結(jié)構(gòu)（定義）1.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容數(shù)據(jù)結(jié)構(gòu)的內(nèi)容1.3 算法算法1.4 算法描述的工具算法描述的工具1.5 對算法作性能評價對算法作性能評價1.6 關(guān)于學習數(shù)據(jù)結(jié)構(gòu)關(guān)于學習數(shù)據(jù)結(jié)構(gòu) 第 1章 緒 論 第一章第一章 緒論緒論計算機的應(yīng)用計算機的應(yīng)用:科學計算；科學計算；控制、管理及數(shù)據(jù)處理等非數(shù)

3、值計算的處理工作；控制、管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作；計算機加工的對象計算機加工的對象:純粹的數(shù)值；純粹的數(shù)值；文本、表格和圖像數(shù)據(jù)；文本、表格和圖像數(shù)據(jù)；如何表示、處理這些如何表示、處理這些新的新的、具有一定、具有一定結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)？的數(shù)據(jù)？第 1章 緒 論 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門什么課程是一門什么課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門研究是一門研究非數(shù)值計算非數(shù)值計算的程序設(shè)計問題時處理的程序設(shè)計問題時處理的的操作對象操作對象以及它們之間的以及它們之間的關(guān)系和操作關(guān)系和操作等等的學科。等等的學科。解決數(shù)值計算問題的解決數(shù)值計算問題的中心中心: 建立適當?shù)慕⑦m當?shù)臄?shù)學模型數(shù)學模型。解決非數(shù)值計

4、算問題的解決非數(shù)值計算問題的中心中心: 尋找適當?shù)膶ふ疫m當?shù)臄?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)。第 1章 緒 論 數(shù)值問題數(shù)值問題:例例1，求解梁架結(jié)構(gòu)中的應(yīng)力。求解梁架結(jié)構(gòu)中的應(yīng)力。數(shù)學模型數(shù)學模型: K U = Ma11annx1xnb1bn例例2，預(yù)報人口增長情況。預(yù)報人口增長情況。數(shù)學模型數(shù)學模型:dN(t)d tr N(t)N(t)| |t=t N00N(t) N0 e r t第 1章 緒 論 非數(shù)值問題非數(shù)值問題:例例1，圖書館的書目檢索系統(tǒng)自動化問題。圖書館的書目檢索系統(tǒng)自動化問題。通過提供書名、作者或分類信息，你就可以從圖書館通過提供書名、作者或分類信息，你就可以從圖書館中檢索某一本書。中檢索某

5、一本書。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):線性表線性表。D01曲守寧曲守寧數(shù)據(jù)庫數(shù)據(jù)庫004S01王永燕王永燕數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)003L01潘玉奇潘玉奇程序設(shè)計程序設(shè)計002S01周勁周勁數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)001004數(shù)據(jù)庫數(shù)據(jù)庫002程序設(shè)計程序設(shè)計001,003數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)004曲守寧曲守寧003王永燕王永燕002潘玉奇潘玉奇001周勁周勁004D002L001,003S第 1章 緒 論 例例2，計算機和人對奕問題。計算機和人對奕問題。計算機可以根據(jù)當前棋盤格局，來預(yù)測棋局發(fā)展的趨計算機可以根據(jù)當前棋盤格局，來預(yù)測棋局發(fā)展的趨勢，甚至最后結(jié)局。勢，甚至最后結(jié)局。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):對弈樹對弈樹。OO當前格局

6、當前格局派生格局派生格局OOOOOOOOOO第 1章 緒 論 例例3，地圖的著色問題。地圖的著色問題。對地圖上的每個區(qū)域染一種顏色，并且要求相鄰的兩對地圖上的每個區(qū)域染一種顏色，并且要求相鄰的兩個區(qū)域不能具有相同顏色。個區(qū)域不能具有相同顏色。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):圖圖。12435671234567紅紅綠綠綠綠藍藍紅紅黑黑綠綠1243567用最少的顏色染色用最少的顏色染色第 1章 緒 論 數(shù)學數(shù)學計算機計算機硬件硬件計算機計算機軟件軟件數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)第 1章 緒 論 1. 數(shù)據(jù)（數(shù)據(jù)（Data） 對客觀事物的符號描述，能輸入到計算機中并被對客觀事物的符號描述，能輸入到計算機中并被計算機程序處理的符

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

8、據(jù)元素可由若干個數(shù)據(jù)項組成。例，例，一條書目信息是由書名、作者名、分類等多個數(shù)據(jù)一條書目信息是由書名、作者名、分類等多個數(shù)據(jù)項組成的項組成的數(shù)據(jù)項是數(shù)據(jù)的不可分割的數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小最小單位。單位。第 1章 緒 論 例如例如 有一個學生表如下所示。這個表中的有一個學生表如下所示。這個表中的數(shù)據(jù)元素數(shù)據(jù)元素是學是學生記錄生記錄,每個數(shù)據(jù)元素由四個每個數(shù)據(jù)元素由四個數(shù)據(jù)項數(shù)據(jù)項(即學號、姓名、性即學號、姓名、性別和班號別和班號)組成。組成。學號學號姓名姓名性別性別班號班號1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男99012

9、6董強董強男男99025王萍王萍女女9901第 1章 緒 論 3. 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data Structure） 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，的數(shù)據(jù)元素集合， 結(jié)構(gòu)（結(jié)構(gòu)（Structure） 數(shù)據(jù)元素相互之間的關(guān)系。數(shù)據(jù)元素相互之間的關(guān)系。 在形式上可用二元組表示：在形式上可用二元組表示： Data_Structure = ( D,S) D: 數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集 S: D上關(guān)系的有限集上關(guān)系的有限集第 1章 緒 論 D = ki | 1in, n0ki表示集合表示集合D中的第中的第i個結(jié)點或數(shù)據(jù)元素個

10、結(jié)點或數(shù)據(jù)元素n為為D中結(jié)點的個數(shù)中結(jié)點的個數(shù)若若n=0, 則則D是一個空集是一個空集, 表示表示D無結(jié)構(gòu)可言無結(jié)構(gòu)可言, 有時有時也可以認為它具有任意的結(jié)構(gòu)也可以認為它具有任意的結(jié)構(gòu)第 1章 緒 論 S=rj| 1jm, m0rj 表示集合表示集合S中的第中的第j個二元關(guān)系個二元關(guān)系(簡稱關(guān)系簡稱關(guān)系)m為為S中關(guān)系的個數(shù)中關(guān)系的個數(shù)若若m=0, 則則S是一個空集是一個空集, 表明集合表明集合D中的元結(jié)點中的元結(jié)點間不存在任何關(guān)系間不存在任何關(guān)系, 彼此是獨立的彼此是獨立的第 1章 緒 論 D D上的一個關(guān)系上的一個關(guān)系r是序偶的集合是序偶的集合, 對于對于r中的任一序偶中的任一序偶(x,y

11、D),我們稱序偶的第一結(jié)點為第二結(jié)點的直我們稱序偶的第一結(jié)點為第二結(jié)點的直接前驅(qū)結(jié)點接前驅(qū)結(jié)點(通常簡稱前驅(qū)結(jié)點通常簡稱前驅(qū)結(jié)點),稱第二結(jié)點為第一結(jié)稱第二結(jié)點為第一結(jié)點的直接后繼結(jié)點點的直接后繼結(jié)點(通常簡稱后繼結(jié)點通常簡稱后繼結(jié)點)。如在。如在的的序偶中序偶中,x為為y的前驅(qū)結(jié)點的前驅(qū)結(jié)點,而而y為為x的后繼結(jié)點。的后繼結(jié)點。 若某個結(jié)點沒有前驅(qū)若某個結(jié)點沒有前驅(qū),則稱該結(jié)點為開始結(jié)點；若則稱該結(jié)點為開始結(jié)點；若某個結(jié)點沒有后繼某個結(jié)點沒有后繼,則稱該結(jié)點為終端結(jié)點；除此之外則稱該結(jié)點為終端結(jié)點；除此之外的節(jié)點稱為內(nèi)部節(jié)點。的節(jié)點稱為內(nèi)部節(jié)點。 “尖括號尖括號”表示有向關(guān)系，表示有向關(guān)系，

12、“圓括號圓括號”表示無向關(guān)表示無向關(guān)系。系。第 1章 緒 論 例如例如,用二元組表示學生表，學生表中共有用二元組表示學生表，學生表中共有7個結(jié)點個結(jié)點,依次用依次用k1k7表示表示,則對應(yīng)的二元組表示為則對應(yīng)的二元組表示為Data_Structure=(D,S)其中：其中： D=k1, k2, k3, k4, k5, k6, k7 S= , , , , , 第 1章 緒 論 邏輯結(jié)構(gòu)圖：邏輯結(jié)構(gòu)圖：可以將數(shù)據(jù)結(jié)構(gòu)用圖形形象地表示可以將數(shù)據(jù)結(jié)構(gòu)用圖形形象地表示出來出來, ,圖形中的每個圖形中的每個結(jié)點結(jié)點對應(yīng)著一個對應(yīng)著一個數(shù)據(jù)元素數(shù)據(jù)元素, ,兩結(jié)兩結(jié)點之間的點之間的連線連線對應(yīng)著對應(yīng)著關(guān)系關(guān)

13、系中的一個序偶。中的一個序偶。 上述上述“學生表學生表”數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。 k1 k2 k3 k4 k5 k6 k7 第 1章 緒 論 例例1，內(nèi)部關(guān)系，內(nèi)部關(guān)系，復(fù)數(shù)復(fù)數(shù)Complex = ( C，R )其中其中: C是含兩個實數(shù)的集合是含兩個實數(shù)的集合c1 1,c2；R = P，而，而P是定義在集是定義在集合合C上的一種關(guān)系上的一種關(guān)系，其中有序偶，其中有序偶表示表示c1 1是復(fù)數(shù)是復(fù)數(shù)的實部，的實部，c2是復(fù)數(shù)的虛部。是復(fù)數(shù)的虛部。其中其中: C是數(shù)據(jù)記錄的集合是數(shù)據(jù)記錄的集合ai；R = P，而，而P是定義在集合是定義在集合C上上的一種關(guān)系的一種關(guān)系，

14、其中有序偶，其中有序偶表示表示ai-1 1是是ai的直接的直接前驅(qū)元素，前驅(qū)元素，ai是是ai-1 1的直接后繼元素。的直接后繼元素。例例2，外部關(guān)系，外部關(guān)系，線性表線性表List = ( C，R )OOOOO線性線性a1a2a3a4a5第 1章 緒 論 例例3、設(shè)數(shù)據(jù)的結(jié)構(gòu)描述如下：Tree = (D, R)D = 1,2,3,4,5,6R = , , , , 畫出其邏輯結(jié)構(gòu)圖？第 1章 緒 論 1.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容數(shù)據(jù)結(jié)構(gòu)的內(nèi)容邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)元素之間的關(guān)系 。邏輯結(jié)構(gòu)可看作是從具體問題抽象出來的數(shù)學模型。邏輯結(jié)構(gòu)可看作是從具體問題抽象出來的數(shù)學模型。第 1章

15、緒 論 按照邏輯關(guān)系的不同特性分類：按照邏輯關(guān)系的不同特性分類：集合：（同屬于一個集合）集合：（同屬于一個集合）線性結(jié)構(gòu)：（一對一）線性結(jié)構(gòu)：（一對一）非線性結(jié)構(gòu)：非線性結(jié)構(gòu)：樹型結(jié)構(gòu)：（一對多）樹型結(jié)構(gòu)：（一對多）圖形結(jié)構(gòu)：（多對多）圖形結(jié)構(gòu)：（多對多）邏輯結(jié)構(gòu)類型的分類邏輯結(jié)構(gòu)類型的分類 集合 線性表 樹 圖第 1章 緒 論 (1)(1)線性結(jié)構(gòu)線性結(jié)構(gòu) 所謂所謂線性結(jié)構(gòu)線性結(jié)構(gòu), ,該結(jié)構(gòu)中的結(jié)點之間存在該結(jié)構(gòu)中的結(jié)點之間存在一對一一對一的的關(guān)系。關(guān)系。 其特點是：其特點是：開始結(jié)點開始結(jié)點和和終端結(jié)點終端結(jié)點都是惟一的都是惟一的, ,除了除了開始結(jié)點和終端結(jié)點以外開始結(jié)點和終端結(jié)點以外

16、, ,其余結(jié)點都其余結(jié)點都有且僅有有且僅有一個一個前前驅(qū)結(jié)點驅(qū)結(jié)點, ,有且僅有有且僅有一個一個后繼結(jié)點后繼結(jié)點。 順序表順序表就是典型的線性結(jié)構(gòu)。就是典型的線性結(jié)構(gòu)。邏輯結(jié)構(gòu)類型邏輯結(jié)構(gòu)類型 k1 k2 k3 k4 k5 k6 k7 第 1章 緒 論 (2)非線性結(jié)構(gòu)非線性結(jié)構(gòu) 所謂所謂非線性結(jié)構(gòu)非線性結(jié)構(gòu),該結(jié)構(gòu)中的結(jié)點之間存在該結(jié)構(gòu)中的結(jié)點之間存在一對多一對多或或多對多多對多的關(guān)系。它又可以細分為的關(guān)系。它又可以細分為樹形樹形結(jié)構(gòu)結(jié)構(gòu)和和圖形結(jié)構(gòu)圖形結(jié)構(gòu)兩類。兩類。第 1章 緒 論 所謂所謂樹形結(jié)構(gòu)樹形結(jié)構(gòu), ,該結(jié)構(gòu)中的結(jié)點之間存在該結(jié)構(gòu)中的結(jié)點之間存在一對多一對多的的關(guān)系。其特點是關(guān)

17、系。其特點是每個結(jié)點最多只有一個前驅(qū)每個結(jié)點最多只有一個前驅(qū), ,但可以有但可以有多個后繼多個后繼, ,可以有多個終端結(jié)點。非線性結(jié)構(gòu)樹形結(jié)構(gòu)可以有多個終端結(jié)點。非線性結(jié)構(gòu)樹形結(jié)構(gòu)簡稱為樹。簡稱為樹。 A C G J B E D F I H M K L 第 1章 緒 論 第 1章 緒 論 所謂所謂圖形結(jié)構(gòu)圖形結(jié)構(gòu), ,該結(jié)構(gòu)中的結(jié)點之間存在該結(jié)構(gòu)中的結(jié)點之間存在多對多多對多的的關(guān)系。其特點是關(guān)系。其特點是每個結(jié)點的前驅(qū)和后繼的個數(shù)都可以每個結(jié)點的前驅(qū)和后繼的個數(shù)都可以是任意的是任意的。因此。因此, ,可能沒有開始結(jié)點和終端結(jié)點可能沒有開始結(jié)點和終端結(jié)點, ,也可也可能有多個開始結(jié)點、多個終端結(jié)

18、點。圖形結(jié)構(gòu)簡稱為能有多個開始結(jié)點、多個終端結(jié)點。圖形結(jié)構(gòu)簡稱為圖。圖。10231023第 1章 緒 論 2. 存儲結(jié)構(gòu)（物理結(jié)構(gòu)）存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 邏輯結(jié)構(gòu)在計算機中的存儲映象，是邏邏輯結(jié)構(gòu)在計算機中的存儲映象，是邏 輯結(jié)構(gòu)在計算機中的實現(xiàn)，它包括數(shù)據(jù)輯結(jié)構(gòu)在計算機中的實現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。元素的表示和關(guān)系的表示。l順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)l非順序存儲結(jié)構(gòu)（鏈式存儲結(jié)構(gòu)）非順序存儲結(jié)構(gòu)（鏈式存儲結(jié)構(gòu)）l 索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)l散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)第 1章 緒 論 例如例如 用用順序存儲法順序存儲法和和鏈式存儲法鏈式存儲法表示下面的學表示下面的學生表。生表。學號學

19、號姓名姓名性別性別班號班號1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強董強男男99025王萍王萍女女9901第 1章 緒 論 用用順序存儲法順序存儲法存放學生表的結(jié)構(gòu)體定義為：存放學生表的結(jié)構(gòu)體定義為： struct Stud int no; /*學號學號*/ char name8; /*姓名姓名*/ char sex2; /*性別性別*/ char class4; /*班號班號*/ Studs7=1,“張斌張斌”,“男男”,“9901”, 5,王萍王萍,女女,9901 ;第 1章 緒 論 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組St

20、uds各元素在內(nèi)各元素在內(nèi)存中存中按順序存放按順序存放,即第即第i(1i6)個個學生對應(yīng)的元素學生對應(yīng)的元素Studsi存放在存放在第第i+1個學生對應(yīng)的元素個學生對應(yīng)的元素Studsi+1之前之前,Studsi+1正好正好在在Studsi之后。之后。1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強董強男男 99025王萍王萍女女 9901第 1章 緒 論 用用鏈式存儲法鏈式存儲法存放學生表的結(jié)構(gòu)體定義為：存放學生表的結(jié)構(gòu)體定義為： typedef struct node int no; /*學號學號*/ c

21、har name8; /*姓名姓名*/ char sex2; /*性別性別*/ char class4; /*班號班號*/ struct node *next; /*指向下個學生的指針指向下個學生的指針*/ StudType；第 1章 緒 論 head1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強董強男男 99025王萍王萍女女 9901學生表構(gòu)成的學生表構(gòu)成的鏈表鏈表如右圖所示。其中如右圖所示。其中的的head為第一個數(shù)為第一個數(shù)據(jù)元素的指針。據(jù)元素的指針。 學生表構(gòu)成的鏈表學生表構(gòu)成的鏈表第 1章 緒

22、論 鏈式存儲法的缺點：鏈式存儲法的缺點：存儲空間占用大存儲空間占用大無法隨機訪問無法隨機訪問鏈式存儲法的優(yōu)點：鏈式存儲法的優(yōu)點：便于修改（插入、刪除便于修改（插入、刪除、移動）移動）第 1章 緒 論 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系l存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；l如何用計算機語言表示數(shù)據(jù)元素之間的各種關(guān)系。如何用計算機語言表示數(shù)據(jù)元素之間的各種關(guān)系。 存儲結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身的映象。邏輯結(jié)構(gòu)是數(shù)存儲結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身的映象。邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，兩者綜合起來建據(jù)結(jié)構(gòu)的抽象，存儲結(jié)

23、構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，兩者綜合起來建立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。 第 1章 緒 論 3. 數(shù)據(jù)的運算數(shù)據(jù)的運算 就是施加于數(shù)據(jù)的操作，如查找、添加、修改、刪除等。在數(shù)據(jù)結(jié)構(gòu)中運算不僅僅實加減乘除這些算術(shù)運算，它的范圍更為廣泛，常常涉及算法問題。舉例：線性表的初始化、查找、插入、刪除操作等 算法的設(shè)計取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，算法的設(shè)計取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。 抽象運算定義在邏輯結(jié)構(gòu)上，而實現(xiàn)在存儲抽象運算定義在邏輯結(jié)構(gòu)上，而實現(xiàn)在存儲結(jié)構(gòu)上。結(jié)構(gòu)上。第 1章 緒 論 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三

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

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

26、簡寫為ADT)指指的是用戶進行軟件系統(tǒng)設(shè)計時從問題的的是用戶進行軟件系統(tǒng)設(shè)計時從問題的數(shù)學模型數(shù)學模型中中抽象出來的抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)邏輯數(shù)據(jù)結(jié)構(gòu)和和邏輯數(shù)據(jù)結(jié)構(gòu)上的運算邏輯數(shù)據(jù)結(jié)構(gòu)上的運算,而不考慮計算機的而不考慮計算機的具體存儲結(jié)構(gòu)具體存儲結(jié)構(gòu)和運算的和運算的具體實現(xiàn)具體實現(xiàn)算法算法。 第 1章 緒 論 一個抽象數(shù)據(jù)類型的模塊通常應(yīng)包含一個抽象數(shù)據(jù)類型的模塊通常應(yīng)包含定義、表示和實定義、表示和實現(xiàn)現(xiàn)三部分。三部分。抽象數(shù)據(jù)類型的形式定義抽象數(shù)據(jù)類型的形式定義: 抽象數(shù)據(jù)類型是一個三元組抽象數(shù)據(jù)類型是一個三元組( D，S ，P)其中其中: D是數(shù)據(jù)對象是數(shù)據(jù)對象S是是D上數(shù)據(jù)關(guān)系的有限集

27、上數(shù)據(jù)關(guān)系的有限集P是對是對D的基本操作的有限集的基本操作的有限集數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義基本操作的定義基本操作的定義ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名第 1章 緒 論 其中其中,數(shù)據(jù)對象、數(shù)據(jù)關(guān)系用偽碼描述；數(shù)據(jù)對象、數(shù)據(jù)關(guān)系用偽碼描述；基本操作定義格式為基本操作定義格式為基本操作名（參數(shù)表）基本操作名（參數(shù)表）初始條件：初始條件：初始條件描述初始條件描述操作結(jié)果：操作結(jié)果：操作結(jié)果描述操作結(jié)果描述 基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以引用參數(shù)以&

28、;打頭，打頭， 除可提供輸入值外，還將返回操除可提供輸入值外，還將返回操作結(jié)果。作結(jié)果。 “初始條件初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。錯信息。 “操作結(jié)果操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。之。第 1章 緒 論 例如，例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)復(fù)數(shù)” 數(shù)據(jù)對象：數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)

29、關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分 ADT Complex 第 1章 緒 論 基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實部和虛部 分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( &Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實部值。第 1章 緒 論 GetImag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPar

30、t返回復(fù)數(shù)Z的虛部值。 Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1, z2 的 和值。 ADT Complex第 1章 緒 論 )34()68()34)(68(iiiiz # include # include complex.h void main() 第 1章 緒 論 complex z1,z2,z3,z4,z; float RealPart,ImagPart; AssignComplex(z1,8.0,6.0); AssignComplex(z2,4.0,3.0); Add(z1,z2,z3); Multiply(z1,z

31、2,z4); if (Division (z4,z3,z) GetReal (z, RealPart); GetImag (z, ImagPart); /if第 1章 緒 論 ADT 有兩個重要特征:數(shù)據(jù)抽象數(shù)據(jù)抽象 用ADT描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征本質(zhì)的特征、其所能完成的其所能完成的功能功能以及它和外部用戶的接口外部用戶的接口（即外界外界使用它的方法使用它的方法）數(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ù)類型的表示和實現(xiàn)抽象數(shù)據(jù)類型的表示和實現(xiàn) 抽

32、象數(shù)據(jù)類型需要通過固有數(shù)據(jù)固有數(shù)據(jù)類型類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。例如，對以上定義的復(fù)數(shù)第 1章 緒 論 typedef struct float realpart； float imagpart；complex；/ -存儲結(jié)構(gòu)的定義存儲結(jié)構(gòu)的定義/ -基本操作的函數(shù)原型說明基本操作的函數(shù)原型說明void AssignComplex( complex &Z, float realval, float imagval )；/ 構(gòu)造復(fù)數(shù) Z,其實部和虛部分別被賦以參數(shù) / realval 和 imagval 的值第 1章 緒 論 float GetReal( comple

33、x Z )； / 返回復(fù)數(shù) Z 的實部值float Getimag( complex Z )； / 返回復(fù)數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個復(fù)數(shù) z1, z2 的和 第 1章 緒 論 / -基本操作的實現(xiàn)基本操作的實現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart =

34、 z1.imagpart + z2.imagpart; 其它省略 第 1章 緒 論 1.3 算算 法法 1. 算法（算法（Algorithm）的定義）的定義 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是規(guī)則的算法是規(guī)則的有限集合，有限集合， 是為解決特定問題而規(guī)定的一系列操作。是為解決特定問題而規(guī)定的一系列操作。 ) 第 1章 緒 論 2. 算法的特性算法的特性 (1)有窮性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮

35、循環(huán)。有窮性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)。 (2)確定性：確定性： 算法中的每一個步驟必須有確定含義，無二算法中的每一個步驟必須有確定含義，無二義性。義性。 (3) 可行性：可行性： 原則上能精確進行，操作可通過已實現(xiàn)的基原則上能精確進行，操作可通過已實現(xiàn)的基本運算執(zhí)行有限次而完成。本運算執(zhí)行有限次而完成。 (4) 輸入：輸入： 有多個或有多個或0個輸入。個輸入。 (5) 輸出：輸出： 至少有一個或多個輸出。至少有一個或多個輸出。 在算法的五大特性中，在算法的五大特性中， 最基本的是有限性、最基本的是有限性、 確定性和可確定性和可行性。行性。 第 1章 緒 論 void exam1

36、() n=2; while(n%2=0) n=n+2; printf(“%dn”,n);void exam2() y=0; x=3/y; printf(“%d,%dn” ,x,y);違反了有窮性。違反了有窮性。違反了可行性。違反了可行性。第 1章 緒 論 算法和數(shù)據(jù)結(jié)構(gòu)是兩個不可分割的統(tǒng)一體算法和數(shù)據(jù)結(jié)構(gòu)是兩個不可分割的統(tǒng)一體程序程序 = 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法數(shù)據(jù)結(jié)構(gòu)通過算法實現(xiàn)操作數(shù)據(jù)結(jié)構(gòu)通過算法實現(xiàn)操作算法根據(jù)數(shù)據(jù)結(jié)構(gòu)設(shè)計程序算法根據(jù)數(shù)據(jù)結(jié)構(gòu)設(shè)計程序第 1章 緒 論 算法設(shè)計的要求算法設(shè)計的要求: 正確性正確性 正確反映需求正確反映需求(通過測試通過測試) 可讀性可讀性 有助于理

37、解、調(diào)試和維護有助于理解、調(diào)試和維護 健壯性健壯性 完備的異常和出錯處理完備的異常和出錯處理 高效率與低存儲的需求高效率與低存儲的需求 時間、空間的要求時間、空間的要求第 1章 緒 論 描述算法的方法 自然語言：優(yōu)點簡單。缺點有歧異，表達復(fù)雜思想不明晰，不能和實現(xiàn)方式很好結(jié)合 高級程序設(shè)計語言，如Pascal, C/C+, Java等。優(yōu)點克服了自然語言的缺點，可直接執(zhí)行。缺點對部分問題的描述比較煩雜，啰嗦 *類語言。和高級程序設(shè)計語言類似，但是對其中一些比較煩雜的部分進行簡化（原因：算法主要目的是為了清晰的表述思想）*舉例：兩個數(shù)據(jù)a, b交換空間自然語言：交換a, b的存儲空間；高級語言：

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

39、法執(zhí)行的法執(zhí)行的時間度量時間度量。例，例，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)基本操作重復(fù)執(zhí)行的次數(shù)分別為基本操作重復(fù)執(zhí)行的次數(shù)分別為 1，n，n2第 1章 緒 論 頻度頻度: 語句重復(fù)執(zhí)行的次數(shù)稱為該語句的頻度，記語句重復(fù)執(zhí)行的次數(shù)稱為該語句的頻度，記f(n)。設(shè)算法的問題規(guī)模為設(shè)算法的問題規(guī)模為n；時間復(fù)雜度時間復(fù)雜度: 算法執(zhí)行時間度量算法執(zhí)行時間度量, ,記記T(n)=O( maxle

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

41、略其低階項和常系數(shù),這樣既可簡化T(n)的計算,又能比較客觀地反映出當n很大時,算法的時間性能。第 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+1n(n+1)n2n2(n+1)n31232)(23nnnnfT(n) = O( n3 )第 1章 緒 論 （1） x=x+1 ； 其時間復(fù)雜度為其時間復(fù)雜度為O(1)， 我們稱之為常量階；我們稱之為常量階； （2） for (i=1; i= n; i+) x=x+1; 其時間復(fù)

42、雜度為其時間復(fù)雜度為O(n)， 我我們稱之為線性階；們稱之為線性階； （3） for (i=1; i= n; i+) for (j=1; j= n; j+) x=x+1; 其時間復(fù)雜度為其時間復(fù)雜度為O(n2), 我我們稱之為平方階。們稱之為平方階。 此外算法還能呈現(xiàn)的時間復(fù)雜度有對數(shù)階此外算法還能呈現(xiàn)的時間復(fù)雜度有對數(shù)階O(log2n), 指數(shù)階指數(shù)階O(2n)等。等。 第 1章 緒 論 ) 1 (O)(log2nO)(nO)log(2nnO)(2nO)(3nO)(knO)2(nO第 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 =n(n+1)/2l而該語句執(zhí)行次數(shù)關(guān)于而該語句執(zhí)行次數(shù)關(guān)于n的增長率為的增長率為n2, 即時間復(fù)雜