散列表構(gòu)造與查找的動(dòng)態(tài)實(shí)現(xiàn)

1、散列表構(gòu)造與查找的動(dòng)態(tài)實(shí)現(xiàn)吳洲512126 廣東松山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系 摘要數(shù)據(jù)結(jié)構(gòu)中散列表的教學(xué)一直是一個(gè)難點(diǎn)，如果結(jié)合動(dòng)態(tài)的圖形演示，則可以使算法的描述更形象、更生動(dòng)，使教學(xué)能產(chǎn)生良好的效果。關(guān)鍵詞散列表 沖突 線性探測(cè)散列表，又稱為哈希表，是線性表中一種重要的存儲(chǔ)方式和檢索方法。在散列表中，可以對(duì)節(jié)點(diǎn)進(jìn)行快速檢索。散列表算法的基本思想是：由結(jié)點(diǎn)的關(guān)鍵碼值決定結(jié)點(diǎn)的存儲(chǔ)地址，即以關(guān)鍵碼值k 為自變量，通過(guò)一定的函數(shù)關(guān)系h（稱為散列函數(shù)），計(jì)算出對(duì)應(yīng)的函數(shù)值h(k) 來(lái)，將這個(gè)值解釋為結(jié)點(diǎn)的存儲(chǔ)地址，將結(jié)點(diǎn)存入該地址中，檢索時(shí)，根據(jù)要檢索的關(guān)鍵碼值，用同樣的散列函數(shù)計(jì)算出地址，然后，到相應(yīng)

2、的地址中去獲取要找的結(jié)點(diǎn)數(shù)據(jù)。因此，散列表有一個(gè)重要特征：平均檢索的長(zhǎng)度不直接依賴于表中元素的個(gè)數(shù)。兩個(gè)不同的關(guān)鍵字，由于散列函數(shù)值相同，因而被映射到同一表位置上。該現(xiàn)象稱為沖突(Collision)或碰撞。發(fā)生沖突的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞(Synonym)。解決沖突有多種方法，我們利用線性探測(cè)處理沖突。線性探查法(Linear Probing)基本思想是：將散列表T0.m-1看成是一個(gè)循環(huán)向量，若初始探查的地址為d(即h(key)=d)，則最長(zhǎng)的探查序列為： d，d+l，d+2，m-1，0，1，d-1即:探查時(shí)從地址d開(kāi)始，首先探查Td，然后依次探查Td+1，直到Tm-1，此后又循

3、環(huán)到T0，T1，直到探查到Td-1為止。探查過(guò)程終止于三種情況： (1) 若當(dāng)前探查的單元為空，則表示查找失敗（若是插入則將key寫入其中）； (2) 若當(dāng)前探查的單元中含有key，則查找成功，但對(duì)于插入意味著失??； (3) 若探查到Td-1時(shí)仍未發(fā)現(xiàn)空單元也未找到key，則無(wú)論是查找還是插入均意味著失敗(此時(shí)表滿)。利用開(kāi)放地址法的一般形式，線性探查法的探查序列為： hi=(h(key)+i)m 0im-1 /即di=i我們可以利用Delphi編寫演示程序，方法如下：窗體Form2組件屬性屬性值組件屬性屬性值Label1Caption請(qǐng)輸入關(guān)鍵碼的個(gè)數(shù)（小于50）Eidit1Textpane

4、l1Caption窗體Form1組件屬性屬性值組件屬性屬性值Label1Caption指定關(guān)鍵碼Button1Caption建散列表Label2Caption位置Button2Caption獲取關(guān)鍵碼Label3CaptionButton3Caption查找Label4Caption利用線性探測(cè)處理沖突建立的散列表Button4Caption關(guān)閉procedure TForm2.Edit1KeyPress(Sender: TObject; var Key: Char);beginif edit1.text thenif key=#13 thenbegin form2.close; if str

5、toint(edit1.Text)50 then pub:=50 else pub:=strtoint(edit1.text);end;end;procedure TForm1.FormCreate(Sender: TObject);var i:integer;beginform1.Caption:=inttostr(pub)+個(gè)關(guān)鍵碼的線性探測(cè)處理沖突的散列表!;for i:=0 to pub-1 do begin ed1i:=tedit.Create(self); ed1i.Parent:=self; ed1i.Text:=0; ed1i.SetBounds(10+i*25,20,30,3

6、0); ed2i:=tedit.Create(self); ed2i.Parent:=self; ed2i.Text:=-1; ed2i.SetBounds(10+i*25,120,30,30); bi:=tlabel.Create(self); bi.Parent:=self; bi.caption:=inttostr(i); bi.SetBounds(15+i*25,105,30,30); end;end;procedure TForm1.Button2Click(Sender: TObject);/獲取關(guān)鍵碼var i:integer;begin for i:=0 to pub-1 do

7、 ed2i.Text:=-1; for i:=0 to pub-1 do gjmi:=strtoint(ed1i.Text);end;procedure TForm1.Button1Click(Sender: TObject);/建散列表var i,j,k:integer;begin for i:=0 to pub-1 do begin j:=gjmi mod pub; if ed2j.text=-1 then ed2j.Text:=inttostr(gjmi) else begin /處理沖突 k:=j; while ed2k.text-1 do k:=(k+1) mod pub; ed2k

8、.text:=inttostr(gjmi); end; end;end;procedure TForm1.Button3Click(Sender: TObject);/查找var i,j,k,n:integer;begin i:=strtoint(edit1.text); j:=i mod pub; if i=strtoint(ed2j.text) then label3.caption:=inttostr(j+1) mod pub) else begin n:=1;k:=j; while(istrtoint(ed2k.text)and(n=pub then showmessage(該關(guān)鍵碼不存在) else label3.c