资源描述：
《数据结构实验报告(哈夫曼树).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.数据结构实验报告实验题目：Huffman编码与解码姓名：学号：院系：word范文.实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完成以下功能：1.输入电文串2.统计电文串中各个字符及其出现的次数3.构造哈弗曼树4.进行哈弗曼编码5.将电文翻译成比特流并打印出来6.将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。存储结构：使用结构体来对数据进行存储：typedefstruct
2、{intweight;intparent,lc,rc;}HTNode,*HuffmanTree;typedefstructLNode{char*elem;intstacksize;inttop;}SqStack;在main函数里面定义一个哈弗曼树并实现上述各种功能。程序结构的描述：本次实验一共构造了10个函数：1.voidHuffTree(HuffmanTree&HT,intn[],intmun);此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。2.voidSelect(Huf
3、fmanTree&HT,intn,inti,int&s1,int&s2);此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1,s2.3.voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn);此函数从哈弗曼树HT上求得n个叶子结点的哈弗曼编码并存入数组HC中。word范文.3.voidCoding(HuffmanTreeHT,char**HC,introot,SqStack&S)；此函数用于哈弗曼编码，先序遍历
4、哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。5.voidInitStack(SqStack&S);此函数用于初始化一个栈。6.voidPop(SqStack&S,chare);此函数为出栈操作。7.voidPush(SqStack&S,chare);此函数为进栈操作。8.intStackLength(SqStackS);此函数用于求栈长，返回一个int型的值。9.intFind(chara,chars[],i
5、ntnum);此函数用于查找字符a在电文串中的位置。10.intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn);此函数用于将比特流还原成电文。调试分析：输入任意一个字符串，如输入welcometoustc:运行结果如下：word范文.按照提示输入任意一个或多个哈弗曼编码，如输入11111110101：结果正确。若输入一个11111：结果正确。实验完成！实验体会和收获：本次实验提高了对哈弗曼树的认识，同时加深了对二叉树
6、的理解，在栈的运用上更加熟练，对数组的应用也有了提高。源代码：#include#include#include#includetypedefstruct{intweight;intparent,lc,rc;}HTNode,*HuffmanTree;typedefstructLNode{word范文.char*elem;intstacksize;inttop;}SqStack;#definesize20voidHuffTre
7、e(HuffmanTree&HT,intn[],intmun);voidSelect(HuffmanTree&HT,intn,inti,int&s1,int&s2);voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn);voidCoding(HuffmanTreeHT,char**HC,introot,SqStack&S);voidInitStack(SqStack&S);voidPop(SqStack&S,chare);voidPush(SqStack&S
8、,chare);intStackLength(SqStackS);intFind(chara,chars[],intnum);intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn);intmain(){inti=0,n[size]={0},j=0,k=1,num=0;charstring[size]={0},m[size]={0},a[size]={0},b[size]={0};char
