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

DS數(shù)據(jù)結(jié)構(gòu)概述DS數(shù)據(jù)結(jié)構(gòu)概述DS數(shù)據(jù)結(jié)構(gòu)概述本章重點難點重點:①數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以與基本操作的概念與相互關(guān)系；②抽象數(shù)據(jù)類型(ADT)的概念和實現(xiàn)方法，算法的時間復(fù)雜性和空間復(fù)雜性分析。難點:①抽象數(shù)據(jù)類型(ADT)的概念和實現(xiàn)方法；②算法的時間復(fù)雜性和空間復(fù)雜性分析。2通過閱讀文學(xué)作品，我們能提高文學(xué)鑒賞水平，培養(yǎng)文學(xué)情趣；DS數(shù)據(jù)結(jié)構(gòu)概述DS數(shù)據(jù)結(jié)構(gòu)概述DS數(shù)據(jù)結(jié)構(gòu)概述本章重點難點本章重點難點重點:

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

①抽象數(shù)據(jù)類型(ADT)的概念和實現(xiàn)方法；②算法的時間復(fù)雜性和空間復(fù)雜性分析。2本章重點難點重點:21.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計

處理問題的策略給出問題的數(shù)學(xué)模型編制出用計算機(jī)處理問題的指令問題構(gòu)建數(shù)學(xué)模型算法實現(xiàn)31.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計處計算機(jī)的發(fā)展數(shù)據(jù)處理的種類數(shù)據(jù)數(shù)值數(shù)據(jù)

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

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

1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)5學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的原因：數(shù)據(jù)結(jié)構(gòu)是一門研究“非數(shù)值計算程

已知數(shù)據(jù)如下：結(jié)論1：雜亂無章的數(shù)據(jù)不能表達(dá)和交流。例11985782335902261011工號：1985070016電話號碼：郵編：233000身份證號碼：34610116結(jié)論1：雜亂無章的數(shù)據(jù)不能表達(dá)和交流。例1198578233

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

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

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

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

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

分為：原子類型和結(jié)構(gòu)類型6、抽象數(shù)據(jù)類型：是指一個邏輯概念上的類型和這個類型上的操作集合。優(yōu)點：將數(shù)據(jù)和操作封裝在一起實現(xiàn)了信息隱藏。101.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語1、數(shù)據(jù)：對客觀事物的符號抽象數(shù)據(jù)類型的定義可以由元素、元素之間的關(guān)系與操作三部分構(gòu)成。

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

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

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

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

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

｝ADT

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

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

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

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

即對數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的抽象的操作。16對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：161.3算法和算法描述1、算法算法是對特定問題求解步驟的一種描述，是指令的集合。算法的特性：有窮性、確定性、可行性、輸入、輸出171.3算法和算法描述1、算法17算法的基本特征有窮性：算法中的操作步驟為有限個，且每個步驟都能在有限時間內(nèi)完成。確定性：組成算法的操作必須清晰無二義性?？尚行裕核惴ㄖ械乃胁僮鞫急仨氉銐蚧?，都可以通過已經(jīng)實現(xiàn)的基本操作運(yùn)算有限次實現(xiàn)之。輸入：作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。些算法的字面上可以沒有輸入，實際上已被嵌入算法之中。輸出：它是一組與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。18算法的基本特征有窮性：算法中的操作步驟為有限個，且每個步驟2、算法設(shè)計的要求

正確性

可讀性

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

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

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

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

(5)問題的規(guī)模，即算法的時間效率與算法所處理的數(shù)據(jù)個數(shù)n的函數(shù)關(guān)系。271.4算法時空效率分析方法1.算法的時間復(fù)雜度27算法的時間復(fù)雜度 是算法執(zhí)行的時間耗費，是求解問題規(guī)模n的函數(shù)。記為：T(n)=O(f(n))。

(1)時間復(fù)雜度的計算方法——頻度統(tǒng)計法例1：語句x=x+1;執(zhí)行頻度為1，時間復(fù)雜度記為：T(n)=O(1)1.4算法時空效率分析方法28算法的時間復(fù)雜度1.4算法時空效率分析方法28

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

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

算法的頻度=n+1

則算法的時間復(fù)雜度為O(n)1.4算法時空效率分析方法29(1)時間復(fù)雜度的計算方法——頻度統(tǒng)計法1.4算法時空(1)時間復(fù)雜度的計算方法——頻度統(tǒng)計法例3：

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

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

則算法的時間復(fù)雜度為O(n2)1.4算法時空效率分析方法30(1)時間復(fù)雜度的計算方法——頻度統(tǒng)計法1.4算法時空效(1)時間復(fù)雜度的計算方法——頻度統(tǒng)計法例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

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

1.4算法時空效率分析方法32(2)有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入討論：“不必最求高效算法，低效算法可以在高速計算機(jī)上得到補(bǔ)償。”這一說法正確嗎？1.4算法時空效率分析方法33討論：1.4算法時空效率分析方法33設(shè)A1,A2,A3是求解同一問題的不同算法，其時間復(fù)雜度分別是：O(n),O(nlgn),O(N!)。C1和C2為計算機(jī)，且C2的計算速度是C1的10倍。復(fù)雜度C1可解規(guī)模C2可解規(guī)?？山庖?guī)模的關(guān)系

O(n)N11N21N21=10N11O(nlgn)N12N22N22=10N12O(N!)N13N23N23=N13+小常數(shù)1.4算法時空效率分析方法結(jié)論：“不必最求高效算法，低效算法可以在高速計算機(jī)上得到補(bǔ)償?！边@一說法是錯誤的!34設(shè)A1,A2,A3是求解同一問題的不同算法，其時間復(fù)雜度分別2.算法的空間復(fù)