数据结构-树的实现实验报告.doc

数据结构设计性实验报告

课程名称_____ ____
题目名称
学生学院
专业班级
学号
学生姓名
指导教师
2010 年 7 月 6 日
抽象数据类型:树的实现
需求分析
树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,直观来看,树是以分支关系定义的内部结构。树的结构在客观世界广泛存在,如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用,如在编译程序中,可用树来表示源程序的语法结构,又如在数据库系统中,树形结构也是信息的重要组织形式之一。
实验目的
对某个具体的抽象数据类型,运用课程所学的知识和方法,设计合理的数据结构,并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验,检验所学知识和能力,发现学****中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。
实验环境
1、硬件:PC机
2、软件:Microsoft Visual C++
设计说明
本程序采用树的二叉链表(孩子指针-兄弟指针-双亲指针)存储表示,以下是树的结构定义和基本操作:
ADT Tree{
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:
若D为空集,则称为空树;
若D仅含有一个数据元素,则R为空集,否则R={H},H是如下二元关系:
(1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;
(2) 若D-{root}≠NULL,则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0),对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m),唯一存在数据元素xi∈Di有<root,xi>∈H;
(3) 对应于D-{root}的划分,H-{<root,xi>,…,<root,xm>}有唯一的一个划分H1,H2,…,Hm(m>0),对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL,且对任意i(1≤i≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合本定义的树,称为根root的子树。
基本操作P:
InitTree(&T);
操作结果:构造空树T。
DestroyTree(&T);
初始条件:树T存在。
操作结果:销毁树T。
CreateTree(&T,definition);
初始条件:definition给出树T的定义。
操作结果:按definition构造树T。
ClearTree(&T);
初始条件:树T存在。
操作结果:将树T清为空树。
TreeEmpty(T);
初始条件:树T存在。
操作结果:若T为空树,则返回TRUE,否则返回FALSE。
TreeDepth(T);
初始条件:树T存在。
操作结果:返回T的深度。
Root(T);
初始条件:树T存在。
操作结果:返回T的根。
Value(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:返回cur_e的值。
Assign(T,cur_e,value);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:结点cur_e赋值为value。
Parent(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e是T的非根结点,则返回它的双亲,否则函数值为“空”。
LeftChild(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e是T的非叶子结点,则返回它的最左孩子,否则返回“空”。
RightSibling(T,cur_e);
初始条件:树T存在,cur_e是T中某个结点。
操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则返回“空”。
InsertChild(&T,&p,I,c);
初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度+1,非空树c与T不相交。
操作结果:插入c为T中p指结点的第i棵子树。
DeleteChild(&T,&p,i);
初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。
操作结果:删除T中p所指结点的第i棵子树。
TraverseTree(T,visit());
初始条件:树T存在,visit是对结点操作的应用函数。
操作结果:按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败,则操作失败。
CSTree Search(CSTree T,TElemType cur_e);
初始条件:树T存在,cur_e可能是树T中某一个结点的值。
操作结果:在树T中查找值为cur_e的结