《數(shù)據(jù)結(jié)構(gòu)》課件第1章

第1章緒論1.1數(shù)據(jù)結(jié)構(gòu)的概念1.2數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)1.3算法本章小結(jié)習(xí)題一實(shí)訓(xùn)1-1算法性能分析

【教學(xué)目標(biāo)】通過對(duì)本章的學(xué)習(xí)，熟悉各名詞和術(shù)語(yǔ)的含義，理解數(shù)據(jù)結(jié)構(gòu)及其有關(guān)的概念，了解算法的基本特征和算法的評(píng)價(jià)標(biāo)準(zhǔn)，掌握估算算法的時(shí)間復(fù)雜度的方法。運(yùn)用計(jì)算機(jī)對(duì)一批數(shù)據(jù)進(jìn)行處理時(shí)，必須解決好三個(gè)方面的問題：第一，根據(jù)數(shù)據(jù)之間的邏輯關(guān)系如何組織這批數(shù)據(jù)？第二，如何將這批數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中？第三，對(duì)于存儲(chǔ)在計(jì)算機(jī)中的這批數(shù)據(jù)可以進(jìn)行哪些操作？如何實(shí)現(xiàn)這些操作？對(duì)同一問題的不同操作方法如何進(jìn)行評(píng)價(jià)？這些問題就是數(shù)據(jù)結(jié)構(gòu)這門課程所要研究的主要問題。1.1數(shù)據(jù)結(jié)構(gòu)的概念1.1.1基本概念和術(shù)語(yǔ)在闡述數(shù)據(jù)結(jié)構(gòu)的概念之前，先對(duì)數(shù)據(jù)結(jié)構(gòu)中常用的幾個(gè)基本概念和術(shù)語(yǔ)給出確切的定義。

1.數(shù)據(jù)(Data)數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)的集合。換句話說，數(shù)據(jù)是對(duì)客觀事物采用計(jì)算機(jī)能夠識(shí)別、存儲(chǔ)和處理的形式所進(jìn)行的描述。簡(jiǎn)而言之，數(shù)據(jù)就是計(jì)算機(jī)化的信息。數(shù)據(jù)一般可分為數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)，如數(shù)學(xué)中的整數(shù)、實(shí)數(shù)等都是數(shù)值型數(shù)據(jù)，字符、表格、圖形、圖像和聲音等都是非數(shù)值型數(shù)據(jù)。又如對(duì)于C源程序，數(shù)據(jù)概念不僅是源程序所處理的數(shù)據(jù)，源程序本身也是被C編譯程序處理的數(shù)據(jù)。編譯程序相對(duì)于源程序是一個(gè)處理程序，它加工的數(shù)據(jù)是字符流的源程序(.c)，輸出的結(jié)果是目標(biāo)程序(.obj)；對(duì)于鏈接程序來(lái)說，它加工的數(shù)據(jù)是目標(biāo)程序(.obj)，輸出的結(jié)果是可執(zhí)行程序(.exe)，如圖1.1所示。圖1.1編譯程序示意圖

2.數(shù)據(jù)元素(DataElement)數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小單位。數(shù)據(jù)元素有時(shí)也叫做結(jié)點(diǎn)、元素、頂點(diǎn)、記錄等。例如：在數(shù)據(jù)庫(kù)管理系統(tǒng)中，數(shù)據(jù)庫(kù)中的一條記錄就是一個(gè)數(shù)據(jù)元素，這條記錄中的每一個(gè)字段就是構(gòu)成這個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，如表1-1所示。表1-1學(xué)籍表

3.數(shù)據(jù)對(duì)象(DataObject)數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是集合Ｎ={0，±1，±2，…}，字母字符數(shù)據(jù)對(duì)象是集合C={'A'，'B'，…，'Z'}。表1-1所示的學(xué)籍表也可看做一個(gè)數(shù)據(jù)對(duì)象。由此可看出，不論數(shù)據(jù)元素集合是無(wú)限集(如整數(shù)集)、有限集(如字符集)，還是由多個(gè)數(shù)據(jù)項(xiàng)組成的復(fù)合數(shù)據(jù)元素(如學(xué)籍表)，只要性質(zhì)相同，都是同一個(gè)數(shù)據(jù)對(duì)象。

4.數(shù)據(jù)類型數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合，即該類型的取值范圍，以及該類型中可允許使用的一組運(yùn)算。例如高級(jí)語(yǔ)言中的數(shù)據(jù)類型就是已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的實(shí)例。從這個(gè)意義上講，數(shù)據(jù)類型是高級(jí)語(yǔ)言中允許的變量種類，是程序語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)(即程序中允許出現(xiàn)的數(shù)據(jù)形式)。在高級(jí)語(yǔ)言中，整型類型可能的取值范圍是-32768～+32767，可用的運(yùn)算符集合為加、減、乘、除、乘方、取模(如C語(yǔ)言中的?+、-、*、/、%)。1.1.2數(shù)據(jù)結(jié)構(gòu)的定義對(duì)于什么是數(shù)據(jù)結(jié)構(gòu)，目前還沒有一個(gè)公認(rèn)的定義，對(duì)數(shù)據(jù)結(jié)構(gòu)的概念，可以從以下兩個(gè)角度來(lái)理解：一是把數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立開設(shè)的課程，看“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)專業(yè)中的地位、性質(zhì)、任務(wù)以及它研究的內(nèi)容等；二是把數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)所處理的數(shù)據(jù)的組織方式來(lái)理解。

1.“數(shù)據(jù)結(jié)構(gòu)”課程“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國(guó)外是從1968年開始設(shè)立的，我國(guó)從1978年開始，各高等院校才先后開設(shè)了這門課程，現(xiàn)在“數(shù)據(jù)結(jié)構(gòu)”已是計(jì)算機(jī)專業(yè)的一門綜合性的專業(yè)基礎(chǔ)課。它是“操作系統(tǒng)”、“編譯原理”、“數(shù)據(jù)庫(kù)系統(tǒng)”、“計(jì)算機(jī)圖形學(xué)”、“人工智能”等課程的先修課?！皵?shù)據(jù)結(jié)構(gòu)”的研究不僅涉及到計(jì)算機(jī)硬件的研究范圍，而且和計(jì)算機(jī)軟件的研究有著密切的關(guān)系，可以說，“數(shù)據(jù)結(jié)構(gòu)”是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門綜合性課程，可以用一個(gè)定義描述如下：“數(shù)據(jù)結(jié)構(gòu)”是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)操作對(duì)象以及它們的關(guān)系和操作的一門學(xué)科。

2.數(shù)據(jù)結(jié)構(gòu)的概念如果從數(shù)據(jù)元素之間的組織形式來(lái)看，可以認(rèn)為數(shù)據(jù)結(jié)構(gòu)指的是計(jì)算機(jī)所處理的數(shù)據(jù)元素之間的組織形式和相互關(guān)系。在任何問題中，數(shù)據(jù)元素都不是孤立存在的，它們之間必定存在著某種內(nèi)在的或者是根據(jù)需要人為定義的關(guān)系，這種關(guān)系就是這些數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)一般包括以下三個(gè)方面的內(nèi)容：

(1)數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)，是用戶根據(jù)需要而建立起來(lái)的。

(2)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，又稱數(shù)據(jù)的物理結(jié)構(gòu)。

(3)數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素所進(jìn)行的操作?？梢园褦?shù)據(jù)結(jié)構(gòu)定義為：對(duì)計(jì)算機(jī)處理的一批數(shù)據(jù)，首先按某種邏輯關(guān)系把它們組織起來(lái)，再按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，然后給這批數(shù)據(jù)規(guī)定一組操作。1.2數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)1.2.1邏輯結(jié)構(gòu)根據(jù)數(shù)據(jù)元素之間的不同特性，可以把數(shù)據(jù)的邏輯結(jié)構(gòu)分為四種基本類型：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。其邏輯結(jié)構(gòu)關(guān)系如圖1.2所示。

1.集合集合中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，沒有其它任何關(guān)系。大街上熙熙攘攘的人群可以看成是一個(gè)集合。集合是數(shù)據(jù)結(jié)構(gòu)的一種特例，本書不予討論。

2.線性結(jié)構(gòu)線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系。即除了第一個(gè)元素外，其它的每個(gè)元素都有且僅有一個(gè)直接前驅(qū)，除了最后一個(gè)元素外，每個(gè)元素都有且僅有一個(gè)直接后繼。火車站長(zhǎng)長(zhǎng)的購(gòu)票隊(duì)列就是線性結(jié)構(gòu)。

3.樹形結(jié)構(gòu)樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系。即每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)，但每個(gè)結(jié)點(diǎn)都可以有多個(gè)直接后繼。其中根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)。軍隊(duì)中師、團(tuán)、營(yíng)、連、排的層次結(jié)構(gòu)就是一種典型的樹形結(jié)構(gòu)，三軍總司令是根，而士兵就是葉子。

4.圖形結(jié)構(gòu)圖形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的任意關(guān)系。即各個(gè)結(jié)點(diǎn)可以有多個(gè)直接前驅(qū)，也可以有多個(gè)直接后繼。城市之間四通八達(dá)的公路網(wǎng)就是圖形結(jié)構(gòu)。有時(shí)也可以把數(shù)據(jù)邏輯結(jié)構(gòu)簡(jiǎn)單地分為兩種類型，即線性結(jié)構(gòu)和非線性結(jié)構(gòu)。非線性結(jié)構(gòu)包括樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。圖1.2四種基本邏輯結(jié)構(gòu)關(guān)系圖1.2.2存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)(又稱物理結(jié)構(gòu))是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映像，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映像與元素本身的映像。邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，兩者綜合起來(lái)建立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。存儲(chǔ)結(jié)構(gòu)可以分為順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)兩大類。順序存儲(chǔ)的特點(diǎn)是將數(shù)據(jù)元素按其邏輯順序依次存儲(chǔ)在內(nèi)存中一組地址連續(xù)的存儲(chǔ)單元中，即邏輯上相鄰的結(jié)點(diǎn)物理上也必須相鄰。非順序存儲(chǔ)則比較靈活，可以將數(shù)據(jù)分散存儲(chǔ)在內(nèi)存中，即邏輯上相鄰的結(jié)點(diǎn)物理上不一定相鄰。常用的非順序存儲(chǔ)有鏈?zhǔn)酱鎯?chǔ)、Hash存儲(chǔ)和索引存儲(chǔ)。1.3算法1.3.1算法的概念及描述

1.算法(Algorithm)簡(jiǎn)單地說，算法就是解決特定問題的方法。嚴(yán)格地說，算法是由若干條指令組成的有窮序列，其中每條指令表示計(jì)算機(jī)的一個(gè)或多個(gè)操作。例如：將一組給定的數(shù)據(jù)由小到大進(jìn)行排序，解決的方法有若干種，而每一種排序方法就是一種算法。一個(gè)算法必須具有以下五個(gè)特性：

(1)有窮性。一個(gè)算法在執(zhí)行有限條指令后必須要終止，且每條指令都要在有限時(shí)間內(nèi)完成。不能形成無(wú)窮循環(huán)。

(2)確定性。算法中每條指令必須有確切的含義，不會(huì)產(chǎn)生二義性

(3)可行性。算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。

(4)輸入。一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取決于某個(gè)特定的對(duì)象的集合。

(5)輸出。一個(gè)算法有一個(gè)或多個(gè)結(jié)果輸出。算法和程序有所不同，程序可以不滿足上述的有窮性。例如，Windows操作系統(tǒng)在用戶未操作之前一直處于“等待”的循環(huán)中，直到出現(xiàn)新的用戶操作為止。

2.算法、語(yǔ)言和程序的關(guān)系

(1)算法。算法描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系(包括數(shù)據(jù)邏輯關(guān)系和存儲(chǔ)關(guān)系)。

(2)語(yǔ)言。算法可用自然語(yǔ)言、框圖或高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行描述。自然語(yǔ)言簡(jiǎn)單但易于產(chǎn)生二義性，框圖直觀但不擅長(zhǎng)表達(dá)數(shù)據(jù)的組織結(jié)構(gòu)，而高級(jí)程序語(yǔ)言則較為準(zhǔn)確且比較嚴(yán)謹(jǐn)。

(3)程序。程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)(與所用計(jì)算機(jī)及所用語(yǔ)言有關(guān))。1.3.2算法的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)于一個(gè)特定的問題，采用不同的存儲(chǔ)結(jié)構(gòu)，其算法描述一般是不相同的，即使在同一種存儲(chǔ)結(jié)構(gòu)下，也可以采用不同的求解策略，從而有許多不同的算法。那么，對(duì)于解決同一問題的不同算法，選擇哪一種算法較為合適，以及如何對(duì)現(xiàn)有的算法進(jìn)行改進(jìn)，從而設(shè)計(jì)出更好的算法，這就是算法評(píng)價(jià)問題。評(píng)價(jià)一個(gè)算法的優(yōu)劣主要有以下幾個(gè)標(biāo)準(zhǔn)：

1.正確性一個(gè)算法能否正確地執(zhí)行預(yù)先的功能，這是評(píng)價(jià)一個(gè)算法的最重要也是最基本的標(biāo)準(zhǔn)。其要求是：

(1)所設(shè)計(jì)的程序沒有語(yǔ)法錯(cuò)誤。

(2)所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。

(3)所設(shè)計(jì)的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。

(4)程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。例如，求5個(gè)數(shù)的最大值問題，給出示意算法如下：max=0;for(i=1;i<=5;i++){scanf("%f",&x);if(x>max)max=x;}printf("%f",max);表面上看來(lái)該算法是正確的，輸入10.1、2.5、-3.4、-6.5、8.4驗(yàn)證，結(jié)果也正確，可是當(dāng)輸入數(shù)據(jù)全部是負(fù)數(shù)的時(shí)候，輸出結(jié)果卻是0，所以該算法并不正確。

2.可讀性算法主要是為了人的閱讀與交流，其次才是機(jī)器執(zhí)行。即使算法已轉(zhuǎn)變成機(jī)器可執(zhí)行的程序，也需考慮人能較好地閱讀理解。可讀性好有助于人對(duì)算法的理解，這既有助于對(duì)算法中隱藏錯(cuò)誤的排除，也有助于算法的交流和移植。

3.健壯性算法應(yīng)具有很強(qiáng)的容錯(cuò)能力，即算法能對(duì)非法數(shù)據(jù)的輸入進(jìn)行檢查和處理，不會(huì)因非法數(shù)據(jù)的輸入而導(dǎo)致異常中斷或死機(jī)等現(xiàn)象。

4.運(yùn)行時(shí)間運(yùn)行時(shí)間是指算法在計(jì)算機(jī)上運(yùn)行所花費(fèi)的時(shí)間，它等于算法中每條語(yǔ)句執(zhí)行時(shí)間的總和。對(duì)于同一個(gè)問題如果有多個(gè)算法可供選擇，應(yīng)盡可能選擇執(zhí)行時(shí)間短的算法，一般來(lái)說，執(zhí)行時(shí)間越短則算法的效率越高、性能越好。

5.占用空間占用空間是指算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。算法占用的存儲(chǔ)空間是指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。對(duì)于一個(gè)問題如果有多個(gè)算法可供選擇，應(yīng)盡可能選擇存儲(chǔ)量需求低的算法。實(shí)際上，算法的時(shí)間效率和空間效率經(jīng)常是一對(duì)矛盾體，相互抵觸，有時(shí)增加輔助的存儲(chǔ)空間可以加快算法的運(yùn)行速度，即用空間換取時(shí)間；有時(shí)因?yàn)閮?nèi)存空間不夠，必須壓縮輔助的存儲(chǔ)空間，從而降低了算法的運(yùn)行速度，即用時(shí)間換取空間。通常把算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間的大小叫做算法的空間復(fù)雜度。算法的空間復(fù)雜度比較容易計(jì)算，它主要包括局部變量所占用的存儲(chǔ)空間和系統(tǒng)為實(shí)現(xiàn)遞歸所使用的堆棧占用的存儲(chǔ)空間。1.3.3算法的時(shí)間復(fù)雜度一個(gè)算法的運(yùn)行時(shí)間是該算法中每條語(yǔ)句執(zhí)行時(shí)間的總和，而每條語(yǔ)句的執(zhí)行時(shí)間是該語(yǔ)句的執(zhí)行次數(shù)(也叫語(yǔ)句頻度)與執(zhí)行一次該語(yǔ)句所需時(shí)間的乘積。由于同一條語(yǔ)句在不同的機(jī)器上執(zhí)行所需的時(shí)間是不相同的，也就是說執(zhí)行一條語(yǔ)句所需的時(shí)間與具體的機(jī)器有關(guān)，因此要想精確地計(jì)算各種語(yǔ)句執(zhí)行一次所需的時(shí)間是比較困難的。實(shí)際上，為了評(píng)價(jià)一個(gè)算法的性能，我們只需計(jì)算算法中所有語(yǔ)句執(zhí)行的總次數(shù)即可。任何一個(gè)算法最終都要被分解成一系列基本操作(如賦值、轉(zhuǎn)向、比較、輸入、輸出等)來(lái)具體執(zhí)行，每一條語(yǔ)句也要分解成具體的基本操作來(lái)執(zhí)行，所以算法的運(yùn)行時(shí)間也可以用算法中所進(jìn)行的基本操作的總次數(shù)來(lái)估算。在一個(gè)算法中，進(jìn)行簡(jiǎn)單操作的次數(shù)越少，其運(yùn)行時(shí)間也相對(duì)越少。為了便于比較同一問題的不同算法，也可以用算法中的基本操作重復(fù)執(zhí)行的頻度作為算法運(yùn)行時(shí)間的度量標(biāo)準(zhǔn)。通常把算法中的基本操作重復(fù)執(zhí)行的頻度稱為算法的時(shí)間復(fù)雜度。算法中的基本操作一般是指算法中最深層循環(huán)內(nèi)的語(yǔ)句，因此，算法中基本操作重復(fù)執(zhí)行的頻度T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))。其中“O”表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，或者說，用“O”表示數(shù)量級(jí)(OrderofMagnitude)的概念。例如，若T(n)=2n2+3n+1,則2n2+3n+1的數(shù)量級(jí)與n2的數(shù)量級(jí)相同，所以T(n)=O(n2)。如果一個(gè)算法沒有循環(huán)語(yǔ)句，則算法的基本操作的執(zhí)行頻度與問題規(guī)模n無(wú)關(guān)，記作O(1)，也稱常數(shù)階。如果一個(gè)算法只有一重循環(huán)，則算法的基本操作的執(zhí)行頻度隨問題規(guī)模n的增大而呈線性增大關(guān)系，記作O(n)，也稱做線性階。按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1)，對(duì)數(shù)階O(log2n)，線性階O(n)，線性對(duì)數(shù)階O(nlog2)，平方階O(n2)，立方階O(n3)，…，k次方階O(nk)，指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度也不斷增大，算法執(zhí)行效率依次降低。下面舉例說明計(jì)算算法時(shí)間復(fù)雜度的方法。

例1.1

分析以下程序段的時(shí)間復(fù)雜度。

for(i=1;i<n;i++){

y=y+1;①

for(j=0;j<=(2*n);j++)

x++;②

}解：該程序段中語(yǔ)句①的頻度是n-1，語(yǔ)句②的頻度是(n-1)(2n?+?1)?=?2n2-n-1，則程序段的時(shí)間復(fù)雜度T(n)?=?(n-1)?+?(2n2-n-1)?=?2n2-2?=?O(n2)。例1.2

分析以下程序段的時(shí)間復(fù)雜度。

i=1; ①

while(i<=n)

i=i*2; ②

解：該程序段中語(yǔ)句①的頻度是1，設(shè)語(yǔ)句②的頻度為f(n)，則有2f(n)≤n，即f(n)≤log2n,取最大值f(n)=log2n，所以該程序段的時(shí)間復(fù)雜度T(n)=1+f(n)=1+log2n=O(log2n)。

例1.3

分析以下程序段的時(shí)間復(fù)雜度。

a=0,b=1; ①

for(i=2;i<=n;i++)

{

s=a+b; ②

b=1; ③

a=s; ④

}

解：該程序段中語(yǔ)句①的頻度是2，語(yǔ)句②、③、④的頻度都是n-1，則該程序段的時(shí)間復(fù)雜度T(n)?=?2?+?3*(n-1)?=?3n-1?=?O(n)。

例1.4

分析下列算法的時(shí)間復(fù)雜度。

prime(intn)

{ inti=2;

while((n%i)!=0&&i*1.0<sqrt(n))

i++; ①if(i*1.0>sqrt(n))

printf("%d是一個(gè)素?cái)?shù)\n",n); ②else

printf("%d不是一個(gè)素?cái)?shù)\n",n); ③}

解：從上面的四個(gè)例題可以看出，算法的時(shí)間復(fù)雜度是由嵌套最深層語(yǔ)句的頻度決定的。prime函數(shù)嵌套最深層語(yǔ)句是①，顯然它的頻度由條件((n%i)!?=?0&&i*1.0?<?sqrt(n))中的i*1.0?<?sqrt(n)決定，即執(zhí)行頻度小于sqrt(n)，所以其時(shí)間復(fù)雜度是T(n)=Ｏ(

)。

例1.5

下面是求兩個(gè)n×n階矩陣乘法C?=?A×B的算法，分析該算法的時(shí)間復(fù)雜度。

#defineMAX100

voidmaxtrixmult(intn,floata[MAX][MAX],

b[MAX][MAX],floatc[MAX][MAX])

{

inti,j,k;

floatx;

for(i=1;i<=n;i++) ①

{

for(j=1;j<=n;j++) ②

{

x=0; ③

for(k=1;k<=n;k++)④

x+=a[i][k]*b[k][j];⑤

c[i][j]=x;

⑥

}

}}

解：該算法中嵌套最深層語(yǔ)句是⑤，其頻度是n3，則該算法的時(shí)間復(fù)雜度T(n)?=?O(n3)。本章小結(jié)本章主要介紹了數(shù)據(jù)結(jié)構(gòu)及其有關(guān)的概念，包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法等基本概念。數(shù)據(jù)結(jié)構(gòu)一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及對(duì)數(shù)據(jù)元素所進(jìn)行的操作。根據(jù)不同的抽象層次，數(shù)據(jù)結(jié)構(gòu)可分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)需要而建立起來(lái)的。根據(jù)數(shù)據(jù)元素之間的不同特性，我們可以把數(shù)據(jù)邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四種基本類型。集合中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，沒有其它任何關(guān)系，它是數(shù)據(jù)結(jié)構(gòu)的一種特例；線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系；樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系；圖形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的任意關(guān)系。有時(shí)我們也可以把數(shù)據(jù)邏輯結(jié)構(gòu)分為兩種類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。非線性結(jié)構(gòu)包括樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)元素在計(jì)算機(jī)的存儲(chǔ)器中的存儲(chǔ)方式。一般來(lái)說，存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)和非順序存儲(chǔ)兩種基本類型，其中非順序存儲(chǔ)中常用的有鏈?zhǔn)酱鎯?chǔ)、Hash存儲(chǔ)和索引存儲(chǔ)。算法是解決特定問題的方法，是由若干條指令組成的有窮序列。一個(gè)算法應(yīng)具有五個(gè)基本特征：有窮性、確定性、可行性、輸入和輸出。評(píng)價(jià)一個(gè)算法的標(biāo)準(zhǔn)主要有五個(gè)方面：正確性、可讀性、健壯性、運(yùn)行時(shí)間和占用的存儲(chǔ)空間。習(xí)題一一、單選題

1.下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是

，隊(duì)列屬于

。

A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖形結(jié)構(gòu)

2.線性結(jié)構(gòu)各數(shù)據(jù)元素之間存在著

的關(guān)系，圖形結(jié)構(gòu)數(shù)據(jù)元素之間存在

的關(guān)系。

A.無(wú)關(guān)B.一對(duì)一 C.一對(duì)多 D.多對(duì)多

3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成

。

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

4.算法中的基本操作重復(fù)執(zhí)行的頻度稱為算法的

；除了考慮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)本身所占用的空間外，實(shí)現(xiàn)算法所用輔助空間的多少稱為算法的

。

A.時(shí)間復(fù)雜度 B.空間復(fù)雜度

C.硬件復(fù)雜度 D.軟件復(fù)雜度

5.算法分析的目的是①，算法分析的兩個(gè)主要方面是②。①A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)

D.分析算法的易懂性和文檔性②A.空間復(fù)雜度和時(shí)間復(fù)雜度

B.正確性

C.可讀性和文檔性

D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

6.計(jì)算機(jī)算法指的是①，它必具備輸入、輸出和②等五個(gè)特性。①A.計(jì)算方法 B.排序方法

C.解決問題的有限運(yùn)算序列 D.調(diào)度方法②A.可行性、可移植性和可擴(kuò)充性

B.可行性、確定性和有窮性

C.確定性、有窮性和穩(wěn)定性

D.易讀性、穩(wěn)定性和安全性

7.線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說法

。

A．正確 B.不正確

8.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址

。

A.必須是連續(xù)的B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以二、填空題(將正確的答案填在相應(yīng)的空中)

1.數(shù)據(jù)邏輯結(jié)構(gòu)包括集合、

、

和

四種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為

。

2.線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)

前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有

個(gè)直接前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)

后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有

個(gè)直接后繼結(jié)點(diǎn)。

3.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有

結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有

個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有

結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以

。

4.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以

。

5.線性結(jié)構(gòu)中元素之間存在

關(guān)系，樹形結(jié)構(gòu)中元素之間存在

關(guān)系，圖形結(jié)構(gòu)中元素之間存在

關(guān)系。

6.算法的五個(gè)重要特性是

、

、

、

、

。

7.下面程序段的時(shí)間復(fù)雜度是

。

for(i=0;i<n;i++)

for(j=0;j<m;j++)

a[i][j]=0;

8.下面程序段的時(shí)間復(fù)雜度是

。

i=s=0;

while(s<n)

{

i++;

s+=i;

}

9.下面程序段的時(shí)間復(fù)雜度是

。

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=b[i][j];

sum=s;

10.下面程序段的時(shí)間復(fù)雜度是

。

i=1;

while(i<=n)

i=i*3;實(shí)訓(xùn)1-1算法性能分析【實(shí)訓(xùn)目的】

1.加深對(duì)算法評(píng)價(jià)標(biāo)準(zhǔn)的理解。

2.掌握時(shí)間復(fù)雜度的分析方法?！緦?shí)訓(xùn)要求】

1.有一個(gè)數(shù)組，編程實(shí)現(xiàn)：

(1)從鍵盤輸入元素值。

(2)找出數(shù)組元素的最大值和最小值。

(3)求數(shù)組元素的平均值。

(4)求出所有小于平均值的元素的個(gè)數(shù)，并輸出其下標(biāo)和值。

2.分別編寫兩個(gè)程序，要求：

(1)編程1：分步實(shí)現(xiàn)上述功能。

(2)編程2：以最高效率實(shí)現(xiàn)上述功能。

3.從可讀性和時(shí)間復(fù)雜度上分別對(duì)兩個(gè)算法進(jìn)行性能分析?！舅惴ǚ治觥?/p>

1.分步實(shí)現(xiàn)四個(gè)功能需要四個(gè)循環(huán)；

2.為提高效率，可在一個(gè)循環(huán)中實(shí)現(xiàn)輸入、求最大值、求和的功能，第四個(gè)功能必須建立在求出平均值的基礎(chǔ)上，要另外使用一個(gè)循環(huán)來(lái)完成?！境绦蚯鍐巍克惴ㄒ唬?include<stdio.h>#defineM10 /*如要修改數(shù)組大小，不用修改程序其它部分*/main(){ inta[M],i,max