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

1、第一章第一章 緒論緒論1. 了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容2. .掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念3. 掌握算法、算法的時(shí)間復(fù)雜度及其分析的掌握算法、算法的時(shí)間復(fù)雜度及其分析的簡(jiǎn)易方法簡(jiǎn)易方法 教學(xué)目標(biāo)教學(xué)目標(biāo)1.1 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn) 1.4 算法與算法分析算法與算法分析教學(xué)內(nèi)容教學(xué)內(nèi)容&N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)&

2、計(jì)算機(jī)的主要用途：計(jì)算機(jī)的主要用途： 早期：早期： 主要用于數(shù)值計(jì)算。主要用于數(shù)值計(jì)算。 后來(lái)：后來(lái)： 處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域，能處理處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域，能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)1.1 1.1 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容例：例： 例例1 線性結(jié)構(gòu)線性結(jié)構(gòu) 學(xué)學(xué) 號(hào)號(hào) 姓姓 名名 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu) 系系統(tǒng)統(tǒng)結(jié)結(jié)構(gòu)構(gòu) 數(shù)數(shù)學(xué)學(xué) 1 20001 劉劉揚(yáng)揚(yáng) 89 69 67 2 20002 李李平平 70 83 89 3 20003 王王方方 86 81 78 4 20004 張張策策 69 69 78 5 20005 董董立立

3、79 89 68 6 20006 謝謝平平 80 88 79 7 20007 高高月月 81 81 80 8 20008 劉劉平平 89 85 87 9 20009 好好園園 86 80 84 例例2 樹(shù)型結(jié)構(gòu)：樹(shù)型結(jié)構(gòu)： 學(xué)校組織形式學(xué)校組織形式學(xué)校學(xué)校計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院理學(xué)院理學(xué)院。外語(yǔ)院外語(yǔ)院計(jì)算機(jī)系計(jì)算機(jī)系信管系信管系數(shù)學(xué)系數(shù)學(xué)系 物理系物理系 化學(xué)系化學(xué)系英語(yǔ)系英語(yǔ)系 公外公外張三張三李四。李四。李洪。李洪。王五王五吳梅吳梅AFCBDE例例3 圖型結(jié)構(gòu)：圖型結(jié)構(gòu)： 城市交通道路圖城市交通道路圖4550683025801004070&求解非數(shù)值計(jì)算的問(wèn)題：求解非數(shù)值計(jì)算的問(wèn)題

4、： 設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法 即：首先要考慮即：首先要考慮對(duì)相關(guān)的各種信息如何表示、組織對(duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？和存儲(chǔ)？ 數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容為：數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容為： 研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作操作對(duì)象對(duì)象以及它們之間的以及它們之間的關(guān)系和操作關(guān)系和操作。 三要素：操作對(duì)象、關(guān)系、操作（算法）三要素：操作對(duì)象、關(guān)系、操作（算法）是數(shù)據(jù)的基本單位，是數(shù)據(jù)的基本單位，通常作為一個(gè)整體來(lái)處理。通常作為一個(gè)整體來(lái)處理。data item)：組成數(shù)據(jù)元素的、有獨(dú)立含組成數(shù)據(jù)元素的、有獨(dú)立含義的義的

5、最小單位最小單位，也稱域，也稱域( (field)field)。四者之間的關(guān)系：四者之間的關(guān)系： 數(shù)據(jù)數(shù)據(jù) 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 數(shù)據(jù)元素?cái)?shù)據(jù)元素 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)例：例： 學(xué)生表學(xué)生表 個(gè)人記錄個(gè)人記錄 學(xué)號(hào)、姓名學(xué)號(hào)、姓名是相互之間存在一種或多是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。種特定關(guān)系的數(shù)據(jù)元素的集合。 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 從解決問(wèn)題的需要出發(fā)，為實(shí)現(xiàn)必要的功能所建立的數(shù)據(jù)模從解決問(wèn)題的需要出發(fā)，為實(shí)現(xiàn)必要的功能所建立的數(shù)據(jù)模型。用于描述數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。型。用于描述數(shù)據(jù)元素之間的邏輯關(guān)系，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。 物理（存儲(chǔ)）結(jié)構(gòu)：物理（存儲(chǔ)）結(jié)構(gòu)： 數(shù)據(jù)元

6、素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。即數(shù)據(jù)邏即數(shù)據(jù)邏輯結(jié)構(gòu)的物理存儲(chǔ)方式。輯結(jié)構(gòu)的物理存儲(chǔ)方式。劃分方法一劃分方法一 （1 1）線性結(jié)構(gòu)）線性結(jié)構(gòu)- 有且僅有一個(gè)開(kāi)始和一個(gè)終端結(jié)點(diǎn)，并且有且僅有一個(gè)開(kāi)始和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)后繼。所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)后繼。 例如：線性表、棧、隊(duì)列、串例如：線性表、棧、隊(duì)列、串 （2 2）非線性結(jié)構(gòu)）非線性結(jié)構(gòu)- 一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。 例如：樹(shù)、圖例如：樹(shù)、圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)一對(duì)一，如線性表、棧、

7、隊(duì)列一對(duì)一，如線性表、棧、隊(duì)列樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)一對(duì)多，如樹(shù)一對(duì)多，如樹(shù)集合集合數(shù)據(jù)元素間除數(shù)據(jù)元素間除“同屬于一個(gè)集合同屬于一個(gè)集合”外，無(wú)其它關(guān)系外，無(wú)其它關(guān)系圖形結(jié)構(gòu)圖形結(jié)構(gòu)多對(duì)多，如圖多對(duì)多，如圖邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)劃分方法二劃分方法二數(shù)據(jù)結(jié)構(gòu)示例：數(shù)據(jù)結(jié)構(gòu)示例： 工號(hào)工號(hào) 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長(zhǎng)連長(zhǎng) 二連二連 02 李四李四 男男 1978.6.14 排長(zhǎng)排長(zhǎng) 一排一排 03 王五王五 男男 1974.12.7 排長(zhǎng)排長(zhǎng) 二排二排 04 趙一趙一 女女 1982.8.5 排長(zhǎng)排長(zhǎng) 三排三排 05 趙二趙二 男

8、男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢(qián)一錢(qián)一 男男 1977.317 士兵士兵 二排二排 09 錢(qián)二錢(qián)二 男男 1985.10.12 士兵士兵 二排二排 10 錢(qián)三錢(qián)三 女女 1986.7.5 士兵士兵 三排三排 工號(hào)工號(hào) 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長(zhǎng)連長(zhǎng) 二連二連 02 李四李四 男男 1978.6.14 排長(zhǎng)排長(zhǎng) 一排一排 03 王五王五 男男 1974.12.7 排長(zhǎng)排長(zhǎng) 二排二

9、排 04 趙一趙一 女女 1982.8.5 排長(zhǎng)排長(zhǎng) 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢(qián)一錢(qián)一 男男 1977.317 士兵士兵 二排二排 09 錢(qián)二錢(qián)二 男男 1985.10.12 士兵士兵 二排二排 10 錢(qián)三錢(qián)三 女女 1986.7.5 士兵士兵 三排三排定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S= 0102030405060708091

10、0集合集合不考慮該表中記錄之間的任何次序不考慮該表中記錄之間的任何次序定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , 05010308020704060910線性結(jié)構(gòu)線性結(jié)構(gòu)考慮按人員出生年月從大到小排列組織數(shù)據(jù)考慮按人員出生年月從大到小排列組織數(shù)據(jù) 工號(hào)工號(hào) 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長(zhǎng)連長(zhǎng) 二連二連 02 李四李四 男男 1978.6.14 排長(zhǎng)排長(zhǎng) 一排一排 03 王五王五 男男 1974.12.7 排長(zhǎng)排長(zhǎng) 二排二排 04

11、 趙一趙一 女女 1982.8.5 排長(zhǎng)排長(zhǎng) 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢(qián)一錢(qián)一 男男 1977.317 士兵士兵 二排二排 09 錢(qián)二錢(qián)二 男男 1985.10.12 士兵士兵 二排二排 10 錢(qián)三錢(qián)三 女女 1986.7.5 士兵士兵 三排三排定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , 05010308020704060910

12、樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)考慮領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)之間的關(guān)系考慮領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)之間的關(guān)系 工號(hào)工號(hào) 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長(zhǎng)連長(zhǎng) 二連二連 02 李四李四 男男 1978.6.14 排長(zhǎng)排長(zhǎng) 一排一排 03 王五王五 男男 1974.12.7 排長(zhǎng)排長(zhǎng) 二排二排 04 趙一趙一 女女 1982.8.5 排長(zhǎng)排長(zhǎng) 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢(qián)一錢(qián)一 男男 1977.

13、317 士兵士兵 二排二排 09 錢(qián)二錢(qián)二 男男 1985.10.12 士兵士兵 二排二排 10 錢(qián)三錢(qián)三 女女 1986.7.5 士兵士兵 三排三排定義：定義：data_structure=( D , S ) D= 01,02,03,04,05,06,07,08,09,10S=, , , 05010302070406圖形結(jié)構(gòu)圖形結(jié)構(gòu)考慮好朋友關(guān)系考慮好朋友關(guān)系 工號(hào)工號(hào) 姓名姓名 性別性別 出生年月出生年月 職務(wù)職務(wù) 班排班排 01 張三張三 男男 1972.3.20 連長(zhǎng)連長(zhǎng) 二連二連 02 李四李四 男男 1978.6.14 排長(zhǎng)排長(zhǎng) 一排一排 03 王五王五 男男 1974.12.7

14、排長(zhǎng)排長(zhǎng) 二排二排 04 趙一趙一 女女 1982.8.5 排長(zhǎng)排長(zhǎng) 三排三排 05 趙二趙二 男男 1969.8.15 士兵士兵 一排一排 06 趙七趙七 男男 1985.4.1 士兵士兵 一排一排 07 趙八趙八 男男 1982.6.28 士兵士兵 二排二排 08 錢(qián)一錢(qián)一 男男 1977.317 士兵士兵 二排二排 09 錢(qián)二錢(qián)二 男男 1985.10.12 士兵士兵 二排二排 10 錢(qián)三錢(qián)三 女女 1986.7.5 士兵士兵 三排三排兩種：兩種：順序順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 借助元素在存儲(chǔ)器中的借助元素在存儲(chǔ)器中的相對(duì)位置相對(duì)位置來(lái)表示數(shù)據(jù)元素來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。要求用地址連續(xù)的一

15、整片存儲(chǔ)空間間的邏輯關(guān)系。要求用地址連續(xù)的一整片存儲(chǔ)空間（數(shù)組）。（數(shù)組）。鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 借助指示元素存儲(chǔ)地址的借助指示元素存儲(chǔ)地址的指針指針表示數(shù)據(jù)元素間的表示數(shù)據(jù)元素間的邏輯關(guān)系。無(wú)需一整塊存儲(chǔ)空間。邏輯關(guān)系。無(wú)需一整塊存儲(chǔ)空間。存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容Loc(元素元素i)=L0+（i-1)*m順序存儲(chǔ)順序存儲(chǔ)每個(gè)元素占每個(gè)元素占m個(gè)字節(jié)個(gè)字節(jié)L0為整片存儲(chǔ)空間的起始地址為整片存儲(chǔ)空間的起始地址1536元素元素2 21400元素元素1 1134

16、6元素元素3 3 元素元素4 41345h存儲(chǔ)地址存儲(chǔ)地址 存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容 指針指針 13451345 元素元素1 1 1400 1400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 15361536 元素元素3 3 1346 1346 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) h后繼元素后繼元素所在地址所在地址記住首元記住首元素地址素地址對(duì)于一種數(shù)據(jù)結(jié)構(gòu)對(duì)于一種數(shù)據(jù)結(jié)構(gòu), , 常見(jiàn)的運(yùn)算包括：常見(jiàn)的運(yùn)算包括： 插入插入 刪除刪除 修改修改 查找查找 排序排序 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同, , 但運(yùn)算不同但運(yùn)算

17、不同, , 則數(shù)據(jù)則數(shù)據(jù)結(jié)構(gòu)不同。結(jié)構(gòu)不同。 例如例如, , 棧與隊(duì)列棧與隊(duì)列數(shù)據(jù)結(jié)構(gòu)關(guān)心的三個(gè)方面：數(shù)據(jù)結(jié)構(gòu)關(guān)心的三個(gè)方面： 1數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) A線性結(jié)構(gòu)線性結(jié)構(gòu) B非線性結(jié)構(gòu)非線性結(jié)構(gòu)A 順序存儲(chǔ)順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表 棧、隊(duì)列棧、隊(duì)列樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 3、數(shù)據(jù)的運(yùn)算：插入、刪除、修改、查找、排序等。、數(shù)據(jù)的運(yùn)算：插入、刪除、修改、查找、排序等。 串、數(shù)組串、數(shù)組集合結(jié)構(gòu)集合結(jié)構(gòu)1.3 1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)一個(gè)數(shù)據(jù)的集合一個(gè)數(shù)據(jù)的集

18、合, , 以及定義于這個(gè)數(shù)以及定義于這個(gè)數(shù)據(jù)集合上的一組操作的總稱。據(jù)集合上的一組操作的總稱。 C C語(yǔ)言中的數(shù)據(jù)類型：語(yǔ)言中的數(shù)據(jù)類型： 基本數(shù)據(jù)類型、指針類型、數(shù)組類型、結(jié)構(gòu)基本數(shù)據(jù)類型、指針類型、數(shù)組類型、結(jié)構(gòu)體類型、公用體類型、枚舉類型體類型、公用體類型、枚舉類型(ADT: Abstract Data Types) 是指是指用戶定義的用戶定義的一個(gè)數(shù)學(xué)模型以及定義在此數(shù)一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作的總稱。學(xué)模型上的一組操作的總稱。 （僅（僅定義定義數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說(shuō)明，不考慮在數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說(shuō)明，不考慮在計(jì)算機(jī)內(nèi)部的表示和實(shí)現(xiàn)）計(jì)算機(jī)內(nèi)部的表示和實(shí)現(xiàn)）抽象數(shù)據(jù)

19、類型抽象數(shù)據(jù)類型可以用以下的三元組來(lái)表示：可以用以下的三元組來(lái)表示： ADT = （D，S，P） 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D上的關(guān)系集上的關(guān)系集 D上的操作集上的操作集 ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)數(shù)據(jù)對(duì)象對(duì)象： 數(shù)據(jù)數(shù)據(jù)關(guān)系關(guān)系： 基本基本 ： ADT ADT抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型名名ADT常用常用定義定義格式格式 抽象數(shù)據(jù)類型可以通過(guò)固有的數(shù)據(jù)類型（如整型、抽象數(shù)據(jù)類型可以通過(guò)固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來(lái)表示和實(shí)現(xiàn)。實(shí)型、字符型等）來(lái)表示和實(shí)現(xiàn)。 教材中用的是類教材中用的是類C C語(yǔ)言作為描述工具，語(yǔ)言作為描述工具，p8p8。例題：例題： 定義矩形的抽象數(shù)據(jù)類型

20、，其數(shù)據(jù)包括矩形的長(zhǎng)和寬，定義矩形的抽象數(shù)據(jù)類型，其數(shù)據(jù)包括矩形的長(zhǎng)和寬，操作包括初始化矩形的長(zhǎng)和寬，計(jì)算矩形的周長(zhǎng)與面積。操作包括初始化矩形的長(zhǎng)和寬，計(jì)算矩形的周長(zhǎng)與面積。 ADT Rectangle 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：D=e1,e2|e1,e2是實(shí)數(shù)是實(shí)數(shù) 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：S=|e1是矩形長(zhǎng)，是矩形長(zhǎng)，e2是矩形寬是矩形寬 基本操作基本操作： InitRectangle (&R, len, wid); 操作結(jié)果：構(gòu)造矩形操作結(jié)果：構(gòu)造矩形R，長(zhǎng)與寬分別被賦予參數(shù)，長(zhǎng)與寬分別被賦予參數(shù) len 與與wid的值的值 Circumference (R); 初始條件：初始條件：R已存在

21、已存在 操作結(jié)果：返回矩形操作結(jié)果：返回矩形R的周長(zhǎng)的周長(zhǎng) Area (R); 初始條件：初始條件：R已存在已存在 操作結(jié)果：返回矩形操作結(jié)果：返回矩形R的面積的面積 ADT Rectangle 表示部分：表示部分： typedef struct Rect float length, width; Rectangle;實(shí)現(xiàn)部分：實(shí)現(xiàn)部分： void InitRectangle(&Rectangle r, float len, float wid) r. Length = len; r. Width = wid; float Circumference (Rectangle r) ret

22、urn 2*(r.length + r.width); float Area (Rectangle r) return r.length * r.width; void Main() Rectangle x; InitRectangle(x,10,5); cout Area (x)endl; .( algorithm)1.4 1.4 算法和算法分析算法和算法分析算法效率分析方法：算法效率分析方法： 事后統(tǒng)計(jì)：事后統(tǒng)計(jì)： 事前分析估算：事前分析估算：通常采用這種方法，計(jì)算漸進(jìn)復(fù)雜度通常采用這種方法，計(jì)算漸進(jìn)復(fù)雜度 同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在

23、不同的計(jì)算機(jī)上運(yùn)行，效率均不同，在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，使用使用絕對(duì)時(shí)間單位絕對(duì)時(shí)間單位衡量算法效率不合適衡量算法效率不合適算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度算法的運(yùn)行時(shí)間算法的運(yùn)行時(shí)間 = = 計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作的時(shí)間計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作的時(shí)間* *簡(jiǎn)單操作的執(zhí)行次數(shù)簡(jiǎn)單操作的執(zhí)行次數(shù) （與機(jī)器有關(guān)，不考慮）（與機(jī)器有關(guān)，不考慮）如：如：t=x; x=y; y=t;t=x; x=y; y=t; 運(yùn)行時(shí)間運(yùn)行時(shí)間 = = 一條賦值語(yǔ)句的執(zhí)行時(shí)間一條賦值語(yǔ)句的執(zhí)行時(shí)間* *3 3 通常把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做該算法通

24、常把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做該算法的時(shí)間復(fù)雜度，用它來(lái)衡量一個(gè)算法的運(yùn)行時(shí)間性能。的時(shí)間復(fù)雜度，用它來(lái)衡量一個(gè)算法的運(yùn)行時(shí)間性能。 若解決一個(gè)問(wèn)題的規(guī)模為若解決一個(gè)問(wèn)題的規(guī)模為n n，即表示待處理的數(shù)據(jù)中即表示待處理的數(shù)據(jù)中包含有包含有n n個(gè)元素，則算法的個(gè)元素，則算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度通常是通常是n n的一個(gè)函的一個(gè)函數(shù)，記為數(shù)，記為f(n)f(n)。例例1 1：分析以下程序的時(shí)間復(fù)雜度：分析以下程序的時(shí)間復(fù)雜度 int Sum(int b, int n) int i, s=0; /頻度為頻度為1 for ( i=0; in; i+ ) /頻度為頻度為(n+1) s=s+bi;

25、 /頻度為頻度為n return s; /頻度為頻度為1 （一條語(yǔ)句重復(fù)執(zhí)行的次數(shù)稱語(yǔ)句的頻度）（一條語(yǔ)句重復(fù)執(zhí)行的次數(shù)稱語(yǔ)句的頻度） 時(shí)間復(fù)雜度時(shí)間復(fù)雜度: : f(n) = 2 2n+3 = O(n)例例2 2：分析以下程序段的時(shí)間復(fù)雜度：分析以下程序段的時(shí)間復(fù)雜度 for ( i=1; i=n; i+) /n+1次次 y+ ; /n次次 for ( j=1; j= n0n = n0時(shí)，時(shí)， T(n)T(n)=M=M* *f(n)|f(n)| 表示隨問(wèn)題規(guī)模表示隨問(wèn)題規(guī)模n n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率與函數(shù)與函數(shù)f(n)f(n)的增長(zhǎng)率相同。的增長(zhǎng)率相同。

26、當(dāng)當(dāng) f(n)= c0nm+c1nm-1+cm-1n+cm 時(shí)，時(shí)， T(n)= O(nm) 采用數(shù)量級(jí)的形式表示后采用數(shù)量級(jí)的形式表示后，時(shí)間復(fù)雜度不必計(jì)算出時(shí)間復(fù)雜度不必計(jì)算出簡(jiǎn)單操作的精確次數(shù)，只要計(jì)算出相應(yīng)的簡(jiǎn)單操作的精確次數(shù)，只要計(jì)算出相應(yīng)的數(shù)量級(jí)數(shù)量級(jí)即可。即可。 例：例：lx =x+1; y =y+1; O(1)lfor (i=1;i=n;i+) x=x+1 O(n)lfor (i=1;i=n;i+) for (j=1; j=i-1; j+) x=x+1 O(n2)算法的時(shí)間復(fù)雜度是由算法的時(shí)間復(fù)雜度是由嵌套最深層嵌套最深層語(yǔ)句的頻度決定的語(yǔ)句的頻度決定的算法的時(shí)間復(fù)雜度通常具有

27、形式：算法的時(shí)間復(fù)雜度通常具有形式：O(1)、 O(log2n) 、 O(n) 、O(n*log2n)、O(n2)、O(n3)、O(2n) 、O(n!)隨著隨著n n的增大，各種數(shù)量級(jí)對(duì)應(yīng)值的增長(zhǎng)速度大不相同，的增大，各種數(shù)量級(jí)對(duì)應(yīng)值的增長(zhǎng)速度大不相同，對(duì)應(yīng)關(guān)系如下：對(duì)應(yīng)關(guān)系如下： P14 圖圖1.7 O(1) O(log2n) O(n) O(n*log2n) O(n2) O(2n) O(n!) 一個(gè)算法的一個(gè)算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度還可以具體分為還可以具體分為最好最好、最最差差和和平均平均三種情況來(lái)討論三種情況來(lái)討論 。例：順序查找算法例：順序查找算法 int SequenceSearch(int a , int n, int item) /若查找成功則返回元素的下標(biāo)，否則返回若查找成功則返回元素的下標(biāo)，否則返回-1。 for (int i=0; in; i+) if (ai=item) return i; return -1; 第