试验四二叉树的应用-哈夫曼编码试验报告

1、哈夫曼编码实验四 二叉树的应用-哈夫曼编码一、实验目的1. 在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。2. 掌握构造哈夫曼树以及哈夫曼编码的方法。、实验内容哈夫曼树和哈夫曼编码：从终端输入若干个字符，统计字符出现的频率，将字符出现的频率作为结点的 权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的 哈夫曼编码。设计要求： 哈夫曼殊和哈夫曼编码的存储表示参考教材事例 在程序中构造四个子程序为 int freqchar (char *text, HTree *t) /*统计字符出现的频率 */ int createhtree(HTree *t) /*

2、 根据字符出现的频率建立哈夫曼树 */ void codi ng(HTree *t, int head_i,char *code)/*对哈夫曼树进行编码*/ void printhtree(HTree *t,int head_i,int deep,int* path)/*中序打印树*/三、实验步骤、数据结构与核心算法的设计描述# in clude <stdio.h># in clude <malloc.h># in clude <iostream.h># in clude vconi o.h># in clude <stri ng.h>#

3、defi ne MAX_LENGTH 100typedef char *Huffma nCode;typedef struct/defi ne structure Huffma nTreeun sig ned int weight;un sig ned int pare nt,lchild,rchild;HTNode,*Huffma nTree;总5页第6页、函数调用及主函数设计程序调试及运行结果分析h hh 弋_ 口 t t t 12 3 I1AI1AI1AI1A 请请请请.fflftTEll.weight-854T2 J.weight-26 T3 J.weight=35I立的哈夫曼树如下列

4、次序；Tt2 and HT(3 create HT4, weight=61 T【4J and HTtl create HTESJ, weiQht=915合夫曼编码如下:TE1JTL2TE3Jress0 1 i 0 0 #=!;唤 分fdpfdp i TflTflTfl t fi.fifin 昌ss文 c刼 D UMIMIS t 哈哈哈y 沟也自e 点点点y "pfJiTan实验总结哈弗曼编码输入抽象数据类型，不易掌握，需要慢慢修改。 四、主要算法流程图及程序清单1、主要算法流程图：void Select(HuffmanTree HT,int i,int &s1,int &am

5、p;s2)void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode&HC,i nt *w,i nt n)2 、程序清单哈夫曼转化函数：void Select(Huffma nTree HT,i nt i,i nt & s1,i nt & s2)int j,k=1;while(HTk.pare nt!=O)k+;s仁k;for(j=1;j<=i;+j)if(HTj.pare nt=O&&HTj.weight<HTs1.weight) s1=j;k=1;while(HTk.pare nt!=O

6、|k=s1)k+;s2=k;for(j=1;j<=i;+j)if(HTj.pare nt=O&&H Tj.weight<HTs2.weight&&j!=s1) s2=j;void Huffma nCodi ng(Huffma nTree &H T,Huffma nCode&HC,i nt *w,i nt n)int m,i,s1,s2,start,c,f;Huffma nTree p;if(*=1)return;m=2* n-1;HT=(Huffma nTree)malloc(m+1)*sizeof(HTNode);for(p=HT+

7、1,i=1;i<=n;+i,+p,+w)p->weight=*w;cout«e ndlvv"HT"vvivv".weight="vvp->weight<v""p->pare nt=0;p->lchild=0;初始化哈夫曼树p->rchild=0;for(;i<=m;+i,+p)/in itial HT n+1.2* n1p->weight=0;p->pare nt=0;p->lchild=0;p->rchild=0;coutvvendlvvendlvv&

8、quot;建立的哈夫曼树如下列次序："；for(i=n+1;i<=m;+i)Select(HT,i-1,s1,s2);s1 is the least, s2 is the seco nd leastHTs1.pare nt=i; HTs2.pare nt=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;cout«e ndlvv"HT"vvs1<v" a nd HT"<<s2<<" create" c

9、out«" HT"<<i<<", weight="«HTi.weight;HC=(Huffma nCode)malloc( n+1)*sizeof(char *);char *cd;cd=(char *)malloc( n*sizeof(char);cd n-1='0'cout«endl«endlvv"哈夫曼编码如下:"<<endl;for(i=1;i<=n;+i)start=n-1;for(c=i,f=HTi.pare nt;f!=0;

10、c=f,f=HTf.pare nt)if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc( n-start)*sizeof(char);strcpy(HCi, &cdstart);printf("nHT%d节点的哈夫曼编码是：s",i,HCi);coutvve ndl;free(cd);主函数：void mai n()/ma in() fun ctio nHuffma nTree HT;Huffma nCode HC;int n,i;int *w,WMAX_LENGTH;coutvv"请输入哈夫曼树的元素个数："；cin>&