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