DS-數(shù)據(jù)結(jié)構(gòu)概述

DS-數(shù)據(jù)結(jié)構(gòu)概述第一頁(yè)，共37頁(yè)。本章重點(diǎn)難點(diǎn)重點(diǎn):

①數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及基本操作的概念及相互關(guān)系；②抽象數(shù)據(jù)類型(ADT)的概念和實(shí)現(xiàn)方法，算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。難點(diǎn):

①抽象數(shù)據(jù)類型(ADT)的概念和實(shí)現(xiàn)方法；②算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。第二頁(yè)，共37頁(yè)。1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)

處理問題的策略給出問題的數(shù)學(xué)模型編制出用計(jì)算機(jī)處理問題的指令問題構(gòu)建數(shù)學(xué)模型算法實(shí)現(xiàn)第三頁(yè)，共37頁(yè)。計(jì)算機(jī)的發(fā)展數(shù)據(jù)處理的種類數(shù)據(jù)數(shù)值數(shù)據(jù)

非數(shù)值數(shù)據(jù)

數(shù)(整數(shù),實(shí)數(shù))字符字符串文字圖形圖象聲音對(duì)客觀對(duì)象的符號(hào)表示程序原始數(shù)據(jù)結(jié)果數(shù)據(jù)軟件硬件應(yīng)用領(lǐng)域第四頁(yè)，共37頁(yè)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的原因：①計(jì)算機(jī)處理的數(shù)據(jù)量越來(lái)越大。②數(shù)據(jù)類型越來(lái)越多。③數(shù)據(jù)的結(jié)構(gòu)越來(lái)越復(fù)雜。數(shù)據(jù)結(jié)構(gòu)是一門研究“非數(shù)值計(jì)算程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作"的學(xué)科。

1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)第五頁(yè)，共37頁(yè)。

已知數(shù)據(jù)如下：結(jié)論1：雜亂無(wú)章的數(shù)據(jù)不能表達(dá)和交流。例11985782335902261011工號(hào)：1985070016電話號(hào)碼：郵編：233000身份證號(hào)碼：3461011第六頁(yè)，共37頁(yè)。

例2電話號(hào)碼簿（a1,b1）（a2,b2）（……）（an,bn）,其中，ai為某人姓名，bi為該人的電話號(hào)碼。結(jié)論2：數(shù)據(jù)之間是有聯(lián)系的。第七頁(yè)，共37頁(yè)。

例3家族的族譜:假設(shè)某家族有10個(gè)成員A,B,C,D,E,F,G,H,I,J，他們之間的血緣關(guān)系可以用如下圖表示。JIACBDHGFE結(jié)論3：數(shù)據(jù)之間是有結(jié)構(gòu)的。第八頁(yè)，共37頁(yè)。學(xué)號(hào)姓名性別出生日期入學(xué)成績(jī)所在班級(jí)00201楊潤(rùn)生男82/06/0156100計(jì)算機(jī)2

00102石磊男83/12/2151200計(jì)算機(jī)1

00202李梅女83/02/2353200計(jì)算機(jī)200301馬耀先男82/07/1250900計(jì)算機(jī)3

已知某級(jí)學(xué)生情況,要求分班按入學(xué)成績(jī)排列順序。說(shuō)明：在此類文檔管理中,可以有查找、修改、插入、刪除等操作。例4結(jié)論4：在某種數(shù)據(jù)結(jié)構(gòu)上可以定義一組運(yùn)算。第九頁(yè)，共37頁(yè)。1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)1、數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，信息的載體，能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。如整數(shù)，實(shí)數(shù)，字符串、圖象、聲音等都是數(shù)據(jù)。2、數(shù)據(jù)元素：數(shù)據(jù)的基本單位，又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。3、數(shù)據(jù)項(xiàng):是數(shù)據(jù)不可分割的最小單位。如學(xué)號(hào)、姓名等。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。4、數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。如所有班名相同的記錄集合。5、數(shù)據(jù)類型：是指一個(gè)類型和定義在這個(gè)類型上的操作集合。

分為：原子類型和結(jié)構(gòu)類型6、抽象數(shù)據(jù)類型：是指一個(gè)邏輯概念上的類型和這個(gè)類型上的操作集合。優(yōu)點(diǎn)：將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。第十頁(yè)，共37頁(yè)。抽象數(shù)據(jù)類型的定義可以由元素、元素之間的關(guān)系及操作三部分構(gòu)成。

抽象數(shù)據(jù)類型的定義格式

ADT抽象數(shù)據(jù)類型名｛

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>

｝ADT

抽象數(shù)據(jù)類型名

例如：P4例1-41.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)第十一頁(yè)，共37頁(yè)。1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。形式定義為：Data_Structure(D,R)例如：P5例1-5第十二頁(yè)，共37頁(yè)。數(shù)據(jù)結(jié)構(gòu)包括以下內(nèi)容：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)。從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)存儲(chǔ)無(wú)關(guān)，獨(dú)立于計(jì)算機(jī)。它包括以下四類基本結(jié)構(gòu)：集合：同屬一個(gè)集合線性結(jié)構(gòu)：一對(duì)一樹形結(jié)構(gòu)：一對(duì)多圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：多對(duì)多1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)第十三頁(yè)，共37頁(yè)。數(shù)據(jù)結(jié)構(gòu)類型樹圖線性表?xiàng)ｊ?duì)列串?dāng)?shù)組廣義表數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)第十四頁(yè)，共37頁(yè)。（2）數(shù)據(jù)的物理結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示，又稱存儲(chǔ)結(jié)構(gòu)。它包括：順序存儲(chǔ)結(jié)構(gòu)：借助數(shù)據(jù)元素在存儲(chǔ)器中相對(duì)位置表示邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：依靠數(shù)據(jù)元素中的指針表示元素之間的邏輯關(guān)系索引散列1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)第十五頁(yè)，共37頁(yè)。對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：①數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系，是具體關(guān)系的抽象。②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：

數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)存中的表示；③數(shù)據(jù)的運(yùn)算（或算法）

即對(duì)數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的抽象的操作。第十六頁(yè)，共37頁(yè)。1.3算法和算法描述1、算法算法是對(duì)特定問題求解步驟的一種描述，是指令的集合。算法的特性：有窮性、確定性、可行性、輸入、輸出第十七頁(yè)，共37頁(yè)。算法的基本特征有窮性：算法中的操作步驟為有限個(gè)，且每個(gè)步驟都能在有限時(shí)間內(nèi)完成。確定性：組成算法的操作必須清晰無(wú)二義性。可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。輸入：作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。些算法的字面上可以沒有輸入，實(shí)際上已被嵌入算法之中。輸出：它是一組與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。第十八頁(yè)，共37頁(yè)。2、算法設(shè)計(jì)的要求

正確性

可讀性

健壯性高效性1.3算法和算法描述第十九頁(yè)，共37頁(yè)。算法必須是“正確的”所謂算法是正確的，除了應(yīng)該滿足算法說(shuō)明中寫明的“功能”之外，應(yīng)對(duì)各組典型的帶有苛刻條件的輸入數(shù)據(jù)得出正確的結(jié)果。在算法是正確的前提下，算法的可讀性是擺在第一位的，這在當(dāng)今大型軟件需要多人合作完成的環(huán)境下是換重要的，另一方面，晦澀難讀的程序易于隱藏錯(cuò)誤而難以調(diào)試。應(yīng)有很好的“可讀性”一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡(jiǎn)單明了、易讀易懂。算法的設(shè)計(jì)要求第二十頁(yè)，共37頁(yè)。必須具有“健壯性”算法的健壯性指的是，算法應(yīng)對(duì)非法輸入的數(shù)據(jù)作出恰當(dāng)反映或進(jìn)行相應(yīng)處理，一般情況下，應(yīng)向調(diào)用它的函數(shù)返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值。算法的效率應(yīng)考慮所設(shè)計(jì)的算法具有“高效率與低存儲(chǔ)量”。高效率與低存儲(chǔ)量是矛盾的，要視具體問題而定。算法的設(shè)計(jì)要求第二十一頁(yè)，共37頁(yè)。算法描述：1.文字形式:用中文或英文這樣的文字來(lái)描述算法。2.偽碼形式:用一種仿程序設(shè)計(jì)語(yǔ)言的語(yǔ)言來(lái)描述算法。比如類C語(yǔ)言。3.程序設(shè)計(jì)語(yǔ)言形式:用某種程序設(shè)計(jì)語(yǔ)言描述算法。其優(yōu)點(diǎn)是算法不用修改，直接作為程序語(yǔ)句鍵入計(jì)算機(jī)，計(jì)算機(jī)能調(diào)用和運(yùn)行。1.3算法和算法描述第二十二頁(yè)，共37頁(yè)。算法描述：

類C語(yǔ)言比程序設(shè)計(jì)語(yǔ)言更容易描述和被理解，比文字描述的自然語(yǔ)言更接近程序設(shè)計(jì)語(yǔ)言，容易轉(zhuǎn)換成高級(jí)語(yǔ)言。

例如：P7例1-61.3算法和算法描述第二十三頁(yè)，共37頁(yè)。1.算法是對(duì)特定問題求解步驟的一種描述，是指令的集合。一個(gè)問題可以有多種算法。2.程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn)。軟件開發(fā)生命周期：需求分析→概要設(shè)計(jì)→算法設(shè)計(jì)→程序編碼→運(yùn)行維護(hù)算法和程序的區(qū)別第二十四頁(yè)，共37頁(yè)。1.程序可以是無(wú)窮的，例如：OS；算法必須是有窮的。2.程序可以是錯(cuò)誤的，算法必須是正確的。3.程序是用程序設(shè)計(jì)語(yǔ)言描述，在機(jī)器上可以運(yùn)行；算法也可以用框圖，自然語(yǔ)言等方式描述。算法和程序的區(qū)別第二十五頁(yè)，共37頁(yè)。1.4算法時(shí)空效率分析方法算法分析就是對(duì)算法質(zhì)量?jī)?yōu)劣的評(píng)價(jià)，通常分為事后統(tǒng)計(jì)和事前分析兩種方法。算法分析應(yīng)從兩個(gè)角度：依據(jù)算法編寫的程序在計(jì)算機(jī)中運(yùn)行時(shí)間的多少的度量，即時(shí)間復(fù)雜度。依據(jù)算法編寫的程序在計(jì)算機(jī)中占存儲(chǔ)空間的多少的度量，即空間復(fù)雜度。注：時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法的復(fù)雜度。第二十六頁(yè)，共37頁(yè)。1.4算法時(shí)空效率分析方法1.算法的時(shí)間復(fù)雜度程序運(yùn)行所需要的時(shí)間取決于以下因素：

(1)機(jī)器執(zhí)行指令的速度(2)書寫算法的程序設(shè)計(jì)語(yǔ)言(3)編譯產(chǎn)生的機(jī)器語(yǔ)言代碼質(zhì)量(4)算法所選用的策略

(5)問題的規(guī)模，即算法的時(shí)間效率與算法所處理的數(shù)據(jù)個(gè)數(shù)n的函數(shù)關(guān)系。第二十七頁(yè)，共37頁(yè)。算法的時(shí)間復(fù)雜度 是算法執(zhí)行的時(shí)間耗費(fèi)，是求解問題規(guī)模n的函數(shù)。記為：T(n)=O(f(n))。

(1)時(shí)間復(fù)雜度的計(jì)算方法——頻度統(tǒng)計(jì)法例1：語(yǔ)句x=x+1;執(zhí)行頻度為1，時(shí)間復(fù)雜度記為：T(n)=O(1)1.4算法時(shí)空效率分析方法第二十八頁(yè)，共37頁(yè)。

(1)時(shí)間復(fù)雜度的計(jì)算方法——頻度統(tǒng)計(jì)法例2：

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

算法的頻度=n+1

則算法的時(shí)間復(fù)雜度為O(n)1.4算法時(shí)空效率分析方法第二十九頁(yè)，共37頁(yè)。(1)時(shí)間復(fù)雜度的計(jì)算方法——頻度統(tǒng)計(jì)法例3：

for(i=1;i<=n;++i)for(j=1;j<=n;++j) x=x+1;

算法的頻度=n(n+1)

則算法的時(shí)間復(fù)雜度為O(n2)1.4算法時(shí)空效率分析方法第三十頁(yè)，共37頁(yè)。(1)時(shí)間復(fù)雜度的計(jì)算方法——頻度統(tǒng)計(jì)法例4：

for(i=1;i<=n;++i)for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];}

算法的頻度=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

則算法的時(shí)間復(fù)雜度為O(n3)1.4算法時(shí)空效率分析方法第三十一頁(yè)，共37頁(yè)。(2)有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。此時(shí)，一種辦法是討論平均時(shí)間復(fù)雜度，一種辦法是討論最壞的情況下的時(shí)間復(fù)雜度。(3)常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)<對(duì)數(shù)階O(log2n)<線性階O(n)<線性對(duì)數(shù)階O(nlog2n)<平方階O(n2)<立方階O(n3)<k次方階O(nk)<指數(shù)階O(2n)。

1.4算法時(shí)空效率分析方法第三十二頁(yè)，共37頁(yè)。討論：“不必最求高效算法，低效算法可以在高速計(jì)算機(jī)上得到補(bǔ)償。”這一說(shuō)法正確嗎？1.4算法時(shí)空效率分析方法第三十三頁(yè)，共37頁(yè)。設(shè)A1,A2,A3是求解同一問題的不同算法，其時(shí)間復(fù)雜度分別是：O(n),O(nlgn),O(N!)。C1和C2為計(jì)算機(jī)，且C2的計(jì)算速度是C1的10倍。復(fù)雜度C1可解規(guī)模C2可解規(guī)模可解規(guī)模的關(guān)系

O(n)