數(shù)據(jù)結(jié)構(gòu)第一章緒論P(yáng)PT

1、ABCDEFG10086510說在課程學(xué)習(xí)之前說在課程學(xué)習(xí)之前q為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法？為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法？q課程基本信息課程基本信息q學(xué)習(xí)目的與考核形式學(xué)習(xí)目的與考核形式為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法？為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法？n算法：計(jì)算機(jī)解決具體問題的步驟：算法：計(jì)算機(jī)解決具體問題的步驟：n從具體問題中抽象出數(shù)學(xué)模型從具體問題中抽象出數(shù)學(xué)模型數(shù)據(jù)表示數(shù)據(jù)表示（數(shù)據(jù)數(shù)據(jù)是是計(jì)算機(jī)化的信息，是計(jì)算機(jī)的處理對(duì)象）計(jì)算機(jī)化的信息，是計(jì)算機(jī)的處理對(duì)象）n設(shè)計(jì)或選擇一個(gè)解此數(shù)學(xué)模型的算法設(shè)計(jì)或選擇一個(gè)解此數(shù)學(xué)模型的算法數(shù)據(jù)處理數(shù)據(jù)處理n編程、運(yùn)行編程、運(yùn)行n計(jì)算機(jī)問題分為兩類：計(jì)算機(jī)問題分為兩類：

2、n數(shù)值計(jì)算：數(shù)學(xué)模型可以用數(shù)學(xué)方程式描述，重點(diǎn)在數(shù)值計(jì)算：數(shù)學(xué)模型可以用數(shù)學(xué)方程式描述，重點(diǎn)在算法設(shè)計(jì)的研究；算法設(shè)計(jì)的研究；n非數(shù)值計(jì)算：數(shù)學(xué)模型無法用數(shù)學(xué)方程式描述，需研非數(shù)值計(jì)算：數(shù)學(xué)模型無法用數(shù)學(xué)方程式描述，需研究究數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)間的相互關(guān)系。n算法數(shù)據(jù)結(jié)構(gòu)程序算法數(shù)據(jù)結(jié)構(gòu)程序?yàn)槭裁磳W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？n目的：培養(yǎng)數(shù)據(jù)抽象能力目的：培養(yǎng)數(shù)據(jù)抽象能力n幫助程序員（更有效地）組織數(shù)據(jù)、設(shè)計(jì)（高幫助程序員（更有效地）組織數(shù)據(jù)、設(shè)計(jì)（高效的）算法、完成（高質(zhì)量的）程序效的）算法、完成（高質(zhì)量的）程序n要求：獲得算法及數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)

3、知識(shí)和要求：獲得算法及數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)和技能；進(jìn)行復(fù)雜程序設(shè)計(jì)訓(xùn)練技能；進(jìn)行復(fù)雜程序設(shè)計(jì)訓(xùn)練n分析數(shù)據(jù)結(jié)構(gòu)特性，為應(yīng)用選擇適當(dāng)數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)特性，為應(yīng)用選擇適當(dāng)數(shù)據(jù)結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時(shí)間分析和空間分及相應(yīng)算法，初步掌握算法時(shí)間分析和空間分析技術(shù)析技術(shù)n完成的程序結(jié)構(gòu)清楚、正確易讀、符合規(guī)范完成的程序結(jié)構(gòu)清楚、正確易讀、符合規(guī)范n地位：專業(yè)基礎(chǔ)課地位：專業(yè)基礎(chǔ)課n計(jì)算機(jī)類和管理科學(xué)與工程類專業(yè)的核心課程計(jì)算機(jī)類和管理科學(xué)與工程類專業(yè)的核心課程之一之一學(xué)時(shí)數(shù)：學(xué)時(shí)數(shù)：64（+16） 教教 材：材：嚴(yán)蔚敏等嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社語言版），清華大學(xué)

4、出版社參考書：參考書：1算法導(dǎo)論（第算法導(dǎo)論（第2版），版），Cormen等，機(jī)械工業(yè)出版社等，機(jī)械工業(yè)出版社2計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（第計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（第3版）（版）（Vol.1-3），），D. E. Knuth，清華大學(xué)出版社，清華大學(xué)出版社3 高一凡，高一凡，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析算法實(shí)現(xiàn)及解析(第二版第二版)西安電子西安電子科技大學(xué)出版社科技大學(xué)出版社4 唐發(fā)根，唐發(fā)根，數(shù)據(jù)結(jié)構(gòu)教程數(shù)據(jù)結(jié)構(gòu)教程，北京航空航天大學(xué)出版社，北京航空航天大學(xué)出版社，2005年年5月，第月，第2版版5王玲主編，王玲主編，數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程，四川大學(xué)出版社，四川大學(xué)出版社，2002年年學(xué)習(xí)

5、目的與考核形式學(xué)習(xí)目的與考核形式n課程學(xué)習(xí)目的課程學(xué)習(xí)目的n掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、機(jī)內(nèi)表示、處理掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、機(jī)內(nèi)表示、處理數(shù)據(jù)的算法設(shè)計(jì)，以及算法分析；數(shù)據(jù)的算法設(shè)計(jì)，以及算法分析；n 組織、處理數(shù)據(jù)的理論和方法，建立良好的編程組織、處理數(shù)據(jù)的理論和方法，建立良好的編程風(fēng)格；風(fēng)格；n培養(yǎng)數(shù)據(jù)分析的抽象能力。培養(yǎng)數(shù)據(jù)分析的抽象能力。n課程考核形式課程考核形式n平時(shí)成績(jī)平時(shí)成績(jī)(作業(yè)、課堂考勤筆記、隨堂測(cè)驗(yàn)作業(yè)、課堂考勤筆記、隨堂測(cè)驗(yàn)、半、半期考試期考試等等)計(jì)入課堂成績(jī)計(jì)入課堂成績(jī)n實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)成績(jī)（上機(jī)）（上機(jī)）占總成績(jī)的占總成績(jī)的40%n期末成績(jī)（閉卷期末成績(jī)（閉卷+課

6、堂課堂）占總成績(jī)的）占總成績(jī)的60%第第1章章 緒論緒論q1.1 基本概念與術(shù)語基本概念與術(shù)語q1.2 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)q1.3 算法和算法分析算法和算法分析教學(xué)目標(biāo)教學(xué)目標(biāo)n了解非數(shù)值問題的數(shù)學(xué)模型不是數(shù)學(xué)方程，而是了解非數(shù)值問題的數(shù)學(xué)模型不是數(shù)學(xué)方程，而是表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。n理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)和數(shù)理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型等的定義。掌握數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)據(jù)類型等的定義。掌握數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其種類；算法的重要特征等。構(gòu)及其種類；算法的重要特征等。n熟悉類熟悉類C語言的書寫

7、規(guī)范，特別注意參數(shù)的區(qū)別，語言的書寫規(guī)范，特別注意參數(shù)的區(qū)別，輸入輸出的方式和錯(cuò)誤處理方式，以及抽象數(shù)據(jù)輸入輸出的方式和錯(cuò)誤處理方式，以及抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。類型的表示和實(shí)現(xiàn)。n會(huì)根據(jù)語句頻度估算算法的時(shí)間復(fù)雜度。會(huì)根據(jù)語句頻度估算算法的時(shí)間復(fù)雜度。 n教學(xué)重點(diǎn)及難點(diǎn)教學(xué)重點(diǎn)及難點(diǎn)n數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)n抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)n類類C語言描述算法與程序?qū)崿F(xiàn)語言描述算法與程序?qū)崿F(xiàn)n算法的時(shí)間復(fù)雜度分析算法的時(shí)間復(fù)雜度分析n教學(xué)方法教學(xué)方法n任務(wù)驅(qū)動(dòng)式任務(wù)驅(qū)動(dòng)式n課堂講解（多媒體課件板書）課堂講解（多媒體課件板書）n數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)教學(xué)平臺(tái)數(shù)

8、據(jù)結(jié)構(gòu)網(wǎng)絡(luò)教學(xué)平臺(tái)n教學(xué)內(nèi)容教學(xué)內(nèi)容n什么是數(shù)據(jù)結(jié)構(gòu)，為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)，為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)n基本概念和術(shù)語基本概念和術(shù)語n抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)n算法和算法分析算法和算法分析n算法的五個(gè)基本特征算法的五個(gè)基本特征n算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求n算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析1.1 基本概念與術(shù)語基本概念與術(shù)語q1.1.1 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象q1.1.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)q1.1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型1. 1.1數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)

9、項(xiàng)、數(shù)據(jù)對(duì)象n數(shù)據(jù)數(shù)據(jù)（data)：所有能輸入到計(jì)算機(jī)中進(jìn)行加工處理的：所有能輸入到計(jì)算機(jī)中進(jìn)行加工處理的對(duì)象；數(shù)值、字符、表格、圖象、動(dòng)畫、音對(duì)象；數(shù)值、字符、表格、圖象、動(dòng)畫、音/視頻視頻 etc.n數(shù)據(jù)元素?cái)?shù)據(jù)元素（data element）：組成數(shù)據(jù)的）：組成數(shù)據(jù)的基本單位基本單位，是，是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為整體進(jìn)行處理。數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為整體進(jìn)行處理。也稱也稱結(jié)點(diǎn)結(jié)點(diǎn)（node）或或記錄記錄（record）；）；n數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)（data item）：）：有獨(dú)立含義的數(shù)據(jù)有獨(dú)立含義的數(shù)據(jù)最小單位最小單位，也稱項(xiàng)，也稱項(xiàng)或或字段字段(field)；數(shù)據(jù)對(duì)象數(shù)

10、據(jù)對(duì)象(data object)：性質(zhì)相同性質(zhì)相同的數(shù)據(jù)元素的的數(shù)據(jù)元素的集合集合，是數(shù)據(jù)的一個(gè)子集。例如：是數(shù)據(jù)的一個(gè)子集。例如：1.1.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Data Structure）是相互之間存在一種）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，指的是數(shù)據(jù)或多種特定關(guān)系的數(shù)據(jù)元素的集合，指的是數(shù)據(jù)元素之間的相互關(guān)系，是數(shù)據(jù)的組織形式。元素之間的相互關(guān)系，是數(shù)據(jù)的組織形式。n例如例如：n數(shù)據(jù)結(jié)構(gòu)包含如下三個(gè)方面的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)包含如下三個(gè)方面的內(nèi)容：n1：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) （logic structure）n獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的。獨(dú)立于計(jì)

11、算機(jī)，是數(shù)據(jù)本身所固有的。n2：數(shù)據(jù)的存儲(chǔ)物理結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)物理結(jié)構(gòu)（storagephysical structure)n是邏輯結(jié)構(gòu)在計(jì)算機(jī)存貯器中的映像，必須依賴于計(jì)算是邏輯結(jié)構(gòu)在計(jì)算機(jī)存貯器中的映像，必須依賴于計(jì)算機(jī)。機(jī)。n3：數(shù)據(jù)的操作運(yùn)算數(shù)據(jù)的操作運(yùn)算（operation）n 指所施加的一組操作總稱。操作的定義直接依賴于邏指所施加的一組操作總稱。操作的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必依賴于存貯結(jié)構(gòu)。輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必依賴于存貯結(jié)構(gòu)。登錄號(hào)登錄號(hào)書名書名作者作者分類號(hào)分類號(hào)001高等數(shù)學(xué)高等數(shù)學(xué)樊應(yīng)川樊應(yīng)川S01002理論力學(xué)理論力學(xué)羅遠(yuǎn)祥羅遠(yuǎn)祥L(zhǎng)01003高等數(shù)學(xué)高等數(shù)學(xué)華

12、羅庚華羅庚S01004線性代數(shù)線性代數(shù)欒汝書欒汝書S02線性結(jié)構(gòu)線性結(jié)構(gòu)數(shù)據(jù)的操作數(shù)據(jù)的操作：建立、插入、刪除、查找等：建立、插入、刪除、查找等應(yīng)用實(shí)例應(yīng)用實(shí)例1 1：書目檢索自動(dòng)化問題書目檢索自動(dòng)化問題應(yīng)用實(shí)例應(yīng)用實(shí)例2 2： 智力游戲智力游戲樹型結(jié)構(gòu)樹型結(jié)構(gòu)應(yīng)用實(shí)例應(yīng)用實(shí)例3 3：交通運(yùn)輸問題交通運(yùn)輸問題圖結(jié)圖結(jié)構(gòu)構(gòu)n以上例子的解決，都不是數(shù)值計(jì)算問題。描述這類非以上例子的解決，都不是數(shù)值計(jì)算問題。描述這類非數(shù)值問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、數(shù)值問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。n因此簡(jiǎn)單說來，因此簡(jiǎn)單說來，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是

13、一門研究非數(shù)值計(jì)算的程是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)中計(jì)算機(jī)的序設(shè)計(jì)中計(jì)算機(jī)的操作對(duì)象操作對(duì)象以及它們之間的以及它們之間的關(guān)系關(guān)系和和操操作作等的學(xué)科。等的學(xué)科。n主要研究：主要研究： n 數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)-數(shù)據(jù)關(guān)系之間的邏輯關(guān)系數(shù)據(jù)關(guān)系之間的邏輯關(guān)系 n 數(shù)據(jù)的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)-數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示示 n 操作算法操作算法-插入、刪除、修改、查詢、排序等插入、刪除、修改、查詢、排序等小小的總結(jié)小小的總結(jié)n邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：n設(shè)有一個(gè)表設(shè)有一個(gè)表(a1,a2,a3,a4,a5)，它的抽象描述可表示為：，它的抽象描述可表示為：Line（D，

14、S） 其中：其中：Da1,a2,a3,a4,a5，D表示數(shù)據(jù)元素的有限集表示數(shù)據(jù)元素的有限集 S,， S表示表示D 上關(guān)系的有限集上關(guān)系的有限集 則：它的邏輯關(guān)系圖示如下：則：它的邏輯關(guān)系圖示如下：a1a2a3a4a5線性結(jié)構(gòu)線性結(jié)構(gòu)n應(yīng)用實(shí)例應(yīng)用實(shí)例4: 工廠的組織管理。工廠的組織管理。n設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的抽象描述為設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的抽象描述為:Tree（D，S）其中：其中：D r,a,b,c,d,e,f,g,h, S , ,則：則：它的邏輯關(guān)系圖示如下：它的邏輯關(guān)系圖示如下：rabcdefgh樹型結(jié)構(gòu)樹型結(jié)構(gòu) 應(yīng)用實(shí)例應(yīng)用實(shí)例5：田徑賽的時(shí)間安排問題：田徑賽的時(shí)間安排問題： 設(shè)有六個(gè)比賽項(xiàng)目，

15、規(guī)定每個(gè)選手至多可參設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。內(nèi)完成比賽。 （1 1）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目： 跳高跳高 跳遠(yuǎn)跳遠(yuǎn) 標(biāo)槍標(biāo)槍 鉛球鉛球 100 100米米 200 200米米 A B A B C D E C D E F F （2 2）用頂點(diǎn)代表比賽項(xiàng)目用頂點(diǎn)代表比賽項(xiàng)目 不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。 （3 3）某選

16、手比賽的項(xiàng)目有邊相連）某選手比賽的項(xiàng)目有邊相連, ,則不能同時(shí)比賽則不能同時(shí)比賽。 -田徑賽的時(shí)間安排問題解法姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一 A B E馬二 C D 張三 C E F李四 D F A劉五 B FAEBFDC比賽比賽時(shí)間時(shí)間比賽比賽項(xiàng)目項(xiàng)目1A，C2B，D3E4F 只需安排四個(gè)單位時(shí)間進(jìn)行比賽 一般來說，根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特性，通常有一般來說，根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特性，通常有如下如下4類基本結(jié)構(gòu)：類基本結(jié)構(gòu)：（集合）（集合）線性結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)圖狀結(jié)構(gòu) 在集合結(jié)構(gòu)中的數(shù)據(jù)元素之間僅存在在集合結(jié)構(gòu)中的數(shù)據(jù)元素之間僅存在“同屬于一同屬于一個(gè)集合個(gè)集合

17、”的關(guān)系。如下圖所示。的關(guān)系。如下圖所示。 (1)(1)集合集合集合結(jié)構(gòu)集合結(jié)構(gòu) 元素之間是一一對(duì)應(yīng)的關(guān)系，首元素?zé)o前趨，元素之間是一一對(duì)應(yīng)的關(guān)系，首元素?zé)o前趨，尾元素?zé)o后繼，其他元素都只有一個(gè)前驅(qū)和后繼。尾元素?zé)o后繼，其他元素都只有一個(gè)前驅(qū)和后繼。1234(2)(2)線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)例如：例如： Linear=(D,R) D=1,2,3,4 R=, 元素之間存在一對(duì)多的關(guān)系，其中只有一個(gè)元素沒元素之間存在一對(duì)多的關(guān)系，其中只有一個(gè)元素沒有前驅(qū)，稱為根。其他元素只有一個(gè)前驅(qū)，但可以有多有前驅(qū)，稱為根。其他元素只有一個(gè)前驅(qū)，但可以有多個(gè)后繼。個(gè)后繼。abcdef(3)(3)樹形結(jié)

18、構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)例如：例如： Tree=(D,R) D=a,b,c,d,e,f R=, 在圖狀結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有多個(gè)前驅(qū)和任意個(gè)后在圖狀結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有多個(gè)前驅(qū)和任意個(gè)后繼。元素之間存在多對(duì)多的關(guān)系，任何元素之間都可以繼。元素之間存在多對(duì)多的關(guān)系，任何元素之間都可以存在關(guān)系。存在關(guān)系。3124(4)(4)圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)樹和圖也樹和圖也稱為非線稱為非線性結(jié)構(gòu)性結(jié)構(gòu)例如：例如： Graph=(D,R) D=1,2,3,4 R=,n形式定義：數(shù)據(jù)的邏輯結(jié)構(gòu)可用二元組形式定義：數(shù)據(jù)的邏輯結(jié)構(gòu)可用二元組nData Structure（D，S）的形式來描述。其中：）的形式來描述。其中

19、：nD a1,a2,an為元素集合；為元素集合；nS r1,r2,rm為關(guān)系的集合。為關(guān)系的集合。集 合線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)一般線性表線性表推廣特殊線性表樹型結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)線性表?xiàng)：完?duì)列串?dāng)?shù)組廣義表樹二叉樹有向圖無向圖數(shù)據(jù)的邏輯數(shù)據(jù)的邏輯結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)算法設(shè)計(jì) 邏輯結(jié)構(gòu)算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來表示 數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù) 元素間的邏輯關(guān)系索引存貯結(jié)構(gòu)散列存貯結(jié)構(gòu)元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存

20、儲(chǔ)內(nèi)容Loc(元素元素i)=Lo + (i-1)*m1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存儲(chǔ)地址存儲(chǔ)地址 存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容 指針指針 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346h 應(yīng)用實(shí)例應(yīng)用實(shí)例6 6：電話號(hào)碼查詢問題：電話號(hào)碼查詢問題： 設(shè)有一個(gè)電話號(hào)碼薄，它記錄了設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N N個(gè)人的名字和個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假

21、定按如下形式安排：其相應(yīng)的電話號(hào)碼，假定按如下形式安排： ( (a a1 1，b b1 1)(a)(a2 2，b b2 2) )(a(an n，b bn n) ) 其中其中a ai i，b bi i(i=1(i=1，2 2n) n) 分別表示某人的名字分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼，要求設(shè)計(jì)一個(gè)算法，當(dāng)給定和對(duì)應(yīng)的電話號(hào)碼，要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒有這個(gè)人，電話號(hào)碼，如果該電話簿中根本就沒有這個(gè)人，則該算法也能夠給出沒有這個(gè)人的報(bào)告。則該算法也能夠給出沒有這個(gè)人的報(bào)告。n算法

22、的設(shè)計(jì)，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式。算法的設(shè)計(jì)，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式。電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找（算法電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找（算法）的效率。）的效率。n可將電話號(hào)碼設(shè)計(jì)成：可將電話號(hào)碼設(shè)計(jì)成： （1）按順序存儲(chǔ)）按順序存儲(chǔ)方式方式：須遍歷表：須遍歷表 （2）按姓氏索引）按姓氏索引方式方式：索引：索引順序存儲(chǔ)，順序查找順序存儲(chǔ)，順序查找姓名姓名電話號(hào)碼電話號(hào)碼李李113912345678張張113645678901李李2張張2王王1田田2姓名姓名電話號(hào)碼電話號(hào)碼李113912345678李2張113645678901張2王1王2姓姓存儲(chǔ)地址存儲(chǔ)地址李張1.1.3

23、 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n常用運(yùn)算：新建、撤銷、插入、刪除、修改、常用運(yùn)算：新建、撤銷、插入、刪除、修改、查詢、排序等，這些運(yùn)算的實(shí)現(xiàn)離不開具體查詢、排序等，這些運(yùn)算的實(shí)現(xiàn)離不開具體的語言。的語言。n數(shù)據(jù)類型（數(shù)據(jù)類型（Data Type）n一組性質(zhì)相同的值的集合以及定義于這個(gè)值集合一組性質(zhì)相同的值的集合以及定義于這個(gè)值集合上的一組操作的總稱。上的一組操作的總稱。n例如，在例如，在C語言中提供的數(shù)據(jù)類型：語言中提供的數(shù)據(jù)類型： nint, char, float, double等等原子類型原子類型n以以int為例：為例：n32768到到32767中的整數(shù)值構(gòu)成的集合中的整數(shù)值構(gòu)成的集合n一組

24、操作（加、減、乘、除、乘方等）一組操作（加、減、乘、除、乘方等）1.1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n數(shù)組、結(jié)構(gòu)體、共用體、枚舉等數(shù)組、結(jié)構(gòu)體、共用體、枚舉等結(jié)構(gòu)類型結(jié)構(gòu)類型，n還有指針、空還有指針、空(void)類型等，類型等，n用戶也可用用戶也可用typedef 自己定義數(shù)據(jù)類型自己定義數(shù)據(jù)類型。typedef int integer; typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p;1.1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n為了不影響算法的設(shè)計(jì)，避免具體的程序設(shè)計(jì)語言，更為了不影響

25、算法的設(shè)計(jì)，避免具體的程序設(shè)計(jì)語言，更好的描述數(shù)據(jù)結(jié)構(gòu)，我們采用抽象數(shù)據(jù)類型好的描述數(shù)據(jù)結(jié)構(gòu)，我們采用抽象數(shù)據(jù)類型n抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 （Abstract Data Type） n指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作n表示方法表示方法n格式格式1：三元組的形式（：三元組的形式（D，S，P）n格式格式2： ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：基本操作：基本操作： ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名1.1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 （ADT）的不同視角）的不同視角 1.2

26、應(yīng)用舉例應(yīng)用舉例-ADT Triplet（P9）ADT Triplet 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：De1,e2,e3| e1,e2,e3ElemSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R, 基本操作：基本操作： InitTriplet(&T,v1,v2,v3) DestroyTriplet(&T) Put(&T, i ,e) Get(T, i ,&e) IsAscending(T) IsDescending(T) Max(T,&e) Min(T,&e) ADT Triplet數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容注意：用注意：用ADTADT來理解數(shù)據(jù)來理解數(shù)據(jù)的邏輯

27、結(jié)構(gòu)和操作的邏輯結(jié)構(gòu)和操作1.3 算法與算法分析算法與算法分析q1.3.1 算法的基本概念算法的基本概念q1.3.2 算法描述算法描述q1.3.3 算法分析算法分析1.3.1 算法的基本概念算法的基本概念n算法（算法（algorithm）n解決某一特定問題的解決某一特定問題的具體步驟的描述具體步驟的描述，是指令的，是指令的有窮序列。有窮序列。n算法特性算法特性n有窮性有窮性n確定性確定性n可行性可行性n可有輸入可有輸入n必有輸出必有輸出算法的不同直接影響著程序的執(zhí)行效率算法的不同直接影響著程序的執(zhí)行效率n問題：求問題：求20000以內(nèi)的完全平方數(shù)。以內(nèi)的完全平方數(shù)。n算法一：將算法一：將200

28、00以內(nèi)的數(shù)逐一判斷。以內(nèi)的數(shù)逐一判斷。n算法二：將算法二：將1n的數(shù)逐一平方后輸出，直到的數(shù)逐一平方后輸出，直到n*n超過超過20000。n算法三：用遞推公式。算法三：用遞推公式。 f(n+1)=f(n)+2*n+1補(bǔ)充：利用補(bǔ)充：利用timeb函數(shù)計(jì)算程序段運(yùn)行的時(shí)間函數(shù)計(jì)算程序段運(yùn)行的時(shí)間ntimeb的定義：的定義：struct _timeb time_t time; unsigned short millitm; short timezone, dstflag; time是從是從UTC時(shí)間時(shí)間1970年年1月月1日午夜日午夜(00:00:00)起累計(jì)起累計(jì)的秒數(shù)；的秒數(shù)； millit

29、m是一秒內(nèi)的毫秒數(shù)是一秒內(nèi)的毫秒數(shù) dstflag不為不為0，說明這是夏令時(shí)時(shí)間，說明這是夏令時(shí)時(shí)間 timezone是是UTC時(shí)間和本地時(shí)間的相差分鐘數(shù)時(shí)間和本地時(shí)間的相差分鐘數(shù) 補(bǔ)充：利用補(bǔ)充：利用timeb函數(shù)計(jì)算程序段運(yùn)行的時(shí)間函數(shù)計(jì)算程序段運(yùn)行的時(shí)間n例如：例如：n#includen#includen void main() n struct timeb t1,t2;n int n=1,f;n ftime(&t1); /* 求得當(dāng)前時(shí)間求得當(dāng)前時(shí)間 */n for(f=1;f=20000; n+)n printf(“%d ”,f); f=f+2*n+1;n ftime(&am

30、p;t2); /* 求得當(dāng)前時(shí)間求得當(dāng)前時(shí)間 */n t=(t2.time-t1.time)*1000+(litm); /* 計(jì)算時(shí)間差計(jì)算時(shí)間差 */n printf(sum=%lf 用時(shí)用時(shí)%ld毫秒毫秒n,sum,t);n 1.3.2 算法描述算法描述n1.用流程圖描述算法用流程圖描述算法n一個(gè)算法可以用流程圖的方式來描述，輸入輸出、判一個(gè)算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高流向。這是一種描述算法的較好方法，目前

31、在一些高級(jí)語言程序設(shè)計(jì)中仍然采用。級(jí)語言程序設(shè)計(jì)中仍然采用。n2.用自然語言描述算法用自然語言描述算法n用我們?nèi)粘Ｉ钪械淖匀徽Z言（可以是中文形式，也用我們?nèi)粘Ｉ钪械淖匀徽Z言（可以是中文形式，也可以是英形式）也可以描述算法?？梢允怯⑿问剑┮部梢悦枋鏊惴?。 n3.用其它方式描述算法用其它方式描述算法n我們還可以用數(shù)學(xué)語言或約定的符號(hào)語言來描述算法。我們還可以用數(shù)學(xué)語言或約定的符號(hào)語言來描述算法。1.3.2 算法描述算法描述n4.用類用類C描述算法描述算法n（1）所有算法的描述都用）所有算法的描述都用C中的函數(shù)形式中的函數(shù)形式 函數(shù)類型函數(shù)類型 函數(shù)名（形參及類型說明）函數(shù)名（形參及類型說明）

32、函數(shù)語句部分函數(shù)語句部分 return(表達(dá)式值表達(dá)式值)； n（2）函數(shù)中的形式參數(shù)有兩種傳值方式）函數(shù)中的形式參數(shù)有兩種傳值方式n若為一般變量名，則為單向傳值；若為一般變量名，則為單向傳值；n若在變量前面增加若在變量前面增加“&“符號(hào)，則為雙向傳地址符號(hào)，則為雙向傳地址（借用（借用C+的引用參數(shù)）。的引用參數(shù)）。類類C語言描述算法的符號(hào)約定語言描述算法的符號(hào)約定（1）預(yù)定義的常量和類型）預(yù)定義的常量和類型n/函數(shù)結(jié)果狀態(tài)碼函數(shù)結(jié)果狀態(tài)碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE

33、 1#define OVERFLOW 2n/Status 函數(shù)的類型函數(shù)的類型typedef int Status;數(shù)據(jù)元素類型為數(shù)據(jù)元素類型為ElemType例如：例如：抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)的表示和實(shí)現(xiàn)nStatus Get(Triplet T,int i,ElemType &e)n/*用用e返回返回T的第的第i個(gè)元的值個(gè)元的值.*/nif (i3) return ERROR;ne=Ti-1;nreturn OK;nnStatus Put(Triplet& T,int i,ElemType e)n/*用用e修改的第修改的第i個(gè)元的值個(gè)元的值.*/

34、nif (i3) return ERROR;nTi-1=e;nreturn OK;n 1.3.3 算法的評(píng)價(jià)算法的評(píng)價(jià)n本課程的目的就是要對(duì)特定的問題，按照具體要本課程的目的就是要對(duì)特定的問題，按照具體要求，設(shè)計(jì)出較好的算法。求，設(shè)計(jì)出較好的算法。n算法的評(píng)價(jià)算法的評(píng)價(jià)衡量算法優(yōu)劣的標(biāo)準(zhǔn)衡量算法優(yōu)劣的標(biāo)準(zhǔn)n正確性正確性(correctness)n可讀性可讀性(readability)n健壯性健壯性(robustness)n高效率與低存儲(chǔ)量高效率與低存儲(chǔ)量n時(shí)間復(fù)雜度（計(jì)算復(fù)雜度）時(shí)間復(fù)雜度（計(jì)算復(fù)雜度）算法運(yùn)行時(shí)間算法運(yùn)行時(shí)間的相對(duì)量度。的相對(duì)量度。n空間復(fù)雜度空間復(fù)雜度算法運(yùn)行中臨時(shí)占用空間

35、大小算法運(yùn)行中臨時(shí)占用空間大小的量度。的量度。1.3.3 算法的評(píng)價(jià)算法的評(píng)價(jià)n一、時(shí)間復(fù)雜度一、時(shí)間復(fù)雜度n1 語句頻度語句頻度n一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測(cè)試才能知道。的，必須上機(jī)運(yùn)行測(cè)試才能知道。n算法運(yùn)行時(shí)間大致等于計(jì)算機(jī)執(zhí)行一個(gè)簡(jiǎn)單操作的時(shí)算法運(yùn)行時(shí)間大致等于計(jì)算機(jī)執(zhí)行一個(gè)簡(jiǎn)單操作的時(shí)間與算法所包含簡(jiǎn)單操作次數(shù)之積。即：間與算法所包含簡(jiǎn)單操作次數(shù)之積。即：一個(gè)算法花一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。法

36、中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。n一個(gè)算法中的基本語句的執(zhí)行次數(shù)稱為一個(gè)算法中的基本語句的執(zhí)行次數(shù)稱為語句頻度語句頻度或時(shí)或時(shí)間頻度。間頻度。n例：計(jì)算如下程序段中例：計(jì)算如下程序段中+x；的語句頻度。；的語句頻度。程序程序+x；for(i=0;i=n;i+) +x；for(i=2;i=n;i+) for(j=1;j=n;j+) +x；for(i=2;i=n;i+) for(j=2;j=i-1;j+) +x；語句頻度語句頻度1n+1n(n-1)(1)(2)2nn-1.3.3 算法的評(píng)價(jià)算法的評(píng)價(jià)n2.漸近時(shí)間復(fù)雜度漸近時(shí)間復(fù)雜度n實(shí)際上算法的時(shí)間復(fù)雜度只需大致算出相應(yīng)數(shù)量級(jí)實(shí)際上算法的時(shí)間復(fù)

37、雜度只需大致算出相應(yīng)數(shù)量級(jí)（Order）就可以）就可以,稱為漸近時(shí)間復(fù)雜度，一般地我們簡(jiǎn)稱稱為漸近時(shí)間復(fù)雜度，一般地我們簡(jiǎn)稱為為時(shí)間復(fù)雜度時(shí)間復(fù)雜度。 記作：記作： T(n)O(f (n) )3n+2=O(n) / 因?yàn)橐驗(yàn)?3n+2 4n for n 26*2n+n2=O(2n) /因?yàn)橐驗(yàn)?*2n+n2 7*2n for n 4例如：例如：漸進(jìn)符號(hào)（漸進(jìn)符號(hào)（ O ）的定義：）的定義：當(dāng)且僅當(dāng)存在一個(gè)正的當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)常數(shù) C，使得對(duì)所有的，使得對(duì)所有的 n n0 ，有有 f(n) Cg(n)，則：則： f(n) = O (g(n)解：該算法的運(yùn)行時(shí)間由程序中所有語句的解：該算法

38、的運(yùn)行時(shí)間由程序中所有語句的頻度頻度（即（即該語句重復(fù)執(zhí)行的次數(shù)）該語句重復(fù)執(zhí)行的次數(shù)）之和之和構(gòu)成。構(gòu)成。分析：分析：顯然，語句的頻度是顯然，語句的頻度是1。設(shè)語句。設(shè)語句的頻度是的頻度是f(n)，則有：則有：2f(n) n算法的時(shí)間復(fù)雜度由算法的時(shí)間復(fù)雜度由嵌套最深層語句的頻度嵌套最深層語句的頻度決定決定例如：分析以下程序段的時(shí)間復(fù)雜度。例如：分析以下程序段的時(shí)間復(fù)雜度。i=1; while(i=n) i=i*2; 即即f(n)log2n，取最大值取最大值f(n)=log2n所以該程序段的時(shí)間復(fù)雜度所以該程序段的時(shí)間復(fù)雜度T(n)=1+f(n)=1+ log2n= O( log2n)1.3

39、.3 算法的評(píng)價(jià)算法的評(píng)價(jià)n算法時(shí)間復(fù)雜度的評(píng)價(jià)算法時(shí)間復(fù)雜度的評(píng)價(jià)n情況情況1： n例：設(shè)例：設(shè)n為正整數(shù)，根據(jù)基本操作的語句頻度計(jì)為正整數(shù)，根據(jù)基本操作的語句頻度計(jì)算下列程序段的時(shí)間復(fù)雜度。算下列程序段的時(shí)間復(fù)雜度。for (i=1;i=n ;i+) for (j=1;j=n;j+)cij=0;for (k=1;k=1 & change;-i) change=FALSE; for(j=1;jaj+1) aj aj+1; change=TRUE; / bubble_sort 1.3.3 算法的評(píng)價(jià)算法的評(píng)價(jià)語句頻度語句頻度最好情況最好情況0最壞情況最壞情況平均情況平均情況時(shí)間復(fù)雜度時(shí)間復(fù)雜度0(1)0(1)O(nO(n2 2) )O(nO(n2 2) )(1)2n n -(1)4n n -1.3.3 算法的評(píng)價(jià)算法的評(píng)價(jià)n按數(shù)量級(jí)遞增排列依