📄 ds5.4.2.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">
<p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><b><font lang="ZH-CN" size="6" color="#FFFF00"><font face="oúì?,SimHei">5.4.2
</font><font face="??ì?,SimSun" size="5">广义表的存储</font></font></b></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN"> </font></b></font> <b><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">
由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。</font></b></p>
<p ALIGN="JUSTIFY"><b><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">
按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。</font></b></p>
<font FACE="oúì?,SimHei" LANG="ZH-CN">
<p ALIGN="JUSTIFY"><b><font size="5" color="#FFFFFF">⒈头尾表示法</font></b></p>
</font>
<p ALIGN="JUSTIFY"><b><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">
若广义表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可惟一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种存储方法。</font></b></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">
由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：一种是表结点，用以表示列表；另一种是元素结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">，则表示该结点为表结点；如果标志为</font>0</b><font FACE="??ì?,SimSun" LANG="ZH-CN"><b>，则表示该结点为元素结点。其形式定义说明如下：</b></font></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>typedef
enum {ATOM, LIST} Elemtag; /*ATOM=0<font FACE="??ì?,SimSun" LANG="ZH-CN">：单元素；</font>LIST=1<font FACE="??ì?,SimSun" LANG="ZH-CN">：子表</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">typedef
struct GLNode {</font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Elemtag
tag; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">标志域，用于区分元素结点和表结点</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>union
{ /*<font FACE="??ì?,SimSun" LANG="ZH-CN">元素结点和表结点的联合部分</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>datatype
data; /*data<font FACE="??ì?,SimSun" LANG="ZH-CN">是元素结点的值域</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">struct
{</font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">struct
GLNode *hp, *tp</font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>}ptr;
/*ptr<font FACE="??ì?,SimSun" LANG="ZH-CN">是表结点的指针域，</font>ptr.hp<font FACE="??ì?,SimSun" LANG="ZH-CN">和</font>ptr.tp<font FACE="??ì?,SimSun" LANG="ZH-CN">分别</font>*/</b></font></p>
<font SIZE="3">
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"></font><font size="5" color="#FFFFFF"><b>/*<font FACE="??ì?,SimSun" LANG="ZH-CN">指向表头和表尾</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">};</font></b></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>}*GList;
/*<font FACE="??ì?,SimSun" LANG="ZH-CN">广义表类型</font>*/</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">头尾表示法的结点形式如图</font>5.21<font FACE="??ì?,SimSun" LANG="ZH-CN">所示。</font></b></font></p>
<p ALIGN="JUSTIFY"><img border="0" src="ds5.4.1.gif" width="374" height="105"></p>
<p ALIGN="JUSTIFY"><b><font size="5" color="#FFFFFF"><font FACE="??ì?,SimSun" LANG="ZH-CN">
对于</font>5.5.1<font FACE="??ì?,SimSun" LANG="ZH-CN">所列举的广义表</font>A<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>B<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>C<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>D<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>E<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>F<font FACE="??ì?,SimSun" LANG="ZH-CN">，若采用头尾表示法的存储方式，其存储结构如图</font>5.22<font FACE="??ì?,SimSun" LANG="ZH-CN">所示。</font></font></b></p>
<p ALIGN="center"><font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3"><img border="0" src="ds5.4.2.gif" width="552" height="364"></font></p>
<font FACE="??ì?,SimSun" LANG="ZH-CN" SIZE="3">
<p ALIGN="JUSTIFY"> </font><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">
从上述存储结构示例中可以看出，采用头尾表示法容易分清列表中单元素或子表所在的层次。例如，在广义表</font>D<font FACE="??ì?,SimSun" LANG="ZH-CN">中，单元素</font>a<font FACE="??ì?,SimSun" LANG="ZH-CN">和</font>e<font FACE="??ì?,SimSun" LANG="ZH-CN">在同一层次上，而单元素</font>b<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>c<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>d<font FACE="??ì?,SimSun" LANG="ZH-CN">在同一层次上且比</font>a<font FACE="??ì?,SimSun" LANG="ZH-CN">和</font>e<font FACE="??ì?,SimSun" LANG="ZH-CN">低一层，子表</font>B<font FACE="??ì?,SimSun" LANG="ZH-CN">和</font>C<font FACE="??ì?,SimSun" LANG="ZH-CN">在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表</font>D<font FACE="??ì?,SimSun" LANG="ZH-CN">的最高层有三个表结点，其广义表的长度为</font>3<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></b></font></p>
<font FACE="oúì?,SimHei" LANG="ZH-CN">
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>⒉孩子兄弟表示法</b></font></p>
</font>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">
广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">，则表示该结点为有孩子结点；如果标志为</font>0<font FACE="??ì?,SimSun" LANG="ZH-CN">，则表示该结点为无孩子结点。其形式定义说明如下：</font></b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>typedef
enum {ATOM, LIST} Elemtag; /*ATOM=0<font FACE="??ì?,SimSun" LANG="ZH-CN">：单元素；</font>LIST=1<font FACE="??ì?,SimSun" LANG="ZH-CN">：子表</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>typedef
struct GLENode {</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>Elemtag
tag; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">标志域，用于区分元素结点和表结点</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>union
{ /*<font FACE="??ì?,SimSun" LANG="ZH-CN">元素结点和表结点的联合部分</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>datatype
data; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">元素结点的值域</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>struct
GLENode *hp; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">表结点的表头指针</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>};</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>struct
GLENode *tp; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">指向下一个结点</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>}*EGList;
/*<font FACE="??ì?,SimSun" LANG="ZH-CN">广义表类型</font>*/</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">孩子兄弟表示法的结点形式如图</font>5.23<font FACE="??ì?,SimSun" LANG="ZH-CN">所示。</font></b></font></p>
<p ALIGN="JUSTIFY"><img border="0" src="ds5.4.3.gif" width="369" height="100"></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">
对于</font>5.5.1<font FACE="??ì?,SimSun" LANG="ZH-CN">节中所列举的广义表</font>A<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>B<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>C<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>D<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>E<font FACE="??ì?,SimSun" LANG="ZH-CN">、</font>F<font FACE="??ì?,SimSun" LANG="ZH-CN">，若采用孩子兄弟表示法的存储方式，其存储结构如图</font>5.24<font FACE="??ì?,SimSun" LANG="ZH-CN">所示。</font></b></font></p>
<font SIZE="3">
<p ALIGN="center"><img border="0" src="ds5.4.4.gif" width="552" height="446"></p>
<p ALIGN="JUSTIFY"><font face="??ì?,SimSun" lang="ZH-CN"> </font></font><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">从图</font>5.24<font FACE="??ì?,SimSun" LANG="ZH-CN">的存储结构示例中可以看出，采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的</font>tag=1<font FACE="??ì?,SimSun" LANG="ZH-CN">的结点，且最高层结点的</font>tp<font FACE="??ì?,SimSun" LANG="ZH-CN">域必为</font>NULL<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></b></font></p>
<p ALIGN="JUSTIFY"> </p>
<p ALIGN="center"><font size="5" color="#FFFFFF"><b><a href="ds5.4.HTM">返回</a></b></font></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -