哈希表
- 程序中需要保存数据，而且需要通过给定标号快速找到数据。这个标号叫做键，数据叫做值。
- 若采用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>分享到:
