會計學1DS數(shù)據(jù)結構概述本章重點難點重點:

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

①抽象數(shù)據(jù)類型(ADT)的概念和實現(xiàn)方法；②算法的時間復雜性和空間復雜性分析。第1頁/共37頁1.1為什么要學習數(shù)據(jù)結構算法+數(shù)據(jù)結構=程序設計

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

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

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

1.1為什么要學習數(shù)據(jù)結構第4頁/共37頁

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

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

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

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

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

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

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

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

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

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

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

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

｝ADT

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

例如：P4例1-41.2數(shù)據(jù)結構的有關概念和術語第10頁/共37頁1.2數(shù)據(jù)結構的有關概念和術語數(shù)據(jù)結構：相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。

形式定義為：Data_Structure(D,R)例如：P5例1-5第11頁/共37頁數(shù)據(jù)結構包括以下內(nèi)容：（1）數(shù)據(jù)的邏輯結構。從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)存儲無關，獨立于計算機。它包括以下四類基本結構：集合：同屬一個集合線性結構：一對一樹形結構：一對多圖狀結構或網(wǎng)狀結構：多對多1.2數(shù)據(jù)結構的有關概念和術語第12頁/共37頁數(shù)據(jù)結構類型樹圖線性表棧隊列串數(shù)組廣義表數(shù)據(jù)結構線性結構非線性結構第13頁/共37頁（2）數(shù)據(jù)的物理結構，數(shù)據(jù)結構在計算機存儲器中的表示，又稱存儲結構。它包括：順序存儲結構：借助數(shù)據(jù)元素在存儲器中相對位置表示邏輯關系鏈式存儲結構：依靠數(shù)據(jù)元素中的指針表示元素之間的邏輯關系索引散列1.2數(shù)據(jù)結構的有關概念和術語第14頁/共37頁對每種數(shù)據(jù)結構，主要討論如下三方面的問題：①數(shù)據(jù)的邏輯結構

數(shù)據(jù)元素之間的邏輯關系，是具體關系的抽象。②數(shù)據(jù)的存儲結構(物理結構)：

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

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

(1)機器執(zhí)行指令的速度(2)書寫算法的程序設計語言(3)編譯產(chǎn)生的機器語言代碼質量(4)算法所選用的策略(5)問題的規(guī)模，即算法的時間效率與算法所處理的數(shù)據(jù)個數(shù)n的函數(shù)關系。第26頁/共37頁算法的時間復雜度 是算法執(zhí)行的時間耗費，是求解問題規(guī)模n的函數(shù)。記為：T(n)=O(f(n))。

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

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

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

算法的頻度=n+1

則算法的時間復雜度為O(n)1.4算法時空效率分析方法第28頁/共37頁(1)時間復雜度的計算方法——頻度統(tǒng)計法例3：

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

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

則算法的時間復雜度為O(n2)1.4算法時空效率分析方法第29頁/共37頁(1)時間復雜度的計算方法——頻度統(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

則算法的時間復雜度為O(n3)1.4算法時空效率分析方法第30頁/共37頁(2)有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。此時，一種辦法是討論平均時間復雜度，一種辦法是討論最壞的情況下的時間復雜度。(3)常見的時間復雜度按數(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頁設A1,A2,A3是求解同一問題的不同算法，其時間復雜度分別是：O(n),O(nlgn),O(N!)。C1和C2為計算機，且C2的計算速度是C1的10倍。復雜度C1可解規(guī)模C2可解規(guī)模可解規(guī)模的關系

O(n)N11N21N21=10N11O(nlgn)N12N22N22=10N12O(N!)N13N23N23=N13+小常數(shù)1.4算法時空效率分析方法結論：“不必最求高效算法，低效算法可以在高速計算機上得到補償。”這一說法是錯誤的!第33頁/共37頁2