数据结构20-21

第二十课

本课主题：广义表

教学目的：广义表的定义及存储结构

教学重点：广义表的操作及意义

教学难点：广义表存储结构

授课内容：

一、广义表的定义

广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身.

广义表的定义:

ADT GList{

数据对象:D={i=1,2,...,n& gt;=0;ei(-AtomSet或ei(-GList,

AtomSet为某个数据对象}

数据关系:R1={<ei-1,ei>|ei-1,ei(-D,2=<i<=n}

基本操作:

InitGlist(&L);

操作结果:创建空的广义表L

CreateGList(&L,S);

初始条件:S是广义表的书写形式串

操作结果:由S创建广义表L

DestroyGlist(&L);

初始条件:广义表L存在

操作结果:销毁广义表L

CopyGlist(&T,L);

初始条件:广义表L存在

操作结果:由广义表L复制得到广义表T

GListLength(L);

初始条件:广义表L存在

操作结果:求广义表L的长度,即元素个数

GListDepth(L);

初始条件:广义表L存在

操作结果:求广义表L的深度

GlistEmpty(L);

初始条件:广义表L存在

操作结果:判断广义表L是否为空

GetHead(L);

初始条件:广义表L存在

操作结果:取广义表L的头

GetTail(L);

初始条件:广义表L存在

操作结果:取广义表L的尾

InsertFirst_GL(&L,e);

初始条件:广义表L存在

操作结果:插入元素e作为广义表L的第一元素

DeleteFirst_GL(&L,&e);

初始条件:广义表L存在

操作结果:删除广义表L的第一元素,并用e返回其 值

Traverse_GL(L,Visit());

初始条件:广义表L存在

操作结果:遍历广义表L,用函数Visit处理每 个元素

}ADT GList

广义表一般记作:LS=(a1,a2,...,an)

其中LS是广义表的名称,n是它的长度,ai可以 是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾.

二、广义表的存储结构

广义表的头尾链表存储表示

typedef emnu{ATOM,LIST} ElemTag;

typedef struct GLNode{

ElemTag tag;

union{

AtomType atom;

struct{struct GLNode *hp,*tp;}ptr;

}

}

有A、B、C、D、E五个广义表的描述如下：

A=() A是一个空表,它的长度为零

B=(e) 列表B只有一个原子e,B的长度为1.

C=(a,(b,c,d)) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d)

D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=((),(e),(a,(b,c,d)))

E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,...)))

上述五个广义表用以上的存储结构的存储映像如下:

回目录上一课下一课

第二十一课

本课主题：树、二叉树定义及术语

教学目的：掌握树、二叉树的基本概念和术语，二叉树的性质

教学重点：二叉树的定义、二叉树的性质

教学难点：二叉树的性质

授课内容：

一、树的定义：

树是n(n>=0) 个结点的有限集。在任意一棵非空树中：

(1)有且仅有一个特定的称为根的结 点；

(2)当n>1时,其余结点可 分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树.

二、树的基本概念：

树的结点包含一个数据元素及若干 指向其子树的分支。

结点拥有的子树数称为结点的度。

度为0的结点称为叶子或终端结点。

度不为0的结点称为非终端结点或分支结点。

树的度是树内各结点的度的最大值。

结点的子树的根称为该结点的孩子，相应地，该结点称为孩 子的双亲。

同一个双亲的孩子之间互称兄弟。

结点的祖先是从根到该结点所经分支 上的所有结点。

以某结点为根的子树中的任一结点都称为该结点的子孙。

结点的层次从根开始定义起，根为第一层，根的孩子为第二层。其双 亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度，或高度。

如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序 树，否则称为无序树。

森林是m(m>=0) 棵互不相交的树的集合。

三、二叉树的定义

二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树 （即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

一棵深度为k且有 2(k)-1个结点的二叉树称为满二叉树，如图(a)，按图示给每个结点编号，如果有深度为k的，有n个结点的二叉 树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

二叉树的定义如下：

ADT BinaryTree{

数据对象D:D是具有相 同特性的数据元素的集合。

数据关系R:

基本操作P:

InitBiTree(&T);

DestroyBiTree(&T);

CreateBiTree(&T,definition);

ClearBiTree(&T);

BiTreeEmpty(T);

BiTreeDepth(T);

Root(T);

Value(T,e);

Assign(T,&e,value);

Parent(T,e);

LeftChild(T,e);

RightChild(T,e);

LeftSibling(T,e);

RightSibling(T,e);

InsertChild(T,p,LR,c);

DeleteChild(T,p,LR);

PreOrderTraverse(T,visit());

InOrderTraverse(T,visit());

PostOrderTraverse(T,visit());

LevelOrderTraverse(T,Visit());

}ADT BinaryTree

三、二叉树的性质

四、总结

回目录上一课下一课