哈希表
- 程序中需要保存數據,而且需要通過給定標號快速找到數據。這個標號叫做鍵,數據叫做值。
- 若採用for循環,當數據太多時會循環好多次,效率太低。因此出現了二分法,使得效率提高。
- 而我們可以通過數組實現,將數組下標和鍵綁定在一起,直接找下標實現。但是這樣會浪費大量存儲空間(有些下標不存儲數據),為了解決空間浪費問題,我們引入了哈希函數(散列函數)
- 散列函數:如將鍵/10取餘數,得到的數為數組下標。但是這又產生了空間衝突問題,為解決此問題我們規定,若此下標空間衝突,則+1後再看下標是否空餘,直到有空位為止。
- 但查看下標是否空餘得一個個看,又會影響效率。因此我們需要合理設計散列函數,以防止空間衝突,如/100取餘數等
哈希表類CBHashLK
哈希表編程嘗試:輸入鍵,快速查找值
- 根據模板創建項目
- 具體代碼實現
<code>CBForm
form1
(ID\_form1)
; CBHashLK mHashTest;void
cmdFind\_Click() {int
iKey=form1.Control(ID\_txtID).TextInt();if
(mHashTest.IsKeyExist(iKey)) { form1.Control(ID\_txtResult).TextSet(mHashTest.Item(iKey,false
)); form1.Control(ID\_txtResult2).TextSet(mHashTest.ItemStr(iKey,false
)); }else
{ form1.Control(ID\_txtResult).TextSet(TEXT("該鍵不存在"
)); form1.Control(ID\_txtResult2).TextSet(TEXT("該鍵不存在"
)); } }void
form1\_Load() {const
int
cMaxItems=1000000
; mHashTest.AlloMem(cMaxItems\*2
);for
(int
i=1
;i<=cMaxItems;i++) { mHashTest.Add(i\*10
,i,0
,0
,TEXT("zhr"
)); } mHashTest.Remove(100
,false
); mHashTest.Remove(1000
,false
); MsgBox(TEXT("哈希表建立完畢!請任意輸入1~1000000之間的鍵,來快速查找其值"
)); }int
main
()
{ form1.EventAdd(0
,eForm\_Load,form1\_Load); form1.EventAdd(ID\_cmdFind,eCommandButton\_Click,cmdFind\_Click); form1.Show(); }/<code>
高效數組鏈表
- 儲存數據有兩種方式:數組和鏈表。其中鏈表由一個個節點組成,節點包括數據+下一個數據的地址,最後一個節點的next為0。
- 就查找元素而言,數組可以由下標直接找到,鏈表則需要從頭開始倒騰;但對於插入刪除而言,數組後邊的數據都要移動,鏈表則只需要調整兩個地址。因此兩者都有缺點
- 為此,我們將兩者結合,發明了數組鏈表。數組鏈表由若干小型數組鏈接而成,由於數組元素個數較少,移動也不會移動太多;而查找時也不必一個個倒騰,以四個元素的數組為例,先/4,再%4,得到第幾個數組的第幾個元素(但要注意都要從0開始數!!)
- 值得一提的是,數組鏈表的動態分配,每次至少要分配一個小數組的空間,不可能只分配一個元素的空間。與計算機的簇類似,一次是4096字節(或者8192、16384),若是16385字節就得分配兩個16384字節。在磁盤格式化時,可以設置簇的大小。過大會浪費空間,過小會影響處理速度(一次讀取一簇)。因此我們存小文件多的盤,設置簇小一點(如1024字節);存儲電影時,則可以設置大一點,看的會更加流暢
- 為何是0字節??
數組鏈表類CBArrLink
數組鏈表編程嘗試
- 根據模板創造項目
- 引入combo box,注意設置屬性type,以及sort(程序自作聰明設成true)
- 代碼
<code>CBForm
form1
(ID\_form1)
; CBArrLink m\_al;struct
SArrType
{int
Item;int
Item2; };void
cmdAdd\_Click() {long
iClockStart=clock();int
ct=5000000
;for
(int
i=1
;i<=ct;i++){ m\_al.Add(i,i\*10
); } form1.Control(ID\_lblAdd).TextSet(m\_al.Count()); form1.Control(ID\_lblAdd).TextAdd(TEXT("個數據添加完成,"
)); form1.Control(ID\_lblAdd).TextAdd(TEXT("共用時"
)); form1.Control(ID\_lblAdd).TextAdd((double
)(clock()-iClockStart)); form1.Control(ID\_lblAdd).TextAdd(TEXT("毫秒"
)); }void
cmdAccess\_Click() {long
iClockStart=clock();int
iMethod=form1.Control(ID\_cboAccessMethod).ListIndex();int
ct=m\_al.Count();int
i;if
(1
==iMethod) {for
(i=1
;i<=ct;i++) {if
(m\_al.Item2(i)!=m\_al.Item(i)\*10
) { MsgBox(i,TEXT("發現數據錯誤"
));break
; } } }else
{ struct SArrType \*p=(struct SArrType\*)m\_al.GetItemsArr();for
(i=1
;i<=ct;i++) {if
(p\[i\].Item2!=p\[i\].Item\*10
) { MsgBox(i,TEXT("發現數據錯誤"
));break
; } } }if
(i>ct) { form1.Control(ID\_lblAccess).TextSet(TEXT("測試完成"
)); form1.Control(ID\_lblAccess).TextAdd(ct); form1.Control(ID\_lblAccess).TextAdd(TEXT("個數據,未發現錯誤。用時:"
)); form1.Control(ID\_lblAccess).TextAdd((double
)(clock()-iClockStart)); form1.Control(ID\_lblAccess).TextAdd(TEXT("毫秒"
)); } }void
cmdDel\_Click() {int
index=form1.Control(ID\_txtDelIndex).TextInt(); m\_al.Remove(index); form1.Control(ID\_lblDel).TextSet(TEXT("刪除後,剩餘數據個數:"
)); form1.Control(ID\_lblDel).TextAdd(m\_al.Count()); }int
main
()
{ form1.EventAdd(ID\_cmdAdd,eCommandButton\_Click,cmdAdd\_Click); form1.EventAdd(ID\_cmdAccess,eCommandButton\_Click,cmdAccess\_Click); form1.EventAdd(ID\_cmdDel,eCommandButton\_Click,cmdDel\_Click); form1.Control(ID\_cboAccessMethod).AddItem(TEXT("數組法訪問元素"
)); form1.Control(ID\_cboAccessMethod).AddItem(TEXT("指針法訪問元素"
)); form1.Control(ID\_cboAccessMethod).ListIndexSet(1
); form1.Show();return
0
; }/<code>