第1章數(shù)據(jù)結(jié)構(gòu)概念

1、1第一章 數(shù)據(jù)結(jié)構(gòu)概念2 2第一章第一章 數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)概念3 3 學(xué)學(xué) 號號 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚劉激揚 男男 北北 京京 1979.12 2 98164 衣春生衣春生 男男 青青 島島 1979.07 3 98165 盧聲凱盧聲凱 男男 天天 津津 1981.02 4 98182 袁秋慧袁秋慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊南燕熊南燕 女女 蘇蘇 州州 1980.03 7 98297 宮宮 力力 男男 北北 京京 1981.01 8 98310 蔡

2、曉莉蔡曉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.124 4 課程編號課程編號 課課 程程 名名 學(xué)時學(xué)時 024002 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計算機原理計算機原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機技術(shù)微機技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 485 5學(xué)生學(xué)生( (學(xué)號學(xué)號, ,姓名姓名, ,性別性別, ,籍貫籍貫) )課程課程( (課程號課程號, ,課程名課程名, ,學(xué)分學(xué)分) )選課選課( (學(xué)號學(xué)

3、號, ,課程號課程號, ,成績成績, ,時間時間) )6 6UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp7 7百度地圖百度地圖8 8數(shù)據(jù)（數(shù)據(jù)（datadata）n數(shù)據(jù)是數(shù)據(jù)是信息信息的載體，是描述客觀事物的數(shù)、的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。機程序識別和處理的符號的集合。n數(shù)據(jù)的分類：數(shù)據(jù)的分類：u 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù)u 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)9 9姓名姓名

4、 所在院系所在院系 性別性別 出生日期出生日期 年年 月月職務(wù)職務(wù) 業(yè)績業(yè)績數(shù)據(jù)元素數(shù)據(jù)元素 (data element)(data element)n數(shù)據(jù)的基本單位數(shù)據(jù)的基本單位。在計算機程序中常作為在計算機程序中常作為一個整體進行考慮和處理。一個整體進行考慮和處理。n有時一個數(shù)據(jù)元素可以由若干有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項數(shù)據(jù)項 (Data Item)組成。數(shù)據(jù)項是具有獨立含義組成。數(shù)據(jù)項是具有獨立含義的最小的最小標識單位。標識單位。n數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。1010什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)殷人昆殷人昆數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) : 由某一數(shù)據(jù)元素的集合

5、以及該集合由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。記中所有數(shù)據(jù)元素之間的關(guān)系組成。記為：為： Data_Structure Data_Structure = D, R= D, R其中其中，D D 是某一數(shù)據(jù)元素的集合，是某一數(shù)據(jù)元素的集合，R R 是該集合中所有數(shù)據(jù)元素之間的關(guān)系是該集合中所有數(shù)據(jù)元素之間的關(guān)系的的有限有限集合集合nSartaj Sahni 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象，以及存在于該對象數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象，以及存在于該對象的實例和組成實例的數(shù)據(jù)元素之間的各種的實例和組成實例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的

6、函數(shù)聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來給出。來給出。” nClifford A.Shaffer 數(shù)據(jù)結(jié)構(gòu)與算法分數(shù)據(jù)結(jié)構(gòu)與算法分析析：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)是 ADT（抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型 Abstract Data Type） 的物理實現(xiàn)。的物理實現(xiàn)。” nLobert L.Kruse 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計：一個數(shù)據(jù)結(jié)構(gòu)的設(shè)計過程分成抽象層、數(shù)據(jù)一個數(shù)據(jù)結(jié)構(gòu)的設(shè)計過程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實現(xiàn)層。其中，抽象層是指抽象結(jié)構(gòu)層和實現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其運算，數(shù)據(jù)結(jié)構(gòu)層和實現(xiàn)層討論一個數(shù)據(jù)運算，數(shù)

7、據(jù)結(jié)構(gòu)層和實現(xiàn)層討論一個數(shù)據(jù)結(jié)構(gòu)的表示和在計算機內(nèi)的存儲細節(jié)以及結(jié)構(gòu)的表示和在計算機內(nèi)的存儲細節(jié)以及運算的實現(xiàn)。運算的實現(xiàn)。 1414例：例：N N 個網(wǎng)點之間的連通關(guān)系個網(wǎng)點之間的連通關(guān)系 1561524362431515數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式n包括三個方面：包括三個方面：u數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯邏輯結(jié)構(gòu)結(jié)構(gòu)；u數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表示，即數(shù)據(jù)的示，即數(shù)據(jù)的存儲表示存儲表示；u數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作操作。1616數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)

8、構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)與數(shù)據(jù)的存儲無關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽可以看作是從具體問題抽象出來的數(shù)據(jù)模型；象出來的數(shù)據(jù)模型；n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；內(nèi)容無關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位與數(shù)據(jù)元素的相對存儲位置無關(guān)。置無關(guān)。1717數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)的邏輯結(jié)構(gòu)分類n線性結(jié)構(gòu)線性結(jié)構(gòu)u 線性表線性表n非線性結(jié)構(gòu)非線性結(jié)構(gòu)u 樹樹u 圖（或網(wǎng)絡(luò)）圖（或網(wǎng)絡(luò)）1818線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)樹樹 二叉樹二叉樹

9、二叉搜索樹二叉搜索樹bindevetclibuser141312112345678910315871011998745662313111919堆結(jié)構(gòu)堆結(jié)構(gòu)1235487111029164101211512369872020圖結(jié)構(gòu)圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)125436113318146651619211256342121數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)n數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；的實現(xiàn)；n數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。u 順序存儲表示順序存儲表示u 鏈接存儲表示鏈接存儲表示u 索引存儲表示索引存儲表示u 散列存儲表

10、示散列存儲表示主要用于內(nèi)存的主要用于內(nèi)存的存儲表示存儲表示主要用于外存主要用于外存 (文文件件) 的存儲表示的存儲表示 順序存儲n需要一塊連續(xù)的存儲空間，并把邏輯上相需要一塊連續(xù)的存儲空間，并把邏輯上相關(guān)的數(shù)據(jù)元素依次存儲在該連續(xù)的存儲區(qū)關(guān)的數(shù)據(jù)元素依次存儲在該連續(xù)的存儲區(qū)中中。 LocLoc（ak）1021022 2k k 地址信息稱為鏈。地址信息稱為鏈。 表示空鏈。表示空鏈。 鏈接存儲數(shù)據(jù)結(jié)構(gòu)的運算數(shù)據(jù)結(jié)構(gòu)的運算數(shù)據(jù)結(jié)構(gòu)最常見的運算數(shù)據(jù)結(jié)構(gòu)最常見的運算 創(chuàng)建運算創(chuàng)建運算: :創(chuàng)建一個數(shù)據(jù)結(jié)構(gòu)；創(chuàng)建一個數(shù)據(jù)結(jié)構(gòu)； 清除運算清除運算: :刪除數(shù)據(jù)結(jié)構(gòu)中的全部元素；刪除數(shù)據(jù)結(jié)構(gòu)中的全部元素；插入

11、運算插入運算: :在數(shù)據(jù)結(jié)構(gòu)的指定位置上插入一個新元在數(shù)據(jù)結(jié)構(gòu)的指定位置上插入一個新元素；素；刪除運算刪除運算: :將數(shù)據(jù)結(jié)構(gòu)中的某個元素刪除；將數(shù)據(jù)結(jié)構(gòu)中的某個元素刪除； 2525抽象數(shù)據(jù)類型及面向?qū)ο蟾拍畛橄髷?shù)據(jù)類型及面向?qū)ο蟾拍頽數(shù)據(jù)類型數(shù)據(jù)類型 定義：定義：一組性質(zhì)相同的值的集合一組性質(zhì)相同的值的集合, 以及定以及定義于這個值集合上的一組操作的總稱義于這個值集合上的一組操作的總稱.nC語言中的數(shù)據(jù)類型語言中的數(shù)據(jù)類型字符型字符型 整型整型 浮點型浮點型 雙精度型雙精度型 無值無值 2626數(shù)據(jù)類型數(shù)據(jù)類型2727n數(shù)據(jù)類型數(shù)據(jù)類型由由基本數(shù)據(jù)類型基本數(shù)據(jù)類型或或構(gòu)造數(shù)據(jù)類型構(gòu)造數(shù)據(jù)類型

12、組成。組成。n構(gòu)造數(shù)據(jù)類型由構(gòu)造數(shù)據(jù)類型由不同成分類型不同成分類型構(gòu)成。構(gòu)成。n基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。n數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。者的角度來使用的。n數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。類型的變量，才能參加運算。 2828抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)n抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)抽象數(shù)

13、據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。用問題的數(shù)據(jù)模型。n特點是：特點是：信息隱蔽信息隱蔽和和數(shù)據(jù)封裝數(shù)據(jù)封裝，使用與實使用與實現(xiàn)相分離現(xiàn)相分離。n抽象數(shù)據(jù)類型可用抽象數(shù)據(jù)類型可用（D, R, P）三元組表示，三元組表示，其中，其中，D 是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象），象），R 是是 D上的關(guān)系集合，上的關(guān)系集合，P 是對是對 D 的的基本操作集合。基本操作集合。 2929抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找查找 登錄登錄 刪除刪除 修改修改 符符 號號 表表3030抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型的描述n其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼描其中數(shù)據(jù)對象、數(shù)據(jù)之間

14、的關(guān)系用偽碼描述；基本操作定義格式為述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名基本操作名（參數(shù)表）基本操作名（參數(shù)表）前置條件：前置條件：先決條件描述先決條件描述后置條件：后置條件：操作結(jié)果描述操作結(jié)果描述3131n基本操作有兩種參數(shù)：基本操作有兩種參數(shù)：賦值參數(shù)賦值參數(shù)只為操作提只為操作提供輸入值；供輸入值；引用參數(shù)引用參數(shù)以以&打頭，除可提供輸打頭，除可提供輸入值外，還將返回操作結(jié)

15、果。入值外，還將返回操作結(jié)果。n “前置條件前置條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。操作失敗，并返回相應(yīng)出錯信息。n “后置條件后置條件”說明了操作正常完成之后，說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空，則省略之。置條件為空，則省略之。3232自然數(shù)的抽象數(shù)據(jù)類型定義自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合一個整數(shù)的有序子集合,它開始于它開始

16、于0, 結(jié)束于機器能表示的最大整數(shù)結(jié)束于機器能表示的最大整數(shù)(MaxInt)。Function: 對于所有的對于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是等都是可用的服務(wù)?？捎玫姆?wù)。 Zero( ) : NaturalNumber /前置條件前置條件：無：無 /后置條件后置條件：返回自然數(shù)返回自然數(shù)03333IsZero(x) : Boolean /前置條件前置條件：x為為NaturalNumber /后置條件后置條件：if (x = 0) then 返回返回True else 返回返回False Add (x, y) :

17、 NaturalNumber /前置條件前置條件：x, y為為NaturalNumber且且x+yMaxInt /后置條件后置條件：返回返回 x+y Subtract (x, y) : NaturalNumber /前置條件前置條件： x, y為為NaturalNumber且且xy /后置條件后置條件：返回返回 x- - y3434Equal (x, y) : Boolean /前置條件前置條件： x, y為為NaturalNumber /后置條件后置條件： if (x = y) 返回返回True else 返回返回 False Successor (x) : NaturalNumber /前

18、置條件前置條件： x為為NaturalNumber /后置條件后置條件： if (x = MaxInt) 返回返回 x else 返回返回 x+1end NaturalNumber3535面向?qū)ο蟮母拍蠲嫦驅(qū)ο蟮母拍頽面向?qū)ο竺嫦驅(qū)ο?= = 對象類繼承通信對象類繼承通信n對象對象u在應(yīng)用問題中出現(xiàn)的各種在應(yīng)用問題中出現(xiàn)的各種實體實體、事件事件、規(guī)格說明規(guī)格說明等。等。u由一組由一組屬性值屬性值和在這組值上的一組和在這組值上的一組服務(wù)服務(wù)（或稱操作）構(gòu)成。（或稱操作）構(gòu)成。u與與C中構(gòu)造數(shù)據(jù)類型不同在于：中構(gòu)造數(shù)據(jù)類型不同在于：C中的構(gòu)中的構(gòu)造數(shù)據(jù)類型的變量僅涉及屬性值，與操造數(shù)據(jù)類型的變量僅

19、涉及屬性值，與操作分離，而作分離，而C+中的對象則不然。中的對象則不然。3636n類類 (class)，實例，實例 (instance)u具有相同屬性和服務(wù)的對象歸于同一類，具有相同屬性和服務(wù)的對象歸于同一類，形成類。形成類。u類中的對象為該類的實例。類中的對象為該類的實例。u同一類的實例同一類的實例 共享類的屬性和類的操作；共享類的屬性和類的操作； 通過繼承共享其父類的公共的和保護通過繼承共享其父類的公共的和保護性的屬性和操作；性的屬性和操作； 同一類的不同實例有不同的屬性值。同一類的不同實例有不同的屬性值。3737四邊形類及其對象四邊形類及其對象屬性aPoint1 aPoint2aPoin

20、t3 aPoint4服務(wù)服務(wù)Draw( )move(x, y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35, 10) (50, 10)(35, 25) (50, 25)(45, 65) (50, 45)(65, 66) (60, 70)Draw( )move(x, y)contains(aPoint)Draw( )move(x, y)contains(aPoint)服務(wù)服務(wù)服務(wù)服務(wù)quadrilateral3838n繼承繼承u派生類（子類）：派生類（子類）：四邊形，三角形，四邊形，三角形，u基類（父類）：基類（父類）：多邊形多邊形派

21、生類派生類繼承的特性繼承的特性+特有的特性特有的特性基類基類多邊形多邊形四邊形四邊形三角形三角形六邊形六邊形3939n通信通信u消息傳遞消息傳遞uC+中消息傳遞的方式：中消息傳遞的方式：操作含于類中操作含于類中 定義：定義：Point p; void move(int x, inty); 使用：使用：p.move(x, y);uC中則不同，需使用函數(shù)調(diào)用方式：中則不同，需使用函數(shù)調(diào)用方式： 定義：定義：Point p; void move(Point q, int x, inty); 使用：使用：move(p, x, y);4040Draw( )move(x, y)contains(aPoin

22、t)PolygonreferencePointVerticesPolygon 類類referencePointVerticesDraw( )move(x, y)contains(aPoint)Polygon的子類的子類Quadrilateral類類Quadrilateral4141算法定義算法定義n定義：定義： 籠統(tǒng)籠統(tǒng)的說，算法是求解一類問題的任意一的說，算法是求解一類問題的任意一種特殊的方法。較嚴格的說法是一個算法是對種特殊的方法。較嚴格的說法是一個算法是對特定問題的求解步驟的一種描述，它是指令的特定問題的求解步驟的一種描述，它是指令的有限有限序列。序列。4242算法定義算法定義n特性：特

23、性：u輸入輸入 有有0個或多個輸入個或多個輸入u輸出輸出 有一個或多個輸出有一個或多個輸出(處理結(jié)果處理結(jié)果)u確定性確定性 每步定義都是確切無歧義的每步定義都是確切無歧義的u有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束u有效性有效性 每一條運算應(yīng)足夠基本每一條運算應(yīng)足夠基本程序程序 = 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法43434444n事例學(xué)習(xí)：事例學(xué)習(xí)：選擇排序問題選擇排序問題n明確問題：明確問題：遞增排序遞增排序n解決方案：解決方案：逐個選擇最小數(shù)據(jù)逐個選擇最小數(shù)據(jù)n算法框架：算法框架： for (int i = 0; i n-1; i+) /n-1趟趟 從從ai檢查到檢查到

24、an-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak; 算法設(shè)計算法設(shè)計 自頂向下，逐步求精自頂向下，逐步求精 4545細化程序：細化程序：程序程序 SelectSort void selectSort ( int a , const int n ) /對n個整數(shù)a0,a1,an-1按遞增順序排序 for (int i = 0; i n-1; i+) int k = i; /從ai查到an-1, 找最小整數(shù), 在ak for (int j = i+1; j n; j+) if (aj ak) k = j; /記錄最小的值if(k!=i) int temp = ai; ai = ak

25、; ak = temp; 4646算法簡單性能分析與度量算法簡單性能分析與度量4747算法的性能標準算法的性能標準(Correctness ) 算法應(yīng)滿足具體問題算法應(yīng)滿足具體問題的需求。的需求。(Readability) 算法應(yīng)該容易閱讀。算法應(yīng)該容易閱讀。以有利于閱讀者對程序的理解。以有利于閱讀者對程序的理解。效率指的是算法執(zhí)行的時間和空間利效率指的是算法執(zhí)行的時間和空間利用率。通常這兩者與問題的規(guī)模有關(guān)。用率。通常這兩者與問題的規(guī)模有關(guān)。(Robustness) 算法應(yīng)具有容錯處理算法應(yīng)具有容錯處理的功能。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作的功能。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不應(yīng)

26、產(chǎn)生莫名其妙的輸出結(jié)果。出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。4848算法的后期測試算法的后期測試n對一個算法要作出全面的分析可分成兩個階對一個算法要作出全面的分析可分成兩個階段進行，即段進行，即事前分析事前分析和和事后測試事后測試n事前分析事前分析要求事前求出該算法的一個時間界要求事前求出該算法的一個時間界限函數(shù)。限函數(shù)。n事后測試事后測試則要求在算法執(zhí)行后通過算法執(zhí)行則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分析。的時間和實際占用空間的統(tǒng)計資料來分析。n事后分析要求在算法中的某些部位插裝時間事后分析要求在算法中的某些部位插裝時間函數(shù)函數(shù) time ( )，4949例如，

27、給出順序搜索例如，給出順序搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索與給定值 x 相等的元/素，函數(shù)返回其位置，失敗返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i;5050 插裝插裝 time( ) 的計時程序的計時程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&

28、;stop); double runTime = stop - start; cout n runTime endl;事實上，算法運行時間要受事實上，算法運行時間要受輸入規(guī)模、利用輸入規(guī)模、利用編譯程序生成的目標代碼的質(zhì)量、計算機編譯程序生成的目標代碼的質(zhì)量、計算機程序指令系統(tǒng)的品質(zhì)和速度等制約。程序指令系統(tǒng)的品質(zhì)和速度等制約。5151程序在計算機上運行所消耗的時間與下列因程序在計算機上運行所消耗的時間與下列因素有關(guān)：素有關(guān)：（1 1）書寫算法的程序設(shè)計語言；）書寫算法的程序設(shè)計語言；（2 2）代碼書寫的質(zhì)量；）代碼書寫的質(zhì)量；（3 3）編譯產(chǎn)生的機器語言代碼質(zhì)量；）編譯產(chǎn)生的機器語言代碼質(zhì)量

29、；（4 4）機器執(zhí)行指令的速度；）機器執(zhí)行指令的速度；（5 5）問題的規(guī)模，即算法的時間效率與算法）問題的規(guī)模，即算法的時間效率與算法處理的數(shù)據(jù)個數(shù)處理的數(shù)據(jù)個數(shù)n n的關(guān)系。的關(guān)系。5252算法的事前估計算法的事前估計n算法的事前估計主要包括時間復(fù)雜性和空算法的事前估計主要包括時間復(fù)雜性和空間復(fù)雜性的分析：間復(fù)雜性的分析：u問題的規(guī)模：問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)如：矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)等。點個數(shù)、被分類序列的正整數(shù)個數(shù)等。u時間復(fù)雜性時間復(fù)雜性：算法所需時間和問題規(guī)模：算法所需時間和問題規(guī)模的函數(shù)，記為的函數(shù)，記為 T(n)。當(dāng)當(dāng) n 時的時間時的時間復(fù)雜

30、性，稱為復(fù)雜性，稱為漸進時間復(fù)雜性漸進時間復(fù)雜性。u空間復(fù)雜性空間復(fù)雜性：算法所需空間和問題規(guī)模：算法所需空間和問題規(guī)模的函數(shù)。記為的函數(shù)。記為 S(n)。當(dāng)當(dāng) n 時的時間時的時間復(fù)雜性，稱為復(fù)雜性，稱為漸進空間復(fù)雜性漸進空間復(fù)雜性。5353空間復(fù)雜度度量空間復(fù)雜度度量5454時間復(fù)雜度度量時間復(fù)雜度度量5555n程序步確定方法程序步確定方法u插入計數(shù)全局變量插入計數(shù)全局變量countu建表，建表，列出個語句的程序步列出個語句的程序步例例 以迭代方式求累加和的函數(shù)以迭代方式求累加和的函數(shù) float sum (float a , int n) float s = 0.0; for (int

31、i = 0; i n; i+) s = s + ai; return s; 5656在求累加和程序中加入在求累加和程序中加入 count 語句語句 float sum (float a , int n) float s = 0.0; count+; /count 統(tǒng)計執(zhí)行語句條數(shù) for (int i = 0; i n; i+) count +; /針對 for 語句 count +; s += ai;count+; /針對賦值語句 count +; count +; /針對 for 的最后一次 count+; /針對 return 語句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序

32、步數(shù) count = 3*n+45757計算累加和程序計算累加和程序程序步數(shù)計算工作表格程序步數(shù)計算工作表格5858注意注意： 一個語句本身的程序步數(shù)可能不等于該語一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。句一次執(zhí)行所具有的程序步數(shù)。 例如：例如：賦值語句賦值語句x = sum (R, n) 本身程序步數(shù)為本身程序步數(shù)為 1；一次執(zhí)行對函數(shù)一次執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程的調(diào)用需要的程序步數(shù)為序步數(shù)為 3*n+4；一次執(zhí)行的程序步數(shù)為一次執(zhí)行的程序步數(shù)為 1+3*n+4 = 3*n+55959程序程序步練習(xí)步練習(xí)習(xí)題：求兩個習(xí)題：求兩個n階方陣的乘積階

33、方陣的乘積C = A Bvoid MatrixMultiply (int Ann, int Bnn,int Cnn) for (int i = 0; i n; i+) for (int j = 0; j n; j+) Cij = 0; for (int k = 0; k n; k+) Cij = Cij + Aik * Bkj; 6060時間復(fù)雜度的漸進表示法時間復(fù)雜度的漸進表示法n算法中所有語句的頻度之和是算法中所有語句的頻度之和是n的函數(shù)的函數(shù) T(n) = 3n3 + 5n2 + 4n +2n一般地，稱一般地，稱 n 是問題的規(guī)模。則時間復(fù)雜是問題的規(guī)模。則時間復(fù)雜度度 T(n) 是問題

34、規(guī)模是問題規(guī)模 n 的函數(shù)。的函數(shù)。n當(dāng)當(dāng)n趨于無窮大時，把時間復(fù)雜度的趨于無窮大時，把時間復(fù)雜度的數(shù)量級數(shù)量級（階）稱為算法的漸進時間復(fù)雜度（階）稱為算法的漸進時間復(fù)雜度 T(n) = O(n3) 大大O表示法表示法6161n加法規(guī)則加法規(guī)則 針對并列程序段針對并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)n各種函數(shù)的增長趨勢各種函數(shù)的增長趨勢 c log2n n nlog2n n2 n3 2n 3n n!6262T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)for (

35、 int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;6363n乘法規(guī)則乘法規(guī)則 針對嵌套程序段針對嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)n兩個并列循環(huán)的例子兩個并列循環(huán)的例子6464 void exam (float *x, int m, int n) float *sum = new float m; for (int

36、 i = 0; i m; i+) /x中各行 sumi = 0.0; /數(shù)據(jù)累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行數(shù)據(jù)和 cout i “ : ” sum i endl; delete sum; O(max (m*n, m)6565 void main () float *x; int m=5,n=6; x= new float *m; for(int j=0;jm;j+) xj= new float n; int j=0; for(int i=0;im;i+) for(int k=0;kn;k+)

37、 xik=j+; exam(x,m,n); 6666起泡排序起泡排序 void bubbleSort (int a , int n ) /對表 a 逐趟比較, n 是表當(dāng)前長度 for (int i = 1; i = i; j-) /n-i次比較 if (aj-1 aj) int tmp = aj-1; aj-1 = aj;aj = tmp; /一趟比較 6767 O(f (n)*g (n) = O(n2) 1121ccni)n(ni)(nBubblrSort 外層循環(huán)外層循環(huán) n-1 趟趟內(nèi)層循環(huán)內(nèi)層循環(huán) n-i 次比較次比較6868n漸進的空間復(fù)雜度漸進的空間復(fù)雜度 S (n) = O(f

38、 (n)for (i=1;i=n;i=2*i)couti; /基本語句基本語句的執(zhí)行次數(shù)f(n)，則2f(n)=n,因此f(n)=lb n T(n)= O(lb n)6969for (i=1; i=n;i+)for (j=1;j=i;j+)coutj;基本語句執(zhí)行次數(shù) nT(n)= O(n2)7070niniijnninf1112) 1(1)(for (i=1; i=n;i+)for (j=1;j=i;j+)for (k=1;k=j;k+) cout= 0 & Ai != k) i-; return i;n算法的語句算法的語句 i- 的頻度不僅與的頻度不僅與 n 有關(guān)，還與有關(guān)，還與

39、A 中各元素的取值中各元素的取值以及以及 k 的取值的取值有關(guān)。有關(guān)。本章重點本章重點：n1數(shù)據(jù)結(jié)構(gòu)的概念n2抽象數(shù)據(jù)類型n3算法和算法性能分析73737474模板模板 (template)(template)定義定義 適合適合多種數(shù)據(jù)類型多種數(shù)據(jù)類型的的類定義類定義或或算法算法，在特，在特定環(huán)境下通過簡單地代換，變成定環(huán)境下通過簡單地代換，變成針對具體某針對具體某種數(shù)據(jù)類型種數(shù)據(jù)類型的的類定義類定義或或算法。算法。7575用模板定義用于排序的數(shù)據(jù)表類用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H#define DATALIST_H#include template / /E

40、是表項類型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);7676 public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operato