数据结构—广义表 第五章 数组和广义表 主讲：张昱 说明：数组移到<算法基础课中介绍 yuzhang@ustc.edu 重点：广义表的定义和存储结构、广义表 0551-3603804 的递归算法 1114 214 第五章广义表 54广义表的定义(1) 5.4广义表的定义 。广义表是线性表的推广 ·元素类型可以是原子，也可以是子表，习惯上 5.5广义表的存储结构 用大写字母表示广义表的名称，小写字母表示 原子。S=(a,a,an） 5.6m元多项式的表示 ·应用举例：表处理语言LISP中，把广义表作为 5.7广义表的递归算法 基本的数据结构 ,表头：表中的第1个元素，即a1 。表尾：除第1个元素外，其余元素组成的表， 3/14 即(a2,,an) 4/14 图 ADTGListf 数据对象：D-6i-1,2,mn>0,s长AtomSet或E GLit, GListEmpty(L). 初始条件，广义表L存在。。 数据关系：R1=(1,ere,fD,2gs) 视作结果：判定广义表工是否为空。。 基本操作， GetHead(L) 初始条件，广义表L存在。 操作结果：创健空的广义表工。 规作结果：取广义表工的头。 CreateGList(&L,S) GetTail(L) 初始条件：S是广义表的书写形式串。。 初始条件：广义表L存在。 操作结果：由S创广义表L。 DestroyGLit(&L) 操作结果：取广义表工的尾。 初始条件：广义表工存在。 InsertFirst GL(&L.e 操作结果：销毁广义表工。 初始条件：广义表工存在。 CopyGLisK &T.L)- 操作结果：插入元素：作为广义表工的第一个元素。， 材始条件：广义表工存在。 DeleteFi 操作结果。由广义表工复制得到广义表工。 :_GL(&L.&c). 初始条件：广义表工存在。 初始条件 广义表工存在 操作结墨：到殊广义表工的第一个元素，并用：返回其值 操作结果：求广义表L的长度。即元素个数。 Traverse GLL Vist() 初帕条件：广义表工存在。 初始条件：广义表工存在。 操作结朵：遇历广义表L,用函数：t处理每个元素。 操什结某：术扩义表L的深售d 图 )ADT-GList 6/14 回 11 1 /14 数据结构——广义表 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2 /14 说明：数组移到«算法基础»课中介绍 重点：广义表的定义和存储结构、广义表 的递归算法 第五章 数组和广义表 3/14 第五章 广义表 5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示 5.7 广义表的递归算法 4/14 5.4 广义表的定义(1) „ 广义表是线性表的推广 „ 元素类型可以是原子，也可以是子表，习惯上 用大写字母表示广义表的名称，小写字母表示 原子。LS = (a1, a2, …, an ) „ 应用举例：表处理语言LISP中，把广义表作为 基本的数据结构 „ 表头：表中的第1个元素，即a1 „ 表尾：除第1个元素外，其余元素组成的表， 即(a2, …, an ) 5/14 6/14