中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第5章 广义表

数据结构—广义表 第五章 数组和广义表 主讲：张昱 说明：数组移到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 回 1

1 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

5.4广义表的定义(2) 5.4广义表的定义(3) ·示例 A■()∥A是一个空表，A的长度为0 。广义表是线性表的推广 B■(e)∥表B只有一个原子e,B的长度为1 ,表可以为其它表所共享(P108,D、A) C-(a,b,cd)1C的长度为2，第1个元素为原子，第2个 元素为子表 ·表可以是一个递归的表(P108,E) D=(A,B,C) D的长度为3,3个元素都是子表 E■(a,E ∥E是递归的表，它的长度为2 ·广义表还可以看成是图的推广 GetHead(B)■e GetTail(B)=() GetHead(D)=A, GetTail(D)(B,C) GetHead((()))■( GetTail((())》■() 714 囵 8/14 日 5.5广义表的存储结构 55广义表的存储结构 ·广义表难以用顺序存储结构表示 ■扩展线性链表存储表示 (“数据元素可以具有不同的结构) ·结点类型 ·原子结点 ■头尾链表存储表示 原子值、下一结点的指针 tag=0 atom tp ·结点类型 。表结点 表的头指针、下一结点的指针 ,原子结点：原子值 tag=0atom tag=1 hptp .类型定义P110 。表结点：表头、表尾 tag=1 hp tp ,类型定义P109 9/14 图 10/14 图 5.6m元多项式的表示 5.7广义表的通归算法(1) 。一元多项式的表示：线性表 ·递归定义 元素为(exp,coef)exp-指数域，coef-系数域 。蓄本项：描述一个或几个道归过程的终结状志， 。m元多项式 悠结状志，不需要继续递归而可直装求解的状态】 。归纳项：描述如何实现从当前状态到终结状态的转化， 。将m个变元着成有主次之分 一个元多项式首先是其主变元的多项式，而其系数又是第二个 递归函数的设计：归纳思维 变元的多项式 ·首先应书写函数头和规格说明，严格定义函数的功能和養 。结点类型 旦，对求精函敢中所得的和原问愿性质相同的子问愿，只要 ,原子情点：指辣、系敢、下一箱点的指针ag=0 exp coef中 接口一章，便可进行递归调用. ,妻结燕：抛收、系歌子表、下一墙点的指计ta9=1巴php中 ,对通数中的每个递归酒用整叠成汉是一个植单的操拖，只要 養口一袁，必能实现规格说明中定义的功糖，切恩想得太源 。类型定义P111 图 太远. 12/14 网囵 2

2 7/14 5.4 广义表的定义(2) „ 示例 A = ( ) //A是一个空表，A的长度为0 B = ( e ) // 表B只有一个原子e，B的长度为1 C = ( a, (b, c, d)) //C的长度为2, 第1个元素为原子，第2个 元素为子表 D = (A, B, C) //D的长度为3, 3个元素都是子表 E = (a, E) // E是递归的表，它的长度为2 GetHead(B) = e, GetTail(B) = ( ) GetHead(D) = A, GetTail(D) = ( B, C) GetHead(( ( ) ) ) = ( ), GetTail( ( ( ) )) = ( ) 8/14 5.4 广义表的定义(3) „ 广义表是线性表的推广 „ 表可以为其它表所共享(P108, D、A) „ 表可以是一个递归的表(P108, E) „ 广义表还可以看成是图的推广 9/14 5.5 广义表的存储结构 „ 广义表难以用顺序存储结构表示 (∵数据元素可以具有不同的结构) „ 头尾链表存储表示 „ 结点类型 „ 原子结点：原子值 „ 表结点：表头、表尾 „ 类型定义 P109 tag=0 atom tag=1 hp tp 10/14 5.5 广义表的存储结构 „ 扩展线性链表存储表示 „ 结点类型 „ 原子结点 原子值、下一结点的指针 „ 表结点 表的头指针、下一结点的指针 „ 类型定义 P110 tag=0 atom tp tag=1 hp tp 11/14 5.6 m元多项式的表示 „ 一元多项式的表示：线性表 元素为(exp, coef) exp-指数域，coef-系数域 „ m元多项式 „ 将m个变元看成有主次之分 „ 一个m元多项式首先是其主变元的多项式，而其系数又是第二个 变元的多项式 „ 结点类型 „ 原子结点：指数、系数、下一结点的指针 „ 表结点：指数、系数子表、下一结点的指针 „ 类型定义 P111 tag=1 exp hp tp tag=0 exp coef tp 12/14 5.7 广义表的递归算法(1) „ 递归定义 „ 基本项：描述一个或几个递归过程的终结状态． 终结状态：不需要继续递归而可直接求解的状态． „ 归纳项：描述如何实现从当前状态到终结状态的转化． „ 递归函数的设计：归纳思维 „ 首先应书写函数头和规格说明，严格定义函数的功能和接 口，对求精函数中所得的和原问题性质相同的子问题，只要 接口一致，便可进行递归调用． „ 对函数中的每个递归调用都看成只是一个简单的操作，只要 接口一致，必能实现规格说明中定义的功能，切忌想得太深 太远．

5.7广义表的递归算法(2) 5.7广义表的递归算法(3) 求广义表的深度 。复制广义表 。广义表的深度：广义表中括号的重数 ·善本项InitGList(NEWLS)当LS为空表时 LS=(aa2,,am） ,归纳项当LS非空时 。基本项DEPTH(LS)=1 当LS为空表时 CopyGList(GetHead(LS),GetHead(NEWLS)) DEPTH(LS■O 当LS为原子时 CopyGList(GetTail(LS),GetTail(NEWLS)) 。归纳项 ,算法实现 DEPTH(LS))-l+Max1GiGn{DEPTH(a》n≥1 ·盖于头尾链表存情结构算法5.6P115 。算法实现 。基于扩展线性链表存铺结构 ,基于头尾链表存铺结构算法5.5P114 。建立广义表的存储结构 。基于岁展线性链表存倩结构 13/14 回 14/14 图 0

3 13/14 5.7 广义表的递归算法(2) „ 求广义表的深度 „ 广义表的深度：广义表中括号的重数 LS = (a1, a2, …, an ) „ 基本项 DEPTH(LS) = 1 当LS为空表时 DEPTH(LS) = 0 当LS为原子时 „ 归纳项 DEPTH(LS) = 1+ Max1≤i≤n {DEPTH(ai )} n≥1 „ 算法实现 „ 基于头尾链表存储结构 算法5.5 P114 „ 基于扩展线性链表存储结构 14/14 5.7 广义表的递归算法(3) „ 复制广义表 „ 基本项 InitGList(NEWLS) 当LS为空表时 „ 归纳项 当LS非空时 CopyGList(GetHead(LS), GetHead(NEWLS)) CopyGList(GetTail(LS), GetTail(NEWLS)) „ 算法实现 „ 基于头尾链表存储结构 算法5.6 P115 „ 基于扩展线性链表存储结构 „ 建立广义表的存储结构