资源描述：
《数据结构广义表、开发结构、排序、树和图ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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的表头（head）,
2、称第其余元素组成的表(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表示取头操作he
4、ad，用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其他操作member(e,ls)判别e是否为ls的成员merg(ls1,ls2)以ls1为头ls2为尾建立广义表equal(ls1,ls2)判别ls1,ls2是否相等copy(ls1,ls2)复制广义表，即按ls1建立广义表ls2depth(ls)求广义表ls的深度print(ls)打印广义表ls8广义表与其他数据结构的关系
5、1与线性表的关系当限定广义表的每一项只能是基本元素而非子表时，广义表就退化为线性表：(a1,a2,…,an)；2与二维数组的关系当将数组的每行（或每列）看作为子表时，数组即为一个广义表：((a11,a12,…,a1n),(a21,a22,…,a2n),…(an1,an2,…,ann))3与树的关系树也可以用广义表来表示，例如图7.1所表示的树可以用如下的广义表来表示：(a,(b,c,d),e,(f,g))4.在LISP语言中，使用函数嵌套的形式来构造程序。例如：（op（opAB）（opCD））在这种情形下，程序本身就是一个广义表。9存储方式：头尾表示法二类节点表节点元素节点struc
6、tnode{inttag;union{chardata;structnode*hp;};structnode*tp;};typedefstructnodenodetp;typedefstructnode*pointp;typedefpointpgybtp;Tag=1hptpTag=0data10存储方式：头尾表示法C=(a,(b,c,d))((b,c,d))10b0c0d0a1٨111٨(b,c,d)(c,d)(d)11存储方式：儿子兄弟表示法二类节点有儿子无儿子类型定义与头尾表示法的类型定义是一致的，只不过各字域所代表的含义有所不同。Tag=1hptpTag=0datatp12存储
7、方式：儿子兄弟表示法C=(a,(b,c,d))最高层结点的tp域必为nil1٨0d٨0c1٨0b(b,c,d)0a13广义表的类定义classTgyb{private:structTgybnode*ls;voidsever(String&st,String&hst);structTgybnode*crtlists(Stringst);voidena(charch);voidprt(structTgybnode*ls);public:Tgyb(){ls=NU
