第三章算法與數(shù)據(jù)結(jié)構,設計程序首先要了解需要研究要解決的問題，提出適當?shù)挠嬎隳Ｐ筒⒘谐鼋鉀Q問題的方法和步驟,模型一旦建立起來，就要選擇合適的算法，并將解題步驟表述出來本章著重討論解決問題的核心-算法以及算法的處理對象-數(shù)據(jù)的結(jié)構,31算法,解題過程的準確、完整的描述稱作解該問題的算法程序就是用計算機語言表述的算法，流程圖就是圖形化了的算法程序算法數(shù)據(jù)結(jié)構3.1.1算法的兩要素算法由操作與控制結(jié)構兩要素組成1.操作,(1)邏輯運算：“與”、“或”、“非”；(2)算術運算：加、減、乘、除；(3)數(shù)據(jù)比較：大于、小于、等于、不等于；(4)數(shù)據(jù)傳送：輸入、輸出、賦值。,2.控制結(jié)構,算法的控制結(jié)構，決定了各操作的執(zhí)行次序。用流程圖可以形象地表示出算法的控制結(jié)構任何復雜的算法都可以用順序、選擇、循環(huán)三種控制結(jié)構組合而成,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算法的表示,算法設計一般是由粗到細的過程，一般可以使用下面幾種類型的工具描述算法:1.自然語言自然語言描述算法通俗易懂，但它有著難以克服的缺陷：(1)易產(chǎn)生歧義性(2)語句繁瑣冗長，很難清楚地表達算法的邏輯流程(3)當今的計算機尚不能處理用自然語言表示的算法2.專用工具常用的有流程圖、PAD圖和N-S圖、偽代碼等3.算法描述語言為了便于轉(zhuǎn)換成某種編程語言，一般采用準程序設計語言作算法描述語言。在本書中為類VB語言繼續(xù),流程圖是采用不同的幾何圖形來描述算法的邏輯結(jié)構，每個幾何圖形表示不同性質(zhì)的操作,常用流程圖符號：,返回,1.枚舉法（窮舉法）基本思想是：先依據(jù)題目的部分條件確定答案的大致范圍在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解,3.1.4常用算法,2.迭代法,使一個復雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復執(zhí)行過程使用迭代法構造算法的基本方法是：首先確定一個合適的迭代公式，選取一個初始近似值以及解的誤差然后用循環(huán)處理實現(xiàn)迭代過程，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于或等于預先給定的誤差并認為最后一次迭代得到的近似值為問題的解。,3.遞歸法,如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的例：求階乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif,遞歸過程必須有一個遞歸終止條件，當n=0時定義為1，是階乘遞歸定義的遞歸出口,遞歸則是從函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值,4.遞推法,所謂遞推法，它的數(shù)學公式也是遞歸的。只是在實現(xiàn)計算時與遞歸相反。從給定邊界出發(fā)逐步迭代到達指定計算參數(shù)。例：求階乘f(n)n!n(n-1)!nf(n-1)要計算10!，可以從遞推初始條件f(0)=1出發(fā)，應用遞推公式f(n)=nf(n-1)逐步求出f(1)、f(2)、f(9)、最后求出f(10)的值遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，科技計算中最常見,5.分治法,解一個夏雜的問題時，盡可能地把這個問題分解為較小部分，找出各個的解，然后再把各部分的解組合成整個問題的解，這就是所謂的分治法6.回溯法在那些涉及到尋找一組解的問題或者滿足某些約束條件的最優(yōu)解的問題中，有許多可以用回溯法來求解,回溯法的算法是：,ProcBacktracking(succ:Boolean)確定起始狀態(tài)值走第一步確定下一步還有幾種可能選一可能走下一步，記住可能和本步特征做完新一步應做的事While目標未達到do確定下一步有幾種可能While沒有可能and還有上一步do回退上一步查有無下一可能EnddoIf上一步?jīng)]有了Thenreturn(SUCC=FALSE)EndIf選一可能走一步，記住可能和本步特征做完新一步應做的事Enddoreturn(SUCC=TRUE)EndBacktracking,3.2數(shù)據(jù)結(jié)構3.2.1數(shù)據(jù)結(jié)構概述。,1數(shù)據(jù)結(jié)構的研究內(nèi)容數(shù)據(jù)的邏輯結(jié)構、數(shù)據(jù)的存儲結(jié)構、數(shù)據(jù)的運算數(shù)據(jù)的邏輯結(jié)構：Data-Structure(D,R)其中：D是數(shù)據(jù)元素的集合，R是D上關系的集合一般將數(shù)據(jù)結(jié)構分為兩大類：線性數(shù)據(jù)結(jié)構和非線性數(shù)據(jù)結(jié)構。線性數(shù)據(jù)結(jié)構有線性表、棧、隊列、串、數(shù)組和文件；非線性數(shù)據(jù)結(jié)構有樹和圖程序中的數(shù)據(jù)運算是定義在數(shù)據(jù)的邏輯結(jié)構上的，但運算的具體實現(xiàn)要在存儲結(jié)構上進行。每種邏輯結(jié)構都有一個運算集合。常用的運算有檢索、插入、刪除、更新、排序等,2數(shù)據(jù)結(jié)構應用示例例3.4識別“體”字的過程,按分支和層次組織的數(shù)據(jù)，稱為：“樹形結(jié)構”,例3.5計算機換房系統(tǒng)中的“多角互換問題”,數(shù)據(jù)結(jié)構叫它們?yōu)椤把h(huán)鏈表”,例3.6飯店服務系統(tǒng)中的客房預訂問題,這種結(jié)構稱為“隊列”，是一種元素間先后次序很強的數(shù)據(jù)結(jié)構,例3.7管理信息系統(tǒng)中的查詢問題各種計算機管理信息系統(tǒng)中，通常相關的信息(記錄)組成一個文件,文件是一類很重要的數(shù)據(jù)結(jié)構,文件中的記錄可按順序方式組織,順序文件,導出的鏈表,為提高檢索效率，可將所有選修“算法分析”課的同學記錄串接到一起，這種串接稱為“加鏈”,3.2.2線性表,線性表的邏輯結(jié)構是n個數(shù)據(jù)元素的有限序列:(a1,a2,a3,an)n為線性表的長度(n0)，n=0的表稱為空表數(shù)據(jù)元素呈線性關系.必存在唯一的稱為“第一個”的數(shù)據(jù)元素;必存在唯一的稱為“最后一個”的數(shù)據(jù)元素；除第一個元素外，每個元素都有且只有一個前驅(qū)元素；除最后一個元素外，每個元素都有且只有一個后繼元素。所有數(shù)據(jù)元素ai在同一個線性表中必須是相同的數(shù)據(jù)類型,線性表按其存儲結(jié)構可分為順序表和鏈表。用順序存儲結(jié)構存儲的線性表稱為順序表；用鏈式存儲結(jié)構存儲的線性表稱為鏈表線性表的基本運算主要有：(1)在兩個確定的元素之間插入一個新的元素；(2)刪除線性表中某個元素；(3)按某種要求查找線性表中的一個元素，需要時，還可找到元素進行值的更新,1.順序表和一維數(shù)組將線性表中的數(shù)據(jù)元素依次存放在某個存儲區(qū)域中,所形成的表稱為順序表。一維數(shù)組就是用順序方式存儲的線性表，其下標可看成元素的相對地址運算：(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+1an)中刪除第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,在順序表中插入或刪除元素時，每進行一次插入或刪除，都要移動近乎一半的元素。對于長度可變的線性表，必須按可能達到的最大長度分配空間,順序表的不足：,2鏈表,(1）單鏈表(線性鏈表):鏈式存儲的線性表結(jié)點除信息域外還含有一個指針域，用來指出其后繼結(jié)點的位置最后一個結(jié)點沒有后繼結(jié)點，指針它的指針域為空(記為NIL或)。另外還需要設置一個指針head，指向單鏈表的第一個結(jié)點,鏈表的一個重要特點是插入、刪除運算靈活方便，不需移動結(jié)點，只要改變結(jié)點中指針域的值即可,插入,刪除,(2）循環(huán)鏈表：循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個結(jié)點的指針域不為“NIL”，而是指向頭一個結(jié)點，成為一個由鏈指針鏈結(jié)的環(huán),(3）雙向鏈表：設有一個指向后繼結(jié)點的指針和一個指向前驅(qū)結(jié)點的指針,3棧,棧(STACK)也是一種特殊的線性表，是一種“后進先出”的結(jié)構，它的運算規(guī)則受到一些約束和限定，故又稱限定性數(shù)據(jù)結(jié)構(1）棧的結(jié)構特點棧是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂(top)，表頭稱為棧底(bottom)棧的物理存儲可以用順序存儲結(jié)構，也可以用鏈式存儲結(jié)構,(2）棧的運算設置一個空棧判定棧是否為空進棧、退棧讀取棧頂元素等,4隊列,(1）隊列的結(jié)構特點隊列(Queue)是限定所有的插入只能在表的一端進行，而所有的刪除都在表的另一端進行的線性表表中允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)隊列的操作是按先進先出的原則進行的隊列的物理存儲可以用順序存儲結(jié)構，也可以用鏈式存儲結(jié)構。,(2）隊列的運算：設置一個空隊列；判定隊列是否是空隊列；入隊列；出隊列；讀取隊頭元素等,如果隊列的容量無法預先估計時，可以采用鏈表存儲結(jié)構,循環(huán)隊列的插入、刪除,3.2.3串,串(String)可以看作一維字符數(shù)組，但其長度不恒定，可以作刪除、插入操作許多高級語言把串作為一種單獨的類型，其元素不可作四則運算進行連接、刪除、插入操作，用子串有時很方便子串(Substring)是串的一部分，具有串的一切特征,3.2.4樹和二叉樹1.樹和二叉樹的定義和術語,樹的邏輯結(jié)構樹的形式化定義：樹(Tree)是由一個或多個結(jié)點組成的有限集合T，其中有一個特定的稱為根的結(jié)點；其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,T3,Tm，每一個集合本身又是一棵樹，且稱為根的子樹用表來表示樹：(A(B(E,F),C(G),D(H,I,J)結(jié)點子樹個數(shù)為結(jié)點的度,結(jié)點度的最大值為該樹的度結(jié)點B的度為2，樹的度為3,0棵或多棵不相交的樹的集合稱為樹林二叉樹是另一種重要的樹形結(jié)構，其結(jié)構定義為：二叉樹(BinaryTree)是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的、互不相交的二叉樹組成二叉樹的邏輯結(jié)構：二叉樹的結(jié)點的子樹要區(qū)分左子樹和右子樹，即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹,2.樹的存儲結(jié)構,樹的存儲結(jié)構可以采用具有多個指針域的多重鏈表，結(jié)點中指針域的個數(shù)應由樹的度來決定但在實際應用中，這種存儲結(jié)構并不方便，一般將樹轉(zhuǎn)化為二叉樹表示，進行處理,3.二叉樹的存儲結(jié)構,可使用具有2個指針域的鏈表，LC為左指針域，指向結(jié)點的左子樹，RC為右指針域，指向結(jié)點的右子樹。亦可用數(shù)組的下標來模擬指針，即開辟三個一維數(shù)組DATA，LC和RC分別存放結(jié)點的元素及其左、右指針,4.樹的二叉樹表示,每一棵都能唯一地轉(zhuǎn)換到它所對應的二叉樹轉(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.圖的概念和術語,常用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相關聯(lián)的邊。一個結(jié)點的度是與該結(jié)點相關聯(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é)點作始點，重復上述過程，直至圖中所有結(jié)點都被訪問到為止。(2)廣度優(yōu)先遍歷基本思想是：從某個結(jié)點V出發(fā)，訪問此結(jié)點，再依次訪問V鄰接的未訪問結(jié)點。再從這些結(jié)點出發(fā)進行廣度優(yōu)先遍歷，直至圖中所有被訪問過的結(jié)點的相鄰結(jié)點都被訪問到。完成后另選圖中一個未曾訪問的結(jié)點作始點，重復上述過程，直至圖中所有結(jié)點都被訪問到為止,3.3查找,3.3.1基本概念關鍵字是數(shù)據(jù)元素中可以唯一標識一個數(shù)據(jù)元素的數(shù)據(jù)項，比如學號、身份證號等，查找是根據(jù)給定的關鍵值，在一組數(shù)據(jù)中確定一個其關鍵字等于給定值的數(shù)據(jù)元素的過程確切定義：給定一個值K，在含有n個記錄的文件中進行搜索，尋找一個其關鍵字等于給定的K值的記錄，如找到，則輸出記錄或記錄在文件中的相對位置稱查找成功；否則輸出查找不成功的信息稱查找失敗。,3.3.2查找算法1.順序查找,順序查找的方法是：用待查關鍵字值與線性表中各結(jié)點的關鍵字值逐個比較，直到找出相等的關鍵字值;或找遍所有結(jié)點都找不到,即查找失敗順序查找的優(yōu)點是對線性表結(jié)點的邏輯次序無要求,對線性表的存儲結(jié)構無要求,缺點是平均檢索長度長,為n/22.二分法查找要求線性表結(jié)點按關鍵字碼值排好，且以順序方式存儲用要查找的碼值X與中間位置結(jié)點的關鍵碼值W相比較：(1)X=W，此時已經(jīng)查找成功，查找結(jié)束。(2)X>W,表明X在表的后半部分,取后半部分進行查找(3)X<W,表明X在表的前半部分，取前半部分進行查找二分法查找的優(yōu)點是平均檢索長度小，為log2n,3.分塊查找,要求文件中記錄關鍵字“分塊有序”,即前一塊中最大關鍵字小于后一塊中最小關鍵字,而塊內(nèi)的關鍵字不一定有序分塊查找的基本思想：先抽取各塊中的最大關鍵字構成一個索引表，由于文件中的記錄按關鍵字分塊有序，則索引表呈遞增有序狀態(tài)。查找分兩步進行:第一步先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊，第二步在已限定的那一塊中進行順序查找用分塊查找的文件不一定分成大小相等的若干塊，塊大小及其分法可根據(jù)文件的特征來定。分塊查找不僅適用于順序方式存儲的順序表，也適用于線性鏈表方式存儲的文件,3.4排序3.4.1基本概念,設含有n個記錄的文件R1，R2，Rn,其相應的關鍵字為K1，K2，Kn,需確定一種排列P(1),P(2)P(n)使其相應的關鍵字滿足遞增(或遞減)關系：KP(1)KP(2)KP(n)或KP(1)KP(2)KP(n)使上述文件成為一個按其關鍵字線性有序的文件RP(1)，RP(2)，RP(n)，這種運算就稱為排序內(nèi)排序指當文件的數(shù)據(jù)量不太大時，全部信息放在內(nèi)存中處理的排序方法。當文件的數(shù)據(jù)量較大時，排序過程中需要在內(nèi)、外存之間不斷地進行數(shù)據(jù)交換才能達到排序的目的，這種排序稱為外排序,3.4.2插入排序,基本思想是：每步將一個待排序的記錄，按關鍵碼值的大小插入到前面已排序的適當位置上，直到全部插完止1.直接插入排序：在排好的序列中用順序法查找插入位置，找到后將其后記錄后移一個位置，插入新記錄。排序n個記錄的文件，關鍵碼比較次數(shù)為n2量級，記錄移動個數(shù)也為n2量級2.二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移動其后記錄插入新記錄。關鍵字比較次數(shù)降為nlog2n量級，記錄移動個數(shù)仍為n2量級,3.4.3選擇排序,基本思想是：每次從待排序的記錄中選出關鍵字最小(或最大)的記錄，順序放在已排序的記錄序列的最后，直到全部排完為止3.4.4交換排序基本思想是：兩兩比較待排序記錄的關鍵碼，并交換不滿足順序要求的偶對，直至全部滿足為止1.起泡排序：將待排序的記錄按從后向前的順序順次兩兩比較，若為逆序則進行交換。將序列照此方法從頭到尾處理一遍稱作一趟起泡，一趟起泡的效果是將關鍵碼值最小的記錄交換到了最前位置，即該記錄的順序起始位置。若某一趟起泡過程中沒有任何交換發(fā)生，則排序過程結(jié)束對n個記錄的文件進行排序。所需執(zhí)行時間是n2量級,2.快速排序,快速排序的基本方法是：在待排序列中任取一個記錄，以它為基準用交換的方法將所有記錄分成兩部分，關鍵碼值比它小的在一部分，關鍵碼值比它大的在另一部分。再分別對這兩部分實施上述過程，一直重復到排序完成。快速排序法的平均執(zhí)行時間為log2n量級。,3.5文件簡介3.5.1基本概念,文件是命名的性質(zhì)相同的記錄的集合,3.5.2文件的結(jié)構,1.順序文件：文件記錄按關鍵碼遞增(或遞減)的次序定義，且在外存上按同樣的次序排列，則文件叫做順序文件2.索引文件:索引表的每項由一個關鍵碼和一個指針構成的二元組(k,p)。每個索引項對應文件的一個邏輯記錄,k是對應記錄的關鍵碼，p是該記錄的外存地址3.倒排文件:按屬性字段來建立索引。這種索引叫做倒排索引或副索引。帶有倒排索引的文件叫做倒排索引文件，簡稱倒排文件除上述三種文件外，還有直接文件、相對文件、字節(jié)流文件等,3.5.3文件的操作,1.檢索：在文件中查找滿足一定條件的記錄，最常見的是查找關鍵碼為一指定值的記錄，更一般地，可以根據(jù)一組字段的值進行檢索，2.插入：在文件中增加一個新記錄。3.刪除：刪去文件中的一個記錄。這種操作常常需要通過檢索先找到被刪記錄的位置，而后再刪除4.修改：把記錄中某些字段的值改為新值。5.排序：按照一組指定字段的值把文件的全部記錄在外存上重新進行排列，使記錄的外存地址隨這組字段值從小到大(或從大到小)排列,叫做外排序,