《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt
《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt》由會員分享,可在線閱讀,更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt(48頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
第三章算法與數(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ù)比較:大于、小于、等于、不等于;(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ī)則組成的一個(gè)過程2.組成算法的規(guī)則是確定的、可執(zhí)行的3.每種算法必須有確定的結(jié)果,產(chǎn)生一個(gè)或多個(gè)輸出4.每個(gè)算法必須有0個(gè)(自動生成初始數(shù))或多個(gè)輸入5.解答必須在有限步內(nèi)得到,不能出現(xiàn)“死循環(huán)”我們可以得出如下的結(jié)論:算法是一個(gè)過程,這個(gè)過程由一套明確的規(guī)則組成,這些規(guī)則指定了一個(gè)操作的順序,以便用有限的步驟提供特定類型問題的解答,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ù),流程圖是采用不同的幾何圖形來描述算法的邏輯結(jié)構(gòu),每個(gè)幾何圖形表示不同性質(zhì)的操作,常用流程圖符號:,返回,1.枚舉法(窮舉法)基本思想是:先依據(jù)題目的部分條件確定答案的大致范圍在此范圍內(nèi)對所有可能的情況逐一驗(yàn)證,直到全部情況驗(yàn)證完若某個(gè)情況使驗(yàn)證符合題目的條件,則為本題的一個(gè)答案;若全部情況驗(yàn)證完后均不符合題目的條件,則問題無解,3.1.4常用算法,2.迭代法,使一個(gè)復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復(fù)執(zhí)行過程使用迭代法構(gòu)造算法的基本方法是:首先確定一個(gè)合適的迭代公式,選取一個(gè)初始近似值以及解的誤差然后用循環(huán)處理實(shí)現(xiàn)迭代過程,終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于或等于預(yù)先給定的誤差并認(rèn)為最后一次迭代得到的近似值為問題的解。,3.遞歸法,如果一個(gè)過程直接或間接地調(diào)用它自身,則稱該過程是遞歸的例:求階乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif,遞歸過程必須有一個(gè)遞歸終止條件,當(dāng)n=0時(shí)定義為1,是階乘遞歸定義的遞歸出口,遞歸則是從函數(shù)本身出發(fā),逐次上溯調(diào)用其本身求解過程,直到遞歸的出口,然后再從里向外倒推回來,得到最終的值,4.遞推法,所謂遞推法,它的數(shù)學(xué)公式也是遞歸的。只是在實(shí)現(xiàn)計(jì)算時(shí)與遞歸相反。從給定邊界出發(fā)逐步迭代到達(dá)指定計(jì)算參數(shù)。例:求階乘f(n)=n!=n(n-1)!=nf(n-1)要計(jì)算10!,可以從遞推初始條件f(0)=1出發(fā),應(yīng)用遞推公式f(n)=nf(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法,科技計(jì)算中最常見,5.分治法,解一個(gè)夏雜的問題時(shí),盡可能地把這個(gè)問題分解為較小部分,找出各個(gè)的解,然后再把各部分的解組合成整個(gè)問題的解,這就是所謂的分治法6.回溯法在那些涉及到尋找一組解的問題或者滿足某些約束條件的最優(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)做的事Enddoreturn(SUCC=TRUE)EndBacktracking,3.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ù)的邏輯結(jié)構(gòu)上的,但運(yùn)算的具體實(shí)現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的運(yùn)算有檢索、插入、刪除、更新、排序等,,2.?dāng)?shù)據(jù)結(jié)構(gòu)應(yīng)用示例例3.4識別“體”字的過程,按分支和層次組織的數(shù)據(jù),稱為:“樹形結(jié)構(gòu)”,,例3.5計(jì)算機(jī)換房系統(tǒng)中的“多角互換問題”,數(shù)據(jù)結(jié)構(gòu)叫它們?yōu)椤把h(huán)鏈表”,例3.6飯店服務(wù)系統(tǒng)中的客房預(yù)訂問題,這種結(jié)構(gòu)稱為“隊(duì)列”,是一種元素間先后次序很強(qiáng)的數(shù)據(jù)結(jié)構(gòu),例3.7管理信息系統(tǒng)中的查詢問題各種計(jì)算機(jī)管理信息系統(tǒng)中,通常相關(guān)的信息(記錄)組成一個(gè)文件,文件是一類很重要的數(shù)據(jù)結(jié)構(gòu),文件中的記錄可按順序方式組織,順序文件,導(dǎo)出的鏈表,為提高檢索效率,可將所有選修“算法分析”課的同學(xué)記錄串接到一起,這種串接稱為“加鏈”,3.2.2線性表,線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列:(a1,a2,a3,…an)n為線性表的長度(n≥0),n=0的表稱為空表數(shù)據(jù)元素呈線性關(guān)系.必存在唯一的稱為“第一個(gè)”的數(shù)據(jù)元素;必存在唯一的稱為“最后一個(gè)”的數(shù)據(jù)元素;除第一個(gè)元素外,每個(gè)元素都有且只有一個(gè)前驅(qū)元素;除最后一個(gè)元素外,每個(gè)元素都有且只有一個(gè)后繼元素。所有數(shù)據(jù)元素ai在同一個(gè)線性表中必須是相同的數(shù)據(jù)類型,,線性表按其存儲結(jié)構(gòu)可分為順序表和鏈表。用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表;用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表稱為鏈表線性表的基本運(yùn)算主要有:(1)在兩個(gè)確定的元素之間插入一個(gè)新的元素;(2)刪除線性表中某個(gè)元素;(3)按某種要求查找線性表中的一個(gè)元素,需要時(shí),還可找到元素進(jìn)行值的更新,1.順序表和一維數(shù)組將線性表中的數(shù)據(jù)元素依次存放在某個(gè)存儲區(qū)域中,所形成的表稱為順序表。一維數(shù)組就是用順序方式存儲的線性表,其下標(biāo)可看成元素的相對地址運(yùn)算:(1)插入,在線性表(a1,a2…,ai,ai+1…,an)的第i個(gè)位置插入元素x,算法如下:,PROCINSERT(VARA,VARn,i,x)If(in+1)ThenERROR(“位置不存在!”)ElseForj=nDownToiA(j+1)=A(j)NextjEndifA(i)=xn=n+1End,(2)刪除:在表長為n的線性表(a1,a2,…ai-1,ai,ai+1…an)中刪除第i個(gè)數(shù)據(jù)元素,通常還需將第i+1個(gè)至第n個(gè)元素向前推動一個(gè)位置,即(a1,a2,…,ai-1,ai+1,…,an),其算法描述如下:,PROCDELETE(VARA,VARn,I)If(in)ThenERROR(位置不存在!)ELSEFORj=iTOn-1A(j)=A(j+1)Nextjn=n-1EndifEnd,在順序表中插入或刪除元素時(shí),每進(jìn)行一次插入或刪除,都要移動近乎一半的元素。對于長度可變的線性表,必須按可能達(dá)到的最大長度分配空間,順序表的不足:,2.鏈表,(1)單鏈表(線性鏈表):鏈?zhǔn)酱鎯Φ木€性表結(jié)點(diǎn)除信息域外還含有一個(gè)指針域,用來指出其后繼結(jié)點(diǎn)的位置最后一個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn),指針?biāo)闹羔樣驗(yàn)榭?記為NIL或∧)。另外還需要設(shè)置一個(gè)指針head,指向單鏈表的第一個(gè)結(jié)點(diǎn),鏈表的一個(gè)重要特點(diǎn)是插入、刪除運(yùn)算靈活方便,不需移動結(jié)點(diǎn),只要改變結(jié)點(diǎn)中指針域的值即可,插入,刪除,(2)循環(huán)鏈表:循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為“NIL”,而是指向頭一個(gè)結(jié)點(diǎn),成為一個(gè)由鏈指針鏈結(jié)的環(huán),(3)雙向鏈表:設(shè)有一個(gè)指向后繼結(jié)點(diǎn)的指針和一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針,3.棧,棧(STACK)也是一種特殊的線性表,是一種“后進(jìn)先出”的結(jié)構(gòu),它的運(yùn)算規(guī)則受到一些約束和限定,故又稱限定性數(shù)據(jù)結(jié)構(gòu)(1)棧的結(jié)構(gòu)特點(diǎn)棧是限定僅在表尾進(jìn)行插入和刪除運(yùn)算的線性表,表尾稱為棧頂(top),表頭稱為棧底(bottom)棧的物理存儲可以用順序存儲結(jié)構(gòu),也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu),(2)棧的運(yùn)算設(shè)置一個(gè)空棧判定棧是否為空進(jìn)棧、退棧讀取棧頂元素等,4.隊(duì)列,(1)隊(duì)列的結(jié)構(gòu)特點(diǎn)隊(duì)列(Queue)是限定所有的插入只能在表的一端進(jìn)行,而所有的刪除都在表的另一端進(jìn)行的線性表表中允許插入的一端稱為隊(duì)尾(Rear),允許刪除的一端稱為隊(duì)頭(Front)隊(duì)列的操作是按先進(jìn)先出的原則進(jìn)行的隊(duì)列的物理存儲可以用順序存儲結(jié)構(gòu),也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。,(2)隊(duì)列的運(yùn)算:設(shè)置一個(gè)空隊(duì)列;判定隊(duì)列是否是空隊(duì)列;入隊(duì)列;出隊(duì)列;讀取隊(duì)頭元素等,如果隊(duì)列的容量無法預(yù)先估計(jì)時(shí),可以采用鏈表存儲結(jié)構(gòu),循環(huán)隊(duì)列的插入、刪除,,3.2.3串,串(String)可以看作一維字符數(shù)組,但其長度不恒定,可以作刪除、插入操作許多高級語言把串作為一種單獨(dú)的類型,其元素不可作四則運(yùn)算進(jìn)行連接、刪除、插入操作,用子串有時(shí)很方便子串(Substring)是串的一部分,具有串的一切特征,3.2.4樹和二叉樹1.樹和二叉樹的定義和術(shù)語,樹的邏輯結(jié)構(gòu)樹的形式化定義:樹(Tree)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T,其中有一個(gè)特定的稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的有限集T1,T2,T3,…,Tm,每一個(gè)集合本身又是一棵樹,且稱為根的子樹用表來表示樹:(A(B(E,F),C(G),D(H,I,J)))結(jié)點(diǎn)子樹個(gè)數(shù)為結(jié)點(diǎn)的度,結(jié)點(diǎn)度的最大值為該樹的度結(jié)點(diǎn)B的度為2,樹的度為3,0棵或多棵不相交的樹的集合稱為樹林二叉樹是另一種重要的樹形結(jié)構(gòu),其結(jié)構(gòu)定義為:二叉樹(BinaryTree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集,它或?yàn)榭諛?n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹和右子樹的、互不相交的二叉樹組成二叉樹的邏輯結(jié)構(gòu):二叉樹的結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹,即使在結(jié)點(diǎn)只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹,2.樹的存儲結(jié)構(gòu),樹的存儲結(jié)構(gòu)可以采用具有多個(gè)指針域的多重鏈表,結(jié)點(diǎn)中指針域的個(gè)數(shù)應(yīng)由樹的度來決定但在實(shí)際應(yīng)用中,這種存儲結(jié)構(gòu)并不方便,一般將樹轉(zhuǎn)化為二叉樹表示,進(jìn)行處理,3.二叉樹的存儲結(jié)構(gòu),可使用具有2個(gè)指針域的鏈表,LC為左指針域,指向結(jié)點(diǎn)的左子樹,RC為右指針域,指向結(jié)點(diǎn)的右子樹。亦可用數(shù)組的下標(biāo)來模擬指針,即開辟三個(gè)一維數(shù)組DATA,LC和RC分別存放結(jié)點(diǎn)的元素及其左、右指針,4.樹的二叉樹表示,每一棵都能唯一地轉(zhuǎn)換到它所對應(yīng)的二叉樹轉(zhuǎn)換方法:凡是兄弟就用線連接起來,對每個(gè)非終端結(jié)點(diǎn),除其最左孩子外,刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線,再以根結(jié)點(diǎn)為軸心,順時(shí)針旋轉(zhuǎn)450,5.樹和二叉樹的遍歷(周游),樹的遍歷根據(jù)樹的遞歸定義,有兩種遍歷樹的方法:(1)先根(次序)遍歷:若樹中只有一個(gè)根結(jié)點(diǎn),則訪問樹的根結(jié)點(diǎn);否則,首先訪問樹的根結(jié)點(diǎn),然后依次先根遍歷每棵子樹。(2)后根(次序)遍歷:若樹中只有一個(gè)根結(jié)點(diǎn),則訪問樹的根結(jié)點(diǎn);否則,首先依次后根遍歷每一棵子樹,然后訪問樹的根結(jié)點(diǎn)。,二叉樹的遍歷,(3)后序遍歷二叉樹的算法為:若二叉樹不空,則:a)后序遍歷左子樹;b)后序遍歷右子樹;c)訪問根結(jié)點(diǎn)。前圖用后序遍歷為:FEGJIHDCBA,(1)前序遍歷二叉樹算法為:若二叉樹不空,則:a)訪問根結(jié)點(diǎn);b)前序遍歷左子樹;c)前序遍歷右子樹。前圖用前序遍歷為ABEFCGDHIJ,(2)中序遍歷二叉樹的算法為:若二叉樹不空,則作:a)中序遍歷左子樹;b)訪問根結(jié)點(diǎn);c)中序遍歷右子樹。前圖用中序遍歷為:EFBGCHIJDA,3.2.5圖1.圖的概念和術(shù)語,常用G=(V,E)代表一個(gè)圖,V是結(jié)點(diǎn)的有窮集合(非空),E是邊的有窮集合(E可為空集)。若一條邊的結(jié)點(diǎn)對無序,則稱無向圖。(V1,V2)和(V2,V1)相同有向圖由頂點(diǎn)的非空有限集和邊的有限集組成。(V1,V2)和(V2,V1)表示不同邊n個(gè)頂點(diǎn)的無向圖邊的最大數(shù)目是n(n-1)/2。n個(gè)頂點(diǎn)的有向圖邊的最大數(shù)目為n2(雙環(huán)且自環(huán))。若(V1,V2)∈E,則稱V1和V2是相鄰結(jié)點(diǎn)。邊(V1,V2)是V1和V2相關(guān)聯(lián)的邊。一個(gè)結(jié)點(diǎn)的度是與該結(jié)點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。對于有向圖,則把以結(jié)點(diǎn)Vi為終點(diǎn)的邊的數(shù)目稱結(jié)點(diǎn)Vi的入度;把以Vi為始點(diǎn)的邊的數(shù)目稱為Vi的出度。出度為0的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)。,2.圖的存儲(1)圖的相鄰矩陣表示法,若G是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖,則G的相鄰矩陣是:(2)圖的鄰接表表示法用鄰接表法表示有向圖,根據(jù)需要可以保存每個(gè)結(jié)點(diǎn)的出邊表,也可以保存每個(gè)結(jié)點(diǎn)的入邊表,3.圖的遍歷(1)深度優(yōu)先遍歷,基本思想是:從圖中某個(gè)V出發(fā),訪問此結(jié)點(diǎn),再依次訪問所有與V有路徑的結(jié)點(diǎn)。完成后再另選圖中一個(gè)未被訪問的結(jié)點(diǎn)作始點(diǎn),重復(fù)上述過程,直至圖中所有結(jié)點(diǎn)都被訪問到為止。(2)廣度優(yōu)先遍歷基本思想是:從某個(gè)結(jié)點(diǎn)V出發(fā),訪問此結(jié)點(diǎn),再依次訪問V鄰接的未訪問結(jié)點(diǎn)。再從這些結(jié)點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷,直至圖中所有被訪問過的結(jié)點(diǎn)的相鄰結(jié)點(diǎn)都被訪問到。完成后另選圖中一個(gè)未曾訪問的結(jié)點(diǎn)作始點(diǎn),重復(fù)上述過程,直至圖中所有結(jié)點(diǎn)都被訪問到為止,3.3查找,3.3.1基本概念關(guān)鍵字是數(shù)據(jù)元素中可以唯一標(biāo)識一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng),比如學(xué)號、身份證號等,查找是根據(jù)給定的關(guān)鍵值,在一組數(shù)據(jù)中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過程確切定義:給定一個(gè)值K,在含有n個(gè)記錄的文件中進(jìn)行搜索,尋找一個(gè)其關(guān)鍵字等于給定的K值的記錄,如找到,則輸出記錄或記錄在文件中的相對位置稱查找成功;否則輸出查找不成功的信息稱查找失敗。,3.3.2查找算法1.順序查找,順序查找的方法是:用待查關(guān)鍵字值與線性表中各結(jié)點(diǎn)的關(guān)鍵字值逐個(gè)比較,直到找出相等的關(guān)鍵字值;或找遍所有結(jié)點(diǎn)都找不到,即查找失敗順序查找的優(yōu)點(diǎn)是對線性表結(jié)點(diǎn)的邏輯次序無要求,對線性表的存儲結(jié)構(gòu)無要求,缺點(diǎn)是平均檢索長度長,為n/22.二分法查找要求線性表結(jié)點(diǎn)按關(guān)鍵字碼值排好,且以順序方式存儲用要查找的碼值X與中間位置結(jié)點(diǎn)的關(guān)鍵碼值W相比較:(1)X=W,此時(shí)已經(jīng)查找成功,查找結(jié)束。(2)X>W,表明X在表的后半部分,取后半部分進(jìn)行查找(3)X- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 算法與數(shù)據(jù)結(jié)構(gòu) 算法 數(shù)據(jù)結(jié)構(gòu) PPT 課件
鏈接地址:http://www.820124.com/p-11580205.html