【正文】 點的左枝為 0右枝為 1，這樣一個子串可以與這棵二叉樹中的一條路徑一一對應(yīng) 樹中的每個點賦予一定的權(quán)值，表示該點對應(yīng)的子串在文件中出現(xiàn)的頻率，那么我們可以得到一些累加規(guī)律，例如當(dāng) A=1， B=3時，某個中間狀態(tài)對應(yīng)的二叉樹 假設(shè)現(xiàn)在讀到一個串為 “ 011”，其中以 “ 0”開頭且長度為 1到 3的子串有三個： “ 0”、 “ 01”、“ 011”，統(tǒng)計時應(yīng)將這三個子串的頻率加 1，這個操作相當(dāng)于在對應(yīng)的 01路徑上將各頂點的頻率加 1 鑒于對應(yīng)二叉樹的頂點很少（最大為 2131＝ 8191），完全可以多次遍歷，不難從中找出前 N個頻率最大的子串，然后按從大到小的順序輸出 。 分段式數(shù)組 結(jié)合了鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)，兼具了這兩種存儲結(jié)構(gòu)的優(yōu)點，將 “ 不可直接使用 ”的信息轉(zhuǎn)化成了 “ 可直接使用 ” 的信息，算法效率的提高自然在情理之中。 /*記下當(dāng)前段的位移 */ amount[j]←amount[j] 1 /*第 j段的元素數(shù) 1*/ }。 /* 起始段和段內(nèi)位移初始化 */ fillchar(ans,sizeof(ans),false)。 /*排列方案 ,其中 ans[i]為第 i個元素的出列標(biāo)志 */ { readln(n,m)。 這都是由數(shù)據(jù)結(jié)構(gòu)本身決定的，不會隨人的主觀意志存在或消失?？筛鶕?jù)前一個出隊元素的位置（即數(shù)組下標(biāo)）直接定位，找到下一個出隊元素的位置，然后刪去，并將它后面的元素全部前移一次。 圓桌問題 圓桌上圍坐著個人。數(shù)據(jù)的存儲結(jié)構(gòu)影響算法的效率。數(shù)據(jù)關(guān)系上的 構(gòu)造策略 上海市控江中學(xué) xxx 數(shù)據(jù)結(jié)構(gòu)回顧 “數(shù)據(jù)結(jié)構(gòu)＋算法＝程序 ” 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。線性存儲結(jié)構(gòu)分 ⑴、 順序存儲結(jié)構(gòu) ⑵、 鏈?zhǔn)酱鎯Y(jié)構(gòu) 非線性存儲結(jié)構(gòu)一般也是通過線性的存儲方式存入計算機的（例如圖的相鄰矩陣和鄰接表） ； 選擇數(shù)據(jù)的邏輯結(jié)構(gòu)的基本原則 在某些復(fù)雜的問題中，數(shù)據(jù)之間的關(guān)系相當(dāng)復(fù)雜，可選用的邏輯結(jié)構(gòu)可能不止一種。其中個人是好人，另外個人是壞人。 優(yōu)點 :“找點 ” 時，可以由現(xiàn)在出隊元素的位置直接計算并在數(shù)組中精確定位； 缺點 :“去點 ” 時都需要把它后面所有的元素整體移動一次。這就表明 “ 找點 ” 和 “ 去點 ” 的時間復(fù)雜度不會同時降為 O(1)。 /*讀好人和壞人的人數(shù) n和步長值 m*/ fillchar(amount,sizeof(amount),0)。/*初始時全 “ 好人 ” */ for i←1 to n do /* 依次出列 n個元素 */ { k←m。/*for*/ for i←1 to n+n do /* 輸出排列方案 */ { if ans[i] /*出隊的是 “ 壞人 ” ，留下的是 “ 好人 ” */ then write(39。 選擇邏輯結(jié)構(gòu)的因素 2： 不記錄 “ 無用 ” 信息 一般情況下，數(shù)據(jù)結(jié)構(gòu)愈復(fù)雜，可包含的信息量愈大。 統(tǒng)計所有子串的頻率 先構(gòu)造一棵深度為 b的空二叉樹； 以第 b位為尾，分別將長度為 b、 b … 1，的子串送入二叉樹，統(tǒng)計出各子串的頻率； 以第 b+1位為尾，重復(fù)上述過程； … 直至左移至串尾為止。..39。 /*子串的類型 */ var t:array[1..21] of longint。 /*從 floor層出發(fā) ,生成以 p為根的空樹 */ { p^.num←0。/* maketree */ proc init。 /*p的權(quán)值 +1*/ if floorlong /*若層數(shù)未超出子串長度 */ then if ((m and tc[longfloor])=0) /*若 m的第longfloor個二進(jìn)制位為 0,則遞歸左子樹 。 /* 子串的有效長度和初始值為零 ,*/ yu←tc[b+1]。 /* 生成當(dāng)前有效子串 */ inc(long)。 /*循環(huán)變量 */ { if floor=a /*若層數(shù)不低于下限 ,則將 p的權(quán)值插入 t序列的合適位置 。 /*若層數(shù)小于上限 ,則分別遞歸左右子樹 */ }。 39。/*then*/ }。 /*設(shè)置緩沖區(qū) */ for which←1 to n do /* 按照降序枚舉頻率順序 */ { write(outf,t[which])。 /*關(guān)閉輸出文件 */ }。 /*按要求輸出結(jié)果 */ }./*main*/ ⑴ “一對多 ” 的關(guān)系有利于處理好數(shù)據(jù)； ⑵ 規(guī)律性強。 數(shù)據(jù)結(jié)構(gòu) const inputfile=39。..39。 /*輸入文件變量和輸出文件變量 */ a,b,n,long,kind:byte。/*輸入子串的長度范圍和不同頻率的子串個數(shù) */ for i←1 to b do/* 各長度的子串頻率清零 */ { new(tk[i])。 then exit。 /*循環(huán)變量 */ { fillchar(t,sizeof(t),0)。/*for*/ }。 39。/*for*/ close(outf)。 /*關(guān)閉輸入文件 */ sort。例如通過二維數(shù)組的相鄰表存儲圖，用一維的記錄數(shù)組存儲樹。你需要通過一系列的移動（ move（方向）指令，即走入指定方向上的相鄰格）和探索（ look(方向 )指令，即詢問指定方向上的相鄰格是空地還是墻），以確定初始時所在的位置。通過移動和探索過程得出初始位置 (x， y)后，調(diào)用finish(x， y)指令向系統(tǒng)報告。 While can鏈的頂點數(shù) 1 do { 搜索 uk鏈的每個相對位置（ px,py）： (change過程） { If can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）為墻 Then 設(shè)相對位置（ px,py）為墻； If can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）為空地 Then 設(shè)相對位置（ px,py）為空地，（ px,py）的 4個相鄰位置進(jìn)入 uk鏈（不重復(fù)） Else 取 uk鏈的下一個相對位置 }； 搜索 uk鏈的每個相對位置（ px,py）：（ find(xx,yy)） { 累計 can中每個空地（ x,y）相對（ px,py）的格子（ px+x,py+y）中墻的總數(shù) d1和空地總數(shù) d2，將 │ d1d2│ 最小的相對位置記為（ xx， yy），并從 uk鏈中刪除該相對位置 }； 使用寬度優(yōu)先搜索方法尋找（ xx， yy）至（ nowx,nowy）的最短路徑，按照這條路徑確定移動和探索方案，并將 can鏈中不符探索結(jié)果的方格刪除； (path(nowx,nowy,xx,yy)。S39。 /*四個方向?qū)?yīng)的字母 */ st1=39。O39?！?x,y)有墻； 39。 /*探索前的準(zhǔn)備 */ start。/*main*/ readp過程：讀入城市地圖 a proc readp。/*for*/ close(f)。 with uk^[tail]do { x←xx+c[i,1]。nowy←0。 /* 所有空地置入 can鏈表 */ for i←1 to u do for j←1 to v do if a[i,j]=39。 /*can 鏈尾的后繼指針為空 */ new(uk)。 while uk^[i].nexttail do /*沿 next指針取出 uk鏈中的每一個相對位置 (px,py)*/ { px←uk^[uk^[i].next].x。 /* 記錄該方格可能無墻 */ }。/* 若 can鏈中的所有空地相對 (px,py)的方格狀態(tài)未確定，則取 uk鏈的下一個相對位置 */ }。 d1←0。 o←i。 var p:arr。O39。 /*出隊 */ }。nowy←p[l].y。P39。j←k }。 數(shù)據(jù)結(jié)構(gòu)的 “ 并聯(lián) ” 將用多個數(shù)據(jù)結(jié)構(gòu)應(yīng)用于同一數(shù)據(jù)集合的方法叫做數(shù)據(jù)結(jié)構(gòu)的并聯(lián)，這種數(shù)據(jù)結(jié)構(gòu)的結(jié)合方式不僅可以將多種存儲結(jié)構(gòu)的優(yōu)點完全發(fā)揮了出來，而且還可以通過映射建立不同數(shù)據(jù)結(jié)構(gòu)中元素間的對應(yīng)關(guān)系。 (圖 (b))中頂點旁的數(shù)字給出了對應(yīng)猴子落地的時間。 var n,i,j,k,t:longint。 /*答案，其中猴子 i的落地時間為time[i]*/ { readln(n)。 /*讀時間數(shù) */ for i←1 to t do /* 依次讀入每個時刻的松手情況 */ { readln(j,ch,ch)。open[i]^.next←nil。 while pnil do{ time[p^.v]←i。,time[i])}.{main} 數(shù)據(jù)結(jié)構(gòu)并聯(lián)方式的利弊 數(shù)據(jù)結(jié)構(gòu)支持的操作分為兩類： ⑴詢問操作：顧名思義，就是獲取該數(shù)據(jù)結(jié)構(gòu)記錄的某些信息的操作，而并沒有改動數(shù)據(jù)結(jié)構(gòu)里的元素及其相互關(guān)系。 初始時 v0進(jìn)入第一組， v0的距離值為 0；第二組包含其它所有結(jié)點，這些結(jié)點對應(yīng)的距離值這樣確定（設(shè) vi為第二組中的結(jié)點） 然后每次從第二組的結(jié)點中選一個其距離值為最小的結(jié)點 vm加到第一組中。通常情況下，邊數(shù) |E|都不小于頂點數(shù)|V|，所以運行時間又可以簡化為 O(ElgV)。 Dijkstra算法每次尋找一條最短路徑時，需要兩個步驟： ⑴使用貪心策略，找一個不在最短路徑起點集合內(nèi)、并且到終點距離最短的頂點 i。 ⑵進(jìn)行松弛操作，修改從與 i相鄰的頂點到終點的路徑長度。但實現(xiàn)相當(dāng)繁瑣，在較短的時間里基本上不大可能寫出程序并調(diào)試好。修改后再選距離值最小的一個結(jié)點加入到第一組中， … 。 對于這兩類操作，數(shù)據(jù)結(jié)構(gòu)的并聯(lián)方式有利有弊。/*then*/ closed[j]^.next←open[k]。 for i←t downto 1 do /* 倒推時間，將每個時刻斷開的邊連上 */ { k←tree[e[i,1],e[i,2]]。l39。 for i←2 to n do /* 依次讀入每個猴子的連接情況 */ { readln(j,ch,ch)。 /*左（ ‘ l?） 右 (?r?)手標(biāo)志 */ p:point。 用并查集維護(hù) 當(dāng)并查集中某個集合加入編號為 1的點所在的集合時，需要把這個集合中的所有元素的時間記錄一下 (圖（ a） )。每只猴子都有兩只手，編號為 1的猴子的尾巴掛在樹枝上，其它猴子的尾巴都被別的猴子的某只手抓著。/*while*/ }。O39。 e←look(d[i])。j←p[l].next。p[t].x←p[s].x+c[k,1]。 /*隊首指針為 s，隊尾指針為 t*/ { p[1].x←x2。yy←py }。 while can^[j].next0 do /*在 can鏈表的每個空地相對于 (px,py)的方格中，累計墻的總數(shù) d1和空地的總數(shù) d2*/ { j←can^[j].next。/* change */ find：尋找對運氣的依賴度最小的相對位置 (xx,yy)，并將其從 uk鏈表中刪除 proc find(var xx,yy:integer)。 if d=1 then z[px,py]←39。 d←0。uk^[0].next←1。 then{ inc(rest)。Q39。 next←tail+1 }。/* readp */ 對 (xx,yy)的相鄰格進(jìn)行探索 proc changeUK(xx,yy:integer)。 /*文件變量 */ i,j:in