用赫夫曼树进行字符串的编码

数据结构实验报告

实验三树的应用

一、实验题目：

树的应用——哈夫曼编码

二、实验内容：

利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。

从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：

1．输出存放哈夫曼树的数组HT的初态和终态；

2．输出每个字符的哈夫曼编码；

3．输入由上述若干字符组成的字符串，对电文进行编码并输出；

三、程序源代码：

#include

#include

#include

#define N 8

#define M 4

typedef struct{

char data;

char *code;

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树

typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *data,int *w,int n,char *str)

{

//存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n各字符的赫夫曼编码HC

if(n<=1) return;

int m=2*n-1; //总节点数

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用

HuffmanTree p;

int i,j;

printf("\n");

printf("------------------------------\n");

printf("存放哈夫曼树的数组HT的初态:\n");

printf("叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:\n");

for(p=HT+1,i=1;i<=n;++i,++p,++data,++w)

{

p->data=*data;

p->parent=p->lchild=p->rchild=0;

p->weight=*w;

p->code=(char *)malloc(n*sizeof(char));

printf("%c %2d %2d %2d %2d\n",p->data,p->parent,p->weight,p->lchild,p->rchild); }

for(;i<=m;++p,++i)

{

p->parent=p->lchild=p->rchild=p->weight=0;

p->data=NULL;

p->code=(char *)malloc(n*sizeof(char));

printf(" %2d %2d %2d %2d\n",p->parent,p->weight,p->lchild,p->rchild);

}

for(i=n+1;i<=m;++i){//建赫夫曼树

//在HT[1--i-1]选择parent为0且weight最小的两个节点，其序号分别为s1和s2 unsigned int m1=32767;

unsigned int m2=32767;//m1,m2为最小和次小权值

int s1=0;

int s2=0;//s1,s2为最小和次小节点的序号

for(int k=1;k<=i-1;k++)

{

if((HT[k].parent==0)&&(HT[k].weight

{

m2=m1;

s2=s1;

m1=HT[k].weight;

s1=k;

}

else if((HT[k].parent==0)&&(HT[k].weight

{

m2=HT[k].weight;

s2=k;

}

}

HT[s1].parent=i;HT[s2].parent=i;

HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}

printf("\n");

printf("------------------------------\n");

printf("存放哈夫曼树的数组HT的终态:\n");

printf("叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:\n");

for(p=HT+1,i=1;i<=n;++p,++i)

printf("%c %2d %2d %2d %2d\n",p->data,p->parent,p->weight,p->lchild,p->rchild); for(;i<=m;++p,++i)

printf(" %2d %2d %2d %2d\n",p->parent,p->weight,p->lchild,p->rchild);

//----从叶子到根逆向求每个字符的赫夫曼编码----

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量char *cd;

cd=(char *)malloc(n*sizeof(char)); //分配求编码的工作空间

cd[n-1]='\0'; //编码结束符

int start;

unsigned int f,c;

printf("\n");

printf("------------------------------\n");

printf("每个字符的哈夫曼编码:\n");

for(p=HT+1,i=1;i<=n;++i,++p) //逐个字符求赫夫曼编码

{

start=n-1;//编码结束符位置

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码

if(HT[f].lchild==c) cd[--start]='0';

else cd[--start]='1';

HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

char *R=&cd[start];

strcpy(HC[i],&cd[start]);

strcpy(p->code,R);

printf("%c ",p->data);

printf("%s",HC[i]);

printf("\n");

}

printf("输出字符串的赫夫曼编码:\n");

for(i=0;i

{

for(p=HT+1,j=0;j

if(str[i]==p->data)

printf("%s",p->code);

}

free(cd);//释放工作空间

}

int main()

{

char data[N],str[M];

int p[N],i;

for(i=0;i

{

printf("输入第%d个字符及频率：\n",i+1);

scanf("%c",&data[i]);

scanf("%d",&p[i]);

getchar();

}

printf("输入字符串：\n");

for(i=0;i

scanf("%c",&str[i]);

HuffmanTree HT;

HuffmanCode HC;

HuffmanCoding(HT,HC,data,p,N,str);

printf("\n");

return 0;

}

四、测试结果：

五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）

注：内容一律使用宋体五号字，单倍行间距

本次实验中第三个问题没做出来，我本来想出了一种方法，但是总是出错，我的方法是在结构体中加一个编码域，在形参中加一个字符指针，它的值由主函数中输入的字符串传递过来的。将得出的编码复制

到编码域中，然后一遍一遍的访问HT数组，如果HT数组中data域中的字符与由主函数中传递过来的字符相等的话，输出对应的编码域中的编码，字符串中有几个字符，访问HT数组访问几次。但是总是出错，所以没做。后来通过仔细分析，将错误的地方改了过来，程序正确运行出来了。

哈夫曼编码算法实现完整版

实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include #include #include #include typedef struct{ char data; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * * HuffmanCode; void Select(HuffmanTree &HT,int n,int m) {HuffmanTree p=HT; int tmp; for(int j=n+1;j<=m;j++) {int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x<=j-1;x++) { if(p[x].parent==0&&p[x].weights2) //将选出的两个节点中的序号较小的始终赋给s1 { tmp=s1; s1=s2; s2=tmp;} p[s1].parent=j;

哈夫曼树的编码和译码

#include"stdafx.h" #include"stdio.h" #include"conio.h" #include #include #include using namespace std; #define maxbit 100 #define Maxvalue 2000//最大权值整数常量#define Maxleaf 100//最大叶子结点数 #define size 300//0、串数组的长度 static int n;//实际的叶子结点数 struct HNodeType { int weight; int parent; int lchild; int rchild; int ceng;//结点相应的层数 char ch;//各结点对应的字符 }; struct HCodeType { int bit[maxbit];//存放编码的数组 int start;//编码在数组中的开始位置}; static HNodeType *HuffNode;//定义静态指针HNodeType *init()//初始化静态链表 { HuffNode=new HNodeType[2*n-1]; for(int i=0;i<2*n-1;i++) { HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; HuffNode[i].ceng=-1; HuffNode[i].ch='0'; } return HuffNode; }

赫夫曼树的编码译码

#include #include #include typedef struct{ int weight; int lchild,rchild,parent; }Htnode,*HuffmanTree; //哈弗曼树节点类型，动态分配数组存储哈弗曼树typedef char * * Huffmancode; //动态分配数组存储哈弗曼编码表 void bianma(Huffmancode ch,int n); //编码 void yima(Htnode *HT, int n); //译码 int createtree(Htnode *&HT, Huffmancode &HC,int *weight,int n); //构建哈弗曼树void select(Htnode *HT,int n,int *s1,int *s2); //求节点中两个最小数 /*----------main 函数----------*/ int main (void) { Htnode *HT; int n=4,a; //叶子节点4个 int weight[5]={18,7,5,2,4}; //weight[0]为权值之和 char ch[4]={'A','B','C','D'},c; char **HC; createtree(HT, HC,weight, n); while(a!=0){ //a=0时退出,so是按0键退出,或者改成a!=3 printf("***编码请按1，译码请按2，退出请按0***"); printf("请输入您的选择:\n"); scanf("%d%c",&a,&c); switch(a){ case 1: bianma(HC,n); break; case 2: yima(HT,2*n); break; case 0: break; default:printf("输入错误!");break; } } return 0; }

实验六_赫夫曼编码

实验名称：实验六费诺编码 一、实验目的： 加深对赫夫曼编码的理解及其具体的实现过程 二、实验内容与原理： 1.完成赫夫曼的编码 2.计算平均码长及编码效率 三、实验步骤 根据赫夫曼编码的步骤完成该编码 四、实验数据及结果分析(可附程序运行截图) 编码的结果：

五、代码附录 %哈夫曼编码的MATLAB实现（基于0、1编码）：clc; clear; A=[0.25 0.25 0.2 0.15 0.1 0.05];%信源消息的概率序列A=fliplr(sort(A));%按降序排列 T=A; [m,n]=size(A); B=zeros(n,n-1);%空的编码表4*5（矩阵） for i=1:n B(i,1)=T(i);%生成编码表的第一列 end r=B(i,1)+B(i-1,1);%最后两个元素相加 T(n-1)=r; T(n)=0; T=fliplr(sort(T)); t=n-1;%t=4 for j=2:n-1%生成编码表的其他各列 for i=1:t

B(i,j)=T(i); end K=find(T==r);%函数用于返回所需要元素的所在位置 B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在%该列的位置 r=(B(t-1,j)+B(t,j));%最后两个元素相加 T(t-1)=r; T(t)=0; T=fliplr(sort(T)); t=t-1; end B;%输出编码表 END1=sym('[0,1]');%给最后一列的元素编码 END=END1; t=3; d=1; for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码 for i=1:t-2 if i>1 & B(i,j)==B(i-1,j) d=d+1; else d=1; end B(B(n,j+1),j+1)=-1; temp=B(:,j+1); x=find(temp==B(i,j)); END(i)=END1(x(d)); end y=B(n,j+1); END(t-1)=[char(END1(y)),'0']; END(t)=[char(END1(y)),'1']; t=t+1; END1=END; end A%排序后的原概率序列 END%编码结果 for i=1:n [a,b]=size(char(END(i))); L(i)=b; end disp('平均码长：；'); avlen=sum(L.*A)%平均码长 H1=log2(A); H=-A*(H1')%熵

哈夫曼树及编码综合实验报告

《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构B 实验学期 2017 至 2018 学年第一学期学生所在院部计算机学院 年级 2016 专业班级信管B162 学生姓名学号 成绩评定： 1、工作量： A（），B（），C（），D（）,F( ) 2、难易度：A（），B（），C（），D（）,F( ) 3、答辩情况： 基本操作：A（），B（），C（），D（）,F( ) 代码理解：A（），B（），C（），D（）,F( ) 4、报告规范度：A（），B（），C（），D（）,F( ) 5、学习态度：A（），B（），C（），D（）,F( )总评成绩:_________________________________ 指导教师: 兰芸

用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。 微型计算机、Windows 7操作系统、Visual C++6.0软件 输入的字符创建Huffman树，并输出各字符对应的哈夫曼编码。 五.系统设计 输入字符的个数和各个字符以及权值，将每个字符的出现频率作为叶子结点构建Huffman树，规定哈夫曼树的左分支为0，右分支为1，则从根结点到每个叶子结点所经过的分支对应的0和1组成的序列便为该结点对应字符的哈夫曼编码。 流程图如下 1.输入哈夫曼字数及相应权值

相应代码 int main() { HuffmanTree HTree; HuffmanCode HCode; int *w, i; int n,wei; //编码个数及权值 printf("请输入需要哈夫曼编码的字符个数:"); scanf("%d",&n); w=(int*)malloc((n+1)*sizeof(int)); for(i=1; i<=n;i++) { printf("请输入第%d字符的权值:",i); fflush(stdin); scanf("%d",&wei); w[i]=wei; } HuffmanCoding(&HTree,&HCode,w,n); return 1; } 2.输出HT初态（每个字符的权值）

哈夫曼树编码译码源代码及测试文件

测试文件内容 Dear Editor: There is something to tell to you. I'm a middle school student.My name is Li Ming.Final exams are coming.Everyone is preparing for this.But there is some important problem during the review. Most of students often stay up late for the review.As the result,they always take a nap in the class and they can't keep the studying normal. I think we should be a reasonable time.The more relaxing we get,the better we will be.Brothers do not misuse wood workers I hope all the students can access to ideal scores. I'm expecting your answer and suggestion. Li Ming. 源代码 #include #include #include /* 哈夫曼树*/ struct huffmantree { char ch; /* 字符*/ int weight; /* 权值*/ int parent; /* 父亲*/ int lchild; /* 左孩子*/ int rchild; /* 右孩子*/ char *code; /* 编码*/ }; /* 字符-权值*/ struct char_weight { char ch; int weight; }; /* 带大小的字符-权值*/ struct size_cw { int size; struct char_weight *cw; };

哈夫曼编码和译码系统

通达学院 算法与数据结构程序设计 题目：哈夫曼编码和译码系统 专业 学生姓名 班级学号 指导教师 指导单位 日期

教师评语 同学出勤率(满勤、较高、一般，较低)，学习态度(端正、较端正、一般、较差)，程序设计基础（好、较好、一般、较差），演示程序(已经、没有)达到了基本要求，算法设计（好、较好、一般），界面友好程度（好、较好、一般），答辩过程中回答问题（准确、较准确、错误率较高），撰写报告格式(规范、一般)、内容（丰满、简单）、表述(清晰、一般、不清楚)，（圆满、较好、基本)完成了课题任务。 教师签名： 年月日 成绩评定 备注

一、题目要求： 题 目 ：哈夫曼编码和译码系统 基本要求： (1) 能输入字符集和各字符频度建立哈夫曼树； (2) 产生各字符的哈夫曼编码，并进行解码。 提高要求： (1) 能设计出简捷易操作的窗口界面； (2) 编码和译码存储在文件中。 二、需求分析： 2.1基本思想 根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是: (1) 初始化:由给定的n 个权值{w 1, w 2,…, w n }构造n 棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T 1,T 2,…,T n }; (2) 选取与合并:在F 中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和; (3) 删除与加入:在F 中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F 中; (4) 重复(2)、(3)两步,当集合F 中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树. 2.2存储结构 在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n 个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图所示. 图 哈夫曼树的结点结构 其中: weight parent lchild rchild i nf

哈夫曼树编码

哈夫曼树编码/译码系统 【实验内容及要求】 (1) 从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，将它存于文件hfmtree 中。并将建立好的哈夫曼树以树或凹入法形式输出;对每个字符进行编码并且输出。 (2) 利用已建好的哈夫曼编码文件hfmtree ，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。 #include #include #include #include #define num 27 //字母数 #define nod 51 //总的树结点的个数 #define len 15 //编码最大长度 class Node { public: char data; int weight; int parent; int lchild; int rchild; }; int main() { ofstream out("test6.txt"); char ch[27]; for(int nn=0;nn<27;nn++) { ch[nn]=65+nn; out<

int static hc[num][len]; //用于存储编码 int m,n; //初始化数组 for(i=0;itwo&&nodes[j].weight<=one) { one=nodes[j].weight; a=j; } } }//for语句得到parent=-1(即没父结点)且weight最小的两个结点nodes[a].parent=i;

哈夫曼编码的方法

1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律

使用缺省的哈夫曼编码表有

解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等;

表达式求值 哈夫曼树和哈夫曼编码(数据结构程序设计)

课程设计 （数据结构） 课程设计任务书及成绩评定 课题名称表达式求值哈夫曼树和哈夫曼编码 Ⅰ、题目的目的和要求： 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。 （1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 Ⅱ、设计进度及完成情况

Ⅲ、主要参考文献及资料 [1] 严蔚敏数据结构（C语言版）清华大学出版社 1999 [2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999 [3] 谭浩强 C语言程序设计清华大学出版社 [4] 与所用编程环境相配套的C语言或C++相关的资料 目录 第一章概述 (1) 第二章系统分析 (2)

第三章概要设计 (3) 第四章详细设计及实现代码 (5) 第五章调试过程中的问题及系统测试情况 (9) 第六章结束语 (10) 参考文献 (11)

第一章概述 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。 功能：表达式求值以栈为存储结构，实现输入的表达式的求值； 哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。 利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用键盘，输入各个顶点，通过程序构造最优二叉树以及为此编码。

哈夫曼编码与译码

一、设计思想 程序要求： 利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。 实现方法： 输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算权值的函数（jsquanzhi()）进行字符统计，统计出现的字符种数以及每种字符出现的次数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。 重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。

哈夫曼编码

#include #include #include #define MAX 99999 #define N 27 //定义最多节点个数 #define M 2*N-1 //中间节点个数 typedef struct { int weight; int parent; int lchild; int rchild; }HTNode,*HuffmanTree[M+1]; //因为零号单元不适用 typedef char *HuffmanCode[N+1]; HuffmanCode co; //创建全局变量用于存储HuffmanCode char CH[N]; int weight[N]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1}; HuffmanTreeht; char word[30]; //全局变量用于储存键入的内容 void Init_CH() { int i; CH[26]=''; CH[0]='A'; for(i=1;i<26;i++) CH[i]='A'+i; for(i=0;i<27;i++) printf("%c",CH[i]); } void select(int *sr,int *sl,int n) { int i,point; point=MAX; for(i=0;i

哈夫曼编码证明

哈夫曼编码 一、哈夫曼编码的过程 提到哈夫曼编码，我们就不得不提起前缀码，前缀码的定义为：对于任意元素集合C的编码，C中任意一个元素的编码都不能成为C中其他元素编码的前缀。这一点对于编码是很容易理解的，因为如果不满足定义，我们在进行解码的时候就会出现歧义，例如下面的例1。 从例1中我们可以看出，如果我们在编码时不是前缀码，我们在解码时就会得出不同的解码，这是我们不希望看到的结果，因此我们在编码的时候通常是希望能够进行前缀码编码。那么如何得到前缀码呢？我们可以通过二叉树实现，使用二叉树的叶子结点来表示不同元素的编码，因为任意一个叶子结点后面不可能再链接其他叶子结点，所以一定能够满足前缀码的定义，即可以使用二叉树来表示前缀码。 既然我们已经发现使用二叉树可以用来进行编码，得到的编码一定是前缀码，那么使用二叉树编码是唯一的吗？其实并不然，我们通过控制二叉树的左右延伸，可以得到任意的0、1编码，例如我们给出任意一个前缀码，我们都可以使用二叉树表示。我们对ABCD重新进行编码，进而我们又能够得到例三中的二叉树编码形式。既然我们通过二叉树可以得到任意一种前缀码，那么他们之间又有什么不同呢？我们通过比较例2和例3试试来发现一些不 表1 我们根据表1进行比较，可以发现，他们对于不同元素的编码是不同的，特别是长度不

同。如果我们从存储角度来看，我们当然希望相同的A BCDA…元素集合尽量短，这样可以节省空间，这是与不同的编码方式有着很大的关系的，如果我们给出一个字符串：ABCD ，然后使用例2和例3中两种编码方式，这会发现例1：00011011（共占8位），例2：000001011（共占9位），那么就是例1更占有优势，但是我们也一定发现了，这里ABCD 都是仅仅出现了一次，所以这是不是也和出现频率有关呢？我们再给出一个字符串：ABCDDD ，然后使用例2和例3中两种编码方式，这会发现例1：000110111111（共占12位），例2：00000101111（共占11位），这时换成例2的编码方式更占有优势了。这时我们发现编码方式的选择是和元素出现的频率有很大关系的，那么还和其他因素有关系吗？我们发现我们也只能看出不同字符出现的频率，所以就只能从频率下手来研究编码方式的选择了，而最优前缀码就是哈夫曼编码。 步进行的，然后我们再来讨论其产生的编码为什么就能够时最优的呢？首先我们要先引入几个概念： f ：频率 d: 元素编码长度(结点的深度) B: 目标集合的位数=∑ f （X i ）d （X i ）n k=1 其实这里B 就是用来表示集合全部元素所占的位数，例如我们以ABCDDD 为例，我们使用例3中的编码方式，可以得知：f （A ）= 1，d （A ）= 3, f （B ）= 1，d （B ）= 3, f （C ）= 1，d （C ）= 2, f （D ）= 3，d （D ）= 1,那么我们按照公式B = 1*3+1*3+1*2+3*1 =11。B 反应的就是编码的好坏了，对于同一个集合，其B 越小，其所占的位数就越小，这是反映编码好坏的一个重要标志，我们编码的目标也是尽可能的使B 小。 那么关键来了，怎么最小呢？哈夫曼告诉我们这样一种方式，分为以下几个步骤 1、 将集合C 中的所有元素进行频率统计，得到频率统计表 2、 将频率最小的两个元素X i 、X j 拿出来，组成一棵二叉树的左右孩子，同时将其双亲 结点的频率定为：f(X i )+ f(X j )。然后将双亲结点作为新的结点，加入频率表中，X i 、X j 从频率表中去除。 3、 重复2步骤直到频率表中只剩下最后一个。

用赫夫曼树进行字符串的编码

数据结构实验报告 实验三树的应用 一、实验题目： 树的应用——哈夫曼编码 二、实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求： 1．输出存放哈夫曼树的数组HT的初态和终态； 2．输出每个字符的哈夫曼编码； 3．输入由上述若干字符组成的字符串，对电文进行编码并输出； 三、程序源代码： #include #include #include #define N 8 #define M 4 typedef struct{ char data; char *code; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *data,int *w,int n,char *str) { //存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n各字符的赫夫曼编码HC if(n<=1) return; int m=2*n-1; //总节点数 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 HuffmanTree p;

Matlab函数实现哈夫曼编码算法讲解

编写Matlab函数实现哈夫曼编码的算法一、设计目的和意义 在当今信息化时代，数字信号充斥着各个角落。在数字信号的处理和传输中，信源编码是首先遇到的问题，一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真地编码，如何使编码的效率最高，成为了大家研究的对象。 哈夫曼编码就是其中的一种，哈夫曼编码是一种变长的编码方案。它由最优二叉树既哈夫曼树得到编码，码元内容为到根结点的路径中与父结点的左右子树的标识。所以哈夫曼在编码在数字通信中有着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。 二、设计原理 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 而哈夫曼编码的第一步工作就是构造哈夫曼树。哈夫曼二叉树的构造方法原则如下，假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n 个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的 左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈 夫曼树。 具体过程如下图1产所示：（例） 图1 哈夫曼树构建过程 哈夫曼树构造成功后，就可以根据哈夫曼树对信源符号进行哈夫曼编码。具体过程为先找到要编码符号在哈夫曼树中的位置，然后求该叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1，最后的表示路径的01编码既为该符号的哈夫曼编码。可以知道，一个符号在哈夫曼树中的不同位置就有不同的编码。而且，不同符号的编码长度也可能不一样，它由该结点到父结点的路径长度决定，路径越长编码也就越长，这正是哈夫曼编码的优势和特点所在。它以各符号出现的概率大小将各符号的编码区分开。 例如对上例图中“1”的编码为“100”，“3”的编码为“101”，“5” 的编码为“11”。 对于一个信源消息的熵可以以下公式(1)求得： (1) 其中H(x)表示信源的总信息量，既为信源的熵。p()为信源中一特定符号出现的概率。 三、详细设计步骤

哈夫曼树编码实验报告

、 数据结构课程设计 报告 题目：哈夫曼编码/译码 学院数学与信息科学学院 学科门类理科 专业数学类 学号2013433033 姓名田娟 2014年12 月30日

目录 一、需求分析 1．程序的功能 (3) 2．输入输出的要求 (3) 3．测试数据 (3) 二、概要设计 1．本程序所用的抽象数据类型的定义 (3) 2．主程序模块 (3) 3．主模块的流程及各子模块的主要功能 (4) 4．模块之间的层次关系 (4) 三、详细设计 1．采用c语言定义相关的数据类型 (4) 2. 伪码算法 (5) 四、调试分析 1．调试中遇到的问题及对问题的解决方法 (15) 五、使用说明及测试结果 1.建立哈夫曼树，输入叶子结点个数，权值，字符集 (15) 2.编码 (15) 3.译码 (16) 4.显示码文 (16) 5.显示哈夫曼树 (16) 六、源程序

一、需求分析 1．程序的功能； 哈夫曼编码是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压缩的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接收端将传来的数据（密文）进行译码。 2．输入输出的要求；： 2.1．构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。 2.2编码：利用已构造的哈夫曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。 2.3．译码：将“密文”文件中的0、1代码序列进行译码。 2.4．打印“密文”文件：将文件以紧凑格式显示在终端上，每行30个代码；同时，将此字符形式的编码文件保存。 2.5．打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。 3．测试数据。 3.1.令叶子结点个数N为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。 3.2.请自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。 二、概要设计 1．本程序所用的抽象数据类型的定义； class HuffmanTree //哈夫曼树 { private: HuffmanNode *Node; //Node[]存放哈夫曼树 int LeafNum; //哈夫曼树的叶子个数，也是源码个数 2.主程序模块 main() 2.2 建立哈夫曼树函数 // 函数功能：建立哈夫曼树 void HuffmanTree::CreateHuffmanTree() 2.3 函数功能：为哈夫曼树编码

哈夫曼编码步骤

哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/ #include #include #define MAXBIT 100 #define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2 -1 typedef struct { int bit[MAXBIT]; int start;} HCodeType; /* 编码结构体*/ typedef struct{ int weight; int parent; int lchild; int rchild; int value;} HNodeType; /* 结点结构体*/ /* 构造一颗哈夫曼树*/ void HuffmanTree (HNodeType HuffNode[MAXNODE], int n){ /* i、j：循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼树数组HuffNode[] 中的结点*/ for (i=0; i<2*n-1; i++) { HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1;

数据结构课程设计 哈夫曼树及编码

HUFFMAN树及编码 1.需求分析 随机输入一篇英文文章（或读一个TXT文件），生成并显示HUFFMAN树，输出每个字母的HUFFMAN编码，判断ASCII编码与HUFFMAN编码对本篇报文长度节省效果。 (a) 输入的形式为键盘随机输入，输入的字符串长度在10000以内； (b) 输出HUFFMAN树的存储结构； (c) 程序功能为输入英文文章中每个字母的HUFFMAN编码，以及与ASCLL 码编码长度的比较结果； (d) 测试数据：正确的输入一篇英文文章，会输出各个字母的HUFFMAN编码。错误的输入即其输出输入错误。 2. 概要设计 首先统计英文文章中各个字母的个数作为权值，再统计出现的字母的个数，以决定所构造赫夫曼树的节点个数，之后便开始构造赫夫曼树，再构造每个节点的哈夫曼编码。 所设计的抽象数据类型如下： typedef struct { unsigned int weight; //权值 unsigned int parent, lchild, rchild; //双亲，左孩子，右孩子} HTNode, * HuffmanTree; typedef char * * HuffmanCode; 所设计的函数如下： int min(HuffmanTree HT, int i) 找出所有权值中最小的那个。 void Select(HuffmanTree HT, int i, int &s1, int &s2) 找出每次最小的两个权值最小的权值。 Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) 构造赫夫曼树并构造每个字母的赫夫曼编码。 void PrintHT(HuffmanTree HT, int n) 输出赫夫曼树的存储结构。 3. 详细设计 int min(HuffmanTree HT, int i) {int j, flag = 1; unsigned int k = 10000; for(j = 1; j <= i; j++) { if(HT[j].weight < k && HT[j].parent == 0) { k = HT[j].weight, flag = j; }//if } HT[flag].parent = 1; return flag;

哈夫曼编码的分析与实现

吉林建筑大学 电气与计算机学院 信息理论与编码课程设计报告 设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程131 学生姓名： 学号： 指导教师： 设计时间：2016.11.21－2016.12.2

第1章 概述 1.1设计的作用、目的 通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。 通过课程设计各环节的实践，应达到如下要求： 1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2．根据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到哈夫曼编码和码树； 3．掌握哈夫曼编码的优缺点； 4．通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。 1.2设计任务及要求 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程； 4. 能够使用MATLAB 或其他语言进行编程，编写的函数要有通用性。 1.3设计内容 一个有8个符号的信源X ，各个符号出现的概率为： ??????=? ?????04.005.006.007.01.012.017.039.0)(87654321 x x x x x x x x X P X 进行哈夫曼编码，并计算平均码长、编码效率、冗余度。