广东工业大学数据结构实验和课程设计
1.实验:抽像数据类型——树
基本操作描述
树的结构定义和树的一组基本操作:
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有∈H;
(3) 对应于D-{root}的划分,H-{,…,}有唯一的一个划分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()失败,则操作失败。
}ADT Tree
在双亲表存储结构中添加以下基本抽象数据类型:
Status Print(PTree T);
附加函数:用于显示树的所有内容。
初始条件:树T存在;
操作结果:将树T的所有结点显示出来。
在双亲表存储结构中,TraverseTree(T,visit())函数是按层次次序对T的每个结点进行访问的。
2.课程设计:哈夫曼编/译码器
基本要求
一个完整的系统应具有以下功能:
(1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
(2)E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件htmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
(4)P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中。
(5)T:印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
内包含完整正确的代码和实验报告&课程设计报告,希望对大家有所帮助。
1