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

會計學(xué)1DS數(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ù)雜性分析。第1頁/共37頁1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計

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

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

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

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

已知數(shù)據(jù)如下：結(jié)論1：雜亂無章的數(shù)據(jù)不能表達和交流。例119850700163172978233000340304195902261011工號：1985070016電話號碼：3172978郵編：233000身份證號碼5頁/共37頁

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

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

00102石磊男83/12/2151200計算機1

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

已知某級學(xué)生情況,要求分班按入學(xué)成績排列順序。說明：在此類文檔管理中,可以有查找、修改、插入、刪除等操作。例4結(jié)論4：在某種數(shù)據(jù)結(jié)構(gòu)上可以定義一組運算。第8頁/共37頁1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語1、數(shù)據(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)了信息隱藏。第9頁/共37頁抽象數(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ù)語第10頁/共37頁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-5第11頁/共37頁數(shù)據(jù)結(jié)構(gòu)包括以下內(nèi)容：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)。從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)存儲無關(guān)，獨立于計算機。它包括以下四類基本結(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ù)語第12頁/共37頁數(shù)據(jù)結(jié)構(gòu)類型樹圖線性表棧隊列串?dāng)?shù)組廣義表數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)第13頁/共37頁（2）數(shù)據(jù)的物理結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的表示，又稱存儲結(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ù)語第14頁/共37頁對每種數(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)系在計算機內(nèi)存中的表示；③數(shù)據(jù)的運算（或算法）

即對數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的抽象的操作。第15頁/共37頁1.3算法和算法描述1、算法算法是對特定問題求解步驟的一種描述，是指令的集合。算法的特性：有窮性、確定性、可行性、輸入、輸出第16頁/共37頁算法的基本特征有窮性：算法中的操作步驟為有限個，且每個步驟都能在有限時間內(nèi)完成。確定性：組成算法的操作必須清晰無二義性。可行性：算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。輸入：作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。些算法的字面上可以沒有輸入，實際上已被嵌入算法之中。輸出：它是一組與輸入有確定關(guān)系的量值，是算法進行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。第17頁/共37頁2、算法設(shè)計的要求正確性可讀性健壯性高效性1.3算法和算法描述第18頁/共37頁算法必須是“正確的”所謂算法是正確的，除了應(yīng)該滿足算法說明中寫明的“功能”之外，應(yīng)對各組典型的帶有苛刻條件的輸入數(shù)據(jù)得出正確的結(jié)果。在算法是正確的前提下，算法的可讀性是擺在第一位的，這在當(dāng)今大型軟件需要多人合作完成的環(huán)境下是換重要的，另一方面，晦澀難讀的程序易于隱藏錯誤而難以調(diào)試。應(yīng)有很好的“可讀性”一個算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。算法的設(shè)計要求第19頁/共37頁必須具有“健壯性”算法的健壯性指的是，算法應(yīng)對非法輸入的數(shù)據(jù)作出恰當(dāng)反映或進行相應(yīng)處理，一般情況下，應(yīng)向調(diào)用它的函數(shù)返回一個表示錯誤或錯誤性質(zhì)的值。算法的效率應(yīng)考慮所設(shè)計的算法具有“高效率與低存儲量”。高效率與低存儲量是矛盾的，要視具體問題而定。算法的設(shè)計要求第20頁/共37頁算法描述：1.文字形式:用中文或英文這樣的文字來描述算法。2.偽碼形式:用一種仿程序設(shè)計語言的語言來描述算法。比如類C語言。3.程序設(shè)計語言形式:用某種程序設(shè)計語言描述算法。其優(yōu)點是算法不用修改，直接作為程序語句鍵入計算機，計算機能調(diào)用和運行。1.3算法和算法描述第21頁/共37頁算法描述：類C語言比程序設(shè)計語言更容易描述和被理解，比文字描述的自然語言更接近程序設(shè)計語言，容易轉(zhuǎn)換成高級語言。例如：P7例1-61.3算法和算法描述第22頁/共37頁1.算法是對特定問題求解步驟的一種描述，是指令的集合。一個問題可以有多種算法。2.程序是用某種程序設(shè)計語言對算法的具體實現(xiàn)。軟件開發(fā)生命周期：需求分析→概要設(shè)計→算法設(shè)計→程序編碼→運行維護算法和程序的區(qū)別第23頁/共37頁1.程序可以是無窮的，例如：OS；算法必須是有窮的。2.程序可以是錯誤的，算法必須是正確的。3.程序是用程序設(shè)計語言描述，在機器上可以運行；算法也可以用框圖，自然語言等方式描述。算法和程序的區(qū)別第24頁/共37頁1.4算法時空效率分析方法算法分析就是對算法質(zhì)量優(yōu)劣的評價，通常分為事后統(tǒng)計和事前分析兩種方法。算法分析應(yīng)從兩個角度：依據(jù)算法編寫的程序在計算機中運行時間的多少的度量，即時間復(fù)雜度。依據(jù)算法編寫的程序在計算機中占存儲空間的多少的度量，即空間復(fù)雜度。注：時間復(fù)雜度和空間復(fù)雜度合稱算法的復(fù)雜度。第25頁/共37頁1.4算法時空效率分析方法1.算法的時間復(fù)雜度程序運行所需要的時間取決于以下因素：

(1)機器執(zhí)行指令的速度(2)書寫算法的程序設(shè)計語言(3)編譯產(chǎn)生的機器語言代碼質(zhì)量(4)算法所選用的策略(5)問題的規(guī)模，即算法的時間效率與算法所處理的數(shù)據(jù)個數(shù)n的函數(shù)關(guān)系。第26頁/共37頁算法的時間復(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算法時空效率分析方法第27頁/共37頁

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

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

算法的頻度=n+1

則算法的時間復(fù)雜度為O(n)1.4算法時空效率分析方法第28頁/共37頁(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算法時空效率分析方法第29頁/共37頁(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算法時空效率分析方法第30頁/共37頁(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算法時空效率分析方法第31頁/共37頁討論：

“不必最求高效算法，低效算法可以在高速計算機上得到補償?！边@一說法正確嗎？1.4算法時空效率分析方法第32頁/共37頁設(shè)A1,A2,A3是求解同一問題的不同算法，其時間復(fù)雜度分別是：O(n),O(nlgn),O(N!)。C1和C2為計算機，且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é)論：“不必最求高效算法，低效算法可以在高速計算機上得到補償?！边@一說法是錯誤的!第33頁/共37頁2