【正文】 矩陣結(jié)構(gòu) 多 較快 多 廣 隨機(jī)存取，適用于遞推和動(dòng)態(tài)規(guī)劃 鏈 式 結(jié) 構(gòu) 單鏈表 少 快 少 窄 順向搜索線(xiàn)性序列，不便回掃 雙向 鏈表 少 較慢 稍多 較廣 便于查找線(xiàn)性序列中元素間的前后聯(lián)系 樹(shù)型結(jié)構(gòu) 多 一般 多 較廣 體現(xiàn)元素間“一對(duì)多”的聯(lián)系，一般采用遞歸手段 科學(xué)組合多種數(shù)據(jù)結(jié)構(gòu) 對(duì)于多數(shù)的問(wèn)題，可以通過(guò)選擇一種合理的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)達(dá)到優(yōu)化算法的目的。但是，有些問(wèn)題選擇單一的數(shù)據(jù)結(jié)構(gòu)會(huì)顧此失彼。 為了達(dá)到取長(zhǎng)補(bǔ)短的作用，使不同的數(shù)據(jù)結(jié)構(gòu)在算法中發(fā)揮出各自的優(yōu)勢(shì)，可以采用多種數(shù)據(jù)結(jié)構(gòu)結(jié)合的方法。多種數(shù)據(jù)結(jié)構(gòu)結(jié)合的方式一般有兩種 : ⑴ 數(shù)據(jù)結(jié)構(gòu)的 “ 并聯(lián) ” 。 ⑵ 數(shù)據(jù)結(jié)構(gòu)的 “ 嵌套 ” 。 數(shù)據(jù)結(jié)構(gòu)的 “ 并聯(lián) ” 將用多個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)用于同一數(shù)據(jù)集合的方法叫做數(shù)據(jù)結(jié)構(gòu)的并聯(lián)，這種數(shù)據(jù)結(jié)構(gòu)的結(jié)合方式不僅可以將多種存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)完全發(fā)揮了出來(lái)，而且還可以通過(guò)映射建立不同數(shù)據(jù)結(jié)構(gòu)中元素間的對(duì)應(yīng)關(guān)系。 頑皮的猴子 有 N（ 1≤N≤30000 ）只頑皮的猴子掛在樹(shù)上。每只猴子都有兩只手，編號(hào)為 1的猴子的尾巴掛在樹(shù)枝上，其它猴子的尾巴都被別的猴子的某只手抓著。每一時(shí)刻，都有且只有一只猴子的某只手松開(kāi)，從而可能會(huì)有一些猴子掉落至地面。 任務(wù) :給出一開(kāi)始猴子們的情況和每一時(shí)刻松開(kāi)手的情況 (必須保證每只抓住其它猴子尾巴的手松開(kāi)且僅松開(kāi)一次 )，要求計(jì)算每只猴子落地的時(shí)間。 輸入：第 1行為猴子數(shù) n，以下 n1行，其中第 i+1行的格式為 ‘ j ch’，表明猴子 j的 ch手抓住第 i+1只猴子（ ch=‘l’，為左手； ch=‘r’，為右手）；第 n+1行為時(shí)間 t；最后含 t行，其中第 n+1+i行的格式為 ‘ j ch’，表明在時(shí)刻 i猴子 j松開(kāi) ch手（ ch=‘l’，為左手； ch=‘r’，為右手）； 輸出： k行 (最終有 k個(gè)猴子落地 )，每行的格式為 ‘ 猴子序號(hào) 落地時(shí)間 ’ 。 4 把猴子抽象成頂點(diǎn)，猴子的手抽象成邊，則猴子們的連接情況構(gòu)成一個(gè)連通圖（圖（ a））題目就轉(zhuǎn)化成一個(gè)連通圖不斷去邊、求每個(gè)點(diǎn)離開(kāi)編號(hào)為 1的點(diǎn)所在的連通分量的時(shí)間。 猴子 1在時(shí)刻 1松開(kāi)左手，猴子 3在時(shí)刻 2松開(kāi)左手、時(shí)刻 4松開(kāi)右手，猴子 1在時(shí)刻 3松開(kāi)右手(相當(dāng)于猴子 1和猴子 3同時(shí)松開(kāi)右手 ) 。 (圖 (b))中頂點(diǎn)旁的數(shù)字給出了對(duì)應(yīng)猴子落地的時(shí)間。 3 32 1 把刪邊的順序倒過(guò)來(lái)，問(wèn)題轉(zhuǎn)化為從一個(gè)無(wú)邊的圖不斷添邊，求每個(gè)點(diǎn)進(jìn)入編號(hào)為 1的點(diǎn)所在的連通分量的時(shí)間 把每個(gè)連通分量組成一個(gè)集合，如果撇開(kāi)集合中各元素相對(duì)位置的計(jì)算，則添邊對(duì)集合的查詢(xún)和合并，這是一個(gè)典型的并查集算法的模型。 用并查集維護(hù) 當(dāng)并查集中某個(gè)集合加入編號(hào)為 1的點(diǎn)所在的集合時(shí)，需要把這個(gè)集合中的所有元素的時(shí)間記錄一下 (圖（ a） )。但并查集不支持 “ 枚舉集合元素 ” 的功能，怎么辦？ 給每個(gè)并查集分配一個(gè)鏈表，記錄這個(gè)集合中所有的元素，(圖 (b))。這樣，能夠方便的枚舉集合中的元素、合并并查集。 數(shù)據(jù)結(jié)構(gòu) type point=^node。 /*并查集的鏈表指針類(lèi)型 */ node=record /*鏈頂點(diǎn)類(lèi)型 */ v:longint。 /*猴子序號(hào) */ next:point /*后繼指針 */ end。 var n,i,j,k,t:longint。 /*猴子數(shù)為 n*/ ch:char。 /*左（ ‘ l?） 右 (?r?)手標(biāo)志 */ p:point。 tree,m:array [1..30000,1..3] of longint。 /*初始時(shí)猴子間的連接情況為 tree， 添邊過(guò)程中生成的樹(shù)為 m。其中 i頂點(diǎn)的左兒子為 tree[i,1]（ m[i,1])，右兒子為 tree[i,2]（ m[i,2])，父頂點(diǎn)為 tree[i,3] (m[i,3]) */ e:array [1..30000,1..2] of longint。 /*松手情況，其中第 i時(shí)刻松手猴子的編號(hào)為 e[i,1]，松開(kāi)手為 e[i,2](1—左手， 2—右手 )*/ open,closed:array [1..30000] of point。 /*猴子 i所在并查集的首指針為 open[i]，尾指針為 closed[i]*/ time:array[1..60000]of longint。 /*答案，其中猴子 i的落地時(shí)間為time[i]*/ { readln(n)。 /*讀猴子數(shù) */ j←0。 for i←2 to n do /* 依次讀入每個(gè)猴子的連接情況 */ { readln(j,ch,ch)。 /*第 i只猴子被猴子 j的 ch手抓住 */ if ch=39。l39。then tree[j,1]←i else tree[j,2]←i。/* 根據(jù)左右手確定 i為 j的左兒子還是右兒子 */ tree[i,3]←j }。 /*j 為 i的父頂點(diǎn) */ readln(t)。 /*讀時(shí)間數(shù) */ for i←1 to t do /* 依次讀入每個(gè)時(shí)刻的松手情況 */ { readln(j,ch,ch)。 /*猴子 j在時(shí)刻 i松開(kāi) ch手 */ e[i,1]←j ； if ch=39。l39。 then e[i,2]←1 else e[i,2]←2 }。 /* 記錄時(shí)刻 i松手的猴子編號(hào)和左右手標(biāo)志 */ fillchar(m,sizeof(m),0)。 fillchar(time,sizeof(time),0)。 /*初始時(shí)樹(shù)空，每個(gè)猴子的落地時(shí)間為 0 */ for i←1 to n do /* 為每個(gè)猴子建立并查集 */ { new(open[i])。open[i]^.v←i。open[i]^.next←nil。closed[i]←open[i] }。 for i←t downto 1 do /* 倒推時(shí)間，將每個(gè)時(shí)刻斷開(kāi)的邊連上 */ { k←tree[e[i,1],e[i,2]]。m[e[i,1],e[i,2]]←k。m[k,3]←e[i,1]。 j←e[i,1]。 /* 從父頂點(diǎn)出發(fā)沿父指針追溯祖先頂點(diǎn) */ while m[j,3]0 do j←m[j,3]。 if j=1/*若 父頂 點(diǎn)連通根，則 兒子頂點(diǎn) 所在并查集內(nèi)元素的落地時(shí)間為 i*/ then { p←open[k]。 while pnil do{ time[p^.v]←i。p←p^.next }/*while*/ }。/*then*/ closed[j]^.next←open[k]。 /* 將猴子 k所在的并查集并入猴子 j所在的并查集 */ if closed[k]nil /*設(shè)定合并鏈的尾指針 */ then closed[j]←closed[k]。 closed[k]←nil。open[k]←nil /* 猴子 k所在的并查集為空 */ }。/*for*/ for i←1 to n do /* 輸出每個(gè)猴子的落地時(shí)間 */ if time[i]0 then writeln(i,39。 39。,time[i])}.{main} 數(shù)據(jù)結(jié)構(gòu)并聯(lián)方式的利弊 數(shù)據(jù)結(jié)構(gòu)支持的操作分為兩類(lèi)： ⑴詢(xún)問(wèn)操作：顧名思義，就是獲取該數(shù)據(jù)結(jié)構(gòu)記錄的某些信息的操作，而并沒(méi)有改動(dòng)數(shù)據(jù)結(jié)構(gòu)里的元素及其相互關(guān)系。 ⑵維護(hù)操作：跟詢(xún)問(wèn)操作相反，在保持?jǐn)?shù)據(jù)結(jié)構(gòu)性質(zhì)的基礎(chǔ)上改動(dòng)數(shù)據(jù)結(jié)構(gòu)中元素或元素間相互關(guān)系的操作，稱(chēng)為維護(hù)操作。 對(duì)于這兩類(lèi)操作，數(shù)據(jù)結(jié)構(gòu)的并聯(lián)方式有利有弊。優(yōu)點(diǎn)是并聯(lián)而成的新數(shù)據(jù)結(jié)構(gòu)，可以支持組成它的數(shù)據(jù)結(jié)構(gòu)的所有操作；缺點(diǎn)是維護(hù)操作新數(shù)據(jù)結(jié)構(gòu)的時(shí)間，一般為各個(gè)被并聯(lián)數(shù)據(jù)結(jié)構(gòu)的維護(hù)操作的時(shí)間疊加，這是制約計(jì)算時(shí)間的一個(gè)瓶頸。 數(shù)據(jù)結(jié)構(gòu)的并聯(lián)過(guò)程中，有時(shí)需要通過(guò)映射建立不同數(shù)據(jù)結(jié)構(gòu)中元素間的對(duì)應(yīng)關(guān)系。 預(yù)備知識(shí)： 計(jì)算單源最短路問(wèn)題 所謂單源是指一個(gè)出發(fā)頂點(diǎn) ，單源最短路問(wèn)題指的是該頂點(diǎn)至所有可達(dá)頂點(diǎn)的最短路徑問(wèn)題 。 Dijkstra算法 思維方向： 每次延長(zhǎng)最短路時(shí)選擇權(quán)最小的邊，并調(diào)整最短路外每個(gè)結(jié)點(diǎn)至出發(fā)結(jié)點(diǎn)的路長(zhǎng) 步驟： 把圖中所有結(jié)點(diǎn)分為兩組，每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)距離值： 第一組：包括已確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對(duì)應(yīng)的距離值是由 v0到此結(jié)點(diǎn)的最短路徑長(zhǎng)度； 第二組：包括尚未確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對(duì)應(yīng)的距離值 是 v0經(jīng)由第一組結(jié)點(diǎn)（中間結(jié)點(diǎn)）至此結(jié)點(diǎn)的最短路徑長(zhǎng)度； 我們按最短路徑長(zhǎng)度遞增的順序把第二組的結(jié)點(diǎn)加到第一組中去，直至 v0可達(dá)的所有結(jié)點(diǎn)都包含于第一組。在這個(gè)過(guò)程中，總保持從 v0到第一組各結(jié)點(diǎn)的最短路徑長(zhǎng)度都不大于從 v0至第二組任何結(jié)點(diǎn)的路徑長(zhǎng)度。 初始時(shí) v0進(jìn)入第一組， v0的距離值為 0；第二組包含其它所有結(jié)點(diǎn)，這些結(jié)點(diǎn)對(duì)應(yīng)的距離值這樣確定（設(shè) vi為第二組中的結(jié)點(diǎn)） 然后每次從第二組的結(jié)點(diǎn)中選一個(gè)其距離值為最小的結(jié)點(diǎn) vm加到第一組中。每往第一組加入一個(gè)結(jié)點(diǎn) vm，就要對(duì)第二組的各結(jié)點(diǎn)的距離值作一次修正（設(shè) vi為第二組的結(jié)點(diǎn) , （ vm， vi）為圖中的邊）： 若加進(jìn) vm做中間結(jié)點(diǎn)使得 v0至 vi的路徑長(zhǎng)度更短（即 vi的距離值 vm的距離值 +Wmi），則要修改 vi的距離（ vi的距離值 ← vm的距離值 +Wmi）。修改后再選距離值最小的一個(gè)結(jié)點(diǎn)加入到第一組中， … 。如此進(jìn)行下去，直至第一組囊括圖的所有結(jié)點(diǎn)或再無(wú)可加入第一組的結(jié)點(diǎn)存在。顯然，這種從第二組的結(jié)點(diǎn)中選距離值最小的結(jié)點(diǎn)擴(kuò)展是一種貪心策略。 0 5 10 ∞ ∞ 8 14 7 7 13 9 8 圓內(nèi)的數(shù)字為距離值。綠色的結(jié)點(diǎn)為第一組的結(jié)點(diǎn)，灰色的結(jié)點(diǎn)為第二組的結(jié)點(diǎn) Dijkstra算法的執(zhí)行速度取決于優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu) 用一維數(shù)組來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列 Q=VS：算法運(yùn)行時(shí)間為 O(V2+E)=O(V2)。 用二叉堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列 Q：算法運(yùn)行時(shí)間為O((V+E)lgV)。通常情況下，邊數(shù) |E|都不小于頂點(diǎn)數(shù)|V|，所以運(yùn)行時(shí)間又可以簡(jiǎn)化為 O(ElgV)。 用 Fibonacci堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列 Q：算法運(yùn)行時(shí)間為 O(VlgV+E)。但實(shí)現(xiàn)相當(dāng)繁瑣，在較短的時(shí)間里基本上不大可能寫(xiě)出程序并調(diào)試好。另外， Fibonacci堆算法中隱含的系數(shù)相當(dāng)大，程序的實(shí)際運(yùn)行效果并不理想，目前該堆的理論價(jià)值遠(yuǎn)大于實(shí)用價(jià)值，因此不適宜于限時(shí)編程的條件。 該算法的條件是該圖所有邊的權(quán)值非負(fù)，因此約定：對(duì)于每條邊 (u,v)E， w(u,v)≥0 。 最小序列 給定一個(gè) N N（ N≤100 ）的正整數(shù)矩陣。需要在矩陣中尋找一條從起始位置到終止位置的路徑 (可沿上下左右四個(gè)方向 )，并且要求路徑中經(jīng)過(guò)的所有數(shù)字，其相鄰數(shù)字之差的絕對(duì)值之和最小。 輸入：第 1行為整數(shù)矩陣規(guī)模 n；以下為 n*n的正整數(shù)矩陣；第 n+2行為起點(diǎn)位置（ x1,y1）和終點(diǎn)位置（ x2,y2）； 輸出：第 1行為最短路長(zhǎng)度；第 2行依次給出最短路經(jīng)過(guò)的數(shù)字。 Dijkstra算法每次尋找一條最短路徑時(shí)，需要兩個(gè)步驟： ⑴使用貪心策略，找一個(gè)不在最短路徑起點(diǎn)集合內(nèi)、并且到終點(diǎn)距離最短的頂點(diǎn) i。數(shù)組這一步的時(shí)間復(fù)雜度為 O(n)；二叉堆的時(shí)間復(fù)雜度為 O(1) 。 ⑵進(jìn)行松弛操作，修改從與 i相鄰的頂點(diǎn)到終點(diǎn)的路徑長(zhǎng)度。由于最多只有 4個(gè)點(diǎn) (四個(gè)方向 )與 i相鄰，所以數(shù)組這一步的復(fù)雜度為 O(1)，但二叉堆由于無(wú)法預(yù)知 i點(diǎn)的相鄰點(diǎn)在堆中的位置，因此時(shí)間復(fù)雜度升至 O(n)。 解決方案：采用映射的方法，將線(xiàn)性結(jié)構(gòu)中的元素與堆中的頂點(diǎn)一一對(duì)應(yīng)起來(lái)，若線(xiàn)性的數(shù)組中的元素發(fā)生變化，堆中相應(yīng)的頂點(diǎn)也隨之變化；堆中的頂點(diǎn)發(fā)生變化，數(shù)組中相應(yīng)的元素也隨之變化。 將兩種結(jié)構(gòu)進(jìn)行并聯(lián)后的時(shí)間復(fù)雜度為 O(nlog2n)（ 進(jìn)行 n次復(fù)雜度為 O(log2n)的堆化操作） 數(shù)據(jù)結(jié)構(gòu) con