实验三 Huffman编码和译码

实验三 Huffman编码和译码

一、需求分析

1、 用户必须先从键盘输入字符和相应字符的权值，在执行相应的操作。

2、演示程序以用户和计算机的对话方式执行，即在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。 3、程序执行的命令包括：

（1）输入字符和相应的权值（2）程序运行，求解字符的编码并输出运算结果。 （3）输入一个字符串，生成码流。 4、测试数据

A 0.3 B 0.2 C 0.05 D 0.05 E 0.1 F 0.3 ABFEDEFAD 二、概要设计

构造Huffman树的方法——Huffman算法根据给定的n个权值{w1,w2,??wn}，构造n棵只有根 结点的二叉树，令初始权值为wj；在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。哈弗曼树建成后，求编码需要从叶子节点出发走一条从叶子到根的路径。译码需从走一条从根到叶子的路径。 本程序的设计思路是： 1.建立huffman编码树 2.编码指定字符串

3.译码指定码流为字符串 主函数

int main CreatHuffman Tree Huffman Coding编码 Yima 译码 结束 三、详细设计

1、定义头文件 #include #include #include #define MAX 10000 using namespace std; int n=6;

int m=2*n-1;

2、元素类型、节点类型和辅助变量 typedef struct{

char* HfmCode;/*动态分配数组，存储哈夫曼编码*/ char ch;

}code, *HuffmanCode; typedef struct {

unsigned int weight ; /* 用来存放各个结点的权值*/ char ch;

unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/ }HTNode, * HuffmanTree; 3，建立哈弗曼树

void CreatHuffmanTree(HuffmanTree *ht , int *w, char *st,int n) { /* w存放已知的n个权值，构造哈夫曼树ht */

/*由于是用数组的结构来存储树,故ht放的是数组的头指针*/ int m,i;

int s1,s2; /*在select函数中使用,用来存储最小权的结点的序号*/

*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++)

{/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].ch=st[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) {

(*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/

for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/

{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/

select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i;

(*ht)[s2].parent=i; /*设置这两个最小的权的结点的父结点为i*/ (*ht)[i].LChild=s1;

(*ht)[i].RChild=s2; /*设置这个父结点的子结点*/

(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; /*设置这个父结点权*/ }

}/*哈夫曼树建立完毕*/ 4.，select函数

void select(HuffmanTree *ht,int n, int *s1, int *s2)

{ /*ht,为树所在数组的头指针,n叶子节点数,s1,s2,返回最小的两个序号*/ int p1=MAX;

int p2=MAX; /*p1, p2用来记录最小的两个权, 要求p1

int pn2=0, i; /*pn1, pn2 用来记录这两个权的序号*/ for(i=1;i<=n;i++)

if((*ht)[i].weight

{/*如果当前结点的权比p1小,那么p2的权赋为p1的权, p1的权为当前权,同时修改n1, pn2*/

/*查找的结点要求没有父结点*/ pn2=pn1; p2=p1;

p1=(*ht)[i].weight; pn1=i; } else

if((*ht)[i].weight

{/*如果当前结点的权比p2小(由第一个if,当前权不比p1小),那么p2的权赋为当前权,同时修改pn2*/

p2=(*ht)[i].weight; pn2=i; } *s1=pn1;

*s2=pn2; /*赋值返回*/ }

5求解哈佛曼编码

void HuffmanCoding(HuffmanTree *ht, HuffmanCode *hc, int n) /*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ {

char *cd; int i;

unsigned int c; int start; int p;

*hc=(HuffmanCode)malloc((n+1)*sizeof(code)); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd[n-1]='\\0'; /*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/ {

(*hc)[i].ch=(*ht)[i].ch;

start=n-1; /*初始化编码起始指针*/

/*通过c是current的意思,表示向根结点靠拢的当前结点,序号从i开始 p是parent,始终指向c的父结点, p==0时c就是根结点*/

for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/ if( (*ht)[p].LChild == c)

cd[--start]='0'; /*左分支标0*/ else

cd[--start]='1'; /*右分支标1*/

/*for循环结点条件为 *p=0表示c是根结点了,而每循环一次又由cd[--start]倒序记录了

每一步是父结点的左或右结点,也就是形成了H编码,并放在cd中*/

(*hc)[i].HfmCode=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/ /*复制编码到对应的结点(当然是所有的需要编码的结点)*/ strcpy((*hc)[i].HfmCode,&cd[start]); }

free(cd); }

6译码指定字符串为码流

void Yima(HuffmanTree *ht, HuffmanCode *hc,char sh1[]) //将字符串转换为码流 { ofstream fout(\定义输出文件流 if(!fout) { cout<<\文件打开失败\ return; } for(int i=0;i

if(!fout) { cout<<\文件打开失败\ return; } char shs[100]; while(fin>>shs[i]) cout<

8，主函数部分

int main() {

HuffmanTree HT; HuffmanCode HC;

int *w; /*各字符的权重*/

char *st; /* 字符集,和st[i]和s[i]对应*/ float wei; /* the weight of a element;*/ char ch;//临时变量用来输入字符 char str[20];

w=(int *)malloc((n+1)*sizeof(int)); // 开辟空间 st=(char *)malloc((n+1)*sizeof(int));//开辟空间

for(int i=1;i<=n;i++) /*输入元素及其权重,存储在w,st中*/ { cout<<\ element and it's weight:\ cin>>ch;cin>>wei; st[i]=ch;w[i]=wei; } CreatHuffmanTree(&HT,w,st,n); /*构造H树*/

HuffmanCoding(&HT,&HC,n); /*根据H树,求每个字符的编码,放在HC中*/

for(i=1;i<=n;i++) /*输出编码*/

cout<>str; Yima(&HT,&HC,str); return 0; }

四、调试分析

语法错误很容易发现和弄明白，但是遇到逻辑上的错误就很难调试出来。这次同样遇到了一

本文来源：https://www.bwwdw.com/article/ktf8.html