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

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

2、數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實用教程（第二版）數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實用教程（第二版），徐孝凱，徐孝凱，清華大學出版社清華大學出版社 2003算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)C語言描述語言描述，張乃孝等，高等教育出版，張乃孝等，高等教育出版社，社，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.參考書目參考書目 第第1章章 緒論緒論 第第2章章 線性表線性表 第第3章章 棧和隊列棧和隊列 第第4章章 串串 第第5章章 數(shù)組和廣義表數(shù)組和廣義表 第第6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖 第第8章章 查找查找 第第9章章 排序排序本課程的教學內(nèi)容本課程的教學內(nèi)容1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 抽象數(shù)據(jù)類型

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

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

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

7、發(fā)展計算機的發(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ù)據(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ù)值問題與非數(shù)值問題數(shù)值問題與非數(shù)值問題 數(shù)值問題數(shù)值問題 例例1 已知：游泳池的長已知：游泳池的長len和寬和寬wide，求面積，求面積area 設(shè)計設(shè)計 求解問題的方法求解問題的方法 編程編程 建模型：建模型： 問題涉及的對

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

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

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

11、例例 迷宮問題：迷宮問題：在迷宮中，每走到一處，接下來可走的通路在迷宮中，每走到一處，接下來可走的通路有三條。計算機處理的這類對象之間通常不存在線性關(guān)有三條。計算機處理的這類對象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過程中所有可能的通路系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵都畫出，則可得一棵“樹樹”。 入口入口 出口出口第第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)及其討論范疇對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：數(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ù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)( (物理結(jié)構(gòu)物理結(jié)構(gòu)) )： 數(shù)據(jù)元素及其關(guān)系在計算機內(nèi)存中的表示；數(shù)據(jù)元素及其關(guān)系在計算機內(nèi)存中的表示；數(shù)據(jù)的運算數(shù)據(jù)的運算 即對數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的即對數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的抽象的操作。抽象的操作。1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 數(shù)據(jù)結(jié)構(gòu)的分類及表示數(shù)據(jù)結(jié)構(gòu)的分類及表示1.4 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)1.5 算法和算法分析算法和算法分析 數(shù)據(jù)數(shù)

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

14、記錄集合。記錄集合。第第1章章 緒論緒論1.2 基本概念和術(shù)語基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)類型數(shù)據(jù)結(jié)構(gòu)類型樹樹圖圖第第1章章 緒論緒論1.2 基本概念和術(shù)語基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)之間的相互關(guān)系，是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。即數(shù)據(jù)的組織形式。 線性表線性表棧棧隊列隊列串串數(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)：除第一個元素和最后一個元素之外，其他元素：除第一個元素和最后一個元素之外，其他元素都都有且僅有一個有且僅有一個直接前驅(qū)，直接前驅(qū)，有且僅有一個有且僅有一個直接后繼；直接后繼；非線性結(jié)構(gòu)非線性結(jié)構(gòu)：其邏輯特征是一個結(jié)點可能

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

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

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

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

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

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

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

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

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

24、; 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ù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)例例1.1 數(shù)據(jù)結(jié)構(gòu)及其討論范疇數(shù)據(jù)結(jié)構(gòu)及其討論范疇1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4 算法和算法分析算法和算法分析第第1章章 緒論緒論1.4 算法與算法分析算法與算法分析p算法（算法（algorithm）的概念）的概念算法是

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

26、限時間內(nèi)完成。時間內(nèi)完成。確定性：確定性：組成算法的操作必須清晰無二義性。組成算法的操作必須清晰無二義性?？尚行裕嚎尚行裕核惴ㄖ械乃胁僮鞫急仨氉銐蚧?，都可以通過已經(jīng)算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。實現(xiàn)的基本操作運算有限次實現(xiàn)之。輸入：輸入：作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。些算法的字面上可以沒有輸入，實際上已被嵌入算法之中。量。些算法的字面上可以沒有輸入，實際上已被嵌入算法之中。輸出：輸出：它是一組與輸入有確定關(guān)系的量值，是算法進行信息加它是一組與輸入有確定關(guān)系的量值，是算法進行

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

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

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

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