資源描述：
《《算法與數(shù)據(jù)結(jié)構(gòu)》ppt課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第三章算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)程序首先要了解需要研究要解決的問題，提出適當(dāng)?shù)挠?jì)算模型并列出解決問題的方法和步驟,模型一旦建立起來，就要選擇合適的算法，并將解題步驟表述出來本章著重討論解決問題的核心--算法以及算法的處理對象--數(shù)據(jù)的結(jié)構(gòu)3．1算法解題過程的準(zhǔn)確、完整的描述稱作解該問題的算法程序就是用計(jì)算機(jī)語言表述的算法，流程圖就是圖形化了的算法程序＝算法＋數(shù)據(jù)結(jié)構(gòu)3.1.1算法的兩要素算法由操作與控制結(jié)構(gòu)兩要素組成1.操作(1)邏輯運(yùn)算：“與”、“或”、“非”；(2)算術(shù)運(yùn)算：加、減、乘、除；(3)數(shù)據(jù)比較：大于
2、、小于、等于、不等于；(4)數(shù)據(jù)傳送：輸入、輸出、賦值。2.控制結(jié)構(gòu)算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次序。用流程圖可以形象地表示出算法的控制結(jié)構(gòu)任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三種控制結(jié)構(gòu)組合而成3.1.2算法的特征1.算法是由一套計(jì)算規(guī)則組成的一個過程2.組成算法的規(guī)則是確定的、可執(zhí)行的3.每種算法必須有確定的結(jié)果，產(chǎn)生一個或多個輸出4.每個算法必須有0個（自動生成初始數(shù)）或多個輸入5.解答必須在有限步內(nèi)得到,不能出現(xiàn)“死循環(huán)”我們可以得出如下的結(jié)論：算法是一個過程，這個過程由一套明確的規(guī)則組成，
3、這些規(guī)則指定了一個操作的順序，以便用有限的步驟提供特定類型問題的解答3.1.3算法的表示算法設(shè)計(jì)一般是由粗到細(xì)的過程，一般可以使用下面幾種類型的工具描述算法:1.自然語言自然語言描述算法通俗易懂，但它有著難以克服的缺陷：(1)易產(chǎn)生歧義性(2)語句繁瑣冗長，很難清楚地表達(dá)算法的邏輯流程(3)當(dāng)今的計(jì)算機(jī)尚不能處理用自然語言表示的算法2.專用工具常用的有流程圖、PAD圖和N-S圖、偽代碼等3.算法描述語言為了便于轉(zhuǎn)換成某種編程語言，一般采用準(zhǔn)程序設(shè)計(jì)語言作算法描述語言。在本書中為類VB語言繼續(xù)流程圖是采用不同
4、的幾何圖形來描述算法的邏輯結(jié)構(gòu)，每個幾何圖形表示不同性質(zhì)的操作常用流程圖符號：返回1.枚舉法（窮舉法）基本思想是：先依據(jù)題目的部分條件確定答案的大致范圍在此范圍內(nèi)對所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完若某個情況使驗(yàn)證符合題目的條件，則為本題的一個答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問題無解3.1.4常用算法2.迭代法使一個復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復(fù)執(zhí)行過程使用迭代法構(gòu)造算法的基本方法是：首先確定一個合適的迭代公式，選取一個初始近似值以及解的誤差然后用循環(huán)處理實(shí)現(xiàn)迭代過程
5、，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于或等于預(yù)先給定的誤差并認(rèn)為最后一次迭代得到的近似值為問題的解。3.遞歸法如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的例：求階乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif遞歸過程必須有一個遞歸終止條件，當(dāng)n=0時定義為1，是階乘遞歸定義的遞歸出口遞歸則是從函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值4.遞推法所謂遞推法，它
6、的數(shù)學(xué)公式也是遞歸的。只是在實(shí)現(xiàn)計(jì)算時與遞歸相反。從給定邊界出發(fā)逐步迭代到達(dá)指定計(jì)算參數(shù)。例：求階乘f(n)＝n!＝n×(n-1)!＝n×f(n-1)要計(jì)算10!，可以從遞推初始條件f(0)=1出發(fā)，應(yīng)用遞推公式f(n)=n×f(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，科技計(jì)算中最常見5.分治法解一個夏雜的問題時，盡可能地把這個問題分解為較小部分，找出各個的解，然后再把各部分的解組合成整個問題的解，這就是所謂的分治法6.回溯法在那些涉
7、及到尋找一組解的問題或者滿足某些約束條件的最優(yōu)解的問題中，有許多可以用回溯法來求解回溯法的算法是：ProcBacktracking(succ:Boolean)確定起始狀態(tài)值走第一步確定下一步還有幾種可能選一可能走下一步，記住可能和本步特征做完新一步應(yīng)做的事While目標(biāo)未達(dá)到do確定下一步有幾種可能While沒有可能and還有上一步do回退上一步查有無下一可能EnddoIf上一步?jīng)]有了Thenreturn(SUCC=FALSE)EndIf選一可能走一步，記住可能和本步特征做完新一步應(yīng)做的事Enddoretu
8、rn(SUCC=TRUE)EndBacktracking3.2數(shù)據(jù)結(jié)構(gòu)3.2.1數(shù)據(jù)結(jié)構(gòu)概述。1．?dāng)?shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算數(shù)據(jù)的邏輯結(jié)構(gòu)：Data-Structure＝(D,R)其中：D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。線性數(shù)據(jù)結(jié)構(gòu)有線性表、棧、隊(duì)列、串、數(shù)組和文件；非線性數(shù)據(jù)結(jié)構(gòu)有樹和圖程序中的數(shù)據(jù)運(yùn)算是定義在數(shù)據(jù)的邏
