四哈夫曼树及其的应用

《四哈夫曼树及其的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、网络092李雨山200900824225实验四哈夫曼树及其的应用一、实验目的1．在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。2.掌握构造哈夫曼树以及哈夫曼编码的方法。3、熟练掌握哈夫曼树（最优二叉树）特征及其应用二、实验内容题目一、哈夫曼树和哈夫曼编码：从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。设计要求：⑴哈夫曼殊和哈夫曼编码的存储表示参考教材事例⑵在程序中构造四个子程序为①intfreqchar(char*st);/*统计字

2、符出现的频率*/②voidCreateHuffmanTree(HuffmanTree&,int*,int);//生成哈夫曼树③voidHuffmanCoding(HuffmanTree,HuffmanCode&,int);//对哈夫曼树进行编码④voidPrintHuffmanCode(HuffmanCode,int*,int,char*);//显示哈夫曼编码⑤voidSelect(HuffmanTree,int,int&,int&);//在数组中寻找权值最小的两个结点三、实验步骤㈠、数据结构与核心算法的设计描述1.重点：统计字符出现的频率并作为权值intfreqch

3、ar(char*st)/*统计字符出现的频率*/{intn=0;//统计字符的种类memset(num,0,sizeof(num));for(inti=0;i

4、fmanTreep;if(n<=1)return;m=2*n-1;//n个叶子结点的哈夫曼树，有2*n-1个结点HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟2*n各结点空间for(p=HT+1,i=1;i<=n;++i,++p,++w)//进行初始化{p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;+

5、+i)//建哈夫曼树{Select(HT,i-1,s1,s2);//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2HT[s1].parent=i;HT[s2].parent=i;网络092李雨山200900824225//修改s1和s2结点的父指针parentHT[i].lchild=s1;HT[i].rchild=s2;//修改i结点的左右孩子指针HT[i].weight=HT[s1].weight+HT[s2].weight;//修改权值}}1.哈夫曼编码voidHuffmanCoding(HuffmanTree

6、HT,HuffmanCode&HC,intn){//将有n个叶子结点的哈夫曼树HT进行编码，所编的码存放在HC中//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码inti,c,f,start;char*cd;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个编码的头指针向量cd=(char*)malloc(n*sizeof(char));//开辟一个求编码的工作空间cd[n-1]='';//编码结束符for(i=1;i<=n;++i)//逐个地求哈夫曼编码{start=n-1;//编码结束位置for(c=i,f=H

7、T[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';//若是左孩子编为'0'elsecd[--start]='1';//若是右孩子编为'1'HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个编码分配空间strcpy(HC[i],&cd[start]);//将编码从cd复制到HC中}free(cd);//释放工作空间}2.显示有n个叶子结点的哈夫曼树的编码表voidPrintHuffmanC