哈夫曼编码实验报告(2).doc
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
实验一 哈夫曼编码 一、实验目的 1. 掌握哈夫曼编码原理; 2. 熟练掌握哈夫曼树的生成方法; 3、理解数据编码压缩和译码输出编码的实现。 二、实验要求 实现哈夫曼编码和译码的生成算法。 三、实验内容 先统计要压缩编码的文件中的字符字母出现的次数,按字符字母和空格出现的概率对 其进行哈夫曼编码,然后读入要编码的文件,编码后存入另一个文件;接着再调出编码 后的文件,并对其进行译码输出,最后存入另一个文件中。 五、实验原理 1、哈夫曼树的定义:假设有n个权值,试构造一颗有n个叶子节点的二叉树,每个叶子带 权值为wi,其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树; 2、哈夫曼树的构造: weight为输入的频率数组,把其中的值赋给依次建立的HT Node对象中的data属性,即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序,每次从data取出两 个最小和此次小的HT Node,将他们的data相加,构造出新的HTNode作为他们的父节点,指针parent,leftch ild,rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一 棵哈夫曼树。 通过已经构造出的哈夫曼树,自底向上,由频率节点开始向上寻找parent,直到parent为 树的顶点为止。这样,根据每次向上搜索后,原节点为父节点的左孩子还是右孩子,来 记录1或0,这样,每个频率都会有一个01编码与之唯一对应,并且任何编码没有前部分 是同其他完整编码一样的。 六、实验流程 初始化,统计文本文件中各字符的个数作为权值,生成哈夫曼树; 根据符号概率的大小按由大到小顺序对符号进行排序; 把概率最小的两个符号组成一个节点; 重复步骤(2)(3),直到概率和为1; 从根节点开始到相应于每个符号的"树叶",概率大的标"0",概率小的标"1"; 从根节点开始,对符号进行编码; 译码时流程逆向进行,从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。 七、实验程序 #include<iostream> #include<fstream> #include<iomanip> #include<vector> using namespace std; typedef struct //节点结构 { char data; //记录字符值 long int weight; //记录字符权重 unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表 void Select(HuffmanTree &HT,int i,int &s1,int &s2) //在HT[1...t]中选择parent不为0且权值最小的两个结点,其序号分别为s1和s2 { s1=0;s2=0; int n1=30000,n2=30000; for(int k=1;k<=i;k++) { if(HT[k].parent==0) { if(HT[k].weight<n1) { n2=n1; n1=HT[k].weight; s2=s1; s1=k; } else if(HT[k].weight<n2) { n2=HT[k].weight; s2=k; } } } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)//将要编码的字符串存入空树中 { ifstream fin1("zifu.txt"); ifstream fin2("weight.txt"); if(n<=1)return; int m=2*n-1; int i; HT=new HTNode[m+1]; char *zifu; int *weight; zifu= new char[n+1]; weight=new int[n+1]; for(i=1;i<=n;i++)//将待编码的字符放在zifu数组中 { char ch; ch=fin1.get(); zifu[i]=ch; } for(i=1;i<=n;i++)//将带编码字符对应的权值放在weight数组中 { fin2>>weight[i]; } for( i=1;i<=n;i++) { HT[i].data=zifu[i]; HT[i].weight=weight[i]; } for(i=n+1;i<=m;i++) { HT[i].data='@'; } for(i=1;i<=m;i++) { HT[i].parent=HT[i].lchild=HT[i].rchild=0; } for(i=n
- 粉丝: 167
- 资源: 3万+
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
- 1
- 2
前往页