2.4　數據結構基礎

本節選解習題來源于《算法競賽入門經典（第2版）》一書的第6章。

習題6-1　平衡的括號（Parentheses Balance，UVa673）

輸入一個包含“（）”和“［］”的括號序列，判斷是否合法。具體規則如下：

（1）空串合法。

（2）如果A和B都合法，則AB合法。

（3）如果A合法，則（A）和［A］都合法。

【分析】

對輸入的序列進行遍歷，同時用一個棧維護當前遍歷過但是未配對的括號，棧就用STL的stack。

（1）遍歷到右括號，如果棧為空，說明無法匹配到左括號，直接退出。如果棧不為空，需與最近的左括號也就是棧頂的元素匹配。如果匹配直接出棧，繼續處理序列中的下一個元素。否則直接退出。

（2）遇到左括號，入棧。

（3）遍歷完之后如果棧不為空，則說明有無法匹配的左括號，序列非法。

完整程序如下：

習題6-2　S樹（S-Trees，UVa712）

給一棵滿二叉樹，每一層代表一個01變量，取0時往左走，取1時往右走。例如圖2.19中兩個圖都對應表達式x₁∧（x₂∨x₃）。

給出所有葉子的值以及一些查詢（即每個變量x_i的取值），求每個查詢到達的葉子的值。例如有4個查詢：000, 010, 111, 110，則輸出應為0011。

【分析】

仔細觀察可以發現，可以不用建立二叉樹的結構，每遍歷一個輸入的字符，就沿樹下降一層，目標葉子所在的區間就縮小一半，當處理完所有的x_i之后，剛好到達葉子，區間縮小為只有一個元素。注意葉子結點的個數是2ⁿ而不是n。

完整程序如下：

習題6-3　二叉樹重建（Tree Recovery，ULM 1997，UVa536）

輸入一棵二叉樹的先序遍歷和中序遍歷序列，輸出它的后序遍歷序列，如圖2.20所示。

【分析】

具體思路可以參考《算法競賽入門經典（第2版）》6.3.3節的二叉樹重建。

習題6-4　騎士的移動（Knight Moves，UVa439）

輸入標準8*8國際象棋棋盤上的兩個格子（列用a～h表示，行用1～8表示），求馬最少需要多少步從起點跳到終點。例如從a1到b2需要4步。馬的移動方式如圖2.21所示。

【分析】

使用Point類來存儲位置，然后再存儲向8個方向跳對應的8個向量，在BFS搜索位置遍歷8個方向時就可以直接用向量計算來簡化代碼。而且在比較點坐標時也比較方便，具體請參考代碼。完整程序（C＋＋11）如下：

習題6-5　巡邏機器人（Patrol Robot，ACM/ICPC Hanoi 2006，UVa1600）

機器人要從一個m*n（1≤m，n≤20）的網格的左上角（1，1）走到右下角（m，n）。網格中的一些格子是空地（用0表示），其他格子是障礙（用1表示）。機器人每次可以往4個方向走一格，但不能連續地穿越k（0≤k≤20）個障礙，求最短路長度。起點和終點保證是空地。例如對于圖2.22所示左圖的數據，圖2.22的右圖是最優解，路徑長度為10。

【分析】

首先，與習題6-3一樣，同樣可以使用Point類來簡化處理邏輯。而當前狀態除了包含當前坐標，還要包含已經穿越的障礙個數，這一點是和上題的關鍵區別，BFS即可。完整程序如下：

習題6-6　修改天平（Equilibrium Mobile，NWERC 2008，UVa12166）

用一個深度不超過16的二叉樹，代表一個天平。每根桿都懸掛在中間，每個秤砣的重量已知。至少修改多少個秤砣的重量才能讓天平平衡？如圖2.23所示，把7改成3即可。

【分析】

樹在最終平衡之后，只要確定單個結點的重量，整個樹的重量就可以確定。此時深度n（根結點深度為0）的子樹重量為深度n-1子樹重量的1/2。如果一個深度n的秤砣結點重量為x，則整棵樹的重量就是x*2ⁿ。要求計算出需修改重量的秤砣的最小個數，反過來就是計算不需要修改的秤砣的最大個數。對于第n層的重量為x結點，假設它不需要修改，則最終平衡的樹的重量就是T＝x*2ⁿ。遍歷每個結點，計算出現次數最多的那個T的出現次數K，則（結點的個數－K）即是所求的答案。完整程序如下：

習題6-7　Petri網模擬（Petri Net Simulation，ACM/ICPC World Finals 1998，UVa804）

你的任務是模擬Petri網的變遷。Petri網包含NP個庫所（用P1，P2…表示）和NT個變遷（用T1，T2…表示）。0＜NP，NT＜100。當每個變遷的每個輸入庫所都至少有一個token時，變遷是允許的。變遷發生的結果是每個輸入庫所減少一個token，每個輸出庫所增加一個token。變遷的發生是原子性的，即所有token的增加和減少應同時進行。注意，一個變遷可能有多個相同的輸入或者輸出。如果有多個變遷是允許的，一次只能發生一個。

如圖2.24所示，一開始只有T1是允許的，發生一次T1變遷之后有一個token會從P1移動到P2，但仍然只有T1是允許的，因為2要求P2有兩個token。再發生一次T1變遷之后P1中只剩一個token，而P2中有兩個，因此T1和T2都可以發生。假定T2發生，則P2中不再有token，而P3中有一個token，因此T1和T3都是允許的。

輸入一個Petri網絡。初始時每個庫所都有一個token。每個變遷用一個整數序列表示，負數表示輸入庫所，正數表示輸出庫所。每個變遷至少包含一個輸入和一個輸出。最后輸入一個整數NF，表示要發生NF次變遷（同時有多個變遷允許時可以任選一個發生，輸入保證這個選擇不會影響最終結果）。

【分析】

首先建立一個結構Transition表示一個變遷，包含所有的輸入庫所編號及其出現次數，使用map＜int，int＞來表示，例如題圖中T2中P2出現兩次。另外用一個vector＜int＞存儲所有的輸出Place編號。這個Transition只有在每個編號為i的輸入庫所中的Token個數≥ i在出現的次數時才被允許。

每一次變遷時，對于輸入庫所i來說，Token個數要減掉其在Transition的輸入中出現的次數，然后所有的輸出庫所的Token增加1。完整程序（C＋＋11）如下：

習題6-8　空間結構（Spatial Structures，ACM/ICPC World Finals 1998，UVa806）

黑白圖像有兩種表示法：點陣表示和路徑表示。路徑表示法首先需要把圖像轉換為四分樹，然后記錄所有黑結點到根的路徑。例如對于如圖2.25所示的圖像。

四分樹如圖2.26所示。

NW、NE、SW、SE分別用1、2、3、4表示。最后把得到的數字串看成是五進制的，轉換為十進制后排序。例如上面的樹在轉換、排序后的結果是9 14 17 22 23 44 63 69 88 94 113。

你的任務是在這兩種表示法之間進行轉換。在點陣表示法中，1表示黑色，0表示白色。圖像總是正方形的，且長度n為2的整數冪，并滿足n≤64。輸入輸出細節請參見原題。

【分析】

因為題目實際上是要求在四分樹的兩種表示形式之間轉換，那么很容易想到的就是要建立四分樹的結構。

對于輸入黑色點的情況，每一個點計算出其在Grid中對應的區域，然后給對應的區設置黑色標記即可。對于輸入是Grid的情況，可以使用遞歸的方法建立四分樹，然后使用DFS來搜索到所有的黑結點，并且在沿著樹向下搜索的過程中記錄相應的路徑即可。完整程序如下：

習題6-9　紙牌游戲（“Accordian“Patience，UVa127）

把52張牌從左到右排好，每張牌自成一個牌堆（pile）。當某張牌與它左邊那張牌或者左邊第三張牌match（花色suit或者點數rank相同）時，就把這張牌移到那張牌上面去。移動之后還要看看是否可以進行其他的移動。只有位于牌堆頂部的牌才能移動或者參與match。當牌堆之間出現空隙時要立刻把右邊的所有牌堆左移一格來填補空隙。如果有多張牌可以移動，先移動最左邊的那張牌；如果既可以移一格也可以移3格時，移3格。按順序輸入52張牌，輸出最后的牌堆數以及各牌堆的牌數。

樣例輸入：

樣例輸出：

【分析】

本題牽涉兩種數據結構，一是棧（模擬牌堆），使用STL的stack即可；而多個牌堆之間實際上是鏈表的關系（中間牽涉牌堆的刪除以及連接），自己定義一個LinkNode結構，內部包含一個stack。同時，加一個頭結點方便處理。完整程序（C＋＋11）如下：

習題6-10　10-20-30游戲（10-20-30，ACM/ICPC World Finals 1996，UVa246）

有一種紙牌游戲叫作10-20-30。游戲使用除大王和小王之外的52張牌，J、Q、K的面值是10，A的面值是1，其他牌的面值等于它的點數。

把52張牌疊放在一起放在手里，然后從最上面開始依次拿出7張牌從左到右擺成一條直線放在桌子上，每一張牌代表一個牌堆。每次取出手中最上面的一張牌，從左至右依次放在各個牌堆的最下面。當往最右邊的牌堆放一張牌以后，重新往最左邊的牌堆上放牌。

如果當某張牌放在某個牌堆上后，牌堆的最上面兩張和最下面一張牌的和等于10、20或者30，這3張牌將會從牌堆中被拿走，然后按順序放回手中并壓在最下面。如果沒有出現這種情況，將會檢查最上面一張和最下面兩張牌的和是否為10、20或者30，解決方法類似。如果仍然沒有出現這種情況，最后檢查最下面3張牌的和，并用類似的方法處理。例如，如果某一牌堆中的牌從上到下依次是5、9、7、3，那么放上6以后的布局如圖2.27所示。

如果放的不是6，而是Q，對應的情況如圖2.28所示。

如果某次操作后某牌堆中沒有剩下一張牌，那么把該牌堆永遠地清除掉，并把它右邊的所有牌堆順次往左移。如果所有牌堆都清除，游戲勝利結束；如果手里沒有牌了，游戲以失敗告終；有時游戲永遠無法結束，這時我們說游戲出現循環。給出52張牌最開始在手中的順序，請模擬這個游戲并計算出游戲結果。

【分析】

這個題目在數據結構的選取方面關鍵有幾點：

（1）牌堆所用的數據結構，因為要在兩端進行操作，所以使用STL中deque（雙端隊列）最為合適：typedef deque＜int＞ Pile。

（2）要把當前的局面記錄下來進行判重，可以將所有的牌堆中的牌編碼成一個字符串：每張牌的牌面直接轉成char，牌堆與牌堆之間用“|”之類的分隔符隔開，然后局面就可以用string來表示。同時使用一個set＜string＞來對局面的編碼進行判重。

（3）所有的牌堆因為牽涉有刪除以及移位操作，可用STL中的雙向鏈表list＜Pile*＞來表示。

每一次的模擬過程就是以下幾個步驟：

（1）依次判斷牌堆和手中的牌是否已經清空，如果清空，直接輸出結果。

（2）對當前局面進行編碼，然后判重，如果重復直接退出。

（3）從手牌取出一張并且放到左邊的牌堆，同時把這個牌堆放到所有牌堆的最后。

（4）針對最后的牌堆進行10-20-30的操作。操作完成之后判斷牌堆是否已經清空，如果已經被清空，則從鏈表中刪除這個牌堆。

完整程序（C＋＋11）如下：

習題6-11　樹重建（Tree Reconstruction，UVa10410）

輸入一個n（n≤1000）結點樹的BFS序列和DFS序列，你的任務是輸出每個結點的兒子列表。輸入序列（不管是BFS還是DFS）是這樣生成的：當一個結點被擴展時，它的所有孩子應該按照編號從小到大的順序訪問。

例如，若BFS序列為4 3 5 1 2 8 7 6，DFS序列為4 3 1 7 2 6 5 8，則一棵滿足條件的樹如圖2.29所示。

【分析】

根據題目描述可以得出結論：結點u及其直接孩子結點在DFS和BFS序列中出現的順序一致且都是遞增的，且孩子結點在BFS序列形成連續子序列。據此可以得到u的所有子結點，再根據子結點在DFS序列中的位置，就可以得到這兩個子結點對應的子樹對應的DFS序列以及子樹的所有結點。

據此就可以設計出一個遞歸邏輯，讀入一個子樹的DFS序列，以及這個序列對應的BFS序列，構造這棵子樹。

舉例來說，對于以4為根結點的子樹，輸入的BFS和DFS序列分別是（灰色表示4的孩子結點）：BFS: 3 5 1 2 8 7，DFS: 3 1 7 2 6 5 8。則4的兩個孩子結點分別是3和5。根為3的子樹對應的BFS和DFS序列就是：BFS: 1 27 6，DFS: 1 7 2 6。而5為根的子樹對應的兩個子序列就是8。

根為3的子樹，可以繼續遞歸拆成兩棵子樹。

（1）子樹1對應的子樹序列：BFS: 7，DFS: 7。

（2）子樹2對應的子樹序列：BFS: 6，DFS: 6。

如此即可完整還原整棵樹，算法的時間復雜度為O(n²)。完整程序（C++11）如下：

習題6-12　骰子難題（A Dicey Problem, ACM/ICPC World Finals 1999, UVa810）

如圖2.30所示是一個迷宮，如圖2.31所示是一個骰子。你的任務是把骰子放在起點（骰子頂面和正面的數字由輸入給定），經過若干次滾動以后回到起點。

每次到達一個新格子時，格子上的數字必須和它接觸的骰子上的數字相同，除非到達的格子上畫著五星（此時，與它接觸的骰子上的數字可以任意）。輸入一個R和C行（1≤R,C≤10）的迷宮、起點坐標以及頂面、正面的數字，輸出一條可行的路徑。

【分析】

首先要建立表示骰子當前狀態的結構，其中包括當前的行列編號，以及頂面和正面的數字（由此可以確定其他4個面的數字）。然后就是使用BFS來尋找最短路徑。

需要注意以下幾點：

（1）在狀態中還要保留指向上一步狀態的指針。

（2）代碼中手工打表來建立由頂面和正面數字得到左面數字的映射，這樣初始狀態輸入時就直接建立6個面的狀態。

（3）每次骰子旋轉時，可以根據上一次的狀態首先確認新的頂面和正面狀態，然后即可確認6個面的狀態。

完整程序如下：

習題6-13　電子表格計算器（Spreadsheet Calculator, ACM/ICPC World Finals 1992, UVa215）

在一個R行C列（R≤20，C≤10）的電子表格中，行編號為A～T，列編號為0～9。按照行優先順序輸入電子表格的各個單元格。每個單元格可能是整數（可能是負數）或者引用了其他單元格的表達式（只包含非負整數、單元格名稱和加減號，沒有括號）。表達式保證以單元格名稱開頭，內部不含空白字符，且最多包含75個字符。

盡量計算出所有表達式的值，然后輸出各個單元格的值（計算結果保證為絕對值不超過10000的整數）。如果某些單元格循環引用，在表格之后輸出（仍按行優先順序），如圖2.32所示。

【分析】

基本模型就是各個Cell之間的引用關系形成一個有向圖，使用DFS遞歸求值，同時使用類似拓撲排序中的DFS邏輯來判斷是否有循環引用。注意，表達式如果解析構造成樹再遞歸計算，可能導致棧溢出。比較簡潔的方法是直接對表達式進行解析，遇到Cell引用就遞歸計算對應的表達式同時判斷循環引用，具體參見相關代碼。另外，表達式可能以減號開頭，解析時需要注意判斷。完整程序如下：

習題6-14　檢查員的難題（Inspector’s Dilemma, ACM/ICPC Dhaka 2007, UVa12118）

某國家有V（V≤1000）個城市，每兩個城市之間都有一條雙向道路直接相連，長度為T。你的任務是找一條最短的道路（起點和終點任意），使得該道路經過E條指定的邊。

例如，若V=5、E=3、T=1，指定的3條邊為1-2、1-3和4-5，如圖2.33所示，則最優道路為3-1-2-4-5，長度為4*1=4。

【分析】

首先考慮E條邊都連通的情況。如果E條邊組成的圖存在歐拉道路（不需要是歐拉回路），則這條歐拉道路一定就是滿足題目要求的最短道路。否則，記G中的奇度數點個數為P，則一定有P>2，最少需要使其中的P-2個點變成偶數度才能形成歐拉道路，而且題目強調了任意兩個點都有一條邊，那么可以增加(P-2)/2條邊來形成歐拉道路。這樣歐拉道路的長度就是“T*(E的邊數+(P-2)/2)”。

需要強調的是，這里P一定是偶數，因為對于任意的無向圖G，所有點的度數之和等于所有邊的端點個數之和。而每條邊有兩個端點，所有點的度數之和一定是偶數，那么奇度數點的度數之和也必然是偶數。把P-2個奇度數點兩兩連接起來就能保證存在歐拉道路。

如果E條邊不連通，不妨設這E條邊形成了n個連通分量G，則需要首先要求每個G內部存在歐拉道路，不存在則參考單個連通分量的情況在G中構造歐拉道路。把每個G的歐拉道路首尾連接起來，至少需要n-1條邊。所求答案就是T*（n-1+每個G中的歐拉道路長度之和）。而每個G要形成的歐拉道路長度和單個連通分量的情況類似。

舉例來說，圖2.33中存在兩個連通分量：第一個中有4個奇度數點，不存在歐拉道路；第二個中無奇度數點，存在歐拉道路。則前者需要添加(4-2)/2=1條邊（即3-4）形成歐拉道路。然后需要再添加一條邊連接兩個連通分量中的歐拉道路（即2-7）。問題的解就是7*T。完整程序如下：