【文章內容簡介】 read(inf,ch)。 /*讀二進制數碼 */ if ch=39。239。 then exit。 /*若文件已讀完，則退出 */ m←(m*2+tz[ch]) mod yu。 /* 計算有效子串對應的十進制數 */ if longb then inc(long)。/*有效子串的長度 +1*/ for i←1 to long do inc(tk[i]^[m and put[i]])。/* 累加以前綴長度為 i的有效子串的頻率 */ until false。 }。/*init*/ 使用插入排序法計算子串頻率降序的排列 proce sort。 var i,j， k， ii:integer。 /*循環(huán)變量 */ { fillchar(t,sizeof(t),0)。kind←0。 /*t 序列初始化為空 */ for i←a to b do /* 枚舉長度 */ for j←0 to put[i] do /* 枚舉長度為 i的子串對應的十進制數 */ { k←kind。 /* 從 t的尾部出發(fā)，左尋頻率 tk[i]^[j]的插入位置 */ while (k0)and(tk[i]^[j]t[k]) do dec(k)。 if (kn)and((k=0)or(tk[i]^[j]t[k])) then{ if kindn then inc(kind)。 /*若插入后的 t序列長度不超過上限，則從 t的第 k+1位置開始的后綴右移一個位置，將 tk[i]^[j]插入第 k+1位置 */ for ii←kind downto k+1 do t[ii+1]←t[ii]。 t[k+1]←tk[i]^[j] }。/*then*/ }。/*for*/ }。/* sort */ 按要求輸出結果 proce print。 var ii,i,j,l,p:integer。 { assign(outf,outfile)。rewrite(outf)。 /*輸出文件寫準備 */ settextbuf(outf,tch)。 /*設置緩沖區(qū) */ for ii←1 to n do /* 按降序枚舉頻率順序 */ { write(outf,t[ii])。 /*輸出第 ii大的頻率 */ for i←b downto a do/* 按照長度降序的要求枚舉具有相同頻率的子串 */ for j←put[i] downto 0 do /* 按照對應十進制數值降序的要求枚舉相同頻率、相同長度的子串 */ if tk[i]^[j]=t[ii] /*若長度為 i、對應數值為 j的子串的頻率為第 ii大 */ then{write(outf,39。 39。)。 p←j。 /* 輸出數值 j對應的二進制串 */ for l←1 to i do{write(outf,p div tc[i+1 l])。p←p mod tc[i+1 l]}。/*for*/ }。/*then*/ writeln(outf)。 /*換行 */ }。/*for*/ close(outf)。 /*關閉輸出文件 */ }。/* print */ 主程序 { assign(inf,inputfile)。reset(inf)。 /*輸入文件讀準備 */ settextbuf(inf,tch)。 /*設置緩沖區(qū) */ init。 /*輸入信息，二維數組清零 */ make。 /*讀入 01串，構建二維數組 */ close(inf)。 /*關閉輸入文件 */ sort。 /* 計算子串頻率降序的排列 t*/ print。 /*按要求輸出結果 */ }./*main*/ 兩種數據結構比較 ⑴ 矩陣結構為數組的定位操作，而二叉樹結構需要遞歸； ⑵二叉樹結構中記錄的 “ 無用 ” 信息比矩陣結構多； ⑶矩陣結構比二叉樹結構簡潔，且結合了二進制計算，因此速度也快了許多。 既然采用矩陣結構已經足夠，二叉樹結構中的一些信息顯然就成為了 “ 無用 ” 的信息。這些多余的 “ 無用 ” 信息，使我們在分析問題時難于發(fā)現規(guī)律，也很難找到高效的算法。這正如迷宮中的墻一樣，越多越難走。 “ 無用 ” 的信息只會干擾問題的規(guī)律性，使我們難于找出解決問題的方法。 選擇數據的存儲結構的基本方法 存儲結構可以直接影響時間復雜度的階； 即便不影響時間復雜度的階，也會起到類同于剪枝的優(yōu)化效果 重點討論數據的線性存儲結構 非線性的數據關系一般也是要通過線性的存儲方式存入計算機的。例如通過二維數組的相鄰表存儲圖，用一維的記錄數組存儲樹。 數據的線性存儲結構分為 順序存儲結構 ——借助元素在存儲器中的相對位置（即數組下標）來表示數據元素之間的邏輯關系 鏈式存儲結構 ——借助指示元素存儲地址的指針表示數據元素之間的邏輯關系 這兩種存儲結構的不同，導致在具體使用時分別存在著優(yōu)點和缺點。 記錄一個 n n的矩陣，矩陣中包含的非 0元素為 m個（ m≤n 2）。 順序存儲結構：使用一個 n n的二維數組，將所有數據元素全部記錄下來； 鏈式存儲結構：使用一個包含 m個頂點的鏈表，記錄所有非 0的 m個數據元素。 順序存儲結構 鏈式存儲結構 隨機訪問任意元素 O(1) O(m) 遍歷所有數據 O(n2) O(m) 合理采用順序存儲結構 順序結構操作方便； 在程序實現的過程中更便于對程序進行調試和查找錯誤 在頂點數目相差不大的情況下采用順序結構。因為指針占用空間，且編程復雜，運行時間較慢。 必要時采用鏈式存儲結構 地下城市 已知一個城市的地圖，該地圖包含空地和墻。但未給出你的初始位置。你需要通過一系列的移動（ move（方向）指令，即走入指定方向上的相鄰格）和探索（ look(方向 )指令，即詢問指定方向上的相鄰格是空地還是墻），以確定初始時所在的位置。題目的限制是： ⑴不能移動到有墻的方格。 ⑵只能探索當前所在位置四個方向上的相鄰方格。 在這兩個限制條件下，要求我們在探索次數（不包括移動）盡可能少的前提下，最終報告出初始位置 (x， y)（ finish(x， y)指令）。 輸入輸出情況：第 1行輸入城市地圖規(guī)模 u和 v。以下輸入一個 v*u的字符矩陣，自上而下、由左而右讀入每個格子的信息，其中字符 ‘ o’代表空地， ’ w’代表墻；第 v+2行發(fā)出開始探索指令 start。然后反復調用move（方向）和 look(方向 )指令。調用 look(方向 )指令后，若系統(tǒng)返回 ‘ o’，則表示該方向的相鄰格為空地；若返回 ’ w’， 則表示該方向的相鄰格為墻。通過移動和探索過程得出初始位置 (x， y)后，調用finish(x， y)指令向系統(tǒng)報告。 基本思路 先假設所有無墻的方格都可能是初始位置，即可能的解集為所有空地。然后在探索城市的過程中，使用排除法將那些不屬于初始位置的空地從可能的解集中刪去。顯然，當解集中僅剩一塊空地時，最終確定該空地即為真正的初始位置。 用鏈表 can存儲空地 由于運算量最大的操作是篩選初始位置的范圍和選擇探索位置，其操作對象為當前未排除的空地，這只是龐大地圖中很少的一部分，因此順序存儲結構明顯不適宜。 鏈式存儲結構僅存儲需要遍歷的數據。這樣不僅充分發(fā)揮了鏈式存儲結構的優(yōu)點，而且由于不需單獨對某一個數據進行提取，每次都是對所有數據進行判斷，從而避免了鏈式結構的最大缺點 建立一條探索鏈表 uk，將旅行者從解集中的空地（相對位置（ 0， 0））出發(fā)、經過路徑上所有觀察到的相對位置和觀察方向依次存入這條鏈表 初始時，（ 0， 0）的 4個相鄰格進入鏈表 uk； 對鏈表 uk中的每一個頂點，依次搜索 4個相鄰方向。若當前頂點 q的 i（ 1≤i≤4 ）方向的相鄰位置未觀察，則按照 q的相對位置計算鏈表 can中每個頂點的絕對坐標，累計 i方向的空地總數 d1和墻的總數 d2： 若鏈表 can中每個頂點的絕對位置 i方向都是空格，則設定 q的 i方向的相鄰位置已觀察，該位置和 i方向進入探索鏈表； 若鏈表 can中每個頂點的絕對位置 i方向都是墻，則設定 q的 i方向的相鄰位置已觀察； 算法流程 所有空地進入 can鏈； （ 0， 0）的四個相鄰格進入 uk鏈； (nowx,nowy） ← (0,0)。 While can鏈的頂點數 1 do { 搜索 uk鏈的每個相對位置（ px,py）： (change過程） { If can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）為墻 Then 設相對位置（ px,py）為墻； If can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）為空地 Then 設相對位置（ px,py）為空地，（ px,py）的 4個相鄰位置進入 uk鏈（不重復） Else 取 uk鏈的下一個相對位置 }； 搜索 uk鏈的每個相對位置（ px,py）：（ find(xx,yy)） { 累計 can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）中墻的總數 d1和空地總數 d2，將 │ d1d2│ 最小的相對位置記為（ xx， yy），并從 uk鏈中刪除該相對位置 }； 使用寬度優(yōu)先搜索方法尋找（ xx， yy）至（ nowx,nowy）的最短路徑，按照這條路徑確定移動和探索方案，并將 can鏈中不符探索結果的方格刪除； (path(nowx,nowy,xx,yy)。 ) }； /*while*/ 為什么要按照 ∣ d1d2∣ 最小的要求刪除鏈表 can中不屬于初始位置的空地？ 若 can中的每塊空地相對于探索鏈表中頂點 p和觀察方向 i來說，有 d1塊空地和 d2堵墻（ d1,d2鏈表 can中的空地數），則看到墻后可以從 can中刪去 d1個不屬于初始位置的空地；看到空地后， can中可被刪除的頂點數為 d2個。由于看見空地的概率為d1/(d1+d2)，看見墻的概率為 d2/(d1+d2) ，所以從 can中刪去不屬于初始位置的空地的概率為 d2*d1/(d1+d2)+d1* d2/(d1+d2) )=2d1*d2/(d1+d2) （ d1+d2為定值）。由此可以看出， d1與 d2愈接近，這個概率值愈大，即從從可能解集中刪去的無用空地數愈多，選擇當前觀察位置和觀察方向愈有價值。按照最小的要求排除，可以使每一次的探索盡量多的縮小初始位置的范圍，使程序盡量減少對運氣的依賴。 數據結構 uses undertpu。 /*調用庫函數 */ const c:array[1..4,1..2] of shortint=((0,1),(1,0),(1,0),(0,1))。 /*i方向上的水平增量為c[i,1],垂直增量為 c[i,2]*/ d:array[1..4] of char=(39。S39。,39。W39。,39。E39。,39。N39。)。 /*四個方向對應的字母 */ st1=39。39。 /*輸入文件名 */ type aa=record /*鏈頂點類型 */ x,y:shortint。 /*坐標 */ next:integer。 /*后繼頂點的數組下標 */ end。 arr=array[0..10000] of aa。 /*鏈表類型 */ var a:array[1..100,1..100] of char。 /*地下城市地圖，其中 a[x,y]=39。O39。表示 (x,y)無墻，a[x,y]=39。W39。表示 (x,y)有墻 */ z:array[100..100,100..100] of char。 /*已知信息組成的新地圖 ,z[