📄 ds9.2.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 class="MsoNormal" align="center"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="6" color="#FFFF00">9.2.1
顺序表的查找</font></span></b></p>
<p class="MsoNormal"><font color="#FFFFFF" size="5"><b><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></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>/*静态查找表的顺序存储结构*/</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>typedef
struct {</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
ElemType *elem;</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>
int length; /*表长*/</b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>}SSTable;</b></font></p>
<p class="MsoNormal"><font color="#FFFFFF" size="5"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">
其查找方法为：从表的一端开始，向另一端逐个按给定值</span><span lang="EN-US">kx</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与</span><span lang="EN-US">kx</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">相同的关键码，则查找失败，给出失败信息。</span></b></font><span lang="EN-US"><font color="#FFFFFF" size="5"><b> <o:p>
</o:p>
</b></font></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5"><b><font color="#FFFFFF">【算法</font></b></font></span><font size="5"><b><font color="#FFFFFF"><span lang="EN-US">9.1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">】</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5"><b><font color="#FFFFFF">int<span style="mso-spacerun: yes">
</span>s_search(<span style="mso-spacerun: yes">SSTable </span></font></b></font></span><font size="5"><b><font color="#FFFFFF"><span lang="EN-US">ST</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">KeyType<span style="mso-spacerun: yes">
</span>key)</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF"> </font></b></font></span><font size="5"><b><font color="#FFFFFF">{<span style="mso-spacerun: yes">
</span></font></b></font></span><font size="5"><b><font color="#FFFFFF"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.6pt">/</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt">*</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; letter-spacing: -.2pt">在表ST中查找关键码为</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt">key</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; letter-spacing: -.2pt">的数据元素，若找到返回该元素在数组中的下标，否则返回</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt">0
*/</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.6pt"><o:p>
</o:p>
</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font size="5"><b><font color="#FFFFFF">ST.elem[0].key
= </font></b></font></span><font size="5"><b><font color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">key；</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt">/*
</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; letter-spacing: -.2pt">存放监测，这样在从后向前查找失败时，不必判表是否检测完，从而达到算法统一</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt">*/</span><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt" lang="EN-US">
</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt">
</span><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; letter-spacing: -.2pt" lang="EN-US">
</span></font></b></font><span lang="EN-US"><font size="5"><b><font color="#FFFFFF">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -