從一個(gè)策略游戲談搜索算法優(yōu)化

1、.從一個(gè)策略游戲談搜索算法優(yōu)化從一個(gè)策略游戲談搜索算法優(yōu)化對(duì)于策略游戲性質(zhì)的二人博弈問題，比方黑白棋，五子棋等，一般的解答方法就是搜索；但搜索算法的原理不同，其性能就大不一樣。一般來說，假設(shè)我們對(duì)問題的本質(zhì)把握的越深，算法的設(shè)計(jì)就會(huì)相對(duì)的復(fù)雜，但是效率會(huì)高很多。下面我們就通過一個(gè)二人游戲來談這方面的體會(huì)。一.問題的提出問題：TwoFour羅馬尼亞奧林匹克,via Stroe,2002Bessie有一個(gè)新的兩人游戲：TwoFour.她有N3=N=30堆球,每堆有nballs0=nballs=4個(gè).球的總數(shù)為2*N.玩這個(gè)游戲時(shí),游戲者輪流執(zhí)行一個(gè)有效挪動(dòng).一個(gè)有效挪動(dòng)由以下動(dòng)作組成：*第一,游戲

2、者選擇不同的兩堆球.*第二,把一個(gè)球從一堆拿到另一堆.她可以這樣做的前提是運(yùn)完球后第二堆的球數(shù)包括新放上的球不大于第一堆剩下的球的數(shù)目.當(dāng)沒有挪動(dòng)可做時(shí),游戲完畢.實(shí)際上,在游戲的末尾,每堆將包含恰好兩個(gè)球.游戲的勝者擁有多數(shù)球堆.平局是可能的.當(dāng)某堆有兩個(gè)球并且是由于某游戲者最近對(duì)它的的一次挪動(dòng)不管移走還是放入使其變?yōu)閮蓚€(gè)球的,我們就說她擁有這堆球.看看這些例子：*假設(shè)一個(gè)游戲者從有四個(gè)球的某球堆中移走一個(gè)球,放到有一個(gè)球的某球堆中,那么它擁有了第二堆有兩個(gè)球.*假設(shè)一個(gè)游戲者從有三個(gè)球的某球堆中移走一個(gè)球,放到有零個(gè)球的某球堆中,那么它擁有了第一堆,如今這堆有兩個(gè)球.*假設(shè)一個(gè)游戲者從有三

3、個(gè)球的某球堆中移走一個(gè)球,放到有一個(gè)球的某球堆中,那么它擁有了這兩堆他們都有兩個(gè)球.擁有權(quán)可以變化.設(shè)想一個(gè)游戲者擁有兩個(gè)球的一個(gè)球堆,假設(shè)另一個(gè)游戲者選了一個(gè)有四個(gè)球的堆并把一個(gè)球移到此兩個(gè)球的堆中,那么這堆球誰也不屬于了.假設(shè),在游戲的開頭,存在有兩個(gè)球的一些球堆,那么這些堆被平分給兩個(gè)游戲者,剩余的堆那么分給游戲者2.游戲者1先挪動(dòng).你的程序必須判斷,對(duì)一個(gè)初始的游戲狀態(tài),誰將獲勝或者會(huì)否出現(xiàn)平局.你的程序?qū)⑻幚鞧1=G=1000個(gè)游戲狀態(tài).該問題要求使用不超過1.00 MB的內(nèi)存.問題名：twofour輸入格式：*行1：用空格隔開的兩個(gè)整數(shù)：N和G.*行2.G+1：每行包含空格隔開的N

4、個(gè)整數(shù)用于描繪該游戲.第一個(gè)整數(shù)是堆1的球數(shù),第二個(gè)整數(shù)是堆2的球數(shù),.行2描繪了游戲1,行3描繪了游戲2,.你的程序應(yīng)該計(jì)算每個(gè)特定游戲的勝者.輸入樣例文件twofour.in：5 40 34 12 22 22 21 12 24 43 21 0輸出格式：*行1.G：每個(gè)游戲的結(jié)果.行1給出游戲1的結(jié)果,.結(jié)果是一個(gè)整數(shù)：1代表第一個(gè)游戲者獲勝,2代表第二個(gè)獲勝,以及0代表平局.輸出樣例文件twofour.out：1 21 1二.問題的初步分析和第一種解答從問題的描繪來看，我們可以得到如下的一些根本信息：1player1總是先手的，問題也是求player1的勝負(fù)情況；player2在瓜分最初的

5、2堆的時(shí)候具有優(yōu)先權(quán)。2整個(gè)的游戲過程，就是把不均有分布的堆，逐步均勻化，直至所有的堆都是2堆，由于2N個(gè)球，放置在N堆上，這是個(gè)必然。32堆在游戲過程中會(huì)變化成1堆或者3堆；每堆的球數(shù)不超過4，允許0堆。4假設(shè)兩堆之間的球數(shù)目差1，就可以進(jìn)展球的挪動(dòng)，這是我們在程序中判斷可行步的根據(jù)。在上面的根本信息的根底上，我們就要決定用什么搜索算法，用廣度優(yōu)先搜索還是深度優(yōu)先搜索呢?假設(shè)用廣度優(yōu)先搜索的話，一般的方法是從根節(jié)點(diǎn)出發(fā)，平行的推進(jìn)所有從根節(jié)點(diǎn)衍生出來的子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都要保存當(dāng)前棋局的狀態(tài),同時(shí)還要記住父節(jié)點(diǎn)的索引；子節(jié)點(diǎn)需要父節(jié)點(diǎn)的信息來進(jìn)展衍生，而父節(jié)點(diǎn)需要子節(jié)點(diǎn)的結(jié)果來決定本節(jié)點(diǎn)的結(jié)果

6、。一般我們用一個(gè)隊(duì)列來實(shí)現(xiàn)這個(gè)過程；由于所有的節(jié)點(diǎn)都需要保存，一些廢節(jié)點(diǎn)也被保存了，而對(duì)于奇偶深度的節(jié)點(diǎn)的處理還不一樣奇偶深度，對(duì)應(yīng)player1還是player2，下面會(huì)詳細(xì)講到，節(jié)點(diǎn)所要保存和處理的信息都比較復(fù)雜，另外針對(duì)這個(gè)問題的廣度優(yōu)先搜索的剪枝工作也是個(gè)問題，因?yàn)閺V搜的處理方式是先把子節(jié)點(diǎn)全部入隊(duì)列，然后從隊(duì)頭逐個(gè)再擴(kuò)展，一些無用的節(jié)點(diǎn)就占用了珍貴的隊(duì)列空間。比方player1的任何一步挪動(dòng)，只要能成功，其它方式的挪動(dòng)都不需要考慮了；然而對(duì)于走法的判斷是在所有子節(jié)點(diǎn)入隊(duì)之后，所以其他廢節(jié)點(diǎn)就占用了多余的空間。綜合上面的討論，我認(rèn)為本問題不太適宜使用基于廣度優(yōu)先搜索的算法。下面考慮深度

7、優(yōu)先搜索。深度優(yōu)先搜索有一個(gè)好處就是占用的空間少。先講講我們的思路，請(qǐng)大家注意對(duì)于player1和player2的處理的不同。1我們對(duì)所有棋局的考慮都以player1為中心，不管當(dāng)前棋局是由player1的挪動(dòng)還是player2的挪動(dòng)造成的.2假設(shè)相對(duì)與當(dāng)前棋局，對(duì)于player1的所有挪動(dòng)中，有一種能導(dǎo)致player1成功，那么當(dāng)前節(jié)點(diǎn)就能導(dǎo)致player1成功，也就是不需要再擴(kuò)展了,直接返回結(jié)果到上層父節(jié)點(diǎn)；假設(shè)對(duì)于player1的所有挪動(dòng)，全都導(dǎo)致player1失敗，才能說本節(jié)點(diǎn)導(dǎo)致player1失?。患僭O(shè)沒有走法能成功，但有一種走法能使得player1和局，那么player1會(huì)選擇和局

8、。3同樣的道理，假設(shè)相對(duì)與當(dāng)前棋局，對(duì)于player2的所有挪動(dòng)中，有一種能導(dǎo)致player2成功，那么當(dāng)前節(jié)點(diǎn)就能導(dǎo)致player1失敗，也就是不需要再擴(kuò)展了，直接返回結(jié)果到上層父節(jié)點(diǎn)；假設(shè)對(duì)于player2的所有挪動(dòng)，全都導(dǎo)致player2失敗，才能說本節(jié)點(diǎn)導(dǎo)致player1成功；假設(shè)沒有走法能使得player2成功，但有一種走法能使得player2和局，那么player2會(huì)選擇和局，也就是導(dǎo)致player1和局。4由于player1先手，從初始棋局出發(fā)，逐個(gè)擴(kuò)展出子節(jié)點(diǎn)，并遞規(guī)的調(diào)用自身來擴(kuò)展子節(jié)點(diǎn)，直到無法再深度擴(kuò)展為止。下面來看我們的第一個(gè)版本的解答。#define QMAX 30

9、typedef structint qn；/球的個(gè)數(shù)int owner；/所有者，0：沒有所有者,1：屬于player1,-1：屬于player2sq_str；/上面的數(shù)據(jù)構(gòu)造用來描繪堆的屬性。sq_str aQMAX；/用來描繪棋局狀態(tài)int n；/記錄堆的個(gè)數(shù)，全局變量int depthmax=-1；/用來記錄最深的遞規(guī)深度，以便理解堆棧內(nèi)存的使用使用下面的代碼得到輸入，當(dāng)然后面我們會(huì)討論隨機(jī)生成棋局的方式，初始的棋局在這里就準(zhǔn)備好void test1int i,j；int G,c；scanf%d%d,&n,&G；fori=0；i G；i+c=0；forj=0；j n；j+scanf%d,

10、&aj.qn；ifaj.qn=2ifc&1=0aj.owner=-1；/由player2所有else aj.owner=1；/由player1所有c+；else aj.owner=0；/無人所有depthmax=-1；c=qiuv00；printfresult：%d.depthmax=%d.n,c,depthmax；/求解棋局的函數(shù)，勝負(fù)是指player1的勝負(fù)。depth表示當(dāng)前迭代的深度，同時(shí)也表示當(dāng)前執(zhí)子的玩家，depth為偶數(shù)，表示player1執(zhí)子，depth為奇數(shù)，表示player2執(zhí)子。/返回1：成功，-1：失敗,0：和局int qiuv0int depthint i,j,k=0

11、,s,tx=0；int ret0；int fu=0；/會(huì)導(dǎo)致player1失敗的節(jié)點(diǎn)的個(gè)數(shù)int shen=0；/會(huì)導(dǎo)致player1成功的節(jié)點(diǎn)的個(gè)數(shù)sq_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1/判斷可行挪動(dòng)步的標(biāo)準(zhǔn)，從第i堆到第j堆k+；/記錄子節(jié)點(diǎn)的個(gè)數(shù)/保存被修改的堆，方便以后恢復(fù)savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifde

12、pth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；ret0=qiudepth+1；/遞規(guī)調(diào)用/恢復(fù)被修改的棋局ai=savei；aj=savej；/請(qǐng)大家注意下面的不同處理，所有的勝負(fù)都是對(duì)于player1來說的ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；ifk=0/假設(shè)沒有子節(jié)點(diǎn)可以擴(kuò)展，那么這是個(gè)終局fo

13、ri=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；else/否那么是擴(kuò)展了子節(jié)點(diǎn)的ifdepth&1=0iffu=kreturn-1；/所有的走法都導(dǎo)致輸else return 0；/至少有一種走發(fā)可以保證平局elseifshen=kreturn 1；/player2所有的走法都導(dǎo)致player1成功else return 0；/player2會(huì)選擇平局三.初步的優(yōu)化和剪枝好了程序很簡單，應(yīng)該很容易理解，但是效率也很低！下面我們來逐步分析優(yōu)化，看看問題在哪里。首先我們發(fā)現(xiàn)，同層擴(kuò)展出的各棋局的狀態(tài)只和各堆的狀態(tài)有關(guān)

14、，而和各堆的排列沒有關(guān)系，所以在同一層我們就可以進(jìn)展剪枝，把那些本質(zhì)上是一樣的子節(jié)點(diǎn)剪掉。考慮所有的走法一共有8種：4-2-1,1,4-1,4-0,3-1,3-0,2-1,1-0,括號(hào)里的數(shù)表示2堆的歸屬情況。新的程序如下：int qiuv1int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；sq_str savei,savej；sq_str tt82；/一共有8種不同的挪動(dòng)方式int re8；/8種挪動(dòng)方式帶來的結(jié)果int ti=0；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=

15、0；j n；j+ifai.qn-aj.qn 1k+；fors=0；s ti；s+ifai.owner=tts0.owner&ai.qn=tts0.qn&aj.owner=tts1.owner&aj.qn=tts1.qnbreak；ifs！=tiret0=res；ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；continue；elsettti0=ai；ttti1=aj；savei=ai；savej=aj；ai.qn-；aj.q

16、n+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；ret0=qiudepth+1；reti=ret0；ti+；ai=savei；aj=savej；ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；if

17、k=0fori=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；elseifdepth&1=0iffu=kreturn-1；/所有的走法都導(dǎo)致輸else return 0；/至少有一種走發(fā)可以保證平局elseifshen=kreturn 1；/player2所有的走法都導(dǎo)致player1成功else return 0；/player2會(huì)選擇平局四、進(jìn)一步的優(yōu)化和剪枝經(jīng)過上面的優(yōu)化，程序的性能有所提升，但是還不夠快，問題出在哪里呢?我們知道深度優(yōu)先搜索的一大缺點(diǎn)就是對(duì)已有的計(jì)算結(jié)果沒有繼承，造成了大量的計(jì)算浪費(fèi)；qiuv

18、1已經(jīng)做了一點(diǎn)工作，但還不夠；我們需要記錄所有的已經(jīng)訪問過的棋局和相應(yīng)的結(jié)果，方便在后續(xù)的搜索中進(jìn)展剪枝。這就需要對(duì)以往結(jié)果的記錄。定義如下數(shù)據(jù)構(gòu)造：#define STAMAX 11000 unsigned char x_staSTAMAX8；/player1的2就在2，player2的2在5,局勢的結(jié)果放在7,depth的奇偶性放在6里int x_inx=0；/x_sta中的下一個(gè)空位置我們知道棋局只和堆本身有關(guān)，而和堆的排列順序無關(guān)，進(jìn)一步，兩個(gè)一樣的堆也是無區(qū)別的，這樣我們只需要記錄一個(gè)棋局中0堆的個(gè)數(shù)，1堆的個(gè)數(shù),21堆的個(gè)數(shù)，2-1堆的個(gè)數(shù),3堆的個(gè)數(shù)，4堆的個(gè)數(shù)，以及當(dāng)前棋局對(duì)應(yīng)

19、的執(zhí)子方，這種棋局的結(jié)果。由于最多也就30堆，所以1個(gè)字節(jié)足以存放相關(guān)的信息。算算上面的空間才不到90KB，離1MB尚遠(yuǎn)。還有一個(gè)問題，那就是棋局的對(duì)偶性，棋局A的對(duì)偶棋局，就是把depth的奇偶性取反，把相應(yīng)的2堆的歸屬性取反，相應(yīng)的棋局結(jié)果自然取反。這個(gè)很容易理解，相當(dāng)與player2和player1交換位置，下對(duì)方的棋。這樣我們每求得一個(gè)棋局，實(shí)際上是得到了兩個(gè)棋局的結(jié)果。好了還是看看新程序吧.int qiuv2int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；int old_xinx；unsigned char x7；sq

20、_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1k+；memsetx,0,7；savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；fors=0；s n；s+ifas.qn！=2xas

21、.qn+；elseifas.owner=1x2+；else x5+；x6=depth&1；/開場搜索以前保存的結(jié)果fors=0；s x_inx；s+ifmemcmpx,x_stas,7=0break；ifs！=x_inx/找到了！ai=savei；aj=savej；ret0=charx_stas7；ifdepth&1=0/player1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；continue；elsememcpyx_stax_inx,x,7；/每找到，把當(dāng)

22、前棋局添加進(jìn)去old_xinx=x_inx；/記錄自己的位置，后面好吧結(jié)果填進(jìn)去，因?yàn)橄旅娴倪f規(guī)會(huì)參加新的內(nèi)容到存儲(chǔ)隊(duì)列x_inx+；ret0=qiuv1depth+1；x_staold_xinx7=ret0；ai=savei；aj=savej；/把對(duì)偶的情況放進(jìn)去memcpyx_stax_inx,x_staold_xinx,8；x_stax_inx2=x_staold_xinx5；x_stax_inx5=x_staold_xinx2；x_stax_inx6=！x_staold_xinx6；x_stax_inx7=-x_staold_xinx7；x_inx+；ifdepth&1=0/playe

23、r1的局勢ifret0=1return 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；ifk=0fori=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；elseifdepth&1=0iffu=kreturn-1；/所有的走法都導(dǎo)致輸else return 0；/至少有一種走發(fā)可以保證平局elseifshen=kreturn 1；/player2所有的走法都導(dǎo)致player1成功else return 0；/player2

24、會(huì)選擇平局好了，這下我們的程序有了質(zhì)的飛躍，速度進(jìn)步很多，比v1版本進(jìn)步了幾個(gè)數(shù)量級(jí)！很開心-。五.HASH函數(shù)的應(yīng)用但是當(dāng)我們加大測試強(qiáng)度，把堆的數(shù)量推到頂，到達(dá)30之后，我們的程序還是不夠快，對(duì)有的棋局，幾乎半分鐘內(nèi)都解不出來，這是不能承受的。那好吧，看來我們還需要進(jìn)一步優(yōu)化。還有什么地方值得優(yōu)化呢?就是下面這個(gè)地方！/開場搜索以前保存的結(jié)果fors=0；s x_inx；s+ifmemcmpx,x_stas,7=0break；通過測試發(fā)現(xiàn)，對(duì)于30堆的情況，我們的存儲(chǔ)會(huì)有超過10000的情況，一般也會(huì)超過5000！對(duì)于這么大的存儲(chǔ)空間，假設(shè)向上面那樣每次都進(jìn)展線性匹配，效率是很低下的，這也

25、就是為什么在堆變多之后，我們的程序變慢的原因。好了問題找到了，那么如何解決呢?還是有方法的，那就是hash表！通過hash表就可以一步定位到我們需要的位置，只要hash函數(shù)設(shè)置的好，就可以盡量減少碰撞的產(chǎn)生；即使有了碰撞也不怕，搞個(gè)拉鏈鏈接起來就可以了，經(jīng)過測試新的程序，使用hash表，最多也就產(chǎn)生兩三次碰撞，一般都能一擊中的！#define STAMAX 0x4000 typedef structunsigned char x_sta8；/player1的2就在2，player2的2在5,局勢的結(jié)果放在7,depth的奇偶性放在6里unsigned short pr；/低14bit是索引，高

26、2bit：00空工程,01低14bit表示下一個(gè)的位置，10沒有下一個(gè)了X_sta；/hash表X_sta hashSTAMAX；/占用160KB空間，實(shí)際測試，可以處理的堆數(shù)達(dá)35堆的情況/返回14bit的HASH值，我自己構(gòu)造的hash函數(shù)unsigned short cal_hashunsigned char*in,int lenunsigned short x1=0；int i；fori=0；i len；i+x1=x1*11+ini0x3d；returnx1&0x3fff；int qiuv3int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；in

27、t shen=0；int old_xinx；unsigned char x8；/把結(jié)果也含進(jìn)來了unsigned short s_indx；int nexti；int find；sq_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1k+；memsetx,0,8；savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；

28、else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；fors=0；s n；s+ifas.qn！=2xas.qn+；elseifas.owner=1x2+；else x5+；x6=depth&1；find=0；s_indx=cal_hashx,7；/計(jì)算hash值作為索引nexti=s_indx；switchhashs_indx.pr 14/查看高兩bit屬性值case 0：/空項(xiàng)，直接填入memcpyhashnexti.x_sta,x,8；hashnexti.pr=0x8000；old_xinx=nexti；x_in

29、x+；break；case 1：/碰撞，那就順著鏈條往下查找吧doifmemcmpx,hashnexti.x_sta,7=0find=1；break；nexti=hashnexti.pr&0x3fff；whilehashnexti.pr 14！=2；/這里直接滑入case2，因?yàn)榈竭@里處理是一樣的了case 2：/和最后一個(gè)進(jìn)展比較ifmemcmpx,hashnexti.x_sta,7=0find=1；iffind=1/找到了一模一樣的ai=savei；aj=savej；ret0=charhashnexti.x_sta7；ifdepth&1=0/player1的局勢ifret0=1return

30、 1；else ifret0=-1fu+；else/player2的局勢ifret0=-1return-1；else ifret0=1shen+；continue；/否那么就是沒有找到，那么就只能拉拉鏈了，找一個(gè)空地方塞進(jìn)去fors=0；s STAMAX；s+ifhashs.pr 14=0break；ifs=STAMAX/hash表滿了！printferror hashtable full??；return-2；memcpyhashs.x_sta,x,8；hashs.pr=0x8000；/這幾行就是在接拉鏈old_xinx=s；hashnexti.pr=s|0x4000；x_inx+；break

31、；default：printferror in pr！；break；ret0=qiuv1depth+1；hashold_xinx.x_sta7=ret0；ai=savei；aj=savej；/把對(duì)偶的情況放進(jìn)去find=x2；x2=x5；x5=find；find=0；x6=！x6；x7=-ret0；s_indx=cal_hashx,7；/查找對(duì)偶情況，假設(shè)對(duì)偶情況已經(jīng)在里面了，就不用添加了，否那么就需要添加nexti=s_indx；switchhashs_indx.pr 14case 0：x_inx+；memcpyhashnexti.x_sta,x,8；hashnexti.pr=0x8000；break；case 1：doifmemcmpx,hashnexti.x_sta,7=0find=1；break；nexti=hashnexti.pr&0x3fff；whilehashnexti.pr 14！=2；case 2：/和最后一個(gè)進(jìn)展比較ifmemcmpx,hashnexti.x_sta,7=0find=1；iffind=0/否那么就是沒有找到fors=0；s STAMAX；s+ifhashs.pr 14=0break；ifs=STAMAXprintferror hashtable full??；return-2；memcpyhashs.x_sta,x,8；hashs.pr