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

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

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

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

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

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

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

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

2.數(shù)據(jù)結(jié)構(gòu)的概念如果從數(shù)據(jù)元素之間的組織形式來看，可以認(rèn)為數(shù)據(jù)結(jié)構(gòu)指的是計算機所處理的數(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)一般包括以下三個方面的內(nèi)容：

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

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

(3)數(shù)據(jù)的運算，即對數(shù)據(jù)元素所進行的操作?？梢园褦?shù)據(jù)結(jié)構(gòu)定義為：對計算機處理的一批數(shù)據(jù)，首先按某種邏輯關(guān)系把它們組織起來，再按一定的存儲表示方式把它們存儲在計算機的存儲器中，然后給這批數(shù)據(jù)規(guī)定一組操作。1.2數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(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ù)元素之間除了“同屬于一個集合”的關(guān)系外，沒有其它任何關(guān)系。大街上熙熙攘攘的人群可以看成是一個集合。集合是數(shù)據(jù)結(jié)構(gòu)的一種特例，本書不予討論。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)所設(shè)計的程序沒有語法錯誤。

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

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

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

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

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

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

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

例1.1

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

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

y=y+1;①

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

x++;②

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

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

i=1; ①

while(i<=n)

i=i*2; ②

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

例1.3

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

a=0,b=1; ①

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

{

s=a+b; ②

b=1; ③

a=s; ④

}

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

例1.4

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

prime(intn)

{ inti=2;

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

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

printf("%d是一個素數(shù)\n",n); ②else

printf("%d不是一個素數(shù)\n",n); ③}

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

)。

例1.5

下面是求兩個n×n階矩陣乘法C?=?A×B的算法，分析該算法的時間復(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;

⑥

}

}}

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

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

，隊列屬于

。

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.無關(guān)B.一對一 C.一對多 D.多對多

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

。

A.動態(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í)行的頻度稱為算法的

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

。

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

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

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

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

C.分析算法的效率以求改進

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

B.正確性

C.可讀性和文檔性

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

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

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

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

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

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

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

。

A．正確 B.不正確

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

。

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)中，第一個結(jié)點

前驅(qū)結(jié)點，其余每個結(jié)點有且僅有

個直接前驅(qū)結(jié)點；最后一個結(jié)點

后繼結(jié)點，其余每個結(jié)點有且僅有

個直接后繼結(jié)點。

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

結(jié)點，其余每個結(jié)點有且只有

個前驅(qū)結(jié)點；葉子結(jié)點沒有

結(jié)點，其余每個結(jié)點的后繼結(jié)點可以

。

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

。

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

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

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

關(guān)系。

6.算法的五個重要特性是

、

、

、

、

。

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

。

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

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

a[i][j]=0;

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

。

i=s=0;

while(s<n)

{

i++;

s+=i;

}

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

。

s=0;

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

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

s+=b[i][j];

sum=s;

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

。

i=1;

while(i<=n)

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

1.加深對算法評價標(biāo)準(zhǔn)的理解。

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

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

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

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

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

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

2.分別編寫兩個程序，要求：

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

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

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

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

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