【正文】 數(shù)組這一步的時間復(fù)雜度為 O(n)；二叉堆的時間復(fù)雜度為 O(1) 。 用 Fibonacci堆來實(shí)現(xiàn)優(yōu)先隊列 Q：算法運(yùn)行時間為 O(VlgV+E)。每往第一組加入一個結(jié)點(diǎn) vm，就要對第二組的各結(jié)點(diǎn)的距離值作一次修正（設(shè) vi為第二組的結(jié)點(diǎn) , （ vm， vi）為圖中的邊）： 若加進(jìn) vm做中間結(jié)點(diǎn)使得 v0至 vi的路徑長度更短（即 vi的距離值 vm的距離值 +Wmi），則要修改 vi的距離（ vi的距離值 ← vm的距離值 +Wmi）。 ⑵維護(hù)操作：跟詢問操作相反，在保持?jǐn)?shù)據(jù)結(jié)構(gòu)性質(zhì)的基礎(chǔ)上改動數(shù)據(jù)結(jié)構(gòu)中元素或元素間相互關(guān)系的操作，稱為維護(hù)操作。p←p^.next }/*while*/ }。closed[i]←open[i] }。 /*猴子 j在時刻 i松開 ch手 */ e[i,1]←j ； if ch=39。 /*讀猴子數(shù) */ j←0。 /*猴子數(shù)為 n*/ ch:char。 3 32 1 把刪邊的順序倒過來，問題轉(zhuǎn)化為從一個無邊的圖不斷添邊，求每個點(diǎn)進(jìn)入編號為 1的點(diǎn)所在的連通分量的時間 把每個連通分量組成一個集合，如果撇開集合中各元素相對位置的計算，則添邊對集合的查詢和合并，這是一個典型的并查集算法的模型。 頑皮的猴子 有 N（ 1≤N≤30000 ）只頑皮的猴子掛在樹上。/*then*/ }。 then z[i,j]←39。 /* 尋找（ p[l].x， p[l].y）的探索方向 i*/ for i←1 to 4 do if(p[l].x+c[i,1]=p[1].x)and(p[l].y+c[i,2]=p[1].y)then break。/*while*/ l←s。 then{ inc(t)。 /*隊列 */ s,t,k,l,i,j:integer。xx←px。j←0。/*while*/ }。/*while*/ if d3 /*若 can鏈中某空地相對 (px,py)的方格狀態(tài)已確定，則將相對位置 (px,py)從 uk鏈表中刪除 */ then { uk^[i].next←uk^[uk^[i].next].next。py←uk^[uk^[i].next].y。tail←1。O39。 /* 設(shè)當(dāng)前相對位置為（ 0， 0） */ fillchar(z,sizeof(z),39。y←yy+c[i,2]。 /*關(guān)閉輸入文件 */ }。 var f:text。 /*發(fā)出開始探索命令 */ while rest1 do/*反復(fù)移動探索，直至 can鏈?zhǔn)Ｒ粋€頂點(diǎn)為止 */ { change。Q39。表示 (x,y)無墻，a[x,y]=39。39。,39。 ) }； /*while*/ 為什么要按照 ∣ d1d2∣ 最小的要求刪除鏈表 can中不屬于初始位置的空地？ 若 can中的每塊空地相對于探索鏈表中頂點(diǎn) p和觀察方向 i來說，有 d1塊空地和 d2堵墻（ d1,d2鏈表 can中的空地數(shù)），則看到墻后可以從 can中刪去 d1個不屬于初始位置的空地；看到空地后， can中可被刪除的頂點(diǎn)數(shù)為 d2個。 基本思路 先假設(shè)所有無墻的方格都可能是初始位置，即可能的解集為所有空地。題目的限制是： ⑴不能移動到有墻的方格。 數(shù)據(jù)的線性存儲結(jié)構(gòu)分為 順序存儲結(jié)構(gòu) ——借助元素在存儲器中的相對位置（即數(shù)組下標(biāo)）來表示數(shù)據(jù)元素之間的邏輯關(guān)系 鏈?zhǔn)酱鎯Y(jié)構(gòu) ——借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系 這兩種存儲結(jié)構(gòu)的不同，導(dǎo)致在具體使用時分別存在著優(yōu)點(diǎn)和缺點(diǎn)。 /* 計算子串頻率降序的排列 t*/ print。 /*關(guān)閉輸出文件 */ }。)。/* sort */ 按要求輸出結(jié)果 proce print。kind←0。 /*若文件已讀完，則退出 */ m←(m*2+tz[ch]) mod yu。fillchar(tk[i]^,sizeof(tk[i]^),0)}。 /*長度范圍為 [a,b],子串?dāng)?shù)為 n, 當(dāng)前子串長度為 long,t序列的長度為 kind*/ yu:integer。139。39。如果新代頂點(diǎn)與子代頂點(diǎn)之間的關(guān)系建立得好，那么就可以把龐大的元素安排得井井有條，按照一定的順序逐層深入，解決當(dāng)前元素的處理。/* print */ 主程序 { assign(inf,inputfile)。 /*輸出第 which大的頻率 */ for where←b downto a do /* 按照長度降序的要求枚舉具有該頻率的子串 */ { look_up(1,tree^.r,?1?)。/* look_up */ 按要求輸出結(jié)果 proc print。,ss)。/*then*/ }/*then*/ else { find(floor+1,p^.l)。否則分別遞歸左右子樹 */ then{j←now。 /* 子串長度 +1*/ if long=b /*若長度為 b,則各頂點(diǎn)權(quán)值 +1, 有效長度 1*/ then{add(0,tree)。 /* 子串對應(yīng)數(shù)值必須模 2b,使其長度不超過 b*/ repeat read(inf,ch)。否則遞歸右子樹 */ then add(floor+1,p^.l) else add(floor+1,p^.r)。 /* 輸入信息，生成空樹 */ { readln(inf,a,b,n)。 /* 權(quán)值為 0*/ if floor=b /*若已生成 b層 ,則左右指針均為空 。 /*不同頻率按降序要求排列成 t*/ tch:array[1..1024] of char。139。 數(shù)據(jù)結(jié)構(gòu) const inputfile=39。但并不意味著我們一定要使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。B39。 /* 計算第 i個出列元素所在的段號 j和段內(nèi)位移 k+p*/ while k+pamount[j]do { k←k+p amount[j]。 /*各段為空 */ g←1。我們希望有這樣一種數(shù)據(jù)結(jié)構(gòu)，在實(shí)現(xiàn) “ 找點(diǎn) ” 和 “ 去點(diǎn) ” 時，使復(fù)雜度降到盡量低。 “ 去點(diǎn) ” 時的元素移動就是信息由 “ 不可直接使用 ” 向 “ 可直接使用 ” 的轉(zhuǎn)化過程，其時間復(fù)雜度為 O(n)。如果從第一個人開始數(shù)數(shù)，數(shù)到第個人，則立即處死該人；然后從被處死的人之后開始數(shù)數(shù)，再將數(shù)到的第個人處死 …… 依此方法不斷處死圍坐在圓桌上的人。但選用哪種邏輯結(jié)構(gòu)，直接影響算法效率。對確定的問題選擇一種合適的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計一種好的算法，就是所謂的程序設(shè)計 。 數(shù)據(jù)的存儲結(jié)構(gòu) 如何實(shí)現(xiàn)對各個對象的操作，即各對象之間的關(guān)系在計算機(jī)中如何表示。這樣的信息越多，算法的效率就會越 高。即使用數(shù)組記錄當(dāng)前圓排列中每個元素的初始位置，初始值為 1… 2n。 改進(jìn)解法 ——“直接定位法 ” 從哲學(xué)角度分析， “ 找點(diǎn) ” 和 “ 去點(diǎn) ” 是存在于程序和數(shù)據(jù)結(jié)構(gòu)中的一對矛盾： 應(yīng)用順序存儲結(jié)構(gòu)時， “ 找點(diǎn) ” 效率高而 “ 去點(diǎn) ”效率低； 應(yīng)用鏈?zhǔn)酱鎯Y(jié)構(gòu)時， “ 去點(diǎn) ” 效率高而 “ 找點(diǎn) ”效率低 。 /* 分段式數(shù)組為amount，其中第 i段中的元素數(shù)為 amount[i]， t為當(dāng)前排列 */ ans:array[1..65535]of boolean。p←0。 /*第 j段 k+p位置右方所有元素依次左移一個位置 */ p←k+p 1。 順序存儲結(jié)構(gòu) 在 “ 去點(diǎn) ” 的問題上需要數(shù)據(jù)移動； 鏈?zhǔn)酱鎯Y(jié)構(gòu) 在 “ 找點(diǎn) ” 的問題上需要指針移動， 因此線性表中的信息屬于 “ 不可直接使用 ” 的信息。 完成以下兩步操作 ⑴ 找出 n個滿足條件（長度介于 A和 B之間且出現(xiàn)次數(shù)最多）的子串，并統(tǒng)計各子串出現(xiàn)的頻率； ⑵把所有不同子串按降序要求（頻率為第一關(guān)鍵字、長度為第二關(guān)鍵字、對應(yīng)數(shù)值為第三關(guān)鍵字且降序）輸出。/*tc[i]=2i1*/ tz:array[39。 /*權(quán)值 ,即頂點(diǎn)對應(yīng)子串的頻率 */ end。 /* 二進(jìn)制子串對應(yīng)的十進(jìn)制數(shù)為 m，模為 yu（ =2b+1，使其長度不超過 b） */ 輸入數(shù)據(jù)，建立空樹 proc maketree(floor:byte。maketree(floor+1,p^.r) }。var p： point)。 /*循環(huán)變量 */ { long←0。/*for*/ exit }。p： point)。/*then*/ if floorb then{ find(floor+1,p^.l)。ss:ar)。039。rewrite(outf)。 /*換行 */ }。 /*依次讀入數(shù)據(jù)，計算各子串的頻率 */ close(inf)。然而每個十進(jìn)制數(shù)與 01串之間并不是一一對應(yīng)的關(guān)系，如 “ 01”、 “ 010”和 “ 0010”它們對應(yīng)的十進(jìn)制數(shù)都是 2，這是為什么呢？原來， 010和 0010在二進(jìn)制中表示的是同一個數(shù)（ 2），但屬于不同字串，因為這時 “ 0” 代表一個字符，字串間存在長度的差別。 tz:array[39。 /*tk[i]^[j]存儲長度為 i、對應(yīng)十進(jìn)制數(shù)值為 j的子串頻率 */ tch:array[1..1024] of char。 /*讀入字符 */ m:integer。 /*讀二進(jìn)制數(shù)碼 */ if ch=39。/*init*/ 使用插入排序法計算子串頻率降序的排列 proce sort。 t[k+1]←tk[i]^[j] }。 /*設(shè)置緩沖區(qū) */ for ii←1 to n do /* 按降序枚舉頻率順序 */ { write(outf,t[ii])。/*then*/ writeln(outf)。 /*輸入信息，二維數(shù)組清零 */ make。 “ 無用 ” 的信息只會干擾問題的規(guī)律性，使我們難于找出解決問題的方法。 必要時采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 地下城市 已知一個城市的地圖，該地圖包含空地和墻。然后反復(fù)調(diào)用move（方向）和 look(方向 )指令。這樣不僅充分發(fā)揮了鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)，而且由于不需單獨(dú)對某一個數(shù)據(jù)進(jìn)行提取，每次都是對所有數(shù)據(jù)進(jìn)行判斷，從而避免了鏈?zhǔn)浇Y(jié)構(gòu)的最大缺點(diǎn) 建立一條探索鏈表 uk，將旅行者從解集中的空地（相對位置（ 0， 0））出發(fā)、經(jīng)過路徑上所有觀察到的相對位置和觀察方向依次存入這條鏈表 初始時，（ 0， 0）的 4個相鄰格進(jìn)入鏈表 uk； 對鏈表 uk中的每一個頂點(diǎn)，依次搜索 4個相鄰方向。 /*調(diào)用庫函數(shù) */ const c:array[1..4,1..2] of shortint=((0,1),(1,0),(1,0),(0,1))。N39。 /*鏈表類型 */ var a:array[1..100,1..100] of char。—(x,y)無墻； 39。 /*uk鏈的尾指針為 tail， can鏈的尾指針為 rest，地圖的列數(shù)和行數(shù)分別為 u、 v*/ 主程序 {readp。finish(can^[o].x,can^[o].y)。 /*讀城市地圖的規(guī)模 */ for i←v downto 1 do /* 自上而下、由左而右讀入城市地圖信息 */ { for j←1 to u do read(f,a[j,i])。 /*若 (xx,yy)i方向上的相鄰格未入 uk鏈，則入隊 */ then { z[xx+c[i,1],yy+c[i,2]]← 39。 var i,j:integer。/* （ 0， 0）為無墻，其它位置未入 uk*/ new(can)。/*with*/ }。