📄 class20.htm
字号:
<html>
<head>
<title>数据结构--数据空间http://zmofun.lyg165.com</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF">
<p align="center"><b>第二十课</b></p>
<p><b><i>本课主题：</i></b> 广义表</p>
<p><b><i>教学目的：</i></b> 广义表的定义及存储结构</p>
<p><b><i>教学重点：</i></b> 广义表的操作及意义</p>
<p><b><i>教学难点：</i></b> 广义表存储结构</p>
<p><b><i>授课内容：</i></b></p>
<p>一、广义表的定义</p>
<blockquote>
<p>广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身.</p>
<p>广义表的定义:</p>
<p>ADT GList{</p>
<p>数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList,</p>
<p>AtomSet为某个数据对象}</p>
<p>数据关系:R1={<ei-1,ei>|ei-1,ei(-D,2=<i<=n}</p>
<p>基本操作:</p>
<p>InitGlist(&L);</p>
<p>操作结果:创建空的广义表L</p>
<p>CreateGList(&L,S);</p>
<p>初始条件:S是广义表的书写形式串</p>
<p>操作结果:由S创建广义表L</p>
<p>DestroyGlist(&L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:销毁广义表L</p>
<p></p>
<p>CopyGlist(&T,L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:由广义表L复制得到广义表T</p>
<p></p>
<p>GListLength(L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:求广义表L的长度,即元素个数</p>
<p></p>
<p>GListDepth(L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:求广义表L的深度</p>
<p></p>
<p>GlistEmpty(L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:判断广义表L是否为空</p>
<p></p>
<p>GetHead(L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:取广义表L的头</p>
<p></p>
<p>GetTail(L);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:取广义表L的尾</p>
<p></p>
<p>InsertFirst_GL(&L,e);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:插入元素e作为广义表L的第一元素</p>
<p></p>
<p>DeleteFirst_GL(&L,&e);</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:删除广义表L的第一元素,并用e返回其值</p>
<p></p>
<p>Traverse_GL(L,Visit());</p>
<p>初始条件:广义表L存在</p>
<p>操作结果:遍历广义表L,用函数Visit处理每个元素</p>
<p></p>
<p>}ADT GList</p>
<p>广义表一般记作:LS=(a1,a2,...,an)</p>
<p>其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为<font color="#FF0033">原子</font>和<font color="#FF0000">子表</font>,当广义表非空时,称第一个元素a1为LS的<font color="#FF0000">表头</font>称其余元素组成的广义表为<font color="#FF0033">表尾.</font></p>
</blockquote>
<p>二、广义表的存储结构</p>
<blockquote>
<p>广义表的头尾链表存储表示</p>
<p>typedef emnu{ATOM,LIST} ElemTag;</p>
<p>typedef struct GLNode{</p>
<blockquote>
<p>ElemTag tag;</p>
<p>union{</p>
<blockquote>
<p>AtomType atom;</p>
<p>struct{struct GLNode *hp,*tp;}ptr;</p>
<p>}</p>
</blockquote>
</blockquote>
<p>}</p>
<p>有A、B、C、D、E五个广义表的描述如下：</p>
<p>A=() A是一个空表,它的长度为零</p>
<p>B=(e) 列表B只有一个原子e,B的长度为1.</p>
<p>C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)</p>
<p>D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))</p>
<p>E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))</p>
<p>上述五个广义表用以上的存储结构的存储映像如下:</p>
<p> </p>
</blockquote>
<p><a href="../index.htm">回目录</a> <a href="../class19/class19.htm">上一课</a> <a href="../class21/class21.htm">下一课</a></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -