📄 ds9.4.3.htm
字号:
<p style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">……</span></b></font></p>
<p style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">H<sub>m-1</sub>=(a+(m-1)b)
mod m</span></b></font></p>
</blockquote>
<p class="MsoNormal"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体"><font size="5" color="#FFFFFF">二<span lang="EN-US">.
链地址法<o:p>
</o:p>
</span></font></span></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">设哈希函数得到的哈希地址域在区间</span><span lang="EN-US">[0</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">m-1]</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">上，以每个哈希地址作为一个指</span></font></b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><b><font size="5" color="#FFFFFF">针，指向一个链，即分配指针数组</font></b></span></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US"><span style="mso-spacerun: yes">
</span>ElemType<span style="mso-spacerun: yes"> </span>*eptr[m]</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">；</span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""> 建立</span><span lang="EN-US">m</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">个空链表，由哈希函数对关键码转</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">换后，映射到同一哈希地址</span><span lang="EN-US">i</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的同义词均</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">加入到</span><span lang="EN-US">*eptr[i]</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">指向的链表中。</span></font></b><span lang="EN-US"><b><font size="5" color="#FFFFFF"> </font></b></span><img border="0" src="ds9.4.3.gif" width="260" height="386" align="right"><span lang="EN-US"><b><font size="5" color="#FFFFFF"><o:p>
</o:p>
</font></b></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font color="#FFFF00"><b><font size="5">【例</font></b></font></span><b><font color="#FFFF00"><font size="5"><span lang="EN-US">9.l3</span></font></font><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman""><font color="#FFFF00" size="5">】</font><font size="5" color="#FFFFFF">关键码序列为</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">47,7,</span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US">29,11,16,92,22,8,3,50,37, </span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US">89,94,21</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，哈希函数为</span><span style="letter-spacing:-.6pt"> </span></font></b></p>
<p class="MsoNormal"><span lang="EN-US"><b><font size="5" color="#FFFFFF">Hash(key)=key
mod 11</font></b><b><font size="5" color="#FFFFFF"> <o:p>
</o:p>
</font></b></span></p>
<b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">用链地址法处理冲突，建表如图</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">9.21</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">。</span></font></b>
<p align="left"> </p>
<p align="left"> </p>
<p align="left"> </p>
<p align="left"> </p>
<p class="MsoNormal"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体"><font size="5" color="#FFFF00">三<span lang="EN-US">.
建立一个公共溢出区<o:p>
</o:p>
</span></font></span></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">设哈希函数产生的哈希地址集为</span><span lang="EN-US">[0</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">m-1]</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，则分配两个表：</span></font></b></p>
<blockquote>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">一个基本表</span> <span lang="EN-US">ElemType
base_tbl[m]</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">；每个单元只能存放一个元素；</span></font></b></p>
<b><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">一个溢出表</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
ElemType over_tbl[k]</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中。查找时，对给定值</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">k</span><span style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-fareast-font-family: 宋体" lang="EN-US">ey</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">通过哈希函数计算出哈希地址</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">，先与基本表的</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">base_tbl[i]</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">单元比较，若相等，查找成功；否则，再到溢出表中进行查找。</span></font></b>
</blockquote>
<p align="left"> </p>
<p align="center"><b><font size="5"><a href="ds9.4.HTM"><font color="#FFFF00">返回</font></a></font></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -