第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é) 號(hào)號(hào) 姓姓 名名 性別性別 籍籍 貫貫 出生年月出生年月 1 98131 劉激揚(yáng)劉激揚(yáng) 男男 北北 京京 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 課程編號(hào)課程編號(hào) 課課 程程 名名 學(xué)時(shí)學(xué)時(shí) 024002 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 64 024010 匯編語言匯編語言 48 024016 計(jì)算機(jī)原理計(jì)算機(jī)原理 64 024020 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 64 024021 微機(jī)技術(shù)微機(jī)技術(shù) 64 024024 操作系統(tǒng)操作系統(tǒng) 48 024026 數(shù)據(jù)庫原理數(shù)據(jù)庫原理 485 5學(xué)生學(xué)生( (學(xué)號(hào)學(xué)號(hào), ,姓名姓名, ,性別性別, ,籍貫籍貫) )課程課程( (課程號(hào)課程號(hào), ,課程名課程名, ,學(xué)分學(xué)分) )選課選課( (學(xué)號(hào)學(xué)

3、號(hào), ,課程號(hào)課程號(hào), ,成績(jī)成績(jī), ,時(shí)間時(shí)間) )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ù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。機(jī)程序識(shí)別和處理的符號(hào)的集合。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è)績(jī)業(yè)績(jī)數(shù)據(jù)元素?cái)?shù)據(jù)元素 (data element)(data element)n數(shù)據(jù)的基本單位數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)整體進(jìn)行考慮和處理。n有時(shí)一個(gè)數(shù)據(jù)元素可以由若干有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) (Data Item)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小的最小標(biāo)識(shí)單位。標(biāo)識(shí)單位。n數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。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_StructureData_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ù)對(duì)象，以及存在于該對(duì)象數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象，以及存在于該對(duì)象的實(shí)例和組成實(shí)例的數(shù)據(jù)元素之間的各種的實(shí)例和組成實(shí)例的數(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)與算法分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法分析析：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)是 ADT（抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型 Abstract Data Type） 的物理實(shí)現(xiàn)。的物理實(shí)現(xiàn)?！?nLobert L.Kruse 數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)：一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過程分成抽象層、數(shù)據(jù)一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。其中，抽象層是指抽象結(jié)構(gòu)層和實(shí)現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其運(yùn)算，數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層討論一個(gè)數(shù)據(jù)運(yùn)算，數(shù)據(jù)

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

8、n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)與數(shù)據(jù)的存儲(chǔ)無關(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ù)元素的相對(duì)存儲(chǔ)位與數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置無關(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ù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)；的實(shí)現(xiàn)；n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言。u 順序存儲(chǔ)表示順序存儲(chǔ)表示u 鏈接存儲(chǔ)表示鏈接存儲(chǔ)表示u 索引存儲(chǔ)表示索引存儲(chǔ)表示u 散列存儲(chǔ)表示

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

11、算插入運(yùn)算: :在數(shù)據(jù)結(jié)構(gòu)的指定位置上插入一個(gè)新元在數(shù)據(jù)結(jié)構(gòu)的指定位置上插入一個(gè)新元素；素；刪除運(yùn)算刪除運(yùn)算: :將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素刪除；將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素刪除； 2525抽象數(shù)據(jù)類型及面向?qū)ο蟾拍畛橄髷?shù)據(jù)類型及面向?qū)ο蟾拍頽數(shù)據(jù)類型數(shù)據(jù)類型 定義：定義：一組性質(zhì)相同的值的集合一組性質(zhì)相同的值的集合, 以及定以及定義于這個(gè)值集合上的一組操作的總稱義于這個(gè)值集合上的一組操作的總稱.nC語言中的數(shù)據(jù)類型語言中的數(shù)據(jù)類型字符型字符型 整型整型 浮點(diǎn)型浮點(diǎn)型 雙精度型雙精度型 無值無值 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ù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)基本數(shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(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ù)類型的變量，才能參加運(yùn)算。類型的變量，才能參加運(yùn)算。 2828抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)(ADTs: Abstract Data Types)n抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)抽象數(shù)據(jù)

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

14、關(guān)系用偽碼描述；基本操作定義格式為述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義數(shù)據(jù)對(duì)象的定義 數(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)出錯(cuò)信息。操作失敗，并返回相應(yīng)出錯(cuò)信息。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: 一個(gè)整數(shù)的有序子集合一個(gè)整數(shù)的有序子集合,它開始于它開始于

16、0, 結(jié)束于機(jī)器能表示的最大整數(shù)結(jié)束于機(jī)器能表示的最大整數(shù)(MaxInt)。Function: 對(duì)于所有的對(duì)于所有的 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ū)ο?= = 對(duì)象類繼承通信對(duì)象類繼承通信n對(duì)象對(duì)象u在應(yīng)用問題中出現(xiàn)的各種在應(yīng)用問題中出現(xiàn)的各種實(shí)體實(shí)體、事件事件、規(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ù)類型的變量?jī)H涉及屬性值，與操造數(shù)據(jù)類型的變量?jī)H涉

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

20、3 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(aPoint

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

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

24、n-1; 若最小整數(shù)在若最小整數(shù)在ak, 交換交換ai與與ak; 算法設(shè)計(jì)算法設(shè)計(jì) 自頂向下，逐步求精自頂向下，逐步求精 4545細(xì)化程序：細(xì)化程序：程序程序 SelectSort void selectSort ( int a , const int n ) /對(duì)n個(gè)整數(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算法簡(jiǎn)單性能分析與度量算法簡(jiǎn)單性能分析與度量4747算法的性能標(biāo)準(zhǔn)算法的性能標(biāo)準(zhǔn)(Correctness ) 算法應(yīng)滿足具體問題算法應(yīng)滿足具體問題的需求。的需求。(Readability) 算法應(yīng)該容易閱讀。算法應(yīng)該容易閱讀。以有利于閱讀者對(duì)程序的理解。以有利于閱讀者對(duì)程序的理解。效率指的是算法執(zhí)行的時(shí)間和空間利效率指的是算法執(zhí)行的時(shí)間和空間利用率。通常這兩者與問題的規(guī)模有關(guān)。用率。通常這兩者與問題的規(guī)模有關(guān)。(Robustness) 算法應(yīng)具有容錯(cuò)處理算法應(yīng)具有容錯(cuò)處理的功能。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作的功能。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不應(yīng)產(chǎn)

26、生莫名其妙的輸出結(jié)果。出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。4848算法的后期測(cè)試算法的后期測(cè)試n對(duì)一個(gè)算法要作出全面的分析可分成兩個(gè)階對(duì)一個(gè)算法要作出全面的分析可分成兩個(gè)階段進(jìn)行，即段進(jìn)行，即事前分析事前分析和和事后測(cè)試事后測(cè)試n事前分析事前分析要求事前求出該算法的一個(gè)時(shí)間界要求事前求出該算法的一個(gè)時(shí)間界限函數(shù)。限函數(shù)。n事后測(cè)試事后測(cè)試則要求在算法執(zhí)行后通過算法執(zhí)行則要求在算法執(zhí)行后通過算法執(zhí)行的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來分析。的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來分析。n事后分析要求在算法中的某些部位插裝時(shí)間事后分析要求在算法中的某些部位插裝時(shí)間函數(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( ) 的計(jì)時(shí)程序的計(jì)時(shí)程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&

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

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

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

31、 = 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)計(jì)執(zhí)行語句條數(shù) for (int i = 0; i n; i+) count +; /針對(duì) for 語句 count +; s += ai;count+; /針對(duì)賦值語句 count +; count +; /針對(duì) for 的最后一次 count+; /針對(duì) return 語句 return s; 執(zhí)行結(jié)束得執(zhí)行結(jié)束得 程序步數(shù)程序步

32、數(shù) count = 3*n+45757計(jì)算累加和程序計(jì)算累加和程序程序步數(shù)計(jì)算工作表格程序步數(shù)計(jì)算工作表格5858注意注意： 一個(gè)語句本身的程序步數(shù)可能不等于該語一個(gè)語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。句一次執(zhí)行所具有的程序步數(shù)。 例如：例如：賦值語句賦值語句x = sum (R, n) 本身程序步數(shù)為本身程序步數(shù)為 1；一次執(zhí)行對(duì)函數(shù)一次執(zhí)行對(duì)函數(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í)題：求兩個(gè)習(xí)題：求兩個(gè)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時(shí)間復(fù)雜度的漸進(jìn)表示法時(shí)間復(fù)雜度的漸進(jìn)表示法n算法中所有語句的頻度之和是算法中所有語句的頻度之和是n的函數(shù)的函數(shù) T(n) = 3n3 + 5n2 + 4n +2n一般地，稱一般地，稱 n 是問題的規(guī)模。則時(shí)間復(fù)雜是問題的規(guī)模。則時(shí)間復(fù)雜度度 T(n) 是問題規(guī)

34、模是問題規(guī)模 n 的函數(shù)。的函數(shù)。n當(dāng)當(dāng)n趨于無窮大時(shí)，把時(shí)間復(fù)雜度的趨于無窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)數(shù)量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度 T(n) = O(n3) 大大O表示法表示法6161n加法規(guī)則加法規(guī)則 針對(duì)并列程序段針對(duì)并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)n各種函數(shù)的增長(zhǎng)趨勢(shì)各種函數(shù)的增長(zhǎng)趨勢(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ī)則 針對(duì)嵌套程序段針對(duì)嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)n兩個(gè)并列循環(huán)的例子兩個(gè)并列循環(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 ) /對(duì)表 a 逐趟比較, n 是表當(dāng)前長(zhǎ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漸進(jìn)的空間復(fù)雜度漸進(jìn)的空間復(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)，還與 A

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

40、表項(xiàng)類型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