南邮数据结构上机实验二二叉树基本操作及哈夫曼编码译码系统实现.docx
- 文档编号:15796411
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:55
- 大小:292.09KB
南邮数据结构上机实验二二叉树基本操作及哈夫曼编码译码系统实现.docx
《南邮数据结构上机实验二二叉树基本操作及哈夫曼编码译码系统实现.docx》由会员分享,可在线阅读,更多相关《南邮数据结构上机实验二二叉树基本操作及哈夫曼编码译码系统实现.docx(55页珍藏版)》请在冰点文库上搜索。
南邮数据结构上机实验二二叉树基本操作及哈夫曼编码译码系统实现
实验报告
(2015/2016学年第二学期)
课程名称
数据结构A
实验名称
二叉树的基本操作及哈夫曼编码译码系统的实现
实验时间
2016
年
4
月
14
日
指导单位
计算机科学与技术系
指导教师
骆健
学生姓名
班级学号
学院(系)
管理学院
专业
信息管理与信息系统
实习题名:
二叉树的基本操作
班级姓名学号日期2016.04.14
一、问题描述
设计递归算法,实现下列二叉树运算:
删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。
设计算法,按自上到下,从左到右的顺序,按层次遍历一棵二叉树。
设计main函数,测试上述每个运算。
二、概要设计
文件tree.cpp中在该文件中定义二叉树的链式存储结构,用队列实现二叉树的层次遍历,并且编写实现二叉树的各种基本操作函数。
其中包括结点类BTNode,循环队列类SeqQueue,二叉树类BinaryTree。
主函数main的代码如图所示。
三、详细设计
1.类和类的层次设计
程序定义了循环队列SeqQueue类和二叉树BinaryTree类。
SeqQueue类主要是用队列实现,层次遍历。
运用后序遍历思想,把树分解为左右子树和跟结点再进行左右交换并计算树的高度,最后删除二叉树。
T
SeqQueue
-intfront,rear;
-intmaxSize;
-BTNode
+SeqQueue(intmSize);
+~SeqQueue(){delete[]q;}
+boolIsEmpty()const{returnfront==rear;}
+boolIsFull()const{return(rear+1)%maxSize==front;}
+boolFront(BTNode
+boolEnQueue(BTNode
+boolDeQueue();
+voidClear(){front=rear=0;}
T
(a)循环队列类
BinaryTree
+BinaryTree():
s(100){root=NULL;}
+~BinaryTree(){delete[]root;}
+boolClear();
+voidMakeTree(constT&x,BinaryTree
+intHigh(BTNode
+intNode_num(BTNode
+BTNode
+voidExchange(BTNode
+voidLevel_traversal(void(*Visit)(T&x));
#SeqQueue
-voidClear(BTNode
-voidLevel_traversal(void(*Visit)(T&x),BTNode
(b)二叉树类
2.核心算法
程序利用循环队列SeqQueue类通过不断出队并输出节点的值,将左右孩子入队直到队列为空实现二叉树的层次遍历。
并运用后序遍历思想,将二叉树树分解为左右子树和根结点,利用(p->lChild)和(p->rChild)计算结点数目,并通过交换结点的左右子树实现左右交换,计算树的高度,最后删除二叉树。
核心算法主要是二叉树BinaryTree类中的High,Node_num,Exchange,Level_traversal四个函数,其设计流程图如下:
High()
Node_num()
Exchange()
Level_traversal()
四、程序代码
template
intBinaryTree
:
Node_num(BTNode
{
if(p)
{
if(p->lChild==NULL&&p->rChild==NULL)
return1;
else
returnNode_num(p->lChild)+Node_num(p->rChild);
}
else
return0;
}
template
voidBinaryTree
:
Exchange(BTNode
{
if(t)
{
BTNode
t->lChild=t->rChild;
t->rChild=q;
Exchange(t->lChild);
Exchange(t->rChild);
}
}
template
voidBinaryTree
:
Level_traversal(void(*Visit)(T&x))//层次遍历
{
Level_traversal(Visit,root);
cout< } template voidBinaryTree : Level_traversal(void(*Visit)(T&x),BTNode { BTNode Visit(t->element); if(t->lChild) s.EnQueue(t->lChild); if(t->rChild) s.EnQueue(t->rChild); while(s.Front(a)==true) { if(a->lChild) s.EnQueue(a->lChild); if(a->rChild) s.EnQueue(a->rChild); Visit(a->element); s.DeQueue(); } } 五、测试和调试 1.测试用例和结果 测试结果如下图 2.结果分析 1)程序能够正确的实现二叉树的基本的建立、删除、复制、遍历以及结点计算等基本操作。 2)由测试结果来看,可以在输出数据时以二叉树图形的形式输出,更简单直观,因此程序还有待改进。 实习题名: 哈夫曼编码和译码系统 班级姓名学号日期2016.04.14 一、问题描述 所设计的系统重复显示以下菜单项: B―――建树: 读入字符集和各字符频度,建立哈夫曼树。 T―――遍历: 先序和中序遍历二叉树。 E―――生成编码: 根据已建成的哈夫曼树,产生各字符的哈夫曼编码。 C―――编码: 输入由字符集中字符组成的任意字符串,利用已生成的哈夫曼编码进行编码,显示编码结果,并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。 D―――译码: 读入codefile.txt,利用已建成的哈夫曼树进行译码,并将译码结果存入磁盘文件result.txt中。 P―――打印: 屏幕显示文件textfile.txt、codefile.txt和result.txt。 X―――退出。 二、概要设计 文件Huffman.cpp中定义了四个类,分别是优先权队列类PrioQueue和结点类BTNode、二叉树类BinaryTree以及哈夫曼树类HfmTree,其中哈夫曼树类HfmTree继承了二叉树类BinaryTree。 主函数mian的代码如图所示: 三、详细设计 1.类和类的层次结构 程序定义了优先权队列类PrioQueue存储元素,为便于实哈夫曼树的建树运算,定义了哈夫曼树类HfmTree是二叉树类BinaryTree的派生类,新增私有的数据成员weight保存二叉树根的权值。 成员函数getW和putW用于存取该值。 PrioQueue -T*q -intn,maxSize +PrioQueue(intmSize=20); +~PrioQueue(){delete[]q;} +boolIsEmpty()const{returnn==0;} +boolIsFull()const{returnn==maxSize;} +voidAppend(constT&x); +voidServe(T&x); -voidAdjustDown(intr,intj); -voidAdjustUp(intj); T BinaryTree -inti; +BinaryTree(){root=NULL;i=-1;} +~BinaryTree(){} +voidMakeTree(constT&x,constchar&y,BinaryTree +voidPreOrder(void(*Visit)(T&x)); +voidInOrder(void(*Visit)(T&x)); +voidCreate_code(); +voidCreate_code_out(); +voidCode(); +voidCompile(); +voidPrint(); -voidPreOrder(void(*Visit)(T&x),BTNode -voidInOrder(void(*Visit)(T&x),BTNode -voidCreate_code(BTNode -voidCreate_code_out(BTNode -voidCode(BTNode -voidMake(BTNode -voidCompile(BTNode T HfmTree -Tweight +operatorT()const{returnweight;} +TgetW(){returnweight;} +voidputW(constT&x){weight=x;} +voidSetNull(){root=NULL;} T 2.核心算法 定义了类之后,通过函数Make_Ht建树,将相应的字符和权值录入。 通过遍历哈夫曼树,产生每个叶子节点的哈夫曼编码,当遍历访问某个叶节点是,从该结点到根的路径可以确定该叶结点所代表的字符的编码。 实现译码时,首先将字符读入一维数组,根据0或1向左走向右走直到叶子结点,并将结果写入文件中。 其中关键函数编码code和译码Compile以及打印Print的流程图如下。 code() 下接下一页 Compile Print() 四、程序代码 HfmTree intnum; voidMake_Ht() { charstr[100]; intweight[100]; cout<<"请输入字符个数: "; cin>>num;//建树 cout<<"请输入权值: "; for(inti=0;i cin>>weight[i]; cout<<"请输入相应字符集: "; cin>>str; Ht=CreateHfmTree(weight,str,num); } voidTraversal_Ht() { Ht.PreOrder(Visit); Ht.InOrder(Visit); } template voidBinaryTree : Create_code() { Create_code(root); } template voidBinaryTree : Create_code(BTNode { if(t) { if(t->parent) { for(intj=0;j<=i;j++) t->z[j]=t->parent->z[j];//复制双亲的编码域 i++; t->z[i]=t->val;//在编码域中加入自己的编码 } Create_code(t->lChild);//递归,先左孩子,再右孩子 Create_code(t->rChild); i--; } } template voidBinaryTree : Create_code_out()//生成编码并输出 { Create_code_out(root); } template voidBinaryTree : Create_code_out(BTNode { if(t) { if(t->lChild==t->rChild)//叶子结点 { cout< ";//输出叶子结点中的字符 inti=0; while(t->z[i]! =-1) { cout< i++; } cout< } Create_code_out(t->lChild); Create_code_out(t->rChild); } } template voidBinaryTree : Code() { Code(root); } template voidBinaryTree : Code(BTNode { ofstreamoutf("textfile.txt"); if(! outf) { cout<<"Cannotopenthefile\n"; return; } ofstreamouts("codefile.txt",ios: : trunc); if(! outs) { cout<<"Cannotopenthefile\n"; return; } outs.close(); charstr2[100]; cout<<"请输入由字符集中字符组成的任意字符串: "; cin>>str2; outf< outf.close(); intl=strlen(str2); cout<<"编码为: "< for(inti=0;i Make(root,str2[i]); cout< } template voidBinaryTree : Make(BTNode { inti=0; if(t) { if(t->ch==a)//找到相应字符 { ofstreamouts("codefile.txt",ios: : app); while(t->z[i]! =-1) { cout< outs< i++; } outs.close(); return; } Make(t->lChild,a); Make(t->rChild,a); } } template voidBinaryTree : Compile()//译码 { Compile(root); } template voidBinaryTree : Compile(BTNode { ifstreaminf("codefile.txt"); if(! inf) { cout<<"Cannotopenthefile\n"; return; } ofstreamouts("result.txt",ios: : trunc); if(! outs) { cout<<"Cannotopenthefile\n"; return; } outs.close(); char*re; chartmp; intn=0; while(inf.get(tmp)! ='\0') { n++;//确定字符数量 } inf.close(); re=newchar[n+1]; intn2=0; ifstreamin("codefile.txt"); if(! in) { cout<<"Cannotopenthefile\n"; return; } while(in.get(tmp)! ='\0') { re[n2]=tmp;//将字符读入一位数组 n2++; } BTNode cout<<"译码为: "; intn3=0; while(n3 { while(t) { c=t; if(re[n3]=='0')//左0右1根据0或1向左走向右走直到叶子结点 t=t->lChild; else t=t->rChild; n3++; } ofstreamouts("result.txt",ios: : app); if(! outs) { cout<<"Cannotopenthefile\n"; return; } cout< outs< outs.close(); t=root; n3--; } cout< } voidPrint() { charstr; ifstreama("textfile.txt"); ifstreamb("codefile.txt"); ifstreamc("result.txt"); if(! a) { cout<<"Cannotopenthefile\n"; return; } if(! b) { cout<<"Cannotopenthefile\n"; return; } if(! c) { cout<<"Cannotopenthefile\n"; return; } cout<<"textfile.txt内的内容为: "; while(a.get(str)! ='\0') cout< cout< cout<<"codefile.txt内的内容为: "; while(b.get(str)! ='\0') cout< cout< cout<<"result.txt内的内容为: "; while(c.get(str)! ='\0') cout< cout< a.close(); b.close(); c.close(); } 五、测试和调试 1.测试用例和结果 1)输入B选择建树操作 2)分别输入a,b,c,d以及权值2,4,1,1,建树 3)输入T得到该树的遍历 4)输入E生成编码 5)输入C编码,输入字符串aabdcbdacbdadcdb 6)输入D选择译码 7)输入P选择打印文件内容 8)最后输入X退出 2.结果分析 1)程序能够完全实现题目的要求,建树,遍历生成编码,编码以及译码打印都能成功完成 2)不足之处在于译码方面,不能够实现自己输入一串编码来实现译码,下一步的目标是解决这个问题 实习小结 通过这次课程设计,使我对二叉树的相关知识有了更深的理解,我们要根据不同的需求,采用不同的数据存储方式,不一定要用栈,二叉树等高级类型,有时用基本的一维数组,只要运用得当,也能达到相同的效果,甚至更好。 同样的,这次在在程序的运行与调试过程中也出现了很多错误,通过反复地阅读课本上的知识,并且又对哈夫曼树的构造以及哈夫曼编码译码有了更深的理解。 在完成实验的过程中,不停地修改与调试,在调试过程中,我也认识到了自己更多的不足以及在细节上的把握不够,如对队列的知识不够熟悉,在使用过程中出现了很多问题。 在以后的学习中我要集中精力、端正态度,争取把知识学得更扎实、更全面。 附录: 1.二叉树的基本操作 #include #include usingnamespacestd; template structBTNode//结点类 { BTNode(){lChild=rChild=NULL;} BTNode(constT&x) { element=x; lChild=rChild=NULL; } BTNode(constT&x,BTNode { element=x; lChild=l; rChild=r; } Telement; BTNode }; template classSeqQueue { public: SeqQueue(intmSize); ~SeqQueue(){delete[]q;} boolIsEmpty()const{returnfront==rear;} boolIsFull()const{return(rear+1)%maxSize==front;} boolFront(BTNode boolEnQueue(BTNo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 上机 实验 二叉 基本 操作 哈夫曼 编码 译码 系统 实现
文档标签
- 哈夫曼编译码数据结构语言版
- 二叉排序树基本操作
- cvsd译码系统实验
- 树莓派基本操作
- 验证实验二叉子系统
- 操作系统集中上机实验
- 哈夫曼编译码实验指导书
- 二叉基本操作以及
- uCOS操作系统基本函数
- 哈弗曼编码译码器实验
- LDPC及其译码实现
- 哈工大数据结构作业哈夫曼树
- 数据结构实验三哈夫曼编解码器汇总数据结构实验
- 基于Java哈夫曼编码
- 哈夫曼码编译码系统递归
- 操作系统上机实验接口
- 二叉基本操作哈夫曼
- C++数据结构上机作业
- 二叉基本操作实现
- 数据结构上机实验哈夫曼树
- 实验数据编码器译码器
- 数据编码技术
- 数据结构哈夫曼编码
- 语音编码总结
- 哈夫曼编译器
- 数据结构设计哈夫曼编译码
- 哈夫曼编码解码语言
- 赫夫曼编译码器实现数据结构
- 哈夫曼编码与译码数据结构实验哈夫曼编码