📄 ds9.4.1.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体"><p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><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"><font size="6" color="#FFFF00">9.4.1
</font>
</span><font size="6" color="#FFFF00"><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></span></p>
<p align="left"><font size="5" color="#FFFFFF"><b><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></b></font></p>
<p class="MsoNormal"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFF00">【例</font></span><font size="5" color="#FFFF00"><span lang="EN-US">9.6</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">】</span></font><font size="5" color="#FFFFFF"><span lang="EN-US">11</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">个元素的关键码分别为</span>
<span lang="EN-US">18</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">27</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">20</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">22</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">6</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">10</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">13</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">41</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">15</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">25</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">。选取关键码与元素位置间的函数为</span><span lang="EN-US">
f(key)=key<span style="mso-spacerun: yes"> </span>mod<span style="mso-spacerun: yes">
</span>11</span></font></b></p>
<font size="5" color="#FFFFFF"><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"><span style="mso-spacerun: yes">
</span>1. </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">11</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></b></font>
<div align="center">
<center><!--mstheme--></font>
<table border="1" width="388" height="61" bordercolorlight="#3366CC" bordercolordark="#000000">
<tr>
<td width="36" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>0</b></font><!--mstheme--></font></td>
<td width="36" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>1</b></font><!--mstheme--></font></td>
<td width="36" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>2</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>3</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>4</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>5</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>6</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>7</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>8</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>9</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>10</b></font><!--mstheme--></font></td>
</tr>
<tr>
<td width="36" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>22</b></font><!--mstheme--></font></td>
<td width="36" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>1</b></font><!--mstheme--></font></td>
<td width="36" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>13</b></font><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>25</b></font><!--mstheme--></font></td>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -