算法與數(shù)據(jù)結(jié)構(gòu)課件

1、第4章 算法與數(shù)據(jù)結(jié)構(gòu)16學(xué)時算法與數(shù)據(jù)結(jié)構(gòu)目的與要求：掌握算法與算法設(shè)計基本方法 掌握數(shù)據(jù)結(jié)構(gòu)的表示與基本操作重點與難點：算法描述方法及應(yīng)用 數(shù)據(jù)結(jié)構(gòu)及其表示方法 查找與排序算法設(shè)計本章要點算法與數(shù)據(jù)結(jié)構(gòu)4.1 算法及其表示4.2 常用算法結(jié)構(gòu)分析4.3 數(shù)據(jù)結(jié)構(gòu)及表示 2學(xué)時4.4 常用數(shù)據(jù)結(jié)構(gòu)及表示（表、樹、圖） 6學(xué)時4.5 查找與排序 4學(xué)時4.6 文件與文件操作 2學(xué)時4.7 應(yīng)用舉例 2學(xué)時 本章內(nèi)容2學(xué)時算法歷史小知識算法的中文名稱出自周髀算經(jīng)；而英文名稱Algorithm 來自于9世紀(jì)波斯數(shù)學(xué)家比阿勒.霍瓦里松的名字al-Khwarizmi，因為比阿勒.霍瓦里松在數(shù)學(xué)上提出了

2、算法這個概念。他寫的書al-jabr wal muqabalah(代數(shù)學(xué))演變成為現(xiàn)在中學(xué)的代數(shù)教科書。Ad-Khwarizmi強調(diào)求解問題是有條理的步驟。如果他能活到今天的話，他一定會被以他的名字而得名的方法的進展所感動。 “算法”原為“algorism”，意思是阿拉伯?dāng)?shù)字的運算法則，在18世紀(jì)演變?yōu)椤癮lgorithm”。第一次編寫算法是Ada Byron于1842年為巴貝奇分析機編寫求解解伯努利方程的程序，因此Ada Byron被大多數(shù)人認為是世界上第一位程序員。20世紀(jì)的英國數(shù)學(xué)家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現(xiàn)解決了算法定

3、義的難題，圖靈的思想對算法的發(fā)展起到了重要的作用 4.1算法及其表示算法就是一種解題的方法，是解題過程的精確描述。算法是由若干條指令組成的有窮序列。即由有限條可完全執(zhí)行的，有確切含義的指令（或命令，語句）所構(gòu)成。算法通俗說法算法嚴格說法算法五大特征有窮性一個算法必須總是在執(zhí)行有窮步后結(jié)束， 且每一步都可在有窮時間內(nèi)完成；確定性算法中的每一個指令比須有明確的含義， 不能有二義性；可行性算法中描述的操作都是可通過已經(jīng)實現(xiàn)的 基本運算、執(zhí)行有限次實現(xiàn)的；輸入一個算法應(yīng)有0個或多個輸入；輸出一個算法應(yīng)有1個或多個輸出。算法的表示自然語言流程圖 特定的表示算法的圖形符號偽語言 包括程序設(shè)計語言的三大基本

4、結(jié)構(gòu)及自然語言的一種語言類語言 類似高級語言的表示，例如類PASCAL、 類C語言算法的描述插入排序Insertion-Sort(A)1for j = 1 to n-12key = Aj3i = j-14while i = 0 and Ai key5Ai+1 = Ai6i = i - 17Ai+1 = keyj=1j=2j=3j=4j=52 4 5 6 1 32 4 5 6 1 32 4 5 6 6 32 4 5 5 6 32 4 4 5 6 32 2 4 5 6 31 2 4 5 6 3A0A1A2A3A4A5算法的分析與評價1）正確性（Correctness）2）可讀性（Readabili

5、ty） 3）健壯性（robustness）4）高效率與低存儲量算法的評價標(biāo)準(zhǔn)應(yīng)具有容錯處理功能。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。處理速度快；存儲容量小。時間和空間是矛盾的、實際問題的求解往往是求得時間和空間的統(tǒng)一、折中。算法的第一目的是為了閱讀和交流；可讀性有助于對算法的理解；可讀性有助于對算法的調(diào)試和修改。程序不含語法錯誤；程序?qū)捉M輸入數(shù)據(jù)程序?qū)倪x擇的、典型的、 苛刻的、帶有刁難性的幾組輸入數(shù)據(jù)；程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)能產(chǎn)生滿足規(guī)格要求的結(jié)果算法的復(fù)雜性一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比，計算一個算法的時間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量

6、級來衡量。數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個數(shù)n稱為問題的規(guī)模，當(dāng)n不斷變化時，語句的執(zhí)行次數(shù)也會變化。時間復(fù)雜度空間復(fù)雜度問題的規(guī)模 空間復(fù)雜度是指算法在計算機內(nèi)執(zhí)行時所占用的內(nèi)存開銷規(guī)模。但一般討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。時間或空間單位下數(shù)據(jù)的量的多少。空間單位一般規(guī)定為一個簡單變量（如整型、實型等）所占存儲空間的大?。粫r間單位則一般規(guī)定為執(zhí)行一個簡單語句（如賦值語句、判斷語句等）所用時間。時間復(fù)雜度表示 通常用“階”“O（數(shù)量級）”來表示。 常見的時間復(fù)雜度有：O（1）常數(shù)階；O（logn）對數(shù)階；O（n）線性階；O（n2）平方階。例如： for(i=1; i=n; i+) for

7、(j =1; j=i; j+) dij=dataij+1;問題規(guī)模與時間復(fù)雜度的關(guān)系 一般來說，計算機算法是問題規(guī)模n 的函數(shù)f(n)，算法的時間復(fù)雜度也因此記做 T(n)= mathcalO(f(n) 因此，問題的規(guī)模n 越大，算法執(zhí)行的時間的增長率與f(n) 的增長率正相關(guān)，稱作漸進時間復(fù)雜度（Asymptotic Time Complexity）。算法與建模算法/解題策略 計算模型。常用三種計算模型：數(shù)學(xué)模型 簡單、準(zhǔn)確，有成熟的計算方法。過程模擬模型 處理日常事務(wù)問題算法的模型，模型簡單易行。結(jié)構(gòu)模型 結(jié)點和邊代表運算處理和輸入/輸出狀態(tài)。有賴于常見模型結(jié)構(gòu)分析 線性方程組人口預(yù)報 微

8、分方程優(yōu)化問題 線性規(guī)劃、非線性規(guī)劃震動問題 矩陣分析；特征值、特征向量信息管理 二維數(shù)據(jù)表下棋 人工智能(樹型結(jié)構(gòu))交通管理 最佳道路選擇(圖型結(jié)構(gòu))4.2 常用算法結(jié)構(gòu)分析1.枚舉 2.搜索 深度優(yōu)先搜索 廣度優(yōu)先搜索 啟發(fā)式搜索 遺傳算法1.哈夫曼編碼 2.樹的遍歷 3.最短路徑 算法 4.最小生成樹 算法 5.最小樹形圖 6.網(wǎng)絡(luò)流 算法 7.匹配算法 1.數(shù)值分析 2.加密算法 3.排序 算法 4.檢索算法 5.隨機化算法 算法的分類（一）基本算法（二）數(shù)據(jù)結(jié)構(gòu)的算法 （三）數(shù)論與代數(shù)算法 （四）計算幾何的算法（五）圖論算法（六）動態(tài)規(guī)劃 （七）其他 常用算法及舉例遞歸法貪心法迭代法

9、分治法回溯法動態(tài)規(guī)劃法分支界限法遞歸法 基本思想遞歸法的出發(fā)點不放在初始條件上，而放在求解的目標(biāo)上，從所求的未知項出發(fā)逐次調(diào)用本身的求解過程，直到遞歸的邊界，即初始條件。而遞推是從已知的初始條件出發(fā)。遞歸算法在可計算性理論中占有重要地位，它是算法設(shè)計的有力工具，對于拓展編程思路非常有用。就遞歸算法而言并不涉及高深數(shù)學(xué)知識，只不過初學(xué)者要建立起遞歸概念不十分容易。遞歸法之計算 3！初始條件： fact(1) = 1，遞推公式：fact(n) = n*fact(n-1)分析遞歸、遞推過程遞歸法之Tower of Hanoi過程:例1 將一個盤子從A 經(jīng)B移動到 C初始ABC一個步驟: 將一個盤子從

10、A移動到CABCABC例2將兩個盤子從A 經(jīng)B移動到 CABC過程三個步驟將一個盤子從A移動到B將一個盤子從A移動到C將一個盤子從B移動到C初始ABC例3 將三個盤子從A 經(jīng)B移動到 CABC怎么做？例3 將三個盤子從A 經(jīng)B移動到 C:Towers(3, A, C, B)Towers(2, A, B, C)Towers(1, A, C, B)Towers(2, B, C, A)void Towers (int n, char Source, char Target, char Interm) if (n=1)printf(“From %c to %cn”, Source,Target);el

11、seTowers(n-1, Source, Interm, Target);Towers(1, Source, Target, Interm);Towers(n-1, Interm, Target, Source);貪心法 基本思想先依據(jù)題目的部分條件確定答案的范圍，在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完畢，若每個情況使驗證題目符合條件，則為本題的一個答案，若全部情況驗證完畢后均不符合題目的條件，則題目無解。貪心算法使一個復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復(fù)執(zhí)行過程。貪心算法之0/1背包問題從剩余的物品中，選出可以裝入背包的價值最大的物品 從剩下的物品中選擇可裝入背

12、包的重量最小的物品 從剩余物品中選擇可裝入背包的pi /wi 值最大的物品貪婪準(zhǔn)則對容量為c 的背包求解可行的背包裝載。從n 個物品中選取裝入背包的物品，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高。每件物品i 的重量為wi ，價值為pi 。0 / 1背包問題迭代法確定迭代公式，選取解的誤差；從事先估計的一個初始近似解出發(fā)，求另一個近似解；循環(huán)處理實現(xiàn)迭代過程；當(dāng)相鄰兩次近似解之差的絕對值小于或等于給定誤差，則認為最后一次得到的近似解即為問題的解。試想一下高次方程的求解分治法解一個復(fù)雜問題時，盡可能地把這個問題分解為較小部分，找出各個部分的解，然后再把各個部分的解組合

13、成整個問題的解，這就是分治法。遞歸算法就是采用分治策略將問題分解為與原問題相似的子問題的分治法。復(fù)雜問題簡單化，各個擊破！回溯法 回溯算法是所有搜索算法中最為基本的一種算法，采用了一種“走不通就掉頭”的思想作為其控制策略，尋找可行解或所有解以及最優(yōu)解。確定起始狀態(tài)值走第一步確定下一步有幾種可能選一種可能，走下一步，記下可能與本步的特征做完新一步應(yīng)該做的事回溯法之八皇后問題 該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同

14、的作者發(fā)表了40種不同的解后來有人用圖論的方法解出92種結(jié)果。 動態(tài)規(guī)劃法（ dynamic programming ）動態(tài)規(guī)劃算法的基本思想是：將待求解的問題分解成若干個相互聯(lián)系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解； 對于重復(fù)出現(xiàn)的子問題，只在第一次遇到的時候?qū)λM行求解，并把答案保存起來，讓以后再次遇到時直接引用答案，不必重新求解 。動態(tài)規(guī)劃算法的有效性依賴于待求解問題本身具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)子問題重疊性質(zhì)動態(tài)規(guī)劃法之?dāng)r截導(dǎo)彈（問題來源： 1999 年全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽高中組復(fù)賽試題第一題） 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種

15、導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被攔截的導(dǎo)彈飛來時候的高度。 樣例： INPUT 389 207 155 300 299 170 158 65 OUTPUT 6 （最多能攔截的導(dǎo)彈數(shù)） 389 300 299 170 158 65 分支界限法branch-and-bound 過程B

16、ranch-BoundQUEUE:=(s-s)，g(s)=0;LOOP：IF QUEUE=( ) THEN EXIT(FAIL);PATH:=FIRST(QUEUE)，n:=LAST(PATH);IF GOAL(n) THEN EXIT(SUCCESS);EXPAND(n)mi，計算g(mi)=g(n，mi)，REMOVE（s - n，QUEUE），ADD(s-mi，QUEUE);QUEUE中局部路徑g值最小者排在前面；GO LOOP； 分支界限法是優(yōu)先擴展當(dāng)前具有最小耗散值分支路徑的端節(jié)點n,其評價函數(shù)為f(n)=g(n)。 該算法的基本思想很簡單，實際上是建立一個局部路徑（或分支）的隊列表

17、，每次都選耗散值最小的那個分支上的端節(jié)點來擴展，直到生成出含有目標(biāo)節(jié)點的路徑為止。4.3數(shù)據(jù)結(jié)構(gòu)及表示（1）數(shù)據(jù)結(jié)構(gòu)的概念（2）數(shù)據(jù)結(jié)構(gòu)分類（3）數(shù)據(jù)的邏輯結(jié)構(gòu)（4）數(shù)據(jù)的存儲結(jié)構(gòu)（5）數(shù)據(jù)存儲結(jié)構(gòu)分類（6）邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系 （7）數(shù)據(jù)操作/運算 概念和術(shù)語DS是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合以及作用于其上的函數(shù)與運算。DS三要素：數(shù)據(jù)的邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)+數(shù)據(jù)運算。數(shù)據(jù)結(jié)構(gòu)是以數(shù)據(jù)為加工對象，研究數(shù)據(jù)組織方式和相關(guān)操作方法的學(xué)問。也可以說：DS是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。怎樣去組織一批特定的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)（DS Data Structure）根據(jù)數(shù)據(jù)元素之

18、間的邏輯關(guān)系線性結(jié)構(gòu)數(shù)據(jù)元素間呈 現(xiàn)一對一的關(guān)系；非線性結(jié)構(gòu)則呈現(xiàn)一對多的或多對多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)分類常用數(shù)據(jù)結(jié)構(gòu)鏈接表DataDataData堆棧隊列樹排序散列DataDataDataDataDataDataDataDataDataData 003 002 004 006 005 008 007001線性結(jié)構(gòu)表示0 3 5 83 0 6 4115 6 0 28 4 2 01011 100學(xué)生基本情況登記表矩陣數(shù)據(jù)結(jié)構(gòu)表示（一）非線性結(jié)構(gòu)表示JIACBDHGFE3v0v1v4245681110v3v2城市交通距離示例圖家族樹示例圖數(shù)據(jù)結(jié)構(gòu)表示（一）數(shù)據(jù)結(jié)構(gòu)二元組表示（二） 數(shù)據(jù)結(jié)構(gòu)二元組表示是

19、用一個二元素組（D，R）表示數(shù)據(jù)結(jié)構(gòu)，即DS =（D，R）其中： D為數(shù)據(jù)元素的有限集合；R為數(shù)據(jù)元素之間關(guān)系的集合，通常關(guān)系用偶對表示。二元組表示舉例（1）學(xué)生基本情況表的二元組表示為： student（D，R） D=001，002，003，004，005，006，007R=,（2）家族樹的二元組表示為：Family（D，R） D=A,B,C,D,E,F,G,H,I,JR=,（3）課題組由1名教師、13名研究生、16名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo)12名本科生。二元組表示為：Group（D，R）D =T，G1，,Gn,S11,Snm 1n3 , 1m2R =R1,R2R1

20、=|1in , 1n3R2=|1in ,1jm , 1n3 , 1m2 數(shù)據(jù)的邏輯結(jié)構(gòu) 描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)關(guān)系，而不管它們在計算機中如何存放。描述的是數(shù)據(jù)結(jié)構(gòu)的本性。集合/文件結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素除了屬于同一種類型外，別無關(guān)系。線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。如通迅錄、成績單、花名冊樹形結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。如電子字典、家譜、目錄圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。如交通線路、通信網(wǎng)絡(luò)等。 基本邏輯結(jié)構(gòu)類型特點數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)又稱物理結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(又稱映象)，即

21、數(shù)據(jù)在計算機中的存放。分為順序存儲、鏈?zhǔn)酱鎯?、索引存儲、散列存儲四種存儲類型。 數(shù)組邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)比較順序存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)點結(jié)構(gòu) 把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，數(shù)據(jù)元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，通常在程序設(shè)計中用數(shù)組表示。順序存儲是把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。連續(xù)存放。邏輯上相鄰，物理上也相鄰；結(jié)構(gòu)簡單，易實現(xiàn)；插入、刪除操作不便（需大量移動元素）。特點鏈?zhǔn)酱鎯Y(jié)構(gòu) 數(shù)據(jù)結(jié)點結(jié)構(gòu) 邏輯上相鄰的結(jié)點在物理位置可不相鄰。結(jié)點之間的邏輯關(guān)系是由附加的指針字段表示的。即在每一格數(shù)據(jù)元素中增加一個存放地址的指針，用指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實現(xiàn)鏈表間的聯(lián)系。通常用程序設(shè)計語言中的指針類型來描述。 非連續(xù)存放，借助指針來表示元素間的關(guān)系；插入、刪除操作簡單，只要修改指針即可；結(jié)構(gòu)