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

1、第 1章 緒 論 教材數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏，吳偉民語言版）嚴(yán)蔚敏，吳偉民第 1章 緒 論 作業(yè)及考核 作業(yè)： 時(shí)間：周二 數(shù)量：每次交三分之一 考核： 期末筆試：50% 期末機(jī)試：30% 上機(jī)實(shí)驗(yàn)：10% 作業(yè)：10%第 1章 緒 論 課件 courseware_ http:/ 帳號(hào)：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ā)方法學(xué)習(xí)識(shí)字學(xué)習(xí)識(shí)字學(xué)習(xí)寫作文學(xué)習(xí)寫作文學(xué)習(xí)寫小說學(xué)習(xí)寫小說基本

2、要求課程關(guān)系與語文學(xué)習(xí)過程類比第 1章 緒 論 前期課程前期課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)基礎(chǔ)計(jì)算機(jī)基礎(chǔ)C語言語言離散數(shù)學(xué)離散數(shù)學(xué)后期課程后期課程操作系統(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 對(duì)算法作性能評(píng)價(jià)對(duì)算法作性能評(píng)價(jià)1.6 關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 第 1章 緒 論 第一章第一章 緒論緒論計(jì)算機(jī)的應(yīng)用計(jì)算機(jī)的應(yīng)用:科學(xué)計(jì)算；科學(xué)計(jì)算；控制、管理及數(shù)據(jù)處理等非數(shù)

3、值計(jì)算的處理工作；控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作；計(jì)算機(jī)加工的對(duì)象計(jì)算機(jī)加工的對(duì)象:純粹的數(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ù)值計(jì)算非數(shù)值計(jì)算的程序設(shè)計(jì)問題時(shí)處理的程序設(shè)計(jì)問題時(shí)處理的的操作對(duì)象操作對(duì)象以及它們之間的以及它們之間的關(guān)系和操作關(guān)系和操作等等的學(xué)科。等等的學(xué)科。解決數(shù)值計(jì)算問題的解決數(shù)值計(jì)算問題的中心中心: 建立適當(dāng)?shù)慕⑦m當(dāng)?shù)臄?shù)學(xué)模型數(shù)學(xué)模型。解決非數(shù)值計(jì)

4、算問題的解決非數(shù)值計(jì)算問題的中心中心: 尋找適當(dāng)?shù)膶ふ疫m當(dāng)?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ù)學(xué)模型數(shù)學(xué)模型: K U = Ma11annx1xnb1bn例例2，預(yù)報(bào)人口增長(zhǎng)情況。預(yù)報(bào)人口增長(zhǎng)情況。數(shù)學(xué)模型數(shù)學(xué)模型:dN(t)d tr N(t)N(t)| |t=t N00N(t) N0 e r t第 1章 緒 論 非數(shù)值問題非數(shù)值問題:例例1，圖書館的書目檢索系統(tǒng)自動(dòng)化問題。圖書館的書目檢索系統(tǒng)自動(dò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è)計(jì)程序設(shè)計(jì)002S01周勁周勁數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)001004數(shù)據(jù)庫數(shù)據(jù)庫002程序設(shè)計(jì)程序設(shè)計(jì)001,003數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)004曲守寧曲守寧003王永燕王永燕002潘玉奇潘玉奇001周勁周勁004D002L001,003S第 1章 緒 論 例例2，計(jì)算機(jī)和人對(duì)奕問題。計(jì)算機(jī)和人對(duì)奕問題。計(jì)算機(jī)可以根據(jù)當(dāng)前棋盤格局，來預(yù)測(cè)棋局發(fā)展的趨計(jì)算機(jī)可以根據(jù)當(dāng)前棋盤格局，來預(yù)測(cè)棋局發(fā)展的趨勢(shì)，甚至最后結(jié)局。勢(shì)，甚至最后結(jié)局。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):對(duì)弈樹對(duì)弈樹。OO當(dāng)前格局

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

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

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

9、6董強(qiáng)董強(qiáng)男男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個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素個(gè)

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

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

12、“圓括號(hào)圓括號(hào)”表示無向關(guān)表示無向關(guān)系。系。第 1章 緒 論 例如例如,用二元組表示學(xué)生表，學(xué)生表中共有用二元組表示學(xué)生表，學(xué)生表中共有7個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn),依次用依次用k1k7表示表示,則對(duì)應(yīng)的二元組表示為則對(duì)應(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)用圖形形象地表示出來出來, ,圖形中的每個(gè)圖形中的每個(gè)結(jié)點(diǎn)結(jié)點(diǎn)對(duì)應(yīng)著一個(gè)對(duì)應(yīng)著一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素, ,兩結(jié)兩結(jié)點(diǎn)之間的點(diǎn)之間的連線連線對(duì)應(yīng)著對(duì)應(yīng)著關(guān)系關(guān)

13、系中的一個(gè)序偶。中的一個(gè)序偶。 上述上述“學(xué)生表學(xué)生表”數(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是含兩個(gè)實(shí)數(shù)的集合是含兩個(gè)實(shí)數(shù)的集合c1 1,c2；R = P，而，而P是定義在集是定義在集合合C上的一種關(guān)系上的一種關(guān)系，其中有序偶，其中有序偶表示表示c1 1是復(fù)數(shù)是復(fù)數(shù)的實(shí)部，的實(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ù)學(xué)模型。邏輯結(jié)構(gòu)可看作是從具體問題抽象出來的數(shù)學(xué)模型。第 1章

15、緒 論 按照邏輯關(guān)系的不同特性分類：按照邏輯關(guān)系的不同特性分類：集合：（同屬于一個(gè)集合）集合：（同屬于一個(gè)集合）線性結(jié)構(gòu)：（一對(duì)一）線性結(jié)構(gòu)：（一對(duì)一）非線性結(jié)構(gòu)：非線性結(jié)構(gòu)：樹型結(jié)構(gòu)：（一對(duì)多）樹型結(jié)構(gòu)：（一對(duì)多）圖形結(jié)構(gòu)：（多對(duì)多）圖形結(jié)構(gòu)：（多對(duì)多）邏輯結(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é)點(diǎn)之間存在該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)一一對(duì)一的的關(guān)系。關(guān)系。 其特點(diǎn)是：其特點(diǎn)是：開始結(jié)點(diǎn)開始結(jié)點(diǎn)和和終端結(jié)點(diǎn)終端結(jié)點(diǎn)都是惟一的都是惟一的, ,除了除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外

16、, ,其余結(jié)點(diǎn)都其余結(jié)點(diǎn)都有且僅有有且僅有一個(gè)一個(gè)前前驅(qū)結(jié)點(diǎn)驅(qū)結(jié)點(diǎn), ,有且僅有有且僅有一個(gè)一個(gè)后繼結(jié)點(diǎn)后繼結(jié)點(diǎn)。 順序表順序表就是典型的線性結(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é)點(diǎn)之間存在該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多一對(duì)多或或多對(duì)多多對(duì)多的關(guān)系。它又可以細(xì)分為的關(guān)系。它又可以細(xì)分為樹形樹形結(jié)構(gòu)結(jié)構(gòu)和和圖形結(jié)構(gòu)圖形結(jié)構(gòu)兩類。兩類。第 1章 緒 論 所謂所謂樹形結(jié)構(gòu)樹形結(jié)構(gòu), ,該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多一對(duì)多的的關(guān)系。其特點(diǎn)是關(guān)

17、系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū), ,但可以有但可以有多個(gè)后繼多個(gè)后繼, ,可以有多個(gè)終端結(jié)點(diǎn)。非線性結(jié)構(gòu)樹形結(jié)構(gòu)可以有多個(gè)終端結(jié)點(diǎn)。非線性結(jié)構(gòu)樹形結(jié)構(gòu)簡(jiǎn)稱為樹。簡(jiǎn)稱為樹。 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é)點(diǎn)之間存在該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在多對(duì)多多對(duì)多的的關(guān)系。其特點(diǎn)是關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的個(gè)數(shù)都可以每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的個(gè)數(shù)都可以是任意的是任意的。因此。因此, ,可能沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn)可能沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn), ,也可也可能有多個(gè)開始結(jié)點(diǎn)、多個(gè)終端結(jié)

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

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

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

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

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

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

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

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

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

27、上數(shù)據(jù)關(guān)系的有限集P是對(duì)是對(duì)D的基本操作的有限集的基本操作的有限集數(shù)據(jù)對(duì)象的定義數(shù)據(jù)對(duì)象的定義數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義基本操作的定義基本操作的定義ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名第 1章 緒 論 其中其中,數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系用偽碼描述；數(shù)據(jù)對(duì)象、數(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)出錯(cuò)信息。錯(cuò)信息。 “操作結(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ù)對(duì)象：數(shù)據(jù)對(duì)象： De1,e2e1,e2RealSet 數(shù)據(jù)

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

30、t返回復(fù)數(shù)Z的虛部值。 Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(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 有兩個(gè)重要特征:數(shù)據(jù)抽象數(shù)據(jù)抽象 用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征本質(zhì)的特征、其所能完成的其所能完成的功能功能以及它和外部用戶的接口外部用戶的接口（即外界外界使用它的方法使用它的方法）數(shù)據(jù)封裝數(shù)據(jù)封裝 將實(shí)體的外部特性和其內(nèi)部外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)第 1章 緒 論 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 抽

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

33、x Z )； / 返回復(fù)數(shù) Z 的實(shí)部值float Getimag( complex Z )； / 返回復(fù)數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 第 1章 緒 論 / -基本操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個(gè)復(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)確定性：確定性： 算法中的每一個(gè)步驟必須有確定含義，無二算法中的每一個(gè)步驟必須有確定含義，無二義性。義性。 (3) 可行性：可行性： 原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)的基原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成。本運(yùn)算執(zhí)行有限次而完成。 (4) 輸入：輸入： 有多個(gè)或有多個(gè)或0個(gè)輸入。個(gè)輸入。 (5) 輸出：輸出： 至少有一個(gè)或多個(gè)輸出。至少有一個(gè)或多個(gè)輸出。 在算法的五大特性中，在算法的五大特性中， 最基本的是有限性、最基本的是有限性、 確定性和可確定性和可行性。行性。 第 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)是兩個(gè)不可分割的統(tǒng)一體算法和數(shù)據(jù)結(jié)構(gòu)是兩個(gè)不可分割的統(tǒng)一體程序程序 = 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法數(shù)據(jù)結(jié)構(gòu)通過算法實(shí)現(xiàn)操作數(shù)據(jù)結(jié)構(gòu)通過算法實(shí)現(xiàn)操作算法根據(jù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)程序算法根據(jù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)程序第 1章 緒 論 算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求: 正確性正確性 正確反映需求正確反映需求(通過測(cè)試通過測(cè)試) 可讀性可讀性 有助于理

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

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

39、法執(zhí)行的法執(zhí)行的時(shí)間度量時(shí)間度量。例，例，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；時(shí)間復(fù)雜度時(shí)間復(fù)雜度: 算法執(zhí)行時(shí)間度量算法執(zhí)行時(shí)間度量, ,記記T(n)=O( maxle

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

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

42、雜度為其時(shí)間復(fù)雜度為O(n)， 我我們稱之為線性階；們稱之為線性階； （3） for (i=1; i= n; i+) for (j=1; j= n; j+) x=x+1; 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為O(n2), 我我們稱之為平方階。們稱之為平方階。 此外算法還能呈現(xiàn)的時(shí)間復(fù)雜度有對(duì)數(shù)階此外算法還能呈現(xiàn)的時(shí)間復(fù)雜度有對(duì)數(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的增長(zhǎng)率為的增長(zhǎng)率為n2, 即時(shí)間復(fù)雜