1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)12 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程在國外是從作為一門獨立的課程在國外是從1 1968968年開始設(shè)立的。年開始設(shè)立的。 1968 1968年美國唐年美國唐歐歐克努特教授開克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系。創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系。了解該課程：了解該課程： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在軟件工程學(xué)科中是一門綜合性的專業(yè)在軟件工程學(xué)科中是一門綜合性的專業(yè)基礎(chǔ)課，是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三基礎(chǔ)課，是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程。者之間的一門核心課程。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計（特別是非數(shù)值性程不僅是一般程序設(shè)計（特別是非數(shù)值性程序設(shè)計）的基礎(chǔ)，

2、而且是設(shè)計和實現(xiàn)編譯程序、操序設(shè)計）的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。了解該課程：了解該課程：n課程地位課程地位:數(shù)據(jù)結(jié)構(gòu)是軟件工程學(xué)科的核心課程，是一門綜合性的專業(yè)技術(shù)基礎(chǔ)課。3n課程目的課程目的： 掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型、提高閱讀、編寫算法的能力、能針對給定問題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計和分析算法。n先修課程先修課程：C程序設(shè)計4“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”所所處的地位處的地位了解該課程：了解該課程：5 編譯技術(shù)要使用棧、散列表及語法樹操作系統(tǒng)中用隊列、存儲管理表及目錄樹數(shù)據(jù)庫系統(tǒng)運用線性表、多鏈表、

3、及索引樹 增強(qiáng)求解復(fù)雜問題的能力 6軟件工程專業(yè)的專業(yè)基礎(chǔ)課程，是后續(xù)專業(yè)課程學(xué)軟件工程專業(yè)的專業(yè)基礎(chǔ)課程，是后續(xù)專業(yè)課程學(xué)習(xí)的必要知識與技能準(zhǔn)備。習(xí)的必要知識與技能準(zhǔn)備。n程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法（瑞士著名計算機(jī)科學(xué)算法（瑞士著名計算機(jī)科學(xué)家家N.Wirth教授提出）。教授提出）。78例例1 1 求兩個學(xué)生某門課成績之和。求兩個學(xué)生某門課成績之和。 例例2 2 某班某一門課程成績統(tǒng)計。某班某一門課程成績統(tǒng)計。 例例3 3 某班某幾門課程成績統(tǒng)計。某班某幾門課程成績統(tǒng)計。9 例例4 4 某班學(xué)生信息處理。學(xué)生信息包括：學(xué)號、姓某班學(xué)生信息處理。學(xué)生信息包括：學(xué)號、姓名、成績名、成績1

4、1、成績、成績2 2等。等。q例例5 5 書目自動檢索系統(tǒng)書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表登錄號按分類號q例例6 6 人機(jī)對奕問題人機(jī)對奕問題樹. 設(shè)某田徑比賽共有設(shè)某田徑比賽共有六六個比賽項目，規(guī)定每個選手個比賽項目，規(guī)定每個選手至多可參加至多可參加三三個項目，有個項目，

5、有五五人報名參加比賽（如下表人報名參加比賽（如下表所示）。設(shè)計比賽日程表，使得比賽能在盡可能短的所示）。設(shè)計比賽日程表，使得比賽能在盡可能短的時間內(nèi)完成。時間內(nèi)完成。例例7 7 田徑比賽的時間安排問題田徑比賽的時間安排問題 （1 1）設(shè)用如下六個不同的代號代表不同的項目：）設(shè)用如下六個不同的代號代表不同的項目： （2 2）用頂點代表比賽項目）用頂點代表比賽項目 （3 3）在）在不能同時進(jìn)行比賽不能同時進(jìn)行比賽的頂點之間連上一條邊的頂點之間連上一條邊 （4 4）給頂點涂色：任何有邊相連的頂點不能涂）給頂點涂色：任何有邊相連的頂點不能涂 同一種顏色，且使涂色數(shù)目盡量少同一種顏色，且使涂色數(shù)目盡量少

6、姓名姓名項目項目1 1項目項目2 2項目項目3 3丁一丁一 A B E趙二趙二 C D 張三張三 C E F李四李四 D F A王五王五 B FAEBFDC比賽時間比賽項目1A，C2B，D3E4F 只需安排四個單位時間進(jìn)行比賽AEBFDC圖151617n上課認(rèn)真聽課，記筆記，課后按時獨立上課認(rèn)真聽課，記筆記，課后按時獨立完成作業(yè)。完成作業(yè)。n理論、習(xí)題、上機(jī)緊密結(jié)合。理論、習(xí)題、上機(jī)緊密結(jié)合。n成績評定：成績評定： 平時平時15%+15%+實驗實驗15%+15%+期末考試期末考試70%70%18第第1章章 緒論緒論 1.1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語的基本概念和術(shù)語 1.2 什么是數(shù)據(jù)結(jié)構(gòu)

7、什么是數(shù)據(jù)結(jié)構(gòu) 1.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容的研究內(nèi)容 1.4 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的表示與實現(xiàn)的表示與實現(xiàn) 1.5 算法和算法分析算法和算法分析191.1 1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語1 1、數(shù)據(jù)、數(shù)據(jù)：？：？2 2、數(shù)據(jù)元素、數(shù)據(jù)元素：？：？3 3、數(shù)據(jù)項、數(shù)據(jù)項：？：？4 4、數(shù)據(jù)對象、數(shù)據(jù)對象：？：？1、數(shù)據(jù)、數(shù)據(jù):描述客觀事物的描述客觀事物的數(shù)字?jǐn)?shù)字、字符字符以及所有能輸入到計以及所有能輸入到計算機(jī)中并被計算機(jī)程序處理的算機(jī)中并被計算機(jī)程序處理的符號符號的總稱。的總稱。（數(shù)字、字符、聲音、圖形、圖像等）（數(shù)字、字符、聲音、圖形、圖像等）例子：數(shù)值

8、數(shù)據(jù)。學(xué)號姓名語文數(shù)學(xué)C語言6201001張三8554926201002李四9284646201003王五8774736201004 . 例子：圖像、聲音等。2、數(shù)據(jù)元素、數(shù)據(jù)元素:是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。可以小到一個字符，也可以大到一本書或一張地圖。對于較大的數(shù)據(jù)元素，還可以進(jìn)一步分成若干個“數(shù)據(jù)項”。3、數(shù)據(jù)項數(shù)據(jù)項:多個數(shù)據(jù)項可組成一個數(shù)據(jù)元素，數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。例子：4、數(shù)據(jù)對象、數(shù)據(jù)對象:是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例子：例子： 整數(shù)數(shù)據(jù)對象整數(shù)數(shù)據(jù)對象 N=0，+-1，+-2， 字母字符數(shù)據(jù)對象字母字符數(shù)據(jù)對

9、象C=A，B，Z 全班學(xué)生的成績表全班學(xué)生的成績表G=（6201001，張三，張三，85，54，92），）， （6201002，李四，李四，92，84，64），）， 例：有一張學(xué)生成績表如下：例：有一張學(xué)生成績表如下：學(xué)號學(xué)號姓名姓名JAVA離散數(shù)學(xué)離散數(shù)學(xué)物理物理高數(shù)高數(shù)1121010304林智敏林智敏989290971121010314武鑫武鑫908990951121010133楊志勇楊志勇908490911121010306李賽李賽9083908223數(shù)據(jù)元素：一條學(xué)生成績記錄（數(shù)據(jù)元素：一條學(xué)生成績記錄（1121010304，林智敏，林智敏，98，92,90,97）。）。數(shù)據(jù)項：數(shù)據(jù)項

10、： 1121010304是該數(shù)據(jù)元素的數(shù)據(jù)項。是該數(shù)據(jù)元素的數(shù)據(jù)項。數(shù)據(jù)對象：數(shù)據(jù)對象：11210A01班學(xué)生的成績記錄。班學(xué)生的成績記錄。數(shù)據(jù)：全體數(shù)據(jù)：全體11級學(xué)生的成績記錄。級學(xué)生的成績記錄。1.2 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)24數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)元素之間不是相互獨立的，它們之間數(shù)據(jù)元素之間不是相互獨立的，它們之間有某種特定的關(guān)系，這種數(shù)據(jù)元素之間的有某種特定的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系，稱為關(guān)系，稱為“結(jié)構(gòu)結(jié)構(gòu)” 結(jié)構(gòu)結(jié)構(gòu) = = 實體實體+ +關(guān)系關(guān)系形式定義：形式定義：二元組二元組 (D,S) (D,

11、S) 其中其中D D是數(shù)據(jù)元素的是數(shù)據(jù)元素的有限有限集集，S S是是D D上上關(guān)系關(guān)系的有限集。的有限集。例如，可以用三個 4 位的十進(jìn)制數(shù)表示一個含 12 位數(shù)的十進(jìn)制數(shù)。3214,6587,9345 a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序”關(guān)系: a1,a2、a2,a33214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如:例：例：在在一維數(shù)組一維數(shù)組 a1, a2, a3, a4, a5, a6 的的 6 個數(shù)據(jù)元個數(shù)據(jù)元素之間存在如下的素之間存在如下的次序關(guān)系次序關(guān)系:| i=

12、1, 2, 3, 4, 5 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。的數(shù)據(jù)元素的集合。可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”例：在計算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：例：在計算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：n復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)n Complex=(C,R)n其中，C是含兩個實數(shù)的集合c1,c2nR=P,其中P是定義在集合C上的一種關(guān)系P=,n其中，有序偶表示c1是復(fù)數(shù)的實部，c2是復(fù)數(shù)的虛部。27281 1、數(shù)據(jù)的邏輯結(jié)構(gòu)：、數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)元素之間的邏輯關(guān)系集合集合：元素僅屬于同一個集體，沒有其他關(guān)：元素僅屬于同一個集體，

13、沒有其他關(guān)系。系。線性結(jié)構(gòu)：存在一對一關(guān)系，序列相鄰，次序關(guān)系。線性結(jié)構(gòu)：存在一對一關(guān)系，序列相鄰，次序關(guān)系。樹型結(jié)構(gòu)：存在一對多關(guān)系，層次關(guān)系。樹型結(jié)構(gòu)：存在一對多關(guān)系，層次關(guān)系。圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：存在多對多關(guān)系，任意性。圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）：存在多對多關(guān)系，任意性。29練習(xí)練習(xí):n設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），n其中D= d1,d2,d3,d4,nR=r,r=,n按照圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。30d1d2d3d431v是邏輯結(jié)構(gòu)到存儲器的一個映射。是邏輯結(jié)構(gòu)到存儲器的一個映射。2 2、數(shù)據(jù)的物理結(jié)構(gòu)、數(shù)據(jù)的物理結(jié)構(gòu)/ /存儲結(jié)構(gòu)存儲結(jié)構(gòu)v存儲器模型：一個存儲器存儲器模型：一個存儲器

14、M M是一系列固定大小的是一系列固定大小的存儲單元，每個單元存儲單元，每個單元U U有一個唯一的地址有一個唯一的地址A(U)A(U)，該地址被連續(xù)地編碼。每個單元該地址被連續(xù)地編碼。每個單元U U有一個唯一的有一個唯一的后繼單元后繼單元 U=succ(U) U=succ(U) 兩種主要存儲結(jié)構(gòu)：兩種主要存儲結(jié)構(gòu)：順序存儲順序存儲鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?2 順序存儲順序存儲結(jié)構(gòu)：借助元素在存儲器的相對位置結(jié)構(gòu)：借助元素在存儲器的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系來表示數(shù)據(jù)元素之間的邏輯關(guān)系, ,即邏輯上相鄰的數(shù)即邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中。據(jù)元素存儲在物理上相鄰的存儲單元中。

15、鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Y(jié)構(gòu)：不要求將邏輯上相鄰的數(shù)據(jù)元結(jié)構(gòu)：不要求將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中，而是通過附加素存儲在物理上相鄰的存儲單元中，而是通過附加指針字段來表示數(shù)據(jù)元素之間的邏輯關(guān)系。指針字段來表示數(shù)據(jù)元素之間的邏輯關(guān)系。a0a1a2a3例子：例子：表示復(fù)數(shù)表示復(fù)數(shù)z1=3.0-2.3i和和z2=-0.7+4.8i03000302063206343.0-2.3-0.74.80415061106133.00415-2.3算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu) 在在不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描述方法述方法。

16、當(dāng)當(dāng)用高級程序設(shè)計語言進(jìn)行編程時，通常用高級程序設(shè)計語言進(jìn)行編程時，通常可用高級編程語言中提供的數(shù)據(jù)類型描述之。可用高級編程語言中提供的數(shù)據(jù)類型描述之。存儲結(jié)構(gòu)的描述：typedef structfloat realPart;float * imaginaryPart;Complex; typedef structfloat realPart;float imaginaryPart;Complex; 351.4 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)數(shù)據(jù)類型：數(shù)據(jù)類型： 具有相同性質(zhì)的計算機(jī)數(shù)據(jù)的集合及定義在這個數(shù)據(jù)集合具有相同性質(zhì)的計算機(jī)數(shù)據(jù)的集合及定義在這個數(shù)據(jù)集合上的一組操作的

17、總稱。上的一組操作的總稱。 例如：在例如：在C C語言中，整數(shù)類型是集合語言中，整數(shù)類型是集合Z=0Z=0，+ +1 1，+ +2 2 及定及定義在在該集合上的加，減，乘，除等一組操作。有簡單類型義在在該集合上的加，減，乘，除等一組操作。有簡單類型和結(jié)構(gòu)類型（如數(shù)據(jù)、結(jié)構(gòu)體和結(jié)構(gòu)類型（如數(shù)據(jù)、結(jié)構(gòu)體)； 在計算機(jī)中，數(shù)據(jù)類型的概念并非只局限于高級語言中，在計算機(jī)中，數(shù)據(jù)類型的概念并非只局限于高級語言中，每個處理器（廣義的處理器，包括計算機(jī)的硬件系統(tǒng)和軟件每個處理器（廣義的處理器，包括計算機(jī)的硬件系統(tǒng)和軟件系統(tǒng)）都提供了一組原子類型或結(jié)構(gòu)類型。例如：計算機(jī)硬系統(tǒng)）都提供了一組原子類型或結(jié)構(gòu)類型。

18、例如：計算機(jī)硬件系統(tǒng)通常含有件系統(tǒng)通常含有“位位”，“字節(jié)字節(jié)”，“字字”等原子類型。等原子類型。n抽象數(shù)據(jù)類型定義：是指基于一個邏輯類型的數(shù)據(jù)抽象數(shù)據(jù)類型定義：是指基于一個邏輯類型的數(shù)據(jù)模型模型以以及定義在該模型上的一組及定義在該模型上的一組操作操作。每一個操作由它的輸入和。每一個操作由它的輸入和輸出定義。輸出定義。 可以用三元組可以用三元組 (D,S,P)(D,S,P)表示，其中表示，其中D D是數(shù)據(jù)元素的是數(shù)據(jù)元素的有限集有限集，S S是是D D上上關(guān)系關(guān)系的有限集的有限集,P,P是對是對D D的基本操作集。的基本操作集。n抽象的與具體的相對應(yīng)，范疇更廣，不再局限于前述各處抽象的與具體的

19、相對應(yīng)，范疇更廣，不再局限于前述各處理器中已定義并實現(xiàn)的具體數(shù)據(jù)類型，還包括用戶在設(shè)計理器中已定義并實現(xiàn)的具體數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。 361.4 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的定義格式：抽象數(shù)據(jù)類型的定義格式：nADT抽象數(shù)據(jù)類型名n數(shù)據(jù)對象：n數(shù)據(jù)關(guān)系：n基本操作：nADT抽象的數(shù)據(jù)類型名n基本操作的定義格式：基本操作的定義格式：n基本操作名（參數(shù)表）n初始條件：n操作結(jié)果：37例題： 設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“三元組 （Triplet）” 。每個三元組由任意三個實數(shù)的序列構(gòu)成，基本操作包括：創(chuàng)建一個

20、三元組，取三元組的任意一個分量，置三元組的任意一個分量，求三元組的最大分量，求三元組的最小分量，顯示三元組，銷毀三元組等。要求：（1）寫出抽象數(shù)據(jù)類型的定義，即數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作（2）用結(jié)構(gòu)體封裝需要定義的數(shù)據(jù)類型，如定義三元組ADT時，首先用結(jié)構(gòu)體封裝“三元組”的三個分量。并利用typedef對結(jié)構(gòu)體重新命名。（3）完成基本操作的C語言實現(xiàn)與調(diào)用38三元組三元組Triplet的定義的定義ADT Triplet數(shù)據(jù)對象：D = e1,e2,e3 | e1,e2,e3屬于Elemset (定義了關(guān)系的某個集合)數(shù)據(jù)關(guān)系：R1 = | 基本操作：initTriplet(&T,v1

21、,v2,v3)初始條件：操作結(jié)果：構(gòu)造三元組T，元素e1，e2和e3分別被賦予參數(shù)v1,v2,v3的值。 39DestroyTriplet(&T)初始條件：三元組T已經(jīng)存在。操作結(jié)果：銷毀三元組T。 getElem(T,i,&e)初始條件：三元組T已經(jīng)存在，1=i=3.操作結(jié)果：用e返回三元組T的第i個元素。 putElem(&T,i,e)初始條件：三元組T已經(jīng)存在，1=i=3.操作結(jié)果：用e值取代三元組T的第i個元素。 40三元組三元組Triplet的定義的定義IsAscending(T)初始條件：三元組T已經(jīng)存在。操作結(jié)果：如果三元組T的三個元素按升序排列，則返回T

22、RUE；否則返回FALSE。 IsDescending(T)初始條件：三元組T已經(jīng)存在。操作結(jié)果：如果三元組T的三個元素按降序排列，則返回TRUE，否則返回FALSE。41三元組三元組Triplet的定義的定義getMax(T,&e)初始條件：三元組T已經(jīng)存在。操作結(jié)果：用e返回T的3個元素中的最大值。 getMin(T,&e)初始條件：三元組T已經(jīng)存在。操作結(jié)果：用e返回T的3個元素中的最小值。ADT Triplet42三元組三元組Triplet的定義的定義#include#define OK 1#define ERROR 0typedef int Status;/三元組的類

23、型先定義為float,可以隨時變換成別的類型 typedef float ElemType;typedef structElemType e3;Triplet; 43三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/三元組的初始化Status initTriplet(Triplet &T,ElemType v0,ElemType v1,ElemType v2)T.e0=v0;T.e1=v1;T.e2=v2;return OK;44三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/銷毀三元組,靜態(tài)存儲是在程序開始的時候就分配固定的內(nèi)存單元，整個程序結(jié)束后自動釋放存儲單元，不需銷毀 /

24、而動態(tài)存儲單元在程序運行初不分配內(nèi)存單元在用到時才分配，而當(dāng)用過后需要用語句釋放該內(nèi)存空間Status destroyTriplet(Triplet &T)return OK;45三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/用e獲取T的第i(13)個元素的值， Status getElem(Triplet T,int i,ElemType &e)if(i3)return ERROR;else e=T.ei-1;return OK;46三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/置T的第i元的值為e Status putElem(Triplet &T,in

25、t i,ElemType e)if(i3)return ERROR;else T.ei-1=e;return OK;47三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/如果T的三個元素按升序排列，則返回1，否則返回0Status isAscending(Triplet T)return (T.e0=T.e1)&(T.e1=T.e1)&(T.e1=T.e2); 48三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/用e返回指向T的最大元素的值ElemType getMax(Triplet T,ElemType &e)if(T.e0T.e1) e=T.e0; else

26、 e=T.e1; if(T.e2e) e=T.e2; return e; 49三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/用e返回指向T的最小元素的值ElemType getMin(Triplet T,ElemType &e)if(T.e0T.e1) e=T.e0; else e=T.e1; if(T.e2e) e=T.e2; return e; 50三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)/測試程序int main()Triplet T;Status flag;ElemType v0,v1,v2,e;printf(請進(jìn)入三元組的三個值v0,v1,v2:n); sca

27、nf(%f,%f,%f,&v0,&v1,&v2);flag=initTriplet(T,v0,v1,v2);51三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)printf(“調(diào)用初始化函數(shù)后，flag=%d,T的三個值為%4.2f,%4.2f,%4.2fn,flag,T.e0,T.e1,T.e2);if(isAscending(T)printf(該三元組元素為升序n);if(isDescending(T)printf(該三元組元素為降序n);printf(該三元組中的最大值為：%4.2f,最小值為：%4.2f,getMax(T,e),getMin(T,e);retu

28、rn OK; 52三元組三元組Triplet的表示和實現(xiàn)的表示和實現(xiàn)531.4 算法和算法分析算法和算法分析1. 1. 算法算法 定義：指一系列定義：指一系列確定確定的而且是在的而且是在有限有限步驟內(nèi)步驟內(nèi) 能完成的操作。能完成的操作。2. 2. 算法的重要特性算法的重要特性 (1) (1) 有窮性有窮性 ：能執(zhí)行結(jié)束：能執(zhí)行結(jié)束 (2) (2) 確定性確定性 ：對于相同的輸入執(zhí)行相同的路徑：對于相同的輸入執(zhí)行相同的路徑 (3) 0(3) 0至多個至多個輸入輸入 (4) 1(4) 1至多個至多個輸出輸出 (5) (5) 有效性有效性( (可行性可行性) ) （用于描述算法的操作都（用于描述算法

29、的操作都是足夠基本的）是足夠基本的）542. 2. 算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系n計算機(jī)科學(xué)家沃斯（計算機(jī)科學(xué)家沃斯（N.WirthN.Wirth）提出的）提出的: :“算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) = = 程序程序”n一個算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的；反之，一個算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的；反之，算法不確定，就無法決定如何構(gòu)造數(shù)據(jù)。算法不確定，就無法決定如何構(gòu)造數(shù)據(jù)。55算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系舉例算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系舉例例：編寫程序查詢某人的電話號碼例：編寫程序查詢某人的電話號碼 建立一張登記表，存放建立一張登記表，存放2 2個數(shù)據(jù)項：個數(shù)據(jù)項： 姓名姓名 + TEL+ TE

30、L 好的算法取決于這張表的結(jié)構(gòu)及存儲方式：好的算法取決于這張表的結(jié)構(gòu)及存儲方式：v將表中結(jié)點將表中結(jié)點按照姓名順序按照姓名順序地存儲在計算機(jī)中，依次地存儲在計算機(jī)中，依次查找，效率太低。查找，效率太低。v建立一張建立一張姓氏索引表姓氏索引表：姓：姓+ +該姓在表中的起始地址該姓在表中的起始地址則不需查找其他姓氏，查找效率得到提高。則不需查找其他姓氏，查找效率得到提高。563. 算法設(shè)計的要求算法設(shè)計的要求（1 1）正確性正確性 四層含義：四層含義： a.a.無語法錯誤；無語法錯誤； b.b.一般輸入得出一般輸入得出滿足規(guī)格說明要求的結(jié)果；滿足規(guī)格說明要求的結(jié)果；c.c.邊界、苛刻數(shù)據(jù)能產(chǎn)邊界、

31、苛刻數(shù)據(jù)能產(chǎn)生滿足規(guī)格說明要求的結(jié)果；生滿足規(guī)格說明要求的結(jié)果；d.d.一切合法輸入都能一切合法輸入都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果產(chǎn)生滿足規(guī)格說明要求的結(jié)果 。（2 2）可讀性可讀性 首先是給人讀，然后才是機(jī)器執(zhí)行。首先是給人讀，然后才是機(jī)器執(zhí)行。（3 3）健壯性健壯性 容錯性容錯性（4 4）效率與低存儲量需求效率與低存儲量需求57算法的效率算法的效率n定義：一個算法如果能在所要求的資源限制內(nèi)將定義：一個算法如果能在所要求的資源限制內(nèi)將問題解決好，則稱這個算法是問題解決好，則稱這個算法是有效率有效率的。的。 例如，一個資源限制是：可用來存儲數(shù)據(jù)的例如，一個資源限制是：可用來存儲數(shù)據(jù)的全部空間全

32、部空間可能是分離的內(nèi)存空間限制和磁盤可能是分離的內(nèi)存空間限制和磁盤空間限制以及允許執(zhí)行每一個子任務(wù)所需要的時空間限制以及允許執(zhí)行每一個子任務(wù)所需要的時間。間。584 . 算法的分析算法的分析 算法性能的評價算法性能的評價n 評價標(biāo)準(zhǔn)：評價標(biāo)準(zhǔn)： 1 1）算法所需的）算法所需的計算時間計算時間 2 2）算法所需的）算法所需的存儲空間存儲空間 3 3）算法的）算法的簡單性簡單性n 度量算法執(zhí)行時間的兩種方法度量算法執(zhí)行時間的兩種方法 1 1）事后統(tǒng)計法）事后統(tǒng)計法 此方法有兩個缺陷：此方法有兩個缺陷： i i. .必須先運行依據(jù)算法編制的程序；必須先運行依據(jù)算法編制的程序； ii.ii.二是所得時

33、間的統(tǒng)計量依賴于計算機(jī)的硬件、二是所得時間的統(tǒng)計量依賴于計算機(jī)的硬件、軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)劣。軟件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)劣。592 2）事前分析估算法）事前分析估算法 此方法取決于多個因素：此方法取決于多個因素： i i. . 算法選用的策略算法選用的策略; ; ii. ii. 問題的規(guī)模問題的規(guī)模; ; iii. iii. 書寫程序的語言書寫程序的語言; ; iv. iv. 編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量; ; v. v. 機(jī)器執(zhí)行指令的速度。機(jī)器執(zhí)行指令的速度。605 . 時間復(fù)雜度時間復(fù)雜度（1）引例）引例 （a） +x;

34、s=0； +x 的頻度為的頻度為1 （b） for (i=1; i=n; +i) +x; s+=x; +x的頻度為的頻度為n （c） for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x; +x的頻度為的頻度為n2 615 . 時間復(fù)雜度時間復(fù)雜度（2 2）定義：）定義： 一般情況下，算法中一般情況下，算法中基本操作基本操作重復(fù)執(zhí)行重復(fù)執(zhí)行的時間是的時間是問題規(guī)模問題規(guī)模n n的某個函數(shù)的某個函數(shù)f(n)f(n)，算法的時間量度記作，算法的時間量度記作 T(n) = O(f(n) “T(n) = O(f(n) “大大O O記法記法” ” 它表示隨問題規(guī)模它表示隨

35、問題規(guī)模n n的增大，算法執(zhí)行時間的的增大，算法執(zhí)行時間的增長率和增長率和f(n)f(n)的增長率相同，稱作算法的漸進(jìn)時間的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱復(fù)雜度，簡稱時間復(fù)雜度時間復(fù)雜度。n語句的頻度：該語句重復(fù)執(zhí)行的次數(shù)。語句的頻度：該語句重復(fù)執(zhí)行的次數(shù)。62時間復(fù)雜度和算法運行時間的關(guān)系表 T(n) nO(logn) O(n)O(nlogn) O(n2 )O(n3 )O(n5 )O(2n )O(n!)204.3us20us86.4us400us8ms3.2s1.05s771世紀(jì)405.340213160064ms1.7min12.7天2.59*1032世紀(jì)605.9603543

36、600216ms13min366世紀(jì)2.64*1066世紀(jì)63結(jié)論結(jié)論（1 1）當(dāng)）當(dāng)f(n)f(n)為對數(shù)函數(shù)、冪函數(shù)、或它們的乘積時，為對數(shù)函數(shù)、冪函數(shù)、或它們的乘積時，算法的運行時間是算法的運行時間是可以接受可以接受的，稱這些算法是有效的，稱這些算法是有效算法；當(dāng)算法；當(dāng)f(n)f(n)為指數(shù)函數(shù)或階乘函數(shù)時，算法的運為指數(shù)函數(shù)或階乘函數(shù)時，算法的運行時間是行時間是不可接受不可接受的，稱這些算法是無效的算法。的，稱這些算法是無效的算法。（2 2）隨著）隨著n n值的增大，增長速度各不相同，值的增大，增長速度各不相同，n n足夠大時，足夠大時，存在下列關(guān)系：存在下列關(guān)系：對數(shù)函數(shù)對數(shù)函數(shù)

37、冪函數(shù)冪函數(shù) 指數(shù)函數(shù)指數(shù)函數(shù)64常見函數(shù)的增長率常見函數(shù)的增長率 O(1) O(1) 常量階，與常量階，與n n無關(guān)無關(guān) O(O(lognlogn) ) lognlogn階階 O(n) nO(n) n階階 O(O(nlognnlogn) ) nlognnlogn階階 O(nO(n2 2) ) 平方階平方階 O(nO(n3 3) ) 立方階立方階 O(2O(2n n) ) 指數(shù)階指數(shù)階n增長率由慢到快增長率由慢到快n盡量少用指數(shù)階的算法盡量少用指數(shù)階的算法65666. 6. 空間復(fù)雜度空間復(fù)雜度（1 1）存儲算法本身所占用的空間）存儲算法本身所占用的空間（2 2）算法的輸入）算法的輸入/ /輸

38、出數(shù)據(jù)占用的空間輸出數(shù)據(jù)占用的空間（3 3）算法在運行過程中臨時占用的輔助空間）算法在運行過程中臨時占用的輔助空間n原地工作：若輔助空間相對于輸入數(shù)據(jù)量是常數(shù)，原地工作：若輔助空間相對于輸入數(shù)據(jù)量是常數(shù)，則稱此算法是原地工作。則稱此算法是原地工作。n若所占空間量依賴于特定的輸入，按最壞情況來若所占空間量依賴于特定的輸入，按最壞情況來分析。分析。67簡單例子簡單例子nO(1)Temp=i; i=j; j=temp; 以上三條單個語句的頻度均為以上三條單個語句的頻度均為1 1，該程序段的執(zhí)行，該程序段的執(zhí)行時間是一個與問題規(guī)模時間是一個與問題規(guī)模n n無關(guān)的常數(shù)。無關(guān)的常數(shù)。n算法的時間復(fù)雜度為常

39、數(shù)階，記作算法的時間復(fù)雜度為常數(shù)階，記作T(n)=T(n)=o(1)(1)。n如果算法的執(zhí)行時間不隨著問題規(guī)模如果算法的執(zhí)行時間不隨著問題規(guī)模n n的增加而增的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是 o(1)(1)。68nO(n2)n sum=0； （1次） for(i=1;i=n;i+) （n次 ） for(j=1;j=n;j+) sum+； （n2次） 解：解：T(n)=2n2+n+1 =O(n2)69解：解： 語句1的頻度是n-1 語句2的頻度是(n-

40、1)*(2n+1)=2n2-n-1 f(n)=2n2-n-1+(n-1)=2n2-2 該程序的時間復(fù)雜度T(n)=O(n2). for (i=1;in;i+) y=y+1; for (j=0;j=(2*n);j+) x+; O(n2)70nO(n) a=0; b=1; for (i=1;i=n;i+) s=a+b; b=a; a=s; 解： 語句1的頻度：2, 語句2的頻度： n, 語句3的頻度： n, 語句4的頻度：n, 語句5的頻度：n T(n)=2+n+3*n=4n+2=O(n). 71nO(log2n )n i=1; while (i=n) i=i*2; 解：解： 語句1的頻度是1,

41、設(shè)語句2的頻度是f(n), 則： 2f(n)=n;f(n)=log2n 取最大值f(n)= log2n, T(n)=O(log2n )72方法二：方法二： int sum2(int n) int p=1, s=0; for(int i=1; i=n; i+) p*= i; s+=p; return s;分析：單循環(huán)，時間復(fù)雜度：分析：單循環(huán)，時間復(fù)雜度：O(n)方法一：方法一： int sum(int n) int s = 0; for(int i=1; i=n; i+) int p=1; for(int j =1; j = i; j +)p* =j;s+=p; return s;分析：雙重循

42、環(huán)，時間復(fù)雜度：分析：雙重循環(huán)，時間復(fù)雜度：O(n2) 運行時間估計運行時間估計例：例：假設(shè)CPU每秒處理每秒處理106 個指令，對于個指令，對于輸入規(guī)模為108的問題，時間代價為的問題，時間代價為T(n)=2n2的算法要運行的算法要運行多長時間？多長時間？解：解： 操作次數(shù)為 T(n)=T(108)=2(108)2=21016 運行時間為21016/106 = 21010秒秒 每天有86,400秒，因此需要秒，因此需要231,480 天天 (634 年年)7374本章總結(jié)：本章總結(jié)：1 1、數(shù)據(jù)、數(shù)據(jù)：描述客觀事物的：描述客觀事物的數(shù)字?jǐn)?shù)字、字符字符以及所有能輸入到計以及所有能輸入到計算機(jī)中

43、并被計算機(jī)程序處理的算機(jī)中并被計算機(jī)程序處理的符號符號的集合。（數(shù)字、字的集合。（數(shù)字、字符、聲音、圖形、圖像等等）符、聲音、圖形、圖像等等）2 2、數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機(jī)程序中常常作為、數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機(jī)程序中常常作為一個整體進(jìn)行考慮和處理，可以小到一個字符，也可以一個整體進(jìn)行考慮和處理，可以小到一個字符，也可以大到一本書或一張地圖。對于較大的數(shù)據(jù)元素，還可以大到一本書或一張地圖。對于較大的數(shù)據(jù)元素，還可以進(jìn)一步分成若干個進(jìn)一步分成若干個“數(shù)據(jù)項數(shù)據(jù)項”。3 3、數(shù)據(jù)項：數(shù)據(jù)的不可分割的最小單位。、數(shù)據(jù)項：數(shù)據(jù)的不可分割的最小單位。4 4、數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)

44、元素的集合，是數(shù)據(jù)的一個、數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如：全體整數(shù)的集合子集。如：全體整數(shù)的集合Z=0Z=0，+1+1，+2+2 6 6、數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。、數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。 四種邏輯結(jié)四種邏輯結(jié)構(gòu)的特點：構(gòu)的特點： 集合中任何兩個結(jié)點之間都沒有邏輯關(guān)系，組織結(jié)構(gòu)松散集合中任何兩個結(jié)點之間都沒有邏輯關(guān)系，組織結(jié)構(gòu)松散 線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列成一條線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列成一條“鎖鏈鎖鏈”。 樹型結(jié)構(gòu)具有分支、層次特性，形態(tài)像自然界中的樹。樹型結(jié)構(gòu)具有分支、層次特性，形態(tài)像自然界中的樹。 圖狀結(jié)構(gòu)最復(fù)雜，其

45、中的各個結(jié)點按邏輯關(guān)系互相纏繞，任圖狀結(jié)構(gòu)最復(fù)雜，其中的各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接。何兩個結(jié)點都可以鄰接。755 5 、數(shù)據(jù)結(jié)構(gòu)：相互、數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。素的集合。本章總結(jié)：本章總結(jié)：76本章總結(jié)：本章總結(jié)：7 7、數(shù)據(jù)、數(shù)據(jù)的存儲結(jié)構(gòu)的存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)到存儲器的一個映射，即是邏輯結(jié)構(gòu)到存儲器的一個映射，即數(shù)據(jù)在計算機(jī)內(nèi)的表示。兩種存儲方式的特點：數(shù)據(jù)在計算機(jī)內(nèi)的表示。兩種存儲方式的特點：順序存儲方式：每個存儲結(jié)點只含一個數(shù)據(jù)元素，所有順序存儲方式：每個存儲結(jié)點只含一個數(shù)據(jù)元素，所有存儲存儲結(jié)點結(jié)點存放在一塊連續(xù)的存儲區(qū)里，用存儲結(jié)點的位置關(guān)系存放在一塊連續(xù)的存儲區(qū)里，用存儲結(jié)點的位置關(guān)系表示表示數(shù)據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯Ψ绞剑好總€存儲結(jié)點不僅含有一個數(shù)據(jù)