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

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)Data Structures Data Structures 講課學(xué)時(shí)：講課學(xué)時(shí)：3636上機(jī)學(xué)時(shí)：上機(jī)學(xué)時(shí)：3636課程設(shè)計(jì)：課程設(shè)計(jì)：2 2周周教學(xué)安排教學(xué)安排參考書(shū)目參考書(shū)目算法與數(shù)據(jù)結(jié)構(gòu)（算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）語(yǔ)言版）， 范策，周世平，胡嘵范策，周世平，胡嘵琨琨 等編著，機(jī)械工業(yè)出版社，等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，高等教育出版社，2004數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版）數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版），徐孝凱編著，清華大，徐孝凱編著，清華大學(xué)出版社學(xué)出版社 2006

2、數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實(shí)用教程（第二版）數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實(shí)用教程（第二版），徐孝凱，徐孝凱，清華大學(xué)出版社清華大學(xué)出版社 2003算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述語(yǔ)言描述，張乃孝等，高等教育出版，張乃孝等，高等教育出版社，社，2002The Art of Computer Programing.，D.E.Knuth, Volume 1/Fundamentals. Volume 3/Sorting and Searching. MA: Aderson-WesleyFundamentals of Data Structures, Algorithms and Performance, D.Wo

3、rd. MA: Addison-WesleyFundamentals of Data Structures,Horowitz, E. and Sahn, S., Computer Science Press, Inc.參考書(shū)目參考書(shū)目 第第1章章 緒論緒論 第第2章章 線性表線性表 第第3章章 棧和隊(duì)列棧和隊(duì)列 第第4章章 串串 第第5章章 數(shù)組和廣義表數(shù)組和廣義表 第第6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 第第7章章 圖圖 第第8章章 查找查找 第第9章章 排序排序本課程的教學(xué)內(nèi)容本課程的教學(xué)內(nèi)容1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.3 抽象數(shù)據(jù)類型

4、的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4 算法和算法分析算法和算法分析本章重點(diǎn)難點(diǎn) 重點(diǎn)重點(diǎn): 數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及基本操作的概念及相互關(guān)系；抽象數(shù)據(jù)類以及基本操作的概念及相互關(guān)系；抽象數(shù)據(jù)類型型(ATD)的概念和實(shí)現(xiàn)方法，算法的時(shí)間復(fù)雜性的概念和實(shí)現(xiàn)方法，算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。和空間復(fù)雜性分析。 難點(diǎn)難點(diǎn): 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(ATD)的概念和實(shí)現(xiàn)的概念和實(shí)現(xiàn)方法；算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。方法；算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.3 抽象

5、數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4 算法和算法分析算法和算法分析第第1章章 緒論緒論1.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ì) 處理問(wèn)題的策略處理問(wèn)題的策略給出問(wèn)題的數(shù)學(xué)模型給出問(wèn)題的數(shù)學(xué)模型編制出用計(jì)算機(jī)編制出用計(jì)算機(jī)處理問(wèn)題的指令處理問(wèn)題的指令問(wèn)題問(wèn)題構(gòu)建數(shù)學(xué)模型構(gòu)建數(shù)學(xué)模型算法實(shí)現(xiàn)算法實(shí)現(xiàn) 在解決問(wèn)題時(shí)可能遇到的典型的邏輯結(jié)構(gòu)在解決問(wèn)題時(shí)可能遇到的典型的邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）（數(shù)據(jù)結(jié)構(gòu)） 邏輯結(jié)構(gòu)的存儲(chǔ)映象（存儲(chǔ)實(shí)現(xiàn)）邏輯結(jié)構(gòu)的存儲(chǔ)映象（存儲(chǔ)實(shí)現(xiàn)） 數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)。 數(shù)據(jù)結(jié)

6、構(gòu)是一門(mén)討論數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論描述現(xiàn)實(shí)世界實(shí)體的數(shù)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型學(xué)模型(非數(shù)值計(jì)算非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)表示和實(shí)現(xiàn)的學(xué)科。的學(xué)科。 第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇例例1 求求 n 個(gè)整數(shù)中的最大值。個(gè)整數(shù)中的最大值。例例2 交叉路口的紅綠燈管理。交叉路口的紅綠燈管理。例例3 煤氣管道的鋪設(shè)問(wèn)題。煤氣管道的鋪設(shè)問(wèn)題。 說(shuō)明：說(shuō)明： 例子中的例子中的數(shù)學(xué)模型數(shù)學(xué)模型正是數(shù)據(jù)結(jié)構(gòu)要討論的問(wèn)題。正是數(shù)據(jù)結(jié)構(gòu)要討論的問(wèn)題。第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇例例p計(jì)算機(jī)的

7、發(fā)展計(jì)算機(jī)的發(fā)展p數(shù)據(jù)處理的種類數(shù)據(jù)處理的種類p數(shù)據(jù)數(shù)據(jù)數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)數(shù)數(shù) (整數(shù)整數(shù),實(shí)數(shù)實(shí)數(shù)) 字符字符 字符串字符串 文字文字 圖形圖形 圖象圖象 聲音聲音對(duì)客觀對(duì)象的符號(hào)表示對(duì)客觀對(duì)象的符號(hào)表示程序程序原始數(shù)據(jù)原始數(shù)據(jù)結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇軟件軟件 硬件硬件 應(yīng)用領(lǐng)域應(yīng)用領(lǐng)域p 數(shù)值問(wèn)題與非數(shù)值問(wèn)題數(shù)值問(wèn)題與非數(shù)值問(wèn)題 數(shù)值問(wèn)題數(shù)值問(wèn)題 例例1 已知：游泳池的長(zhǎng)已知：游泳池的長(zhǎng)len和寬和寬wide，求面積，求面積area 設(shè)計(jì)設(shè)計(jì) 求解問(wèn)題的方法求解問(wèn)題的方法 編程編程 建模型：建模型： 問(wèn)題涉及的對(duì)

8、象：游泳池的長(zhǎng)問(wèn)題涉及的對(duì)象：游泳池的長(zhǎng)len 寬寬wide，面積，面積area； 對(duì)象之間的關(guān)系：對(duì)象之間的關(guān)系：area=len wide第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇學(xué)號(hào)學(xué)號(hào) 姓名姓名 性別性別 出生日期出生日期 籍貫籍貫 入學(xué)成績(jī)?nèi)雽W(xué)成績(jī) 所在班級(jí)所在班級(jí) 00201 楊潤(rùn)生楊潤(rùn)生 男男 82/06/01 廣州廣州 561 00計(jì)算機(jī)計(jì)算機(jī)200102 石磊石磊 男男 83/12/21 汕頭汕頭 512 00計(jì)算機(jī)計(jì)算機(jī)100202 李梅李梅 女女 83/02/23 陽(yáng)江陽(yáng)江 532 00計(jì)算機(jī)計(jì)算機(jī)200301 馬耀先馬耀先 男男 82/07/1

9、2 廣州廣州 509 00計(jì)算機(jī)計(jì)算機(jī)3非數(shù)值問(wèn)題非數(shù)值問(wèn)題 已知某級(jí)學(xué)生情況已知某級(jí)學(xué)生情況 , 要求分班按入學(xué)成績(jī)排列順序。要求分班按入學(xué)成績(jī)排列順序。說(shuō)明：說(shuō)明： 在此類文檔管理的數(shù)學(xué)模型中在此類文檔管理的數(shù)學(xué)模型中, 計(jì)算機(jī)處理的對(duì)象之間通常計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的線性關(guān)系存在著一種最簡(jiǎn)單的線性關(guān)系 , 該數(shù)學(xué)模型稱為該數(shù)學(xué)模型稱為線性模型線性模型。第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇例例非數(shù)值問(wèn)題非數(shù)值問(wèn)題第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇 下棋程序下棋程序-國(guó)際象棋：國(guó)際象棋： 每次需要考慮的合乎規(guī)

10、則的著法平均只有每次需要考慮的合乎規(guī)則的著法平均只有3535步回合，計(jì)步回合，計(jì)算機(jī)預(yù)先分析算機(jī)預(yù)先分析7 7至至8 8個(gè)回合的著法。若設(shè)為個(gè)回合的著法。若設(shè)為7 7個(gè)回合，則有超過(guò)個(gè)回合，則有超過(guò)1 1億億億個(gè)不同的變化，經(jīng)簡(jiǎn)化后，仍有億億億個(gè)不同的變化，經(jīng)簡(jiǎn)化后，仍有500500億至億至600600億個(gè)變化。億個(gè)變化。多分析一步，增加多分析一步，增加1818億個(gè)變化。億個(gè)變化。根據(jù)計(jì)算機(jī)根據(jù)計(jì)算機(jī)“深藍(lán)深藍(lán)”的速度，的速度，平均平均5 5分鐘走一步。分鐘走一步。算法算法：對(duì)弈的規(guī)則和策略對(duì)弈的規(guī)則和策略棋盤(pán)及棋盤(pán)的格局棋盤(pán)及棋盤(pán)的格局模型模型：根據(jù)計(jì)算機(jī)：根據(jù)計(jì)算機(jī)“深藍(lán)深藍(lán)”的速度的速度

11、例例 迷宮問(wèn)題：迷宮問(wèn)題：在迷宮中，每走到一處，接下來(lái)可走的通路在迷宮中，每走到一處，接下來(lái)可走的通路有三條。計(jì)算機(jī)處理的這類對(duì)象之間通常不存在線性關(guān)有三條。計(jì)算機(jī)處理的這類對(duì)象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過(guò)程中所有可能的通路系。若把從迷宮入口處到出口的過(guò)程中所有可能的通路都畫(huà)出，則可得一棵都畫(huà)出，則可得一棵“樹(shù)樹(shù)”。 入口入口 出口出口第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇例例第第1章章 緒論緒論1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問(wèn)題：對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問(wèn)題：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)

12、據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間的邏輯關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)元素之間的邏輯關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)( (物理結(jié)構(gòu)物理結(jié)構(gòu)) )： 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)存中的表示；數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)存中的表示；數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算 即對(duì)數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的即對(duì)數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的抽象的操作。抽象的操作。1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.3 數(shù)據(jù)結(jié)構(gòu)的分類及表示數(shù)據(jù)結(jié)構(gòu)的分類及表示1.4 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.5 算法和算法分析算法和算法分析 數(shù)據(jù)數(shù)

13、據(jù)：是信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處：是信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。如整數(shù)，實(shí)數(shù)，字符串、圖象、聲音等都是數(shù)據(jù)。理。如整數(shù)，實(shí)數(shù)，字符串、圖象、聲音等都是數(shù)據(jù)。數(shù)據(jù)元素?cái)?shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于：數(shù)據(jù)的基本單位。相當(dāng)于“記錄記錄”, ,在計(jì)算機(jī)程在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理。序中通常作為一個(gè)整體考慮和處理。數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng): : 相當(dāng)于記錄的相當(dāng)于記錄的“域域”或字段或字段, , 是數(shù)據(jù)不可分割的最是數(shù)據(jù)不可分割的最小單位。如學(xué)號(hào)。小單位。如學(xué)號(hào)。數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。如所有班名相同的：性質(zhì)相同的數(shù)據(jù)元素的集合。如所有班名相同的

14、記錄集合。記錄集合。第第1章章 緒論緒論1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)類型數(shù)據(jù)結(jié)構(gòu)類型樹(shù)樹(shù)圖圖第第1章章 緒論緒論1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)之間的相互關(guān)系，是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。即數(shù)據(jù)的組織形式。 線性表線性表?xiàng)ｊ?duì)列隊(duì)列串串?dāng)?shù)組數(shù)組廣義表廣義表數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)：除第一個(gè)元素和最后一個(gè)元素之外，其他元素：除第一個(gè)元素和最后一個(gè)元素之外，其他元素都都有且僅有一個(gè)有且僅有一個(gè)直接前驅(qū)，直接前驅(qū)，有且僅有一個(gè)有且僅有一個(gè)直接后繼；直接后繼；非線性結(jié)構(gòu)非線性結(jié)構(gòu)：其邏輯特征是一個(gè)結(jié)點(diǎn)可能

15、有：其邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)多個(gè)直接前驅(qū)直接前驅(qū)和直接后繼；和直接后繼；第第1章章 緒論緒論1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)p數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 學(xué)號(hào)學(xué)號(hào) 姓名姓名 專業(yè)專業(yè) 政治面藐政治面藐 001 王洪王洪 計(jì)算機(jī)計(jì)算機(jī) 黨員黨員 002 孫文孫文 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 003 謝軍謝軍 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 004 李輝李輝 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 005 沈祥福沈祥福 計(jì)算機(jī)計(jì)算機(jī) 黨員黨員 006 余斌余斌計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 007 鞏力鞏力計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 008 孔令輝孔令輝 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 00100300200400600500800

16、7學(xué)生間學(xué)號(hào)順序關(guān)系學(xué)生間學(xué)號(hào)順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系是一種線性結(jié)構(gòu)關(guān)系第第1章章 緒論緒論學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào)、姓名、專業(yè)、學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào)、姓名、專業(yè)、政治、面貌，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。政治、面貌，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。 1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)例例家族的族譜家族的族譜:假設(shè)某家族有假設(shè)某家族有10個(gè)成員個(gè)成員A， B， C， D， E， F， G， H，I， J，他們之間的血緣關(guān)系可以用如下圖表示。，他們之間的血緣關(guān)系可以用如下圖表示。JIACBDHGFE第第1章章 緒論緒論1.2 基本概念和術(shù)語(yǔ)基本概

17、念和術(shù)語(yǔ)例例順序存儲(chǔ)方法：數(shù)組順序存儲(chǔ)方法：數(shù)組鏈接存儲(chǔ)方法：指針鏈接存儲(chǔ)方法：指針?biāo)饕鎯?chǔ)方法索引存儲(chǔ)方法散列存儲(chǔ)方法散列存儲(chǔ)方法說(shuō)明：說(shuō)明： 同一邏輯結(jié)構(gòu)的不同存儲(chǔ)結(jié)構(gòu)，冠以不同的數(shù)據(jù)結(jié)構(gòu)名同一邏輯結(jié)構(gòu)的不同存儲(chǔ)結(jié)構(gòu)，冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱。如順序表、鏈表、散列表。稱。如順序表、鏈表、散列表。 運(yùn)算不同，數(shù)據(jù)結(jié)構(gòu)也不同。如棧和隊(duì)列。更進(jìn)一步，運(yùn)算不同，數(shù)據(jù)結(jié)構(gòu)也不同。如棧和隊(duì)列。更進(jìn)一步，順順 序棧、鏈棧、順序隊(duì)列、鏈隊(duì)列。序棧、鏈棧、順序隊(duì)列、鏈隊(duì)列。第第1章章 緒論緒論1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)p數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)算法：數(shù)據(jù)運(yùn)算的描述算法：數(shù)據(jù)運(yùn)算的描述數(shù)據(jù)結(jié)構(gòu)：數(shù)

18、據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=程序程序第第1章章 緒論緒論1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4 算法和算法分析算法和算法分析p抽象數(shù)據(jù)型抽象數(shù)據(jù)型Abstract Data Types（ADT）定義定義：抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型和在該模型抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型和在該模型 上定義的操作的集合上定義的操作的集合ADT特點(diǎn)：特點(diǎn)：降低了軟件設(shè)計(jì)的復(fù)雜性；降低了軟件設(shè)計(jì)的復(fù)雜性；提高了程序的可讀性和可維

19、護(hù)性；提高了程序的可讀性和可維護(hù)性；程序的正確性容易保證程序的正確性容易保證第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)在軟件設(shè)計(jì)中，可以對(duì)哪在軟件設(shè)計(jì)中，可以對(duì)哪三種不同的對(duì)象進(jìn)行抽象？三種不同的對(duì)象進(jìn)行抽象？第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)軟件系統(tǒng)軟件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)控制機(jī)能控制機(jī)能操作過(guò)程操作過(guò)程軟件設(shè)計(jì)軟件設(shè)計(jì)抽象抽象軟件設(shè)計(jì)是對(duì)軟件設(shè)計(jì)是對(duì)數(shù)據(jù)抽象、過(guò)程抽象和控制抽象。數(shù)據(jù)抽象、過(guò)程抽象和控制抽象。p抽象數(shù)據(jù)型的規(guī)格描述抽象數(shù)據(jù)型

20、的規(guī)格描述完整性：反映所定義的抽象數(shù)據(jù)型的全部完整性：反映所定義的抽象數(shù)據(jù)型的全部 特征；特征；統(tǒng)一性：前后協(xié)調(diào)，不自相矛盾；統(tǒng)一性：前后協(xié)調(diào)，不自相矛盾；通用性：適用于盡量廣泛的對(duì)象；通用性：適用于盡量廣泛的對(duì)象；不依賴性：不依賴于程序設(shè)計(jì)語(yǔ)言。不依賴性：不依賴于程序設(shè)計(jì)語(yǔ)言。語(yǔ)法：給出操作的名稱、語(yǔ)法：給出操作的名稱、I/OI/O參數(shù)的數(shù)目和類型；參數(shù)的數(shù)目和類型；語(yǔ)義：由一組等式組成，定義各種操作的功能及相互之間的語(yǔ)義：由一組等式組成，定義各種操作的功能及相互之間的關(guān)系；關(guān)系；p規(guī)格描述的兩個(gè)方面規(guī)格描述的兩個(gè)方面: 語(yǔ)法和語(yǔ)義語(yǔ)法和語(yǔ)義第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)

21、現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象描述抽象描述 （高級(jí)語(yǔ)言）編寫(xiě)的程序（高級(jí)語(yǔ)言）編寫(xiě)的程序三條原則：三條原則：符合規(guī)格描述的定義；符合規(guī)格描述的定義；有盡可能好的通用性；有盡可能好的通用性；盡可能獨(dú)立于程序的其它部分盡可能獨(dú)立于程序的其它部分自底向上與自頂向下相結(jié)合、由簡(jiǎn)單到復(fù)雜自底向上與自頂向下相結(jié)合、由簡(jiǎn)單到復(fù)雜第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)p抽象數(shù)據(jù)型的實(shí)現(xiàn)抽象數(shù)據(jù)型的實(shí)現(xiàn)多層次抽象技術(shù)多層次抽象技術(shù)抽象數(shù)據(jù)類型的形式描述抽象數(shù)據(jù)類型的形式描述 DT = ( D，S，P ),其中：其中：D 是數(shù)據(jù)對(duì)象是數(shù)據(jù)對(duì)象; 是是 D 上的關(guān)系集上的關(guān)系集

22、;是是 D 的基本操作集。的基本操作集。第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型和抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型需要通過(guò)高級(jí)編程語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)抽象數(shù)據(jù)類型需要通過(guò)高級(jí)編程語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型（通常稱之謂固有數(shù)據(jù)類型）來(lái)實(shí)現(xiàn)；據(jù)類型（通常稱之謂固有數(shù)據(jù)類型）來(lái)實(shí)現(xiàn)；抽象數(shù)據(jù)類型的實(shí)現(xiàn)包括數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和操作的實(shí)抽象數(shù)據(jù)類型的實(shí)現(xiàn)包括數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和操作的實(shí)現(xiàn)?，F(xiàn)。第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型“復(fù)數(shù)復(fù)數(shù)”的定義為：的定義為：ADT Complex 數(shù)據(jù)對(duì)象：數(shù)

23、據(jù)對(duì)象：D = e1,e2 | e1,e2 RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 = | e1是復(fù)數(shù)的實(shí)部，是復(fù)數(shù)的實(shí)部， e2是復(fù)數(shù)的虛部是復(fù)數(shù)的虛部 其中用兩個(gè)實(shí)數(shù)來(lái)表示復(fù)數(shù)，將復(fù)數(shù)定義為兩個(gè)實(shí)數(shù)的其中用兩個(gè)實(shí)數(shù)來(lái)表示復(fù)數(shù)，將復(fù)數(shù)定義為兩個(gè)實(shí)數(shù)的有序?qū)?，并約定實(shí)部是前驅(qū)，虛部是后繼。有序?qū)?，并約定實(shí)部是前驅(qū)，虛部是后繼。 例例 設(shè)計(jì)函數(shù)設(shè)計(jì)函數(shù) DELEVAL（LIST &L, elementtype d) ，其功能，其功能 為刪除為刪除 L 中所有值為中所有值為 d 的元素。的元素。 Void DELEVAL( LIST &L, elementtype d ) pos

24、ition p ; p = FIRST( L ) ; while ( P != END( L ) ) if ( same( RETRIEVE( p, L ), d ) ) DELETE(p, L ) ; else p = NEXT(p, L ) ; 第第1章章 緒論緒論1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)例例1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4 算法和算法分析算法和算法分析第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析p算法（算法（algorithm）的概

25、念）的概念算法是對(duì)問(wèn)題求解過(guò)程的一種描述，是為解決一個(gè)或算法是對(duì)問(wèn)題求解過(guò)程的一種描述，是為解決一個(gè)或一類問(wèn)題給出的一個(gè)確定的、有限長(zhǎng)的操作序列。嚴(yán)一類問(wèn)題給出的一個(gè)確定的、有限長(zhǎng)的操作序列。嚴(yán)格說(shuō)來(lái)，一個(gè)算法必須滿足以下五個(gè)重要特性格說(shuō)來(lái)，一個(gè)算法必須滿足以下五個(gè)重要特性關(guān)于本書(shū)采用的類語(yǔ)言描述：關(guān)于本書(shū)采用的類語(yǔ)言描述：C 或或 C+自然語(yǔ)言；自然語(yǔ)言；程序設(shè)計(jì)語(yǔ)言；程序設(shè)計(jì)語(yǔ)言；類語(yǔ)言類語(yǔ)言 ；p算法描述算法描述第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析p 算法的基本特征算法的基本特征有窮性：有窮性：算法中的操作步驟為有限個(gè)，且每個(gè)步驟都能在有限算法中的操作步驟為有限個(gè)，且

26、每個(gè)步驟都能在有限時(shí)間內(nèi)完成。時(shí)間內(nèi)完成。確定性：確定性：組成算法的操作必須清晰無(wú)二義性。組成算法的操作必須清晰無(wú)二義性。可行性：可行性：算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。輸入：輸入：作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。些算法的字面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中。量。些算法的字面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中。輸出：輸出：它是一組與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加它是一組與輸入有確定關(guān)系的

27、量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。p在設(shè)計(jì)算法時(shí)通常應(yīng)考慮以下原則在設(shè)計(jì)算法時(shí)通常應(yīng)考慮以下原則算法必須是算法必須是“正確的正確的”l所謂算法是正確的，除了應(yīng)該滿足算法說(shuō)明中寫(xiě)明的所謂算法是正確的，除了應(yīng)該滿足算法說(shuō)明中寫(xiě)明的“功能功能”之外，應(yīng)對(duì)各組典型的帶有苛刻條件的輸入數(shù)據(jù)得出正確的結(jié)之外，應(yīng)對(duì)各組典型的帶有苛刻條件的輸入數(shù)據(jù)得出正確的結(jié)果。果。l在算法是正確的前提下，算法的可讀性是擺在第一位的，這在在算法是正確的前提下，算法的可讀性是擺在第一位的，這在當(dāng)今大型軟件需要多人合作完成的環(huán)境下是換重要的，另一方當(dāng)今大

28、型軟件需要多人合作完成的環(huán)境下是換重要的，另一方面，晦澀難讀的程序易于隱藏錯(cuò)誤而難以調(diào)試。面，晦澀難讀的程序易于隱藏錯(cuò)誤而難以調(diào)試。應(yīng)有很好的應(yīng)有很好的“可讀性可讀性”第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析p在設(shè)計(jì)算法時(shí)通常應(yīng)考慮以下原則在設(shè)計(jì)算法時(shí)通常應(yīng)考慮以下原則必須具有必須具有“健壯性健壯性”l算法的健壯性指的是，算法應(yīng)對(duì)非法輸入的數(shù)據(jù)作出恰當(dāng)算法的健壯性指的是，算法應(yīng)對(duì)非法輸入的數(shù)據(jù)作出恰當(dāng)反映或進(jìn)行相應(yīng)處理，一般情況下，應(yīng)向調(diào)用它的函數(shù)返反映或進(jìn)行相應(yīng)處理，一般情況下，應(yīng)向調(diào)用它的函數(shù)返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值。回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值。算法的效率算法的效率

29、l應(yīng)考慮所設(shè)計(jì)的算法具有應(yīng)考慮所設(shè)計(jì)的算法具有“高效率與低存儲(chǔ)量高效率與低存儲(chǔ)量”。高效率。高效率與低存儲(chǔ)量是矛盾的，要視具體問(wèn)題而定。與低存儲(chǔ)量是矛盾的，要視具體問(wèn)題而定。第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析p影響時(shí)間特性的四個(gè)因素影響時(shí)間特性的四個(gè)因素 定義定義 語(yǔ)句頻度語(yǔ)句頻度：語(yǔ)句重復(fù)執(zhí)行的次數(shù)：語(yǔ)句重復(fù)執(zhí)行的次數(shù)第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析 程序運(yùn)行時(shí)輸入數(shù)據(jù)的總量程序運(yùn)行時(shí)輸入數(shù)據(jù)的總量; 對(duì)源程序編譯所需的時(shí)間對(duì)源程序編譯所需的時(shí)間; 計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間; 程序中指令重復(fù)執(zhí)行的次數(shù)。程序中指令重

30、復(fù)執(zhí)行的次數(shù)。所有算法均以函數(shù)形式給出所有算法均以函數(shù)形式給出, , 算法的輸入數(shù)據(jù)來(lái)自參數(shù)表；算法的輸入數(shù)據(jù)來(lái)自參數(shù)表；參數(shù)表的參數(shù)在算法之前均進(jìn)行類型說(shuō)明；參數(shù)表的參數(shù)在算法之前均進(jìn)行類型說(shuō)明；有關(guān)結(jié)點(diǎn)結(jié)構(gòu)的類型定義有關(guān)結(jié)點(diǎn)結(jié)構(gòu)的類型定義, ,以及全局變量的說(shuō)明等均在算法以及全局變量的說(shuō)明等均在算法之前進(jìn)行說(shuō)明之前進(jìn)行說(shuō)明p描述算法的書(shū)寫(xiě)規(guī)則描述算法的書(shū)寫(xiě)規(guī)則第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析p 評(píng)價(jià)算法標(biāo)準(zhǔn)評(píng)價(jià)算法標(biāo)準(zhǔn)本課程采用以求解問(wèn)題的基本操作（原操作）的執(zhí)行次數(shù)本課程采用以求解問(wèn)題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量。作為算法時(shí)間的度量。 O(n3) 稱為矩陣相乘算法時(shí)間復(fù)雜度；稱為矩陣相乘算法時(shí)間復(fù)雜度； O(n3)表示矩陣相乘算法執(zhí)行時(shí)間與表示矩陣相乘算法執(zhí)行時(shí)間與n3成正比成正比, 即即O（n3）與）與n3 同一數(shù)量級(jí)；同一數(shù)量級(jí)； n 階矩陣相乘的算法階矩陣相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1;