數據關系上的構造策略-資料下載頁

　　

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