《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt
《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt(48頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第三章算法與數(shù)據(jù)結(jié)構(gòu),設(shè)計(jì)程序首先要了解需要研究要解決的問(wèn)題,提出適當(dāng)?shù)挠?jì)算模型并列出解決問(wèn)題的方法和步驟,模型一旦建立起來(lái),就要選擇合適的算法,并將解題步驟表述出來(lái)本章著重討論解決問(wèn)題的核心-算法以及算法的處理對(duì)象-數(shù)據(jù)的結(jié)構(gòu),31算法,解題過(guò)程的準(zhǔn)確、完整的描述稱作解該問(wèn)題的算法程序就是用計(jì)算機(jī)語(yǔ)言表述的算法,流程圖就是圖形化了的算法程序算法數(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è)過(guò)程2.組成算法的規(guī)則是確定的、可執(zhí)行的3.每種算法必須有確定的結(jié)果,產(chǎn)生一個(gè)或多個(gè)輸出4.每個(gè)算法必須有0個(gè)(自動(dòng)生成初始數(shù))或多個(gè)輸入5.解答必須在有限步內(nèi)得到,不能出現(xiàn)“死循環(huán)”我們可以得出如下的結(jié)論:算法是一個(gè)過(guò)程,這個(gè)過(guò)程由一套明確的規(guī)則組成,這些規(guī)則指定了一個(gè)操作的順序,以便用有限的步驟提供特定類型問(wèn)題的解答,3.1.3算法的表示,算法設(shè)計(jì)一般是由粗到細(xì)的過(guò)程,一般可以使用下面幾種類型的工具描述算法:1.自然語(yǔ)言自然語(yǔ)言描述算法通俗易懂,但它有著難以克服的缺陷:(1)易產(chǎn)生歧義性(2)語(yǔ)句繁瑣冗長(zhǎng),很難清楚地表達(dá)算法的邏輯流程(3)當(dāng)今的計(jì)算機(jī)尚不能處理用自然語(yǔ)言表示的算法2.專用工具常用的有流程圖、PAD圖和N-S圖、偽代碼等3.算法描述語(yǔ)言為了便于轉(zhuǎn)換成某種編程語(yǔ)言,一般采用準(zhǔn)程序設(shè)計(jì)語(yǔ)言作算法描述語(yǔ)言。在本書(shū)中為類VB語(yǔ)言繼續(xù),流程圖是采用不同的幾何圖形來(lái)描述算法的邏輯結(jié)構(gòu),每個(gè)幾何圖形表示不同性質(zhì)的操作,常用流程圖符號(hào):,返回,1.枚舉法(窮舉法)基本思想是:先依據(jù)題目的部分條件確定答案的大致范圍在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證,直到全部情況驗(yàn)證完若某個(gè)情況使驗(yàn)證符合題目的條件,則為本題的一個(gè)答案;若全部情況驗(yàn)證完后均不符合題目的條件,則問(wèn)題無(wú)解,3.1.4常用算法,2.迭代法,使一個(gè)復(fù)雜問(wèn)題的求解過(guò)程轉(zhuǎn)化為相對(duì)簡(jiǎn)單的迭代算式的重復(fù)執(zhí)行過(guò)程使用迭代法構(gòu)造算法的基本方法是:首先確定一個(gè)合適的迭代公式,選取一個(gè)初始近似值以及解的誤差然后用循環(huán)處理實(shí)現(xiàn)迭代過(guò)程,終止循環(huán)過(guò)程的條件是前后兩次得到的近似值之差的絕對(duì)值小于或等于預(yù)先給定的誤差并認(rèn)為最后一次迭代得到的近似值為問(wèn)題的解。,3.遞歸法,如果一個(gè)過(guò)程直接或間接地調(diào)用它自身,則稱該過(guò)程是遞歸的例:求階乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif,遞歸過(guò)程必須有一個(gè)遞歸終止條件,當(dāng)n=0時(shí)定義為1,是階乘遞歸定義的遞歸出口,遞歸則是從函數(shù)本身出發(fā),逐次上溯調(diào)用其本身求解過(guò)程,直到遞歸的出口,然后再?gòu)睦锵蛲獾雇苹貋?lái),得到最終的值,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ì)算中最常見(jiàn),5.分治法,解一個(gè)夏雜的問(wèn)題時(shí),盡可能地把這個(gè)問(wèn)題分解為較小部分,找出各個(gè)的解,然后再把各部分的解組合成整個(gè)問(wèn)題的解,這就是所謂的分治法6.回溯法在那些涉及到尋找一組解的問(wèn)題或者滿足某些約束條件的最優(yōu)解的問(wèn)題中,有許多可以用回溯法來(lái)求解,回溯法的算法是:,ProcBacktracking(succ:Boolean)確定起始狀態(tài)值走第一步確定下一步還有幾種可能選一可能走下一步,記住可能和本步特征做完新一步應(yīng)做的事While目標(biāo)未達(dá)到do確定下一步有幾種可能While沒(méi)有可能and還有上一步do回退上一步查有無(wú)下一可能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數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(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ù)和圖程序中的數(shù)據(jù)運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的,但運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的運(yùn)算有檢索、插入、刪除、更新、排序等,2數(shù)據(jù)結(jié)構(gòu)應(yīng)用示例例3.4識(shí)別“體”字的過(guò)程,按分支和層次組織的數(shù)據(jù),稱為:“樹(shù)形結(jié)構(gòu)”,例3.5計(jì)算機(jī)換房系統(tǒng)中的“多角互換問(wèn)題”,數(shù)據(jù)結(jié)構(gòu)叫它們?yōu)椤把h(huán)鏈表”,例3.6飯店服務(wù)系統(tǒng)中的客房預(yù)訂問(wèn)題,這種結(jié)構(gòu)稱為“隊(duì)列”,是一種元素間先后次序很強(qiáng)的數(shù)據(jù)結(jié)構(gòu),例3.7管理信息系統(tǒng)中的查詢問(wèn)題各種計(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為線性表的長(zhǎng)度(n0),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ù)類型,線性表按其存儲(chǔ)結(jié)構(gòu)可分為順序表和鏈表。用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表;用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為鏈表線性表的基本運(yùn)算主要有:(1)在兩個(gè)確定的元素之間插入一個(gè)新的元素;(2)刪除線性表中某個(gè)元素;(3)按某種要求查找線性表中的一個(gè)元素,需要時(shí),還可找到元素進(jìn)行值的更新,1.順序表和一維數(shù)組將線性表中的數(shù)據(jù)元素依次存放在某個(gè)存儲(chǔ)區(qū)域中,所形成的表稱為順序表。一維數(shù)組就是用順序方式存儲(chǔ)的線性表,其下標(biāo)可看成元素的相對(duì)地址運(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)刪除:在表長(zhǎng)為n的線性表(a1,a2,ai-1,ai,ai+1an)中刪除第i個(gè)數(shù)據(jù)元素,通常還需將第i+1個(gè)至第n個(gè)元素向前推動(dòng)一個(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òng)近乎一半的元素。對(duì)于長(zhǎng)度可變的線性表,必須按可能達(dá)到的最大長(zhǎng)度分配空間,順序表的不足:,2鏈表,(1)單鏈表(線性鏈表):鏈?zhǔn)酱鎯?chǔ)的線性表結(jié)點(diǎn)除信息域外還含有一個(gè)指針域,用來(lái)指出其后繼結(jié)點(diǎn)的位置最后一個(gè)結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn),指針?biāo)闹羔樣驗(yàn)榭?記為NIL或)。另外還需要設(shè)置一個(gè)指針head,指向單鏈表的第一個(gè)結(jié)點(diǎn),鏈表的一個(gè)重要特點(diǎn)是插入、刪除運(yùn)算靈活方便,不需移動(dòng)結(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)棧的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu),也可以用鏈?zhǔn)酱鎯?chǔ)結(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ì)列的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu),也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,(2)隊(duì)列的運(yùn)算:設(shè)置一個(gè)空隊(duì)列;判定隊(duì)列是否是空隊(duì)列;入隊(duì)列;出隊(duì)列;讀取隊(duì)頭元素等,如果隊(duì)列的容量無(wú)法預(yù)先估計(jì)時(shí),可以采用鏈表存儲(chǔ)結(jié)構(gòu),循環(huán)隊(duì)列的插入、刪除,3.2.3串,串(String)可以看作一維字符數(shù)組,但其長(zhǎng)度不恒定,可以作刪除、插入操作許多高級(jí)語(yǔ)言把串作為一種單獨(dú)的類型,其元素不可作四則運(yùn)算進(jìn)行連接、刪除、插入操作,用子串有時(shí)很方便子串(Substring)是串的一部分,具有串的一切特征,3.2.4樹(shù)和二叉樹(shù)1.樹(shù)和二叉樹(shù)的定義和術(shù)語(yǔ),樹(shù)的邏輯結(jié)構(gòu)樹(shù)的形式化定義:樹(shù)(Tree)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T,其中有一個(gè)特定的稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,T3,Tm,每一個(gè)集合本身又是一棵樹(shù),且稱為根的子樹(shù)用表來(lái)表示樹(shù):(A(B(E,F),C(G),D(H,I,J)結(jié)點(diǎn)子樹(shù)個(gè)數(shù)為結(jié)點(diǎn)的度,結(jié)點(diǎn)度的最大值為該樹(shù)的度結(jié)點(diǎn)B的度為2,樹(shù)的度為3,0棵或多棵不相交的樹(shù)的集合稱為樹(shù)林二叉樹(shù)是另一種重要的樹(shù)形結(jié)構(gòu),其結(jié)構(gòu)定義為:二叉樹(shù)(BinaryTree)是n(n0)個(gè)結(jié)點(diǎn)的有限集,它或?yàn)榭諛?shù)(n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成二叉樹(shù)的邏輯結(jié)構(gòu):二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù),即使在結(jié)點(diǎn)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù),2.樹(shù)的存儲(chǔ)結(jié)構(gòu),樹(shù)的存儲(chǔ)結(jié)構(gòu)可以采用具有多個(gè)指針域的多重鏈表,結(jié)點(diǎn)中指針域的個(gè)數(shù)應(yīng)由樹(shù)的度來(lái)決定但在實(shí)際應(yīng)用中,這種存儲(chǔ)結(jié)構(gòu)并不方便,一般將樹(shù)轉(zhuǎn)化為二叉樹(shù)表示,進(jìn)行處理,3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),可使用具有2個(gè)指針域的鏈表,LC為左指針域,指向結(jié)點(diǎn)的左子樹(shù),RC為右指針域,指向結(jié)點(diǎn)的右子樹(shù)。亦可用數(shù)組的下標(biāo)來(lái)模擬指針,即開(kāi)辟三個(gè)一維數(shù)組DATA,LC和RC分別存放結(jié)點(diǎn)的元素及其左、右指針,4.樹(shù)的二叉樹(shù)表示,每一棵都能唯一地轉(zhuǎn)換到它所對(duì)應(yīng)的二叉樹(shù)轉(zhuǎn)換方法:凡是兄弟就用線連接起來(lái),對(duì)每個(gè)非終端結(jié)點(diǎn),除其最左孩子外,刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線,再以根結(jié)點(diǎn)為軸心,順時(shí)針旋轉(zhuǎn)450,5.樹(shù)和二叉樹(shù)的遍歷(周游),樹(shù)的遍歷根據(jù)樹(shù)的遞歸定義,有兩種遍歷樹(shù)的方法:(1)先根(次序)遍歷:若樹(shù)中只有一個(gè)根結(jié)點(diǎn),則訪問(wèn)樹(shù)的根結(jié)點(diǎn);否則,首先訪問(wèn)樹(shù)的根結(jié)點(diǎn),然后依次先根遍歷每棵子樹(shù)。(2)后根(次序)遍歷:若樹(shù)中只有一個(gè)根結(jié)點(diǎn),則訪問(wèn)樹(shù)的根結(jié)點(diǎn);否則,首先依次后根遍歷每一棵子樹(shù),然后訪問(wèn)樹(shù)的根結(jié)點(diǎn)。,二叉樹(shù)的遍歷,(3)后序遍歷二叉樹(shù)的算法為:若二叉樹(shù)不空,則:a)后序遍歷左子樹(shù);b)后序遍歷右子樹(shù);c)訪問(wèn)根結(jié)點(diǎn)。前圖用后序遍歷為:FEGJIHDCBA,(1)前序遍歷二叉樹(shù)算法為:若二叉樹(shù)不空,則:a)訪問(wèn)根結(jié)點(diǎn);b)前序遍歷左子樹(shù);c)前序遍歷右子樹(shù)。前圖用前序遍歷為ABEFCGDHIJ,(2)中序遍歷二叉樹(shù)的算法為:若二叉樹(shù)不空,則作:a)中序遍歷左子樹(shù);b)訪問(wèn)根結(jié)點(diǎn);c)中序遍歷右子樹(shù)。前圖用中序遍歷為:EFBGCHIJDA,3.2.5圖1.圖的概念和術(shù)語(yǔ),常用G=(V,E)代表一個(gè)圖,V是結(jié)點(diǎn)的有窮集合(非空),E是邊的有窮集合(E可為空集)。若一條邊的結(jié)點(diǎn)對(duì)無(wú)序,則稱無(wú)向圖。(V1,V2)和(V2,V1)相同有向圖由頂點(diǎn)的非空有限集和邊的有限集組成。(V1,V2)和(V2,V1)表示不同邊n個(gè)頂點(diǎn)的無(wú)向圖邊的最大數(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ù)目。對(duì)于有向圖,則把以結(jié)點(diǎn)Vi為終點(diǎn)的邊的數(shù)目稱結(jié)點(diǎn)Vi的入度;把以Vi為始點(diǎn)的邊的數(shù)目稱為Vi的出度。出度為0的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)。,2.圖的存儲(chǔ)(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ā),訪問(wèn)此結(jié)點(diǎn),再依次訪問(wèn)所有與V有路徑的結(jié)點(diǎn)。完成后再另選圖中一個(gè)未被訪問(wèn)的結(jié)點(diǎn)作始點(diǎn),重復(fù)上述過(guò)程,直至圖中所有結(jié)點(diǎn)都被訪問(wèn)到為止。(2)廣度優(yōu)先遍歷基本思想是:從某個(gè)結(jié)點(diǎn)V出發(fā),訪問(wèn)此結(jié)點(diǎn),再依次訪問(wèn)V鄰接的未訪問(wèn)結(jié)點(diǎn)。再?gòu)倪@些結(jié)點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷,直至圖中所有被訪問(wèn)過(guò)的結(jié)點(diǎn)的相鄰結(jié)點(diǎn)都被訪問(wèn)到。完成后另選圖中一個(gè)未曾訪問(wèn)的結(jié)點(diǎn)作始點(diǎn),重復(fù)上述過(guò)程,直至圖中所有結(jié)點(diǎn)都被訪問(wèn)到為止,3.3查找,3.3.1基本概念關(guān)鍵字是數(shù)據(jù)元素中可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng),比如學(xué)號(hào)、身份證號(hào)等,查找是根據(jù)給定的關(guān)鍵值,在一組數(shù)據(jù)中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過(guò)程確切定義:給定一個(gè)值K,在含有n個(gè)記錄的文件中進(jìn)行搜索,尋找一個(gè)其關(guān)鍵字等于給定的K值的記錄,如找到,則輸出記錄或記錄在文件中的相對(duì)位置稱查找成功;否則輸出查找不成功的信息稱查找失敗。,3.3.2查找算法1.順序查找,順序查找的方法是:用待查關(guān)鍵字值與線性表中各結(jié)點(diǎn)的關(guān)鍵字值逐個(gè)比較,直到找出相等的關(guān)鍵字值;或找遍所有結(jié)點(diǎn)都找不到,即查找失敗順序查找的優(yōu)點(diǎn)是對(duì)線性表結(jié)點(diǎn)的邏輯次序無(wú)要求,對(duì)線性表的存儲(chǔ)結(jié)構(gòu)無(wú)要求,缺點(diǎn)是平均檢索長(zhǎng)度長(zhǎng),為n/22.二分法查找要求線性表結(jié)點(diǎn)按關(guān)鍵字碼值排好,且以順序方式存儲(chǔ)用要查找的碼值X與中間位置結(jié)點(diǎn)的關(guān)鍵碼值W相比較:(1)X=W,此時(shí)已經(jīng)查找成功,查找結(jié)束。(2)XW,表明X在表的后半部分,取后半部分進(jìn)行查找(3)XW,表明X在表的前半部分,取前半部分進(jìn)行查找二分法查找的優(yōu)點(diǎn)是平均檢索長(zhǎng)度小,為log2n,3.分塊查找,要求文件中記錄關(guān)鍵字“分塊有序”,即前一塊中最大關(guān)鍵字小于后一塊中最小關(guān)鍵字,而塊內(nèi)的關(guān)鍵字不一定有序分塊查找的基本思想:先抽取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表,由于文件中的記錄按關(guān)鍵字分塊有序,則索引表呈遞增有序狀態(tài)。查找分兩步進(jìn)行:第一步先對(duì)索引表進(jìn)行二分查找或順序查找,以確定待查記錄在哪一塊,第二步在已限定的那一塊中進(jìn)行順序查找用分塊查找的文件不一定分成大小相等的若干塊,塊大小及其分法可根據(jù)文件的特征來(lái)定。分塊查找不僅適用于順序方式存儲(chǔ)的順序表,也適用于線性鏈表方式存儲(chǔ)的文件,3.4排序3.4.1基本概念,設(shè)含有n個(gè)記錄的文件R1,R2,Rn,其相應(yīng)的關(guān)鍵字為K1,K2,Kn,需確定一種排列P(1),P(2)P(n)使其相應(yīng)的關(guān)鍵字滿足遞增(或遞減)關(guān)系:KP(1)KP(2)KP(n)或KP(1)KP(2)KP(n)使上述文件成為一個(gè)按其關(guān)鍵字線性有序的文件RP(1),RP(2),RP(n),這種運(yùn)算就稱為排序內(nèi)排序指當(dāng)文件的數(shù)據(jù)量不太大時(shí),全部信息放在內(nèi)存中處理的排序方法。當(dāng)文件的數(shù)據(jù)量較大時(shí),排序過(guò)程中需要在內(nèi)、外存之間不斷地進(jìn)行數(shù)據(jù)交換才能達(dá)到排序的目的,這種排序稱為外排序,3.4.2插入排序,基本思想是:每步將一個(gè)待排序的記錄,按關(guān)鍵碼值的大小插入到前面已排序的適當(dāng)位置上,直到全部插完止1.直接插入排序:在排好的序列中用順序法查找插入位置,找到后將其后記錄后移一個(gè)位置,插入新記錄。排序n個(gè)記錄的文件,關(guān)鍵碼比較次數(shù)為n2量級(jí),記錄移動(dòng)個(gè)數(shù)也為n2量級(jí)2.二分法插入排序:在已排好序的序列中使用二分法查找插入位置,找到后移動(dòng)其后記錄插入新記錄。關(guān)鍵字比較次數(shù)降為nlog2n量級(jí),記錄移動(dòng)個(gè)數(shù)仍為n2量級(jí),3.4.3選擇排序,基本思想是:每次從待排序的記錄中選出關(guān)鍵字最小(或最大)的記錄,順序放在已排序的記錄序列的最后,直到全部排完為止3.4.4交換排序基本思想是:兩兩比較待排序記錄的關(guān)鍵碼,并交換不滿足順序要求的偶對(duì),直至全部滿足為止1.起泡排序:將待排序的記錄按從后向前的順序順次兩兩比較,若為逆序則進(jìn)行交換。將序列照此方法從頭到尾處理一遍稱作一趟起泡,一趟起泡的效果是將關(guān)鍵碼值最小的記錄交換到了最前位置,即該記錄的順序起始位置。若某一趟起泡過(guò)程中沒(méi)有任何交換發(fā)生,則排序過(guò)程結(jié)束對(duì)n個(gè)記錄的文件進(jìn)行排序。所需執(zhí)行時(shí)間是n2量級(jí),2.快速排序,快速排序的基本方法是:在待排序列中任取一個(gè)記錄,以它為基準(zhǔn)用交換的方法將所有記錄分成兩部分,關(guān)鍵碼值比它小的在一部分,關(guān)鍵碼值比它大的在另一部分。再分別對(duì)這兩部分實(shí)施上述過(guò)程,一直重復(fù)到排序完成??焖倥判蚍ǖ钠骄鶊?zhí)行時(shí)間為log2n量級(jí)。,3.5文件簡(jiǎn)介3.5.1基本概念,文件是命名的性質(zhì)相同的記錄的集合,3.5.2文件的結(jié)構(gòu),1.順序文件:文件記錄按關(guān)鍵碼遞增(或遞減)的次序定義,且在外存上按同樣的次序排列,則文件叫做順序文件2.索引文件:索引表的每項(xiàng)由一個(gè)關(guān)鍵碼和一個(gè)指針構(gòu)成的二元組(k,p)。每個(gè)索引項(xiàng)對(duì)應(yīng)文件的一個(gè)邏輯記錄,k是對(duì)應(yīng)記錄的關(guān)鍵碼,p是該記錄的外存地址3.倒排文件:按屬性字段來(lái)建立索引。這種索引叫做倒排索引或副索引。帶有倒排索引的文件叫做倒排索引文件,簡(jiǎn)稱倒排文件除上述三種文件外,還有直接文件、相對(duì)文件、字節(jié)流文件等,3.5.3文件的操作,1.檢索:在文件中查找滿足一定條件的記錄,最常見(jiàn)的是查找關(guān)鍵碼為一指定值的記錄,更一般地,可以根據(jù)一組字段的值進(jìn)行檢索,2.插入:在文件中增加一個(gè)新記錄。3.刪除:刪去文件中的一個(gè)記錄。這種操作常常需要通過(guò)檢索先找到被刪記錄的位置,而后再刪除4.修改:把記錄中某些字段的值改為新值。5.排序:按照一組指定字段的值把文件的全部記錄在外存上重新進(jìn)行排列,使記錄的外存地址隨這組字段值從小到大(或從大到小)排列,叫做外排序,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 算法與數(shù)據(jù)結(jié)構(gòu) 算法 數(shù)據(jù)結(jié)構(gòu) PPT 課件
鏈接地址:http://www.szxfmmzy.com/p-11580205.html