二叉树与哈夫曼编码.docx
- 文档编号:15967589
- 上传时间:2023-07-09
- 格式:DOCX
- 页数:32
- 大小:184.71KB
二叉树与哈夫曼编码.docx
《二叉树与哈夫曼编码.docx》由会员分享,可在线阅读,更多相关《二叉树与哈夫曼编码.docx(32页珍藏版)》请在冰点文库上搜索。
二叉树与哈夫曼编码
实验报告
(2014/2015学年第二学期)
课程名称
数据结构
实验名称
实验二二叉树的基本操作及哈夫曼编码译码系统的实现
实验时间
2015
年
10
月
31
日
指导单位
计算机软件学院
指导教师
骆健
学生姓名
陈兵
班级学号
B14041126
学院(系)
计软院
专业
软嵌NIIT
实验报告
实验名称
实验二二叉树的基本操作及哈夫曼编码译码系统的实现
指导教师
骆健
实验类型
设计
实验学时
2
实验时间
一、实验目的和要求
(1)掌握二叉链表上实现二叉树基本去处的方法。
(2)学会设计基于遍历的求解二叉树应用问题的递归算法。
(3)理解哈夫曼树的构造算法,学习设计哈夫曼编码和译码系统。
二、实验环境(实验设备)
硬件:
微型计算机
软件:
MicrosoftVisualC++6.0
三、实验原理及内容
实验题一:
在二叉链表上实现二叉树运算
(1)设计递归算法,实现下列二叉树运算:
删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。
(2)设计算法,按自上到下,从左到右的顺序,按层次遍历一棵二叉树。
(3)设计main函数,测试上述每个运算。
内容:
1、建立头文件BTree.H,在该文件中定义二叉树的链式存储结构,并编写二叉树的各种基本操作实现函数。
同时建立一个验证操作实现的主函数文件Test.cpp,编译并调试程序,直到正确运行。
注意:
需要用到队列的有关操作。
实验报告
(一)概要设计
1.流程图及设计思想
实验报告
代码:
#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
classBinaryTree
{
public:
BinaryTree(){root=NULL;}
~BinaryTree(){};
boolIsEmpty()const;
voidClear();
boolRoot(T&x)const;
voidMakeTree(constT&x,BinaryTree
voidMakeTree(BTNode
voidBreakTree(T&x,BinaryTree
voidDeleteTree();
voidPreOrder(void(*Visit)(T&x));
intGetTreeHeight()const;
intGetLeavesNumber()const;
BTNode
voidExchangeChildTree();
protected:
BTNode
private:
voidClear(BTNode
voidPreOrder(void(*Visit)(T&x),BTNode
voidDeleteTree(BTNode
intGetTreeHeight(BTNode
intGetLeavesNumber(BTNode
BTNode
voidExchangeChildTree(BTNode
};
template
boolBinaryTree
:
Root(T&x)const
{
if(root){
x=root->element;returntrue;
}
else
{
returnfalse;
}
}
template
voidBinaryTree
:
MakeTree(constT&x,BinaryTree
{
if(root||&left==&right)return;
root=newBTNode
left.root=NULL;
right.root=NULL;
}
template
voidBinaryTree
:
MakeTree(BTNode
{
root=r;
}
template
voidBinaryTree
:
BreakTree(T&x,BinaryTree
{
if(!
root||&left==&right||left.root||right.root)return;
x=root->element;
left.root=root->lChild;
right.root=root->rChild;
deleteroot;
root=NULL;
}
template
voidBinaryTree
:
PreOrder(void(*Visit)(T&x))
{
PreOrder(Visit,root);
}
template
voidBinaryTree
:
PreOrder(void(*Visit)(T&x),BTNode
{
if(t){
Visit(t->element);
PreOrder(Visit,t->lChild);
PreOrder(Visit,t->rChild);
}
}
template
voidBinaryTree
:
DeleteTree()
{
DeleteTree(root);
}
template
voidBinaryTree
:
DeleteTree(BTNode
{
if(t){
DeleteTree(t->lChild);
DeleteTree(t->rChild);
deletet;
}
}
template
intBinaryTree
:
GetTreeHeight()const
{
returnGetTreeHeight(root);
}
template
intBinaryTree
:
GetTreeHeight(BTNode
{
if(t)
return(GetTreeHeight(t->lChild)>GetTreeHeight(t->rChild)?
GetTreeHeight(t->lChild):
GetTreeHeight(t->rChild))+1;
else
return0;
}
template
intBinaryTree
:
GetLeavesNumber()const
{
returnGetLeavesNumber(root);
}
template
intBinaryTree
:
GetLeavesNumber(BTNode
{
if(!
t->lChild&&!
t->rChild)
return1;
else
returnGetLeavesNumber(t->lChild)+GetLeavesNumber(t->rChild);
}
template
BTNode
:
CopyTree()const
{
returnCopyTree(root);
}
template
BTNode
:
CopyTree(constBTNode
{
if(t)
{
BTNode
p->lChild=CopyTree(t->lChild);
p->rChild=CopyTree(t->rChild);
returnp;
}
returnNULL;
}
template
voidBinaryTree
:
ExchangeChildTree()
{
ExchangeChildTree(root);
}
template
voidBinaryTree
:
ExchangeChildTree(BTNode
{
if(!
t->lChild&&!
t->rChild)return;
ExchangeChildTree(t->lChild);
ExchangeChildTree(t->rChild);
BTNode
tmp=t->lChild;
t->lChild=t->rChild;
t->rChild=tmp;
}
template
voidVisit(T&x)
{
cout< } voidmain() { BinaryTree chare; y.MakeTree('E',a,b); z.MakeTree('F',a,b); x.MakeTree('C',y,z); y.MakeTree('D',a,b); z.MakeTree('B',y,x); z.PreOrder(Visit); cout<<"\n叶子结点数: "< cout<<"\n树的高度: "< BTNode BinaryTree m.MakeTree(r); cout< m.PreOrder(Visit); z.ExchangeChildTree(); cout< z.PreOrder(Visit); charn=getchar(); } 实验题二: 哈夫曼编码和译码系统 (1)所设计的系统重复显示以下菜单项: B―――建树: 读入字符集和各字符频度,建立哈夫曼树。 T―――遍历: 先序和中序遍历二叉树。 E―――生成编码: 根据已建成的哈夫曼树,产生各字符的哈夫曼编码。 C―――编码: 输入由字符集中字符组成的任意字符串,利用已生成的哈夫曼编码进行编码,显示编码结果,并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。 D―――译码: 读入codefile.txt,利用已建成的哈夫曼树进行译码,并将译码结果存入磁盘文件result.txt中。 P―――打印: 屏幕显示文件textfile.txt、codefile.txt和result.txt。 X―――退出。 源代码: #include #include #include #include usingnamespacestd; template classPrioQueue//优先权队列类 { public: PrioQueue(intmSize=20); ~PrioQueue(){delete[]q;} boolIsEmpty()const{returnn==0;} boolIsFull()const{returnn==maxSize;} voidAppend(constT&x); voidServe(T&x);private: voidAdjustDown(intr,intj); voidAdjustUp(intj); T*q; intn,maxSize; }; template PrioQueue : PrioQueue(intmSize) { maxSize=mSize; n=0; q=newT[maxSize]; } template voidPrioQueue : AdjustUp(intj) { inti=j; Ttemp=q[i]; while(i>0&&temp { q[i]=q[(i-1)/2]; i=(i-1)/2; } q[i]=temp; } template voidPrioQueue : Append(constT&x)//插入新元素 { if(IsFull()) { cout<<"Overflow"< return; } q[n++]=x; AdjustUp(n-1); }template voidPrioQueue : Serve(T&x)//删除堆顶元素 { if(IsEmpty()) { cout<<"Underflow"< return; }x=q[0]; q[0]=q[--n]; AdjustDown(0,n-1); }template voidPrioQueue : AdjustDown(intr,intj)//向上调整 { intchild=2*r+1; Ttemp=q[r]; while(child<=j) { if((child child++; if(temp<=q[child]) break; q[(child-1)/2]=q[child]; child=2*child+1; } q[(child-1)/2]=temp; } template structBTNode//结点类 { BTNode() { lChild=rChild=NULL; } BTNode(constT&x,constchar&y) { element=x; ch=y; lChild=rChild=parent=NULL; memset(z,-1,sizeof(z)); } BTNode(constT&x,constchar&y,BTNode { element=x; ch=y; lChild=l; rChild=r; parent=NULL; memset(z,-1,sizeof(z)); } Telement; BTNode charch; intval; intz[100]; }; template classBinaryTree { public: 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(); BTNode private: inti; 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 { 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)) { n++;//确定字符数量 } inf.close(); re=newchar[n+1]; intn2=0; ifstreamin("codefile.txt"); if(! in) { cout<<"Cannotopenthefile\n"; return; } while(in.get(tmp)) { 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< } }; template voidBinaryTree : MakeTree(constT&x,constchar&y,BinaryTree { if(root||&left==&right) return; root=newBTNode if(left.root! =right.root) { left.root->parent=root; right.root->parent=root; left.root->val=0; right.root->val=1; } left.root=right.root=NULL; }template voidVisit(T&x) { cout< }template voidBinaryTree : PreOrder(void(*Visit)(T&x))//先序遍历 { cout<<"先序遍历为: "; PreOrder(Visit,root); cout< }template voidBinaryTree : PreOrder(void(*Visit)(T&x),BTNode { if(t) { Visit(t->element); PreOrder(Visit,t->lChild); PreOrder(Visit,t->rChild); } } template
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 哈夫曼 编码