首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
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

最新搜索

 

试为这样的信息收发站编 写一个赫夫曼码的编/译码...《数据结构与算法课程设计》就是要运用本课程以及到...三、概要设计:开始 建哈弗曼树 哈弗曼编码 哈弗曼...

37. 哈夫曼编码/译码系统(树应用)任务:利用哈夫曼...②利用上述哈夫曼树对编码信息进行翻译,即将编 码...散列表的设计与实现任务:设计散列表实现电话号码查找...

和数 据,在文件中读取数据以及权值,然后进行译码和...由郭祎堂编写哈夫曼编 码以及主函数的定义等;由储...问题中基本原理的应用,知道 了树的不同存储结构的...

课程设计任务书一、设计题目、内容及要求 1、设计题目:哈夫曼编码译码器设计与...哈夫曼树的应用 课程设计... 1页 免费 哈夫曼编译码器数据结构... 16页 ...

4.仓库管理系统(线性表应用)【问题描述】 建立一个...试为这样的信息收发站写一个哈夫曼编/译码系统。 ...数据建立哈夫曼树,并实现以下报文的编码和 译码:“...

huffman(哈夫曼)树编码译码 课程设计报告_计算机软件及应用_IT/计算机_专业资料...对于双工信道(即可以双向传输信息的信 道) , 每端都需要一个完整的编/译码...

Huffman编码器_信息与通信_工程科技_专业资料。#...{//哈夫曼树的结点 unsigned int weight; unsigned...[N]; cout<<"\t***欢迎使用赫夫曼编译码***"...

-树-哈夫曼编解码的实现-实验内容与要求_计算机硬件...编程语言说明: 1.编程软件,Code Blocks 16.0; 2...哈夫曼树编码以及译码—... 6页 1下载券 综合训练...

哈夫曼编\译码器 院系:计算机科学与信息工程学院 ...软件工程 16-2 指导教师:孙高飞 2017 年 12 月 ...哈夫曼树编码原理,构造哈夫曼树,创建一套哈夫曼编码...

《数据结构与算法应用》上机实验题目题目 1(线性表) [问题描述] 利用带头结点...题目 6(哈夫曼树的编/译码器) [问题描述] 利用哈夫曼编码进行通讯可以大大...