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