線性表應(yīng)用2014

1、線性表？線性表？本期要點(diǎn)本期要點(diǎn) 線性表的設(shè)計(jì)技巧線性表的設(shè)計(jì)技巧 用數(shù)組模擬動(dòng)態(tài)鏈表用數(shù)組模擬動(dòng)態(tài)鏈表 哈希哈希一、最佳游覽路線一、最佳游覽路線 某游覽區(qū)街道成網(wǎng)絡(luò)狀，東西向的街道是某游覽區(qū)街道成網(wǎng)絡(luò)狀，東西向的街道是旅游街，只能由西向東走，并有一定的分旅游街，只能由西向東走，并有一定的分值，南北向的街道是林蔭道，既可從南向值，南北向的街道是林蔭道，既可從南向北走，也可從北向南走，沒有分值，要求北走，也可從北向南走，沒有分值，要求從某一路口開始游覽，并在另一路口結(jié)束從某一路口開始游覽，并在另一路口結(jié)束游覽，使所走過的街道分值總和最大。其游覽，使所走過的街道分值總和最大。其中中1旅游街道數(shù)目旅

2、游街道數(shù)目100，1林蔭道數(shù)目林蔭道數(shù)目20001，-100分值分值100。 不記錄無用信息不記錄無用信息 規(guī)模規(guī)模 ：100*20001=2000100 ？ 只能由西向東走，每一縱行至多只能通過一次，同只能由西向東走，每一縱行至多只能通過一次，同一縱行可以通過林蔭道自由到達(dá)，只需走分值最大一縱行可以通過林蔭道自由到達(dá)，只需走分值最大的街道，所用空間為的街道，所用空間為20001個(gè)個(gè)shortint。 定義定義Pi為以為以i結(jié)尾的最優(yōu)路徑分值的總和，結(jié)尾的最優(yōu)路徑分值的總和，Ai表示第表示第I縱行的最大分值縱行的最大分值 p0=0 求求max(pi)為負(fù)數(shù)）（非負(fù)數(shù)）iiiiiiAPAPAPP

3、i1110(二、圓桌問題二、圓桌問題 圓桌上圍坐著圓桌上圍坐著2n個(gè)人，其中個(gè)人，其中n個(gè)是好人，個(gè)是好人，n個(gè)是壞人。如果從第一個(gè)人開始數(shù)數(shù)，數(shù)個(gè)是壞人。如果從第一個(gè)人開始數(shù)數(shù)，數(shù)到第到第m人，則立即處死該人。然后從被處死人，則立即處死該人。然后從被處死的人后重新數(shù)數(shù)，數(shù)到第的人后重新數(shù)數(shù)，數(shù)到第m人處死人處死 如何預(yù)先安排如何預(yù)先安排2n人位置，使得在處死人位置，使得在處死n人之人之后，剩下的都是好人。后，剩下的都是好人。靜態(tài)數(shù)組靜態(tài)數(shù)組查找：直接計(jì)算刪除：移動(dòng)for i:=1 to 2*n do bi:=0;for i:=1 to 2*n do ai:=i;k:=1;for i:=1 t

4、o n do begin k:=(k+m-1 ) mod (2*n-i+1); if k=0 then k:=2*n-i+1; bak:=1; for j:=k to 2*n-i do aj:=aj+1; end;O(n2)用數(shù)組模擬鏈表用數(shù)組模擬鏈表for i:=1 to 2*n do begin :=i; ai.next:=i mod (2*n)+1; end;k:=1;for i:=1 to n do begin for j:=1 to m-2 do k:=ak.next; p:=ak.next; :=1; ak.next:=ap.next; k:=ak.n

5、ext; end;type node=record info,next:integer; end;var a:array1.maxn of node; 查找：順序刪除：不產(chǎn)生移動(dòng)O(nm)改進(jìn)改進(jìn)直接定位法直接定位法動(dòng)態(tài)數(shù)組順序Amount：表示此段中現(xiàn)有元素的個(gè)數(shù)Group=4 將原來的數(shù)據(jù)分為4段存儲(chǔ)解釋解釋 Group表示將原來的數(shù)據(jù)分為幾段存儲(chǔ)表示將原來的數(shù)據(jù)分為幾段存儲(chǔ) 每一段的開頭記下每一段的開頭記下amount值表示此段中現(xiàn)值表示此段中現(xiàn)有元素的個(gè)數(shù)有元素的個(gè)數(shù) 隨程序運(yùn)行，隨程序運(yùn)行，amount不斷減小不斷減小 充分利用充分利用“可直接使用可直接使用”的信息的信息充分利用充分

6、利用“可直接使用可直接使用”的信息的信息group:=2*n div m;for i:=1 to group do amounti:=m;if 2*n mod m 0 then begin inc(group); amountgroup:=2*n mod m; end;k:=0;j:=1;for i:=1 to n do begin p:=m; while k+pamountj do begin p:=p+k-amountj;j:=j mod group+1;k:=0; end; ba(j-1)*m+p+k:=1; for l:=(j-1)*m+p+k to (j-1)*m+amountj-1

7、 do al:=al+1; amountj:=amountj-1; k:=k+p-1; end;查找：快速刪除：段內(nèi)移動(dòng)O(nm)三、尋找子串三、尋找子串 從由從由01串構(gòu)成的文件中，找出長(zhǎng)度介于串構(gòu)成的文件中，找出長(zhǎng)度介于A和和B之間出現(xiàn)次數(shù)最多的之間出現(xiàn)次數(shù)最多的N個(gè)不同頻率的子串，個(gè)不同頻率的子串，子串可以相互覆蓋，輸出結(jié)果必須按子串子串可以相互覆蓋，輸出結(jié)果必須按子串出現(xiàn)頻率的降序排列，頻率相同的子串按出現(xiàn)頻率的降序排列，頻率相同的子串按長(zhǎng)度降序排列，頻率和長(zhǎng)度均相同的子串長(zhǎng)度降序排列，頻率和長(zhǎng)度均相同的子串則按其對(duì)應(yīng)數(shù)值降序排列。其中則按其對(duì)應(yīng)數(shù)值降序排列。其中0AB12，0N20，

8、輸入文件可達(dá)到，輸入文件可達(dá)到2MB。分析分析找出所有滿足條件的子串，并統(tǒng)計(jì)各子串找出所有滿足條件的子串，并統(tǒng)計(jì)各子串出現(xiàn)的頻率；出現(xiàn)的頻率；把所有不同子串按要求排序輸出。把所有不同子串按要求排序輸出。選擇二叉樹結(jié)構(gòu)選擇二叉樹結(jié)構(gòu) 樹中的每個(gè)點(diǎn)賦予一定的權(quán)值，表示該點(diǎn)樹中的每個(gè)點(diǎn)賦予一定的權(quán)值，表示該點(diǎn)對(duì)應(yīng)的子串在文件中出現(xiàn)的頻率，可以得對(duì)應(yīng)的子串在文件中出現(xiàn)的頻率，可以得到累加規(guī)律。例如當(dāng)?shù)嚼奂右?guī)律。例如當(dāng)A=1，B=3時(shí)，某中間時(shí)，某中間狀態(tài)：狀態(tài)： 假設(shè)現(xiàn)在讀到一個(gè)串為假設(shè)現(xiàn)在讀到一個(gè)串為“011”，其中以，其中以“0”開頭開頭且長(zhǎng)度為且長(zhǎng)度為1到到3的子串有三個(gè)：的子串有三個(gè)：“0”、

9、“01”、“011”，統(tǒng)計(jì)時(shí)應(yīng)將這三個(gè)子串的頻率加，統(tǒng)計(jì)時(shí)應(yīng)將這三個(gè)子串的頻率加1，從，從圖上可以直觀地看到，這個(gè)操作相當(dāng)于在對(duì)圖上可以直觀地看到，這個(gè)操作相當(dāng)于在對(duì)應(yīng)的應(yīng)的01路徑上將各結(jié)點(diǎn)的頻率加路徑上將各結(jié)點(diǎn)的頻率加1 對(duì)應(yīng)二叉樹的結(jié)點(diǎn)最大為對(duì)應(yīng)二叉樹的結(jié)點(diǎn)最大為213-18191，可，可以多次遍歷，不難從中找出前以多次遍歷，不難從中找出前N個(gè)頻率最大個(gè)頻率最大的子串，然后按從大到小的順序輸出。的子串，然后按從大到小的順序輸出。 出現(xiàn)次數(shù)不是最多的字串被重復(fù)使用出現(xiàn)次數(shù)不是最多的字串被重復(fù)使用采用數(shù)組存儲(chǔ)采用數(shù)組存儲(chǔ) 一個(gè)二維數(shù)組來表示矩陣結(jié)構(gòu)，一個(gè)二維數(shù)組來表示矩陣結(jié)構(gòu)，x軸表示數(shù)據(jù)的

10、元軸表示數(shù)據(jù)的元素，素，y軸表示元素各種狀態(tài)條件。數(shù)組內(nèi)具體的值軸表示元素各種狀態(tài)條件。數(shù)組內(nèi)具體的值表示元素在當(dāng)前狀態(tài)條件下的表現(xiàn)，一般用數(shù)值表示元素在當(dāng)前狀態(tài)條件下的表現(xiàn)，一般用數(shù)值表示。表示。 每一個(gè)僅由每一個(gè)僅由0和和1組成的子串也可以當(dāng)作二組成的子串也可以當(dāng)作二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)來表示進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)來表示 “10”、“010”和和“0010” 長(zhǎng)度的差別長(zhǎng)度的差別 設(shè)定了設(shè)定了“長(zhǎng)度長(zhǎng)度”座標(biāo)座標(biāo) 查找出頻率最大的前查找出頻率最大的前N個(gè)串個(gè)串 四、團(tuán)隊(duì)隊(duì)列四、團(tuán)隊(duì)隊(duì)列 在一個(gè)團(tuán)隊(duì)隊(duì)列中每個(gè)元素屬于一個(gè)團(tuán)隊(duì)。在一個(gè)團(tuán)隊(duì)隊(duì)列中每個(gè)元素屬于一個(gè)團(tuán)隊(duì)。當(dāng)一個(gè)元素進(jìn)入隊(duì)列時(shí)，他首先從

11、隊(duì)列的當(dāng)一個(gè)元素進(jìn)入隊(duì)列時(shí)，他首先從隊(duì)列的首部到尾部搜索檢查是否他的隊(duì)友已經(jīng)在首部到尾部搜索檢查是否他的隊(duì)友已經(jīng)在隊(duì)列中。如果有的話，該元素進(jìn)入隊(duì)列排隊(duì)列中。如果有的話，該元素進(jìn)入隊(duì)列排在他的隊(duì)友的后面。如果沒有，他進(jìn)入隊(duì)在他的隊(duì)友的后面。如果沒有，他進(jìn)入隊(duì)列排在隊(duì)列尾部，成為最后一個(gè)新元素。列排在隊(duì)列尾部，成為最后一個(gè)新元素。出隊(duì)列如同正常的隊(duì)列操作：按元素在團(tuán)出隊(duì)列如同正常的隊(duì)列操作：按元素在團(tuán)隊(duì)隊(duì)列中的順序，從頭到尾出隊(duì)列。隊(duì)隊(duì)列中的順序，從頭到尾出隊(duì)列。 模擬團(tuán)隊(duì)隊(duì)列的過程。模擬團(tuán)隊(duì)隊(duì)列的過程。輸入輸入 團(tuán)隊(duì)數(shù)目團(tuán)隊(duì)數(shù)目t（1=t0 then qteamr1.next:=r else

12、f:=r; r1:=belongx; enelse begin k:=teambelongx; qr.next:=qk.next; qk.next:=r; teambelongx:=r; end;出隊(duì)出隊(duì)writeln(qf.num);if (qf.next=0) or (belongqf.numbelongqqf.next.num) then teambelongqf.num:=0;f:=qf.next;五、五、10-20-30 52張不分花色。張不分花色。J、Q、K為為10，A為為1，其余，其余為點(diǎn)數(shù)。為點(diǎn)數(shù)。 從左到右從左到右7組。按序發(fā)牌組。按序發(fā)牌(組別、牌堆上下組別、牌堆上下) 每

13、組每組10-20-30： 前兩張和最后一張前兩張和最后一張 第一張和最后二張第一張和最后二張 最后三張最后三張 抽出并放入牌堆底部抽出并放入牌堆底部 全部抽走即全部抽走即“消失消失”7組均消失，獲勝無牌發(fā)，失敗平局輸入輸入/出樣例出樣例 2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1 10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2 4 3 2 10 8 10 6 8 9 5 8 10 5 3 5 4 6 9 9 1 7 6 3 5 10 10 8 10

14、 9 10 10 7 2 6 10 10 4 10 1 3 10 1 1 10 2 2 10 4 10 7 7 10 10 5 4 3 5 7 10 8 2 3 9 10 8 4 5 1 7 6 7 2 6 9 10 2 3 10 3 4 4 9 10 1 1 10 5 10 10 1 8 10 7 8 10 6 10 10 10 9 6 2 10 10 Win : 66 Loss: 82 Draw: 73狀態(tài)查找及判重先考慮能定勝負(fù)的情況先考慮能定勝負(fù)的情況 模擬鏈表模擬鏈表 ？字符串？字符串type node=record info:longint; next:longint; front

15、:longint; end;Var q:array0.53 of node; team:array1.8,1.3 of longint; count,total:longint; for i:=1 to 52 do begin read(); qi.next:=i+1; qi.front:=i-1; end;q7.next:=1; q1.front:=7;for i:=1 to 7 do begin teami,1:=1; teami,2:=i;teami,3:=i end;team8,3:=52;team8,2:=8; team8,1:=52-7; 發(fā)牌發(fā)牌total:=tot

16、al+1;p1:=teamcount+1,2; p2:=teami,3;p3:=qp2.next;TeamiTeami+1Teamcount+1nextfrontp1p2p3teamcount+1,2:=qp1.next;p1.front:=p2;qp1.next:=p3; qp3.front:=p1; qp2.next:=p1; teami,3:=p1;inc(teami,1); dec(teamcount+1,1);輸輸抽牌抽牌p1:=qp.front;p2:=qp.next;p3:=teamcount+1,3; 120TeamiTeami+1Teamcount+1Teami-1qp1.n

17、ext:=p2; qp2.front:=p1; qp3.next:=p; qp.front:=p3;inc(teamcount+1,1); teamcount+1,3:=p; dec(teami,1);if k=1 then teami,2:=p2 else if k=0 then teami,3:=p1;p1p2p3p 對(duì)于頻繁使用的查找，我們希望平均查找對(duì)于頻繁使用的查找，我們希望平均查找長(zhǎng)度接近于長(zhǎng)度接近于0預(yù)先知道所查關(guān)鍵字在表中的位置預(yù)先知道所查關(guān)鍵字在表中的位置記錄在表中位置和其關(guān)鍵字之間存在一記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系種確定的關(guān)系判重決策判重決策 哈希表：哈希

18、表：應(yīng)用應(yīng)用哈希函數(shù)哈希函數(shù)，由記錄的關(guān)鍵字確，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表。這樣構(gòu)成的表叫哈希表。 哈希查找：哈希查找：又叫散列查找，利用又叫散列查找，利用哈希函數(shù)哈希函數(shù)進(jìn)進(jìn)行查找。行查找。 哈希表的數(shù)組是定長(zhǎng)的，如果太大，則浪費(fèi)，哈希表的數(shù)組是定長(zhǎng)的，如果太大，則浪費(fèi)，如果太小，體現(xiàn)不出效率。合適的數(shù)組大小如果太小，體現(xiàn)不出效率。合適的數(shù)組大小是哈希表的性能的關(guān)鍵。是哈希表的性能的關(guān)鍵。 哈希表的尺寸最好是一個(gè)質(zhì)數(shù)。哈希表的尺寸最好是一個(gè)質(zhì)數(shù)。哈希（哈希（hash）構(gòu)造哈希函數(shù)的幾種方法構(gòu)造哈希函數(shù)的

19、幾種方法 對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理1. 直接定址法直接定址法3. 平方取中法平方取中法4. 折疊法折疊法6. 隨機(jī)數(shù)法隨機(jī)數(shù)法2. 數(shù)字分析法數(shù)字分析法1. 直接定址法直接定址法 構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希函數(shù)作哈希函數(shù) H(key) = key 或者或者 H(key) = a. key + b 特點(diǎn)特點(diǎn) 直接定址法所得地址集合與關(guān)鍵字集合大小相直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突等，不會(huì)發(fā)生沖突2. 除

20、留余數(shù)法除留余數(shù)法 構(gòu)造：關(guān)鍵字被某個(gè)不大于構(gòu)造：關(guān)鍵字被某個(gè)不大于hash表長(zhǎng)（表長(zhǎng)（m）的數(shù)的數(shù)p求余做哈希地址，即求余做哈希地址，即 H(key)=key % p p通常取小于通常取小于hash表長(zhǎng)的最大素?cái)?shù)表長(zhǎng)的最大素?cái)?shù) 特點(diǎn)特點(diǎn) 簡(jiǎn)單、常用簡(jiǎn)單、常用 p的選取很重要的選取很重要: p選的不好，容易產(chǎn)生同義詞選的不好，容易產(chǎn)生同義詞對(duì)對(duì)P要加一定的限制要加一定的限制3.隨機(jī)數(shù)法隨機(jī)數(shù)法 構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址H(key)=random(key) 適于關(guān)鍵字長(zhǎng)度不等的情況適于關(guān)鍵字長(zhǎng)度不等的情況回到回到10-20-30 7組狀態(tài)合一謀取高

21、效率（其實(shí)可看成組狀態(tài)合一謀取高效率（其實(shí)可看成8組）組） 狀態(tài)？狀態(tài)？ 通過通過ABCDEFGH分割分割 2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1 10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2 A2 10 B6 10 C5 4 D10 5 E10 10 F4 4 G10 5 H10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1 10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8

22、2哈希函數(shù)哈希函數(shù)1999997%13*)inf.()(1.0lenqiioiqshash1000009%13*)inf.()(2.1lenqiioiqshash 為產(chǎn)生沖突的關(guān)鍵字尋找一個(gè)新的地址為產(chǎn)生沖突的關(guān)鍵字尋找一個(gè)新的地址Hi(key)， 求得一個(gè)地址序列求得一個(gè)地址序列 H0, H1, H2, , Hs 1 sm-1 其中：其中：H0 = H(key) H1 = (H(key) + d1 ) % m H2 = (H(key) + d2 ) % m Hi = ( H(key) + di ) % m i=1, 2, , s解決沖突解決沖突開放地址法開放地址法 線性探測(cè)：線性探測(cè)：di=

23、1,2,3,m-1 二次探測(cè)：二次探測(cè)：di=1,-1,2,-2,3,k增量增量diNoip初賽題初賽題廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是（廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）A鏈表鏈表 B隊(duì)列隊(duì)列 C棧棧 D散列表散列表 散列表的地址區(qū)間為散列表的地址區(qū)間為0-10,散列函數(shù)為散列函數(shù)為H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列關(guān)鍵字序列26，25，72，38，8，18，59存儲(chǔ)到散存儲(chǔ)到散列表中，這些元素存入散列表的順序并不確定。列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素假定之前散列表為空，則元素59存放在散列表中存放在散列表中的可能地址有：的可能地址有：A)