首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
43树的应用 哈夫曼编编码 和 译码


华%%%%%%%%%%%%%%%%%%学院 数据结构 实验报告 2011~2012 学年 第 二 学期 班级: 学号: 2011 级 姓名: 实验三 树的应用 一、 实验题目: 树的应用——哈夫曼编/译码 二、 实验内容: 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈 夫曼编码的原理,编写一个程序,在用户输入字符及权值的基础上求哈夫曼编码。要求: (1) 从键盘输入字符集(字母 a~z,空格)共 27 个字符,以及出现的频率,将字符出现的频率作为结 点的权值,建立哈夫曼树,并输出数组 ht[]的初态和终态。 (2) 对各个字符进行哈夫曼编码,打印输出字符及对应的哈夫曼编码。 (3) 编码:从键盘输入字符串,利用已建好的哈夫曼编码,实现该字符串的编码。 (4) (选作)译码:从键盘输入二进制串,利用已建好的哈夫曼编码,将二进制串还原为字符串。 三、程序源代码: typedef struct { char data; int weight; int parent; int lchild; int rchild; }HTNode; typedef struct { char cd[100]; int start; }HCode; //这里保存字母对应的编码,我本来想用指向字符数组的指针数组,可是后来想到利用结构体更简单。 struct Codes { char ch; 计算机 专业

char codes[27]; }; #include<iostream.h> #include<stdio.h> #include<string.h> const int maxsize=100; //特色,动态编码 void tongji(char str[],int *pinlv); void createHT(HTNode *ht,int n,int pinlv[]); void showHT(HTNode ht[],int n); void createHcode(HTNode ht[],HCode* hcd,int n); void showHCode(HCode hcd[],int n,int pinlv[]); //使字符与编码对应 void matchcodes(HCode hcd[],int pinlv[],int n,Codes* code); void charToCode(Codes codes[],char *str); void codeToChar(Codes codes[]); void main() { cout<<"本例实现动态编码:根据输入的字符串建立编码规则,然后按此规则对输入的字符串进行编 码,对输入的编码进行译码操作"<<endl; //输入 cout<<"input a string"<<endl; char str[maxsize]; gets(str); //统计 int pinlv[27]; int len=0; for(int i=0;i<27;i++) pinlv[i]=0; tongji(str,pinlv);

for(int k=0;k<27;k++) if(pinlv[k]!=0) len++; cout<<len<<endl; // cout<<pinlv[26]<<endl;

//构造哈夫曼树 HTNode ht[199]; createHT(ht,len,pinlv); //哈夫曼编码 HCode hcd[27]; createHcode(ht,hcd,len); showHCode(hcd,len,pinlv); //字符与编码对应匹配 Codes codes[27]; matchcodes(hcd,pinlv,len,codes); //char to code charToCode(codes,str); // code to char codeToChar(codes); } //这个函数有错误,已经改正 void codeToChar(Codes codes[]) { cout<<"根据上面输出的编码规则,请输入要译码的 01 编码(相邻编码要以逗号分割,以“#”结束) "<<endl; char str[100]; gets(str); cout<<str<<"的译码为:"<<endl; char temp[27]; //保存每个字符的编码,每次要赋 0 啊

int i,j; for(i=0,j=0;i<100;i++) { if(str[i]!=',') { temp[j]=str[i]; j++; } else { temp[j]='\0'; for(int k=0;k<27;k++) { if(strcmp(codes[k].codes ,temp)==0) { cout<<codes[k].ch <<" "; //cout.flush(); break; } } j=0; //赋 0 操作

} if(str[i]=='#') { break; }

} cout<<endl;

} void charToCode(Codes codes[],char *str) { char ch=*str; int k=0; cout<<str<<"的编码为:"<<endl; while(ch!='\0') { for(int i=0;i<27;i++) { if(codes[i].ch ==ch) cout<<codes[i].codes<<","; } k++; ch=*(str+k);

} cout<<endl; } //已经改进过的地方 void matchcodes(HCode hcd[],int pinlv[],int n,Codes* codes) { int i,k,m; char ch='a'; int p=0; char temp[27]; for(int z=0;z<26;z++) { temp[z]=' '; }

temp[26]='\0';

for(i=0;i<27;i++) { if(pinlv[i]!=0) { ch='a'; ch=char(ch+i); if(ch>='a'&&ch<='z') { codes[p].ch =ch; //测试 /* if(codes[p].ch==ch) { cout<<"succss"<<endl; }*/ }

else codes[p].ch =' '; m=0;

for(k=hcd[p].start;k<=n;k++) { temp[m]=hcd[p].cd [k]; m++; } //字符串必须给出结束符位置,否则会输出乱码啊 temp[m]='\0';

//codes[p]=temp; strcpy(codes[p].codes ,temp); // cout<<codes[p].ch;

// cout<<codes[p].ch<<"-----"<<codes[p].codes<<endl; p++;

} } } void showHCode(HCode hcd[],int n,int pinlv[]) { int i,k; char ch='a'; int p=0; cout<<"字符"<<" "<<"对应编码"<<endl; for(i=0;i<27;i++) { //每次必须从字符'a'开始 ch='a'; //// ch=char(ch+i); if(pinlv[i]!=0) {

if(ch>='a'&&ch<='z') cout<<ch<<" else cout<<" "<<" "; ";

for(k=hcd[p].start;k<=n;k++) cout<<hcd[p].cd [k]; p++; cout<<endl; }

}

} void createHcode(HTNode ht[],HCode* hcd,int n) { int i,f,c; HCode hc; for(i=0;i<n;i++) { //不是书上的 hc.start =n-1; c=i; f=ht[i].parent ; while(f!=-1) { if(ht[f].lchild ==c) hc.cd [hc.start --]='0'; else hc.cd [hc.start --]='1'; c=f; f=ht[f].parent ; } //最后一位必须赋值为结束符 hc.cd[n]='\0'; hc.start =n;

hc.start ++; hcd[i]=hc;

} } void createHT(HTNode* ht,int n,int pinlv[]) { for(int m=0;m<=2*n-1;m++)//初始化节点的所有与域值 ht[m].parent =ht[m].lchild =ht[m].rchild =-1;

char ch='a'; int p=0; for(int z=0;z<27;z++)//循环 27 个字母(a-z 和'') ,若频数大于 0,就创建节点 { if(pinlv[z]!=0) { if(ch>='a'&&'z'>=ch) { ht[p].data =ch; ht[p].weight =pinlv[ch-97];

12

 


 

  【Top

最新搜索

 

课程设计样板

2 哈弗曼编码与译码 2.1 基本术语( 1 )路径和路径长度 在一棵树中,从一...即应用哈夫曼树对传送中 的数据进行二进制编码。在所构造出来的哈夫曼树中,...

哈夫曼树编码课程设计实验报告

四、综合设计(课程设计)摘要: 在这次课程设计中,所进行的实验是:哈夫曼编码和...在译码过程中,由所输入的二进制电文,根据所建立的哈夫曼树,如果是 0 走左 ...

哈夫曼编_译码器数据结构课程设计报告

哈夫曼编_译码器数据结构课程设计报告_工学_高等教育_教育专区。摘要 哈夫曼...树;用递归调用的方式对哈 夫曼树的节点进行编码,生成与字符对应的哈夫曼编码。...

哈夫曼编码与译码完整版

哈夫曼编码与译码完整版_计算机软件及应用_IT/计算机_专业资料。编码与译码《...() //将树结点初始化为空 { delete[] Node; } //释放结点空间 void ...

哈夫曼编码译码器数据结构C语言

然而,如何进行前缀编码就是利用哈夫曼树来做,也就有了现在的哈夫曼编码和译码。 二、概要设计利用哈夫曼树编/译码 (一) 、建立哈夫曼树 (二) 、对哈夫曼树...

哈夫曼树编码译码实验报告

数据结构课程设计 设计题目: 哈夫曼树编码译码 课题名称 院学系号姓名 哈夫曼...编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编 码。...

二叉树的基本操作及哈夫曼编码译码系统的实现

2、学会设计基于遍历的求解二叉树应用问题的递归算法。 3、理解哈夫曼树的构造算法,学会设计哈夫曼编码和译码系统。 内容和要求: 1、在二叉链表上实现二叉树运算 ...

哈夫曼编码译码系统实验报告,数据结构课程设计

软件工程完成日期 2016/7/4 计算机科学与技术学院 1 .需求分析 1.1 问题描述...根据已经建立好的哈夫曼树,找到每一字符对应的编 码 3:将报文译码: 步骤一:...

数据结构设计-哈夫曼编译码系统的设计与实现

数据结构设计-哈夫曼编译码系统的设计与实现_兵器/核科学_工程科技_专业资料。...构造赫夫曼树 HT,并求出 n 个字符的赫夫曼编码 HC void HuffmanCoding(...