【正文】 數(shù)據(jù)關系上的 構造策略 上海市控江中學 xxx 數(shù)據(jù)結構回顧 “數(shù)據(jù)結構＋算法＝程序 ” 數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。對確定的問題選擇一種合適的數(shù)據(jù)結構，加上設計一種好的算法，就是所謂的程序設計 。 數(shù)據(jù)的邏輯結構 定義：用數(shù)學方法來描述問題中所涉及的操作對象及對象之間的關系，將操作對象抽象為數(shù)據(jù)元素，將對象之間的復雜關系用數(shù)學語言描述出來。 重要性：設計數(shù)學模型的基礎是確定數(shù)據(jù)的邏輯結構，而算法又是用來解決數(shù)學模型的。要使得算法效率高，必須提高數(shù)據(jù)的邏輯結構中信息的利用效果。 基本的邏輯結構： ⑴、 集合 ——集合中的數(shù)據(jù)元素之間只有 “ 同屬于一個集合 ” 的關系 ⑵、 線性結構 ——“一對一 ” 的關系 ⑶、 樹形結構 ——一對多 ” 的關系 ⑷、 圖狀（網(wǎng)狀）結構 ——“多對多 ” 的關系。 數(shù)據(jù)的存儲結構 如何實現(xiàn)對各個對象的操作，即各對象之間的關系在計算機中如何表示。數(shù)據(jù)的存儲結構影響算法的效率。線性存儲結構分 ⑴、 順序存儲結構 ⑵、 鏈式存儲結構 非線性存儲結構一般也是通過線性的存儲方式存入計算機的（例如圖的相鄰矩陣和鄰接表） ； 選擇數(shù)據(jù)的邏輯結構的基本原則 在某些復雜的問題中，數(shù)據(jù)之間的關系相當復雜，可選用的邏輯結構可能不止一種。但選用哪種邏輯結構，直接影響算法效率。一般來講，選擇合理邏輯結構應充分考慮的兩個因素 ⑴充分利用 “ 可直接使用 ” 的信息 ⑵不記錄 “ 無用 ” 信息 選擇邏輯結構的因素 1： 充分利用 “ 可直接使用 ” 的信息 “信息 ” 指的是元素與元素之間的關系。一般分為 “ 可直接使用 ” ： 只需直接拿來即可。 “ 不可直接使用 ” ： 可通過某些間接的方式，使之成為可以使用的信息，但其中轉(zhuǎn)化的過程需要花費一定的時間。 由此可見，我們所需要的是盡量多的 “ 可直接使用 ” 的信息。這樣的信息越多，算法的效率就會越 高。 圓桌問題 圓桌上圍坐著個人。其中個人是好人，另外個人是壞人。如果從第一個人開始數(shù)數(shù)，數(shù)到第個人，則立即處死該人；然后從被處死的人之后開始數(shù)數(shù)，再將數(shù)到的第個人處死 …… 依此方法不斷處死圍坐在圓桌上的人。試問預先應如何安排這些好人與壞人的座位，能使得在處死個人之后，圓桌上圍坐的剩余的個人全是好人。 輸入：好人和壞人的人數(shù) n（ n≤32767 ）、步長 m（ m ≤32767 ）； 輸出： 2個大寫字母， ‘ G’表示好人， ‘ B’表示壞人，50個字母為一行，不允許出現(xiàn)空白字符和空行。 例如 n= m=3時，依次列出 “ 處死 5人 ” 的操作： 該題實際上是在一個長度為 2*n的圓排列上，以 m為間隔進行 n次出隊操作。 普通解法 ——線性表 “ 查找 ” 法 ① 、用順序存儲結構實現(xiàn)。即使用數(shù)組記錄當前圓排列中每個元素的初始位置，初始值為 1… 2n?？筛鶕?jù)前一個出隊元素的位置（即數(shù)組下標）直接定位，找到下一個出隊元素的位置，然后刪去，并將它后面的元素全部前移一次。 優(yōu)點 :“找點 ” 時，可以由現(xiàn)在出隊元素的位置直接計算并在數(shù)組中精確定位； 缺點 :“去點 ” 時都需要把它后面所有的元素整體移動一次。 “ 去點 ” 時的元素移動就是信息由 “ 不可直接使用 ” 向 “ 可直接使用 ” 的轉(zhuǎn)化過程，其時間復雜度為 O(n)。由于出隊元素有 n個，因此程序的整體時間復雜度是 O(n2)。 ② 、用鏈式存儲結構實現(xiàn) 用鏈表記錄當前圓排列中每個元素的初始位置，初始值為 1..2n。每出隊一個元素后，只要將這個元素直接從鏈表中刪去即可，然后指針后移 (m1)次，找到下一個出隊元素。 n=5,m=3的初始鏈表 依次列出了 “ 處死 5人 ” 的操作（☆為當前出隊元素的鏈表位置） 優(yōu)點： “ 去點 ” 時只要修改應該被刪除頂點的父指針的指向就可以了，毋需移動元素； 缺點： “ 找點 ” 時需要移動 (m1)次定位指針； 所以應用鏈式存儲結構，程序的整體時間復雜度是 O(nm)。 改進解法 ——“直接定位法 ” 從哲學角度分析， “ 找點 ” 和 “ 去點 ” 是存在于程序和數(shù)據(jù)結構中的一對矛盾： 應用順序存儲結構時， “ 找點 ” 效率高而 “ 去點 ”效率低； 應用鏈式存儲結構時， “ 去點 ” 效率高而 “ 找點 ”效率低 。 這都是由數(shù)據(jù)結構本身決定的，不會隨人的主觀意志存在或消失。這就表明 “ 找點 ” 和 “ 去點 ” 的時間復雜度不會同時降為 O(1)。我們希望有這樣一種數(shù)據(jù)結構，在實現(xiàn) “ 找點 ” 和 “ 去點 ” 時，使復雜度降到盡量低。 總體思想：在較好地實現(xiàn) “ 直接定位 ”的基礎上，盡量避免大量元素移動 Group—段數(shù)； Amount—段中現(xiàn)有元素個數(shù)。隨程序運行，段內(nèi)出隊元素右方的元素左移， amount值不斷減小。 var n,m,i,j,k,l,p,g:longint。 /*好人和壞人的人數(shù)為 n，步長值為 m，上次出列元素的段內(nèi)位移為 p，當前出列元素位于其右方第 k個位置，即段內(nèi)位移為 k+p*/ t,amount:array [1..65535] of longint。 /* 分段式數(shù)組為amount，其中第 i段中的元素數(shù)為 amount[i]， t為當前排列 */ ans:array[1..65535]of boolean。 /*排列方案 ,其中 ans[i]為第 i個元素的出列標志 */ { readln(n,m)。 /*讀好人和壞人的人數(shù) n和步長值 m*/ fillchar(amount,sizeof(amount),0)。 /*各段為空 */ g←1。 /* 從第 1段開始構建分段式數(shù)組 */ for i←1 to n+n do { t[i]←i。inc(amount[g])。 /* 設置第 i個位置序號，累計第 g段的元素數(shù) */ if amount[g]=m then inc(g) }。/*若第 g段滿，則新增一個段 */ j←1。p←0。 /* 起始段和段內(nèi)位移初始化 */ fillchar(ans,sizeof(ans),false)。/*初始時全 “ 好人 ” */ for i←1 to n do /* 依次出列 n個元素 */ { k←m。 /* 計算第 i個出列元素所在的段號 j和段內(nèi)位移 k+p*/ while k+pamount[j]do { k←k+p amount[j]。j←(j mod g)+1。p←0 }。/*while */ ans[t[(j1)*m+k+p]]←true。 /* 第 (j1)*m+k+p個元素作為 “ 壞人 ” 出列 */ for l←(j 1)*m+k+p to(j1)*m+amount[j]1 do t[l]←t[l+1]。 /*第 j段 k+p位置右方所有元素依次左移一個位置 */ p←k+p 1。 /*記下當前段的位移 */ amount[j]←amount[j] 1 /*第 j段的元素數(shù) 1*/ }。/*for*/ for i←1 to n+n do /* 輸出排列方案 */ { if ans[i] /*出隊的是 “ 壞人 ” ，留下的是 “ 好人 ” */ then write(39。B39。) else write(39。G39。)。 if (i mod 50=0)and(in*2)then writeln/*50個數(shù)組成一行 */ }/*for*/ }.{main} “直接定位法 ” 較好的體現(xiàn)出 “ 直接定位 ” 的思想，而且由于將所有的頂點分為若干段之后，每次刪除一個頂點后，需要移動的頂點數(shù)相對而言不是很多，這樣就使程序效率大大提高，且 m越大，這種效果越明顯。 順序存儲結構 在 “ 去點 ” 的問題上需要數(shù)據(jù)移動； 鏈式存儲結構 在 “ 找點 ” 的問題上需要指針移動， 因此線性表中的信息屬于 “ 不可直接使用 ” 的信息。 分段式數(shù)組 結合了鏈式存儲結構與順序存儲結構，兼具了這兩種存儲結構的優(yōu)點，將 “ 不可直接使用 ”的信息轉(zhuǎn)化成了 “ 可直接使用 ” 的信息，算法效率的提高自然在情理之中。 選擇邏輯結構的因素 2： 不記錄 “ 無用 ” 信息 一般情況下，數(shù)據(jù)結構愈復雜，可包含的信息量愈大。但并不意味著我們一定要使用復雜的數(shù)據(jù)結構。在某些時候，復雜的數(shù)據(jù)結構中容易混雜冗余信息。 數(shù)據(jù)結構內(nèi)含的信息多自然是好事，但倘若其中 “ 無用 ” （不需要）的信息太多，就只會增加我們思考分析和處理問題時的復雜程度， 尋找子串 從由 01串構成的文件中，找出長度介于 A和 B之間出現(xiàn)次數(shù)最多的 N個不同頻率的子串，子串可以相互覆蓋，輸出結果必須按子串出現(xiàn)頻率的降序排列，頻率相同的子串按長度降序排列，頻率和長度均相同的子串則按其對應數(shù)值降序排列。其中 0＜A≤B≤12 ， 0＜ N≤20 ，輸入文件可達到 2MB。 輸入：第 1行為 ‘ a b n’，表明子串的長度范圍為 [a， b]和不同頻率的子串數(shù) n；從第 2行開始為由 01串構成的文件，以‘ 2’為結束標志； 輸出： n行，其中第 i行的行首為第 i大的頻率，接下來按照長度遞減、長度相同的子串按其對應數(shù)值遞減的順序給出該頻率的子串，子串與子串之間用空格隔開。 完成以下兩步操作 ⑴ 找出 n個滿足條件（長度介于 A和 B之間且出現(xiàn)次數(shù)最多）的子串，并統(tǒng)計各子串出現(xiàn)的頻率； ⑵把所有不同子串按降序要求（頻率為第一關鍵字、長度為第二關鍵字、對應數(shù)值為第三關鍵字且降序）輸出。 所有的子串及其頻率的存儲方式有兩種 ⑴、采用二叉樹結構 ⑵、采用矩陣結構 ⑴ 、采用二叉樹結構 最上的為根頂點，定義每個頂點的左枝為 0右枝為 1，這樣一個子串可以與這棵二叉樹中的一條路徑一一對應 樹中的每個點賦予一定的權值，表示該點對應的子串在文件中出現(xiàn)的頻率，那么我們可以得到一些累加規(guī)律，例如當 A=1， B=3時，某個中間狀態(tài)對應的二叉樹 假設現(xiàn)在讀到一個串為 “ 011”，其中以 “ 0”開頭且長度為 1到 3的子串有三個： “ 0”、 “ 01”、“ 011”，統(tǒng)計時應將這三個子串的頻率加 1，這個操作相當于在對應的 01路徑上將各頂點的頻率加 1 鑒于對應二叉樹的頂點很少（最大為 2131＝ 8191），完全可以多次遍歷，不難從中找出前 N個頻率最大的子串，然后按從大到小的順序輸出 。 統(tǒng)計所有子串的頻率 先構造一棵深度為 b的空二叉樹； 以第 b位為尾，分別將長度為 b、 b … 1，的子串送入二叉樹，統(tǒng)計出各子串的頻率； 以第 b+1位為尾，重復上述過程； … 直至左移至串尾為止。 數(shù)據(jù)結構 const inputfile=39。39。outfile= 39。39。 /*輸入文件名和輸出文件名 */ tc:array[1..13]of integer=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096)。/*tc[i]=2i1*/ tz:array[39。039。..39。139。] of byte=(0,1)。 /*字符轉(zhuǎn)數(shù)值 */ type point=^node。 /*二叉樹的指針類型 */ node=record /*頂點類型 */ l,r:point。 /* 左右指針 (分別對應字符 0和 1*/ num:longint。 /*權值 ,即頂點對應子串的頻率 */ end。 ar=string[12]。 /*子串的類型 */ var t:array[1..21] of longint。 /*不同頻率按降序要求排列成 t*/ tch:array[1..1024] of char。 /*緩沖區(qū) */ tree:point。 /*二叉樹的根 */ inf,outf:text。