实验四 树和二叉树的操作.docx
- 文档编号:17868105
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:17
- 大小:18.63KB
实验四 树和二叉树的操作.docx
《实验四 树和二叉树的操作.docx》由会员分享,可在线阅读,更多相关《实验四 树和二叉树的操作.docx(17页珍藏版)》请在冰点文库上搜索。
实验四树和二叉树的操作
实验四树和二叉树的操作
(2)
一、实验目的
3.熟练掌握哈夫曼树的建立和哈夫曼编码方法。
二、实现提示
哈夫曼树的理论创建过程如下:
一、构成初始集合
对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。
二、选取左右子树
在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、删除左右子树
从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步,
重复二和三两步,直到集合F中只有一棵二叉树为止。
三、实验内容
3、练习哈夫曼二叉树的建立与编码;
四、参考程序
#include
#include
#include
typedefstruct//结点的结构
{
unsignedintweight;//结点的权值
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码
HuffmanTreeHT;
HuffmanCodeHC;
intn=8;
constcharmenu[]=
"|1建立哈夫曼树|\n"
"|2查看哈夫曼编码|\n"
"|3树形输出哈夫曼树|\n"
"|4哈夫曼文件编码|\n"
"|5哈夫曼文件解码|\n"
"|6帮助|\n"
"|7退出系统|\n";
constcharhelpsabout[]=
"|主要功能:
|\n"
"|利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息的传输时间,降低|\n"
"|传输成本。
但是,这要求在发送端通过一个编码系统对待传输的数据预先编码,在接收|\n"
"|端将传来的数据进行译码(复原)。
对于双工信道,每端都要有一个完整的编/译码系|\n"
"|统。
本系统即是为这样的信息收发站写一个哈夫曼码的编/译系统。
|\n"
"||\n"
"||\n";
voidHuffmantree();
voidHuffmancode();
voidpreorder();
voidstringcopy();
intmin();
voidselect();
voiddecode();
voidencode();
voidint_huffmantree();
voidprint_end();
voidprint_title();
voidprint_menu();
voidprint_helpabout();
voidprint_huffmancode();
voidprint_tree();
//------------------先序遍历----------------------------------------------------
voidpreorder(introot,intdepth)
{
inti;
for(i=1;i<=depth;i++)
printf("");
if(depth!
=0)
printf("└");
else
printf("");
printf("%d",HT[root].weight,depth);
if(root<=n)
printf(":
%s\n",HC[root]);//依次输出哈夫曼编码
else
printf("\n");
if(HT[root].lchild!
=0)
{depth++;preorder(HT[root].lchild,depth);}
if(HT[root].rchild!
=0)
{preorder(HT[root].rchild,depth);}
}
//--------------字符串拷贝函数----------------------------------------------------
voidstringcopy(char*strDest,char*strSrc)
{
char*strDestCopy=strDest;
if(!
(strDest&&strSrc))
printf("ERROR!
");
while((*strDest++=*strSrc++)!
='\0');
}
//--------返回哈夫曼树t的前i个结点中权值最小的树的根结点序号,函数select()调用------------
intmin(HuffmanTreet,inti)
{
intj,m;
unsignedintk=0xffffffff;//k存最小权值,初值取为不小于可能的值
for(j=1;j<=i;j++)//对于前i个结点
if(t[j].weight {k=t[j].weight;//t[j]的权值赋给k m=j;//序号赋给m } t[m].parent=1;//给选中的根结点的双亲赋非零值,避免第2次查找该结点 returnm;//返回权值最小的根结点的序号 } //----在哈夫曼树t的前i个结点中选择2个权值最小的树的根结点序号,s1为其中序号(权值)较小的---- voidselect(HuffmanTreet,inti,int&s1,int&s2) { intj; s1=min(t,i);//权值最小的根结点序号 s2=min(t,i);//权值第2小的根结点序号 if(s1>s2)//s1的序号大于s2的 {//交换 j=s1; s1=s2;//s1是权值最小的2个中序号较小的 s2=j;//s2是权值最小的2个中序号较小的 } } //-------w存放n个字符的权值(均>0),构造哈夫曼树HT---------------------------------------- voidHuffmantree(int*w) { intm,i,s1,s2; HuffmanTreep; if(n<=1)//叶子结点数不大于n return; m=2*n-1;//n个叶子结点的哈夫曼树共有m个结点 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 for(p=HT+1,i=1;i<=n;++i,++p,++w)//从1号单元开始到n号单元,给叶子结点赋值 {//p的初值指向1号单元 (*p).weight=*w;//赋权值 (*p).parent=0;//双亲域为空(是根结点) (*p).lchild=0;//左右孩子为空(是叶子结点,即单结点树) (*p).rchild=0; } for(;i<=m;++i,++p)//i从n+1到m (*p).parent=0;//其余结点的双亲域初值为0 for(i=n+1;i<=m;++i)//建哈夫曼树 {//在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HT[s1].parent=HT[s2].parent=i;//i号单元是s1和s2的双亲 HT[i].lchild=s1;//i号单元的左右孩子分别是s1和s2 HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;//i号单元的权值是s1和s2的权值之和 } } //-------并求出n个字符的哈夫曼编码HC-------------------------------------------------- voidHuffmancode() { intstart; unsignedintf; inti; unsignedintc; char*cd; HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针 cd=(char*)malloc(n*sizeof(char));//分配求编码的字符数组 cd[n-1]='\0'; for(i=1;i<=n;i++)//逐个字符求哈夫曼编码 { start=n-1;//编码结束符位置 for(c=i,f=HT[i].parent;f! =0;c=f,f=HT[f].parent)//从叶子到根逆向求编码 if(HT[f].lchild==c)//c是其双亲的左孩子 cd[--start]='0';//由叶子向根赋值'0' else//c是其双亲的右孩子 cd[--start]='1';//由叶子向根赋值'1' HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 stringcopy(HC[i],&cd[start]);//从cd复制编码串到HC矩阵 } free(cd);//释放工作空间 } //---------------------译码----------------------------------------------------- voidencode() { FILE*fp1=NULL,*fp2=NULL; charinput[20]="input.txt",output[20]="output.txt"; printf("请输入输入文件名(input.txt): "); scanf("%s",input); if((fp1=fopen(input,"r"))==NULL) { printf("无此文件! "); getchar(); getchar(); return; } printf("请输入输出文件名(output.txt): "); scanf("%s",output); if((fp2=fopen(output,"w"))==NULL) { printf("不能创建文件! "); getchar(); getchar(); return; } inti,k; unsignedint*w,p,m=0,j; for(k=0;! feof(fp1);k++) { if(fgetc(fp1)=='') m++; } printf("哈夫曼编码为: "); fp1=fopen(input,"r"); w=(unsignedint*)malloc(m*sizeof(unsignedint));//动态生成存放m个权值的空间 for(j=0;j<=m-1;j++) { fscanf(fp1,"%d",w+j);//依次输入原码 } for(p=0;p { for(i=0;i if(*(w+p)==HT[i+1].weight) { fprintf(fp2,"%s",HC[i+1]); printf("%s",HC[i+1]); } } fclose(fp1); fclose(fp2); printf("\n输出完成.按任意键继续...."); getchar(); getchar(); } //-------------------------解码------------------------------------------------- voiddecode() { FILE*fp1=NULL,*fp2=NULL; charinput[20],output[20]; char*code; code=(char*)malloc(n*sizeof(char)); printf("请输入输入文件名(input.txt): "); scanf("%s",input); if((fp1=fopen(input,"r"))==NULL) { printf("无此文件! "); getchar(); getchar(); return; } printf("请输入输出文件名(output.txt): "); scanf("%s",output); if((fp2=fopen(output,"w"))==NULL) { printf("不能创建文件! "); getchar(); getchar(); return; } inti,j; printf("哈夫曼译码为: "); for(i=0;! feof(fp1);i++) { *(code+i)=fgetc(fp1); *(code+i+1)='\0'; for(j=0;j if(strcmp(code,HC[j+1])==0) { fprintf(fp2,"%d",HT[j+1].weight); printf("%d",HT[j+1].weight); i=-1; break; } } fclose(fp1); fclose(fp2); printf("\n输出完成.按任意键继续...."); getchar(); getchar(); } //---------------------初始化哈夫曼树------------------------------------------ voidint_huffmantree() { system("cls"); print_title(); int*w,i; printf("请输入权值的个数(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int));//动态生成存放n个权值的空间 printf("请依次输入%d个权值(整型): \n",n); for(i=0;i { scanf("%d",w+i); } Huffmantree(w);//根据w所存的n个权值构造哈夫曼树HT, Huffmancode();//n个哈夫曼编码存于HC print_end(); printf("哈夫曼编码为: \n"); for(i=1;i<=n;i++) printf("%5d: %s\n",*(w+i-1),HC[i]); print_end(); printf("按任意键返回..."); getchar(); getchar(); } //-----------------哈夫曼编码菜单---------------------------------- voidprint_huffmancode() { inti; system("cls"); print_title(); printf("哈夫曼编码为: \n"); for(i=1;i<=n;i++) printf("%5d: %s\n",HT[i].weight,HC[i]); print_end(); printf("按任意键返回..."); getchar(); getchar(); } //--------------帮助菜单------------------------------------------- voidprint_helpabout() { system("cls"); print_title(); printf(helpsabout); print_end(); printf("按任意键返回..."); getchar(); getchar(); } //----------------树形输出菜单-------------------------------------- voidprint_tree() { system("cls"); print_title(); printf("哈夫曼树为: \n"); preorder(2*n-1,0); print_end(); printf("按任意键返回..."); getchar(); getchar(); } //--------------------选择菜单输出------------------------------------------------- voidprint_menu() { while (1) { intselected=0; system("cls"); print_title(); printf(menu); print_end(); printf(">请选择[1~7]"); scanf("%d",&selected); if(selected<1||selected>7) { printf("错误的选择! (请输入1~7).按任意键继续...."); getchar(); getchar(); } switch(selected){ case1: int_huffmantree(); break; case2: print_huffmancode(); break; case3: print_tree(); break; case4: encode(); break; case5: decode(); break; case6: print_helpabout(); break; case7: exit(0); break; } } } voidprint_title() { printf("+=============================================================================+\n"); printf("|哈夫曼编码译码器|\n"); printf("|DesignedByOrganne|\n"); printf("+=============================================================================+\n"); } voidprint_end() { printf("+=============================================================================+\n"); } voidmain() { intw[8]={5,29,7,8,14,23,3,11}; Huffmantree(w);//根据w所存的n个权值构造哈夫曼树HT, Huffmancode();//n个哈夫曼编码存于HC system("color17"); print_title(); print_menu(); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验四 树和二叉树的操作 实验 二叉 操作