资源描述：
《数据结构：面向对象语言描述bppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、版权所有,1997(c)DaleCarnegie&Associates,Inc.数据结构面向对象语言描述朱振元1版权所有,1997(c)DaleCarnegie&Associates,Inc.数据结构广义表朱振元2广义表的初步认识广义表（又称为列表）是n(n>=0)个数据元素a1,a2,…,ai,…,an的有限序列，一般记作：ls=(a1,a2,…,ai,…,an)其中，ls是广义表(a1,a2,…,an)的名称，n是它的长度。每个ai(1<=i<=n)是ls的成员，它可以是单个元素，也可以是一个广义表,分别称为广义表ls的单元素和子表。当广义表ls非空时，称第一个元素a1为ls的表头（
2、head）,称第其余元素组成的表(a2,a3,…,an)为ls的表尾（tail）3广义表的初步认识例：A=()A是空表，其长度为0。B=(e)B中只有一个单元素e，长度为1。C=(a,(b,c,d))D=(A,B,C)D的长度为3，三个元素都是列表。D＝((),(e),(a,(b,c,d)))E=(a,E)E是一个长度为2的递归的广义表，E相当于一个无穷表E=(a,(a,(a,……)))F=(())F的长度为1，其中的一个元素为一个空表。4广义表的初步认识特性：（1）广义表是一个多层次的结构。因为广义表的元素可以是一个子表，而子表的元素还可以是子表。（2）广义表可以为其它广义表所共享。例
3、如在上述的例子中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表可以是一个递归表，即广义表也可以是本身的一个子表。例如广义表E就是一个递归表。5二个重要的基本操作取头操作head取尾操作tail对于广义表ls=(a1,a2,…,an)head(ls)=a1tail(ls)=(a2,a3,…,an)对于任意一个非空的列表，其表头可能是单元素也可能是列表，而其表尾必为列表。例如：head(C)=atail(C)=(b,c,d)head(D)=Atail(D)=(B,C)head(F)=()tail(F)=()6取头去尾复合操作用H表示取头操作
4、head，用T表示取尾操作tail，对于广义表ls=(a,(b,c,d))执行一系列的基本操作，其结果如下：H(ls)=aT(ls)=((b,c,d))H(T(ls))=(b,c,d)T(T(ls))=()H(H(T(ls)))=bT(H(T(ls)))=(c,d)7广义表抽象数据类型数据元素：D={ei
5、i=1,2,……,n;n≧0;ei∈AtomSet或ei∈GList}结构关系：R1={
6、ei-1,ei∈D,2≤i≤n}基本操作：对广义表可执行以下的基本操作。InitGList(L)初始化。创建一个空的广义表L。CopyGList(L,L0)复制。由广义表L0复制
7、得到一个广义表L。GListDepth(L)求深度。求广义表L的深度。GListLength(L)求长度。求广义表L的长度，即元素个数。GlistEmpty(L)判空表。判广义表L是否为空。GetHead(L)取头。取广义表L的头。GetTail(L)取尾。取广义表L的尾。InsertFirst(L,e)插入元素。插入元素e作为广义表L的第一元素。8广义表与其他数据结构的关系1与线性表的关系当限定广义表的每一项只能是基本元素而非子表时，广义表就退化为线性表：(a1,a2,…,an)；2与二维数组的关系当将数组的每行（或每列）看作为子表时，数组即为一个广义表：((a11,a12,…,a1n
8、),(a21,a22,…,a2n),…(an1,an2,…,ann))3与树的关系树也可以用广义表来表示，例如图7.1所表示的树可以用如下的广义表来表示：(a,(b,c,d),e,(f,g))4.在LISP语言中，使用函数嵌套的形式来构造程序。例如：（op（opAB）（opCD））在这种情形下，程序本身就是一个广义表。9存储方式：头尾表示法二类节点表节点元素节点typedefcharTatom;structGListNode{inttag;union{Tatomdata;GListNode*hp;};GListNode*tp;};Tag=1hptpTag=0data10存储方式：头尾表示
9、法C=(a,(b,c,d))((b,c,d))10b0c0d0a1٨111٨(b,c,d)(c,d)(d)11存储方式：儿子兄弟表示法二类节点有儿子无儿子类型定义与头尾表示法的类型定义是一致的，只不过各字域所代表的含义有所不同。Tag=1hptpTag=0datatp12存储方式：儿子兄弟表示法C=(a,(b,c,d))最高层结点的tp域必为nil1٨0d٨0c1٨0b(b,c,d)0a13互动环节：G=((a,b),(c,d))的
