哈希表
- 程序中需要保存數據，而且需要通過給定標號快速找到數據。這個標號叫做鍵，數據叫做值。
- 若採用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>分享到:
