高級數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用ppt課件

1、高級數(shù)據(jù)構(gòu)造及其運(yùn)用高級數(shù)據(jù)構(gòu)造及其運(yùn)用福建師大附中周成C內(nèi)容提要內(nèi)容提要l一個(gè)簡單的例子塊鏈l檢索樹？及其運(yùn)用再做8數(shù)碼l并查集及其運(yùn)用l二叉排序樹及其運(yùn)用圓桌問題菜鳥級問題l圓桌上圍坐著2n個(gè)人其中n個(gè)人是好人，另外n個(gè)人是壞人。假設(shè)從第一個(gè)人開場數(shù)數(shù)數(shù)到第m個(gè)人，那么立刻處死該人，然后從被處死的人之后開場數(shù)數(shù)，再將數(shù)到的第m個(gè)人處死依此方法不斷處死圍坐在圓桌上的人。試問預(yù)先應(yīng)如何安排這些好人與壞人的座位，能使得在處死n個(gè)人之后，圓桌上圍坐的剩余的n個(gè)人全是好人。輸入格式：輸入文件中的僅一行都有兩個(gè)數(shù)依次為n和m，表示一個(gè)問題的描畫信息，n32767，m3276

2、7。輸出格式：輸出問題的解，問題的解可以用延續(xù)的假設(shè)干行字符來表示，每行的字符數(shù)量不超越50，但是在問題的解中不允許出現(xiàn)空白字符和空行，用大寫字母G表示好人大寫字母B表示壞人。輸入輸出2 3 GBBG順序表和塊鏈順序表和塊鏈1234567891012345678910Head順序表、鏈表的時(shí)間復(fù)雜度均約為On2)1238910兩種數(shù)據(jù)構(gòu)造下時(shí)間效率的比較兩種數(shù)據(jù)構(gòu)造下時(shí)間效率的比較編號NM算法一用時(shí)算法二用時(shí)1500004001.10s0.44s2327673276746.92s0.33s3327673276546.32s0.33s4500004000093.96s0.60s算法一：順序表算法

3、二：塊鏈結(jié)論：隨著問題規(guī)模的進(jìn)一步擴(kuò)展，算法二與一相比，時(shí)間效率會更明顯！檢索樹檢索樹l檢索樹是一種簡單但用途廣的數(shù)據(jù)構(gòu)造。l有時(shí)可替代哈希表l它可以用來儲存各種元素類型范圍一定的串，例如字符串，數(shù)串等。l例如用檢索樹來儲存abc,abd,bca,bcb,bcd這個(gè)字符串集合，可表示為：檢索樹檢索樹l由圖可知，在一棵檢索樹中查找一個(gè)目的只需求OL的時(shí)間，L為目的的串長度，比盲目比較要快得多。在空間上，由于檢索樹是動態(tài)創(chuàng)建的，防止了不用要的浪費(fèi)。 檢索樹檢索樹8數(shù)碼問題中的運(yùn)用數(shù)碼問題中的運(yùn)用l八數(shù)碼問題是一題經(jīng)典的廣度搜索問題。l問題1：簡單地采用廣度搜索對步數(shù)較多和無解的情況就無法得出結(jié)果。

4、l可以運(yùn)用雙向搜索進(jìn)展優(yōu)化。l問題2：但在判重時(shí)仍需求很大的復(fù)雜度導(dǎo)致了整個(gè)算法的復(fù)雜度很大。l處理方法：可以運(yùn)用檢索樹來存儲一切已擴(kuò)展的形狀進(jìn)展判重，復(fù)雜度為O(8)，大大提高了算法的效率。l8數(shù)碼的檢索樹只用到了8層，但不用把最后一層開出來，所以在實(shí)踐內(nèi)存中之開了7層的空間。形狀在檢索樹的表示形狀在檢索樹的表示檢索樹數(shù)據(jù)構(gòu)造的表示：檢索樹數(shù)據(jù)構(gòu)造的表示：Type Ttree = ty; ty = array0.9of Ttree;Var Tree : Ttree;檢索某形狀能否出現(xiàn)的函數(shù)檢索某形狀能否出現(xiàn)的函數(shù)oklfunction ok(t:longint;s:string):longi

5、nt;l判別形狀s能否在檢索樹中出現(xiàn)，假設(shè)出現(xiàn)，那么前往相應(yīng)1或2(分別代表正向和反向搜索時(shí)產(chǎn)生),否那么在檢索樹并建立該形狀l var p:Ttree;l i:integer;l 函數(shù)函數(shù)okl beginl p:=tree;l for i:=1 to 7 dol beginl if psi=nil then 該形狀末出現(xiàn)，那么建立l beginl new(psi); fillchar(psi,sizeof(psi),0);l end;l p:=psi;指針下移到下一層l end; 函數(shù)函數(shù)oklif ps8=nil then 第8個(gè)數(shù)碼所指的指針為空，表示該形狀末出現(xiàn)lbeginl ok:

6、=0;前往0l ps8:=pointer(t); 將搜索的方向值(1或2)強(qiáng)迫轉(zhuǎn)換成指針存入該指針域l endl else否那么，表示該形狀出現(xiàn)過l ok:=longint(ps8);將第8個(gè)數(shù)碼所對應(yīng)的指針值強(qiáng)迫轉(zhuǎn)換生長整數(shù)，并做為前往值l end;8數(shù)碼中運(yùn)用檢索樹的效果數(shù)碼中運(yùn)用檢索樹的效果編編號號初始形狀初始形狀目的形狀目的形狀步數(shù)步數(shù)算法一用時(shí)算法一用時(shí)檢索樹檢索樹算法二用時(shí)算法二用時(shí)普通普通1123456780123087654150.00s0.00s2123456780087654321280.00s6.5s3876543210132745608310.05s46s4876543

7、210123804765無解無解1.9s并查集l競賽中會經(jīng)常遇到這樣的標(biāo)題：給出各個(gè)元素之間的聯(lián)絡(luò)，要求將這些競賽中會經(jīng)常遇到這樣的標(biāo)題：給出各個(gè)元素之間的聯(lián)絡(luò)，要求將這些元素分成幾個(gè)集合，每個(gè)集合中的元素直接或間接有聯(lián)絡(luò)。在這類問題元素分成幾個(gè)集合，每個(gè)集合中的元素直接或間接有聯(lián)絡(luò)。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。l鏈構(gòu)造的并查集鏈構(gòu)造的并查集l樹構(gòu)造的并查集樹構(gòu)造的并查集ll鏈構(gòu)造的并查集l鏈表被普通用來計(jì)算并查集：表中的每個(gè)元素設(shè)兩個(gè)指針：一個(gè)指向同鏈表被普通用來計(jì)算并查集：表中的每個(gè)元素設(shè)

8、兩個(gè)指針：一個(gè)指向同一集合中的下一個(gè)元素；另一個(gè)指向表首元素。采用鏈?zhǔn)酱鎯?gòu)造，在一集合中的下一個(gè)元素；另一個(gè)指向表首元素。采用鏈?zhǔn)酱鎯?gòu)造，在進(jìn)展集合的查找時(shí)的算法復(fù)雜度僅為進(jìn)展集合的查找時(shí)的算法復(fù)雜度僅為O O1 1；但合并集合時(shí)的算法復(fù)雜；但合并集合時(shí)的算法復(fù)雜度卻到達(dá)了度卻到達(dá)了O On n。假設(shè)我們希望兩種根本操作的時(shí)間效率都比較高的。假設(shè)我們希望兩種根本操作的時(shí)間效率都比較高的話，鏈?zhǔn)酱鎯Ψ绞骄驮?，鏈?zhǔn)酱鎯Ψ绞骄汀傲Σ粡男牧?。力不從心了。l 前往前往樹構(gòu)造的并查集l采用樹構(gòu)造支持并查集的計(jì)算可以滿足我們的要求。并查集與普采用樹構(gòu)造支持并查集的計(jì)算可以滿足我們的要求。并查集與普通的樹

9、構(gòu)造不同，每個(gè)頂點(diǎn)紀(jì)錄的不是它的子結(jié)點(diǎn)，而是將它的通的樹構(gòu)造不同，每個(gè)頂點(diǎn)紀(jì)錄的不是它的子結(jié)點(diǎn)，而是將它的父結(jié)點(diǎn)記錄下來。下面我引見一下樹構(gòu)造的并查集的兩種運(yùn)算方父結(jié)點(diǎn)記錄下來。下面我引見一下樹構(gòu)造的并查集的兩種運(yùn)算方式式l直接在樹中查詢直接在樹中查詢l邊查詢邊邊查詢邊“途徑緊縮途徑緊縮l對應(yīng)與前面的鏈?zhǔn)酱鎯?gòu)造，樹狀構(gòu)造的優(yōu)勢非常明顯：編程復(fù)雜度低；時(shí)間效率高。 前往直接在樹中查詢集合的合并算法很簡單，只需將兩棵樹的根結(jié)點(diǎn)相連即可，這步操集合的合并算法很簡單，只需將兩棵樹的根結(jié)點(diǎn)相連即可，這步操作只需作只需O O1 1時(shí)間復(fù)雜度。所以算法的時(shí)間效率取決于集合查找的快慢。時(shí)間復(fù)雜度。所以算法的

10、時(shí)間效率取決于集合查找的快慢。而集合的查找效率與樹的深度呈線性關(guān)系。因此直接查詢所需求的時(shí)間復(fù)而集合的查找效率與樹的深度呈線性關(guān)系。因此直接查詢所需求的時(shí)間復(fù)雜度平均為雜度平均為O OlogNlogN。但在最壞情況下，樹退化成為一條鏈，使得每一。但在最壞情況下，樹退化成為一條鏈，使得每一次查詢的算法復(fù)雜度為次查詢的算法復(fù)雜度為O ON N。邊查詢邊“途徑緊縮 其實(shí)，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用其實(shí)，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用“途徑途徑緊縮算法。它的想法很簡單：在集合的查找過程中順便將樹的深度緊縮算法。它的想法很簡單：在集合的查找過程中順便將樹的深度降低。采用途徑緊縮后，每一次查詢所用的時(shí)間復(fù)