ds9.1.htm

这是清华大学所用的数据结构的电子版教材

  </tr>
  <tr>
    <td width="14%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="14%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="7%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="10%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="6%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="5%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="18%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="11%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
    <td width="15%" align="center"><!--mstheme--><font face="宋体"><font size="4" color="#FFFFFF"><b>…</b></font><!--mstheme--></font></td>
  </tr>
</table>
<!--mstheme--><font face="宋体"><!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal" style="margin-top: 12; margin-bottom: 0"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">数据项 
      (也称项或字段)：</font></b></span><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF" size="5">项是具有独立含义的标识单位，是数据不可分割的最小单位。如表中“学号”、“姓名”、</font></span><font color="#FFFFFF" size="5"> 
      <span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">“年”等。项有名和值之分，项名是一个项的标识，用变量定义，而项值是它的一个可能取值，表中“</span><span lang="EN-US">20010983</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">”是项“学号”的一个取值。项具有一定的类型，依项的取值类型而定。</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">&nbsp;</span></font></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">组合项</font></b></span><b><span lang="EN-US"><font size="5" color="#FFFF00"><span style="mso-bidi-font-size: 10.0pt">：</span></font></span><span style="mso-bidi-font-size: 10.0pt; 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"><font color="#FFFFFF" size="5">由若干项、组合项构成，表中“出生日期”就是组合项，它由“年”、“月”、“日”三项组成。</font></span></b><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal" style="margin-top: 10"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">数据元素（记录）：</font></b></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><b><font color="#FFFFFF" size="5">数据元素是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。数据元素有型和值之分，表中项名的集合，也即表头部分就是数据元素的类型；而一个学生对应的一行数据就是一个数据元素的值，表中全体学生即为数据元素的集合。</font></b></span><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">关键码：</font></b></span><span style="mso-bidi-font-size: 10.0pt; 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"><b><font color="#FFFFFF" size="5">关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。能唯一确定一个数据元素（记录）的关键码，称为主关键码；而不能唯一确定一个数据元素（记录）的关键码，称为次关键码。表中“学号”即可看成主关键码，“姓名”则应视为次关键码，因可能有同名同姓的学生。</font></b></span><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">查找表：</font></b></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><b><font color="#FFFFFF" size="5">是由具有同一类型（属性）的数据元素（记录）组成的集合。分为静态查找表和动态查找表两类</font></b></span><b><font color="#FFFFFF" size="5"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">：</span></font></b><!--mstheme--></font>
      <!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <!--msthemelist--><tr>
          <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu2.gif" width="12" height="12" hspace="15"></td>
          <td valign="top" width="100%"><!--mstheme--><font face="宋体">
            <p class="MsoNormal"><b><span style="mso-ascii-font-family: Times New Roman"><font size="5" color="#FFFF00">静态查找表</font></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFF00">：</font><font color="#FFFFFF" size="5">仅对查找表进行查找操作，而不能改变的表；</font></span></b><!--mstheme--></font><!--msthemelist--></td>
        </tr>
        <!--msthemelist--><tr>
          <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu2.gif" width="12" height="12" hspace="15"></td>
          <td valign="top" width="100%"><!--mstheme--><font face="宋体">
            <p class="MsoNormal"><b><span style="mso-ascii-font-family: Times New Roman"><font size="5" color="#FFFF00">动态查找表</font></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFF00">：</font><font color="#FFFFFF" size="5">对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。</font></span></b><!--mstheme--></font><!--msthemelist--></td>
        </tr>
      <!--msthemelist--></table>
      <!--mstheme--><font face="宋体"><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">查找：</font></b></span><font color="#FFFFFF" size="5"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">按给定的某个值</span><span lang="EN-US">kx</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">，在查找表中查找关键码为给定值</span><span lang="EN-US">kx</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的数据元素（记录）。</span></b></font><!--mstheme--></font>
      <!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <!--msthemelist--><tr>
          <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu2.gif" width="12" height="12" hspace="15"></td>
          <td valign="top" width="100%"><!--mstheme--><font face="宋体">
            <p class="MsoNormal"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><b><font size="5" color="#FF00FF">关键码是主关键码时</font><font color="#FFFFFF" size="5">：由于主关键码唯一，所以查找结果也是唯一的，一旦找到，查找成功，结束查找过程，并给出找到的数据元素（记录）的信息，或指示该数据元素（记录）的位置。要是整个表检测完，还没有找到，则查找失败，此时，查找结果应给出一个“空”记录或“空”指针。</font></b></span><!--mstheme--></font><!--msthemelist--></td>
        </tr>
        <!--msthemelist--><tr>
          <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu2.gif" width="12" height="12" hspace="15"></td>
          <td valign="top" width="100%"><!--mstheme--><font face="宋体">
            <p class="MsoNormal"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><b><font size="5" color="#FF00FF">关键码是次关键码时：</font><font color="#FFFFFF" size="5">需要查遍表中所有数据元素（记录），或在可以肯定查找失败时，才能结束查找过程。</font></b></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font color="#FFFFFF" size="5"><o:p>
            </o:p>
            </font></b></span><!--mstheme--></font><!--msthemelist--></td>
        </tr>
      <!--msthemelist--></table>
      <!--mstheme--><font face="宋体"><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="../chp%208/aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF" size="5"><b>&nbsp;</b></font></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><font size="5" color="#FFFF00">数据元素类型说明：</font><font color="#FFFFFF" size="5"><o:p>
      </o:p>
      </font></b></span><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF" size="5"><b>&nbsp;&nbsp;&nbsp; 
</b></font></span><font color="#FFFFFF" size="5"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在手工绘制表格时，总是根据有多少数据项，每个数据项应留多大宽度来确定表的结构，即表头的定义</span><span style="mso-hansi-font-family: Times New Roman">。</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">然后，再根据需要的行数，画出表来。在计算机中存储的表与手工绘制的类似，需要定义表的结构，并根据表的大小为表分配存储单元。以</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">上表为例，用</span><span lang="EN-US">C</span><span style="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"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font color="#FFFFFF" size="5">/* 
</font></span><font color="#FFFFFF" size="5"><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">出生日期类型定义</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"> 
*/<o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><b><font color="#FFFFFF" size="5">typedef<span style="mso-spacerun: yes">&nbsp; 
</span>struct<span style="mso-spacerun: yes"> </span>{</font></b></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF" size="5"><b>&nbsp;&nbsp; 
</b></font></span><font color="#FFFFFF" size="5"><b>char<span style="mso-spacerun: yes">&nbsp; 
</span>year[5]</b></font></span><font color="#FFFFFF" size="5"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">；</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*<span style="mso-spacerun: yes"> 
</span></span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">年：用字符型表示，宽度为</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">4</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">个字符</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"> 
*/<o:p>