实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计.docx
《实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计.docx》由会员分享,可在线阅读,更多相关《实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计.docx(20页珍藏版)》请在冰点文库上搜索。
实验报告模版二叉树基本操作与哈夫曼编码译码系统的设计
(此文档为word格式,下载后您可任意编辑修改!
)
课程设计报告
(20132014学年第2学期)
题目:
二叉树基本操作与哈夫曼编码译码系统的设计
专业:
学生姓名:
班级学号:
指导教师
指导单位
日期
评分细则
评分项
成绩
遵守机房规章制度(5分)
上机时的表现(5分)
学习态度(5分)
程序准备情况(5分)
程序设计能力(10分)
团队合作精神(5分)
课题功能实现情况(10分)
算法设计合理性(10分)
用户界面设计(10分)
报告书写认真程度(5分)
内容详实程度(10分)
文字表达熟练程度(10分)
回答问题准确度(10分)
简短评语
教师签名:
年月日
评分等级
备注
评分等级有五种:
优秀、良好、中等、及格、不及格
课题题目
二叉树基本操作与哈夫曼编码译码系统的设计
一、课题内容和要求
创建一棵二叉树,分别实现先序、中序和后序遍历一棵二叉树,计算二叉树结点个数等操作。
设计哈夫曼编码译码系统。
能成功演示二叉树的有关运算,运算完毕后能成功释放二叉树所有结点占用的系统内存。
二、需求分析
我们根据需求得到以上的菜单,以链表方式存储二叉树,以插入二叉搜索树的方式,将数据一个一个地插入二叉树,以递归的方式分别实现先、中、后三种方式的遍历和计算二叉树的高度,删除二叉树时,先搜索找到那个节点,若有两个子节点,查找中序遍历直接后继节点,之后常规的替代删除操作,最后是哈夫曼树的实现,从文件读取字符串的时候,用while循环来得到每个字母的出现次数,得到权值,之后实现哈夫曼树,通过译码函数输出译码序列。
三、概要设计
typedefcharEtype;
typedefstructbtnode
{
Etypedata;
structbtnode*lch,*rch;
intweight;
}btnode;
typedefstructbtree
{
structbtnode*root;
}btree;
typedefstruct{
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
其他的就是各类函数,见下文。
四、详细设计
#include}
btnode*newnode(Etypee)
{
btnode*p=(btnode*)malloc(sizeof(btnode));
p->data=e;
p->lch=NULL;
p->rch=NULL;
returnp;
}
voidMAKEBTREE(btree*bt,intx,btree*lt,btree*rt)
{
btnode*p=newnode();
p->weight=x;
p->lch=lt->root;
p->rch=rt->root;
lt->root=NULL;
rt->root=NULL;
bt->root=p;
}
voidCREATEBTREE(btree*bt)*构造一颗空二叉数*
{
bt->root=NULL;
}
模仿先序递归遍历方法,建立二叉树
btnode*creat_bt2()
{
btnode*t;
Etypee;
scanf("%c",&e);
if(e=='#')t=NULL;对于'#'值,不分配新结点
else{
t=(btnode*)malloc(sizeof(btnode));
t->data=e;
t->lch=creat_bt2();左孩子获得新指针值
t->rch=creat_bt2();右孩子获得新指针值
}
returnt;
}creat_bt2
voidpreorder(btnode*p)前序遍历
{
if(p){
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}preorder
中序递归遍历二叉树
voidinorder(btnode*p)
{
if(p){
inorder(p->lch);
cout<data<inorder(p->rch);
}
}inorder
后序递归遍历二叉树
voidpostorder(btnode*p)
{
if(p){postorder(p->lch);
postorder(p->rch);
cout<data<}
}postorder
intDepth(btnode*p)
{
if(!
p)
return0;
else
return1+((Depth(p->lch)>Depth(p->rch))?
Depth(p->lch):
Depth(p->rch));
}
intleafcount(btnode*bt)输入btree的root
{计算叶结点数
intcount=0;
if(bt!
=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
}
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
returncount;
}
intremove(btree*bt)输入那个节点的值
{
btnode*p=bt->root;
btnode*c,*r,*s,*q;
Etypex,e;
cout<<"请输入要删除的节点的值"<cin>>e;
while(p&&p->data!
=e)
{
q=p;
if(edata)p=p->lch;
elsep=p->rch;
}
if(!
p)
{
cout<<"不存在"<return0;
}
x=p->data;
if(p->lch&&p->rch)
{
s=p->rch;
r=p;
while(s->lch)
{
r=s;
s=s->lch;
}
p->data=s->data;
p=s;
q=r;
}
if(p->lch)c=p->lch;
elsec=p->rch;
if(p==bt->root)bt->root=c;
elseif(p==q->lch)q->lch=c;
elseq->rch=c;
free(p);
return1;
}
intinsert(btree*btr,Etypeet)二叉搜索树的插入函数
{
btnode*r,*p=btr->root,*q;
while(p)
{
q=p;
if(etdata)p=p->lch;
elseif(et>p->data)p=p->rch;
else{
cout<<"duplicate"<return0;
}
}
r=newnode(et);
if(btr->root)
if(etdata)q->lch=r;
elseq->rch=r;
elsebtr->root=r;
return1;
}
voidmycreate(btreebt)创建二叉搜索树
{
intx=1;
Etypec;
cout<<"第一个输入的值为根的值,请输入根值"<cin>>c;
btnodebtn;
btn.lch=NULL;
btn.rch=NULL;
btn.data=c;
bt.root->data=btn.data;
bt.root->lch=btn.lch;
bt.root->rch=btn.rch;
c=getchar();
cout<<"其他节点的值"<while((c=getchar())!
='\n'&&x)
{
x=insert(&bt,c);
}
}
voidFmin(btree("c:
\\test.txt","r+");
while(!
feof(fp))
{
w[fgetc(fp)-97]++;
}
for(i=0;i<26;i++)
{
MAKEBTREE(&()
{
inti,j;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!
=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!
=j)
s2=j;
}
if(s1>s2)
{
inttemp=s1;
s1=s2;
s2=temp;
}
}
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)
{
inti;
char*cd;
intp;
intcdlen;
if(n<=1)return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
添加查看,便于调试
*printf("构造过程显示:
\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
system("pause");*
for(i=n+1;i<=m;i++)
{
Select(HT,i-1);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
添加查看,便于调试
*printf("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);
system("pause");
*
}
cd=(char*)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!
=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
elseif(HT[p].rchild==0)
{
HC[p]=(char*)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
elseif(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!
=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}
}
int=0;
intx,y,z=0;
FILE*fp;
fp=fopen("c:
\\test.txt","r+");
FILE*fp2=fopen("c:
\\test.txt","r+");
intzimu[26]={0};
repeat:
while(!
feof(fp))
{
y=fgetc(fp);
for(x=97;x<123;x++)
{
for(i=0;i{
if(y==zimu[i])
gotorepeat;
}
if(x==y)
{
n++;
zimu[z]=y;
z++;
}
}
}
HC=(HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int*)malloc(n*sizeof(int));
for(i=0;i{
w[i]=0;
}
while(!
feof(fp2))
{
w[fgetc(fp2)-97]++;
}
HuffmanCoding(HT,HC,w,n);
printf("输出编码:
\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):
%s\n",i,w[i-1],HC[i]);
return0;
}
voidmain()
{
charch;
intk;
btree*t;
btreebt,\n\n");
printf("\n===================主菜单===================");
printf("\n\n1.建立二叉搜索树");
printf("\n\n2.建立二叉树方式二");
printf("\n\n3.先序递归遍历二叉树");
printf("\n\n4.中序递归遍历二叉树");
printf("\n\n5.后序递归遍历二叉树");
printf("\n\n6.计算二叉树的高度");
printf("\n\n7.删除某个二叉树节点");
printf("\n\n8.从文件读取文本得到权值生成哈夫曼树");
printf("\n\n0.结束程序运行");
printf("\n============================================");
printf("\n请输入您的选择(6,7,8)");
scanf("%d",&k);
switch(k)
{
case1:
mycreate(bt);
t=&bt;
break;
case2:
printf("\n请输入二叉树各结点值:
");
fflush(stdin);
t->root=creat_bt2();break;调用递归建立二叉树算法
case3:
if(t)
{
printf("先序遍历二叉树:
");
preorder(t->root);
printf("\n");
}
elseprintf("二叉树为空!
\n");
break;
case4:
if(t)
{printf("中序遍历二叉树:
");
inorder(t->root);
printf("\n");
}
elseprintf("二叉树为空!
\n");
break;
case5:
if(t)
{printf("后序遍历二叉树:
");
postorder(t->root);
printf("\n");
}
elseprintf("二叉树为空!
\n");
break;
case6:
if(t)
{printf("二叉树的高度为:
%d",Depth(t->root));
printf("\n");
}
elseprintf("二叉树为空!
\n");
break;
case7:
remove(t);
break;
case8:
");
ch=getchar();
}main
五、测试数据及其结果分析
六、调试过程中的问题
创建二叉树的时候,要注意生成节点,不能只是给指针赋值,只有生成节点,二叉树才能保存下来。
递归设计的时候注意程序的结束,不然会死循环
七、课程设计总结
我设计了,哈夫曼树一段的程序,它包括了创建一个二叉搜索树,创建一个根节点,然后在写了一个插入函数,其他的节点值通过插入的方式进入程序,方便本组的同学进行程序编辑。
另外,我还根据实验要求收集资料,然后进行整合,提供给其他同学。
并于最后完成校验程序。
总之,这次学习到了很多东西,了解许多二叉树数据结构的细节,感觉到收获颇丰。