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

最新搜索

 

实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计

实验报告模版 二叉树基本操作与哈夫曼编码译码系统的设计_兵器/核科学_工程科技_...实验报告哈夫曼编译码系... 447人阅读 8页 免费 实验3 树和二叉树的应用....

哈夫曼(Huffman)

哈夫曼(Huffman)_计算机软件及应用_IT/计算机_专业资料。哈夫曼(Huffman) 编/...(Decoding) 利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果存入...

课程设计--哈夫曼编码与译码

课程设计--哈夫曼编码与译码_工学_高等教育_教育专区。哈夫曼编码与译码 学生...通常有两种存储结构:顺序存 储结构和链接存储结构。 树是一种在实际应用中被...

哈弗曼树课程设计

哈弗曼树课程设计_工学_高等教育_教育专区。09 计算机课程设计 哈夫曼编码/译码器(树的应用) 1 一.题目 哈弗曼树编码/译码(树的应用) 二 .目的 1. 巩固...

哈夫曼编码和译码系统(附源代码)

哈夫曼编码和译码系统(附源代码)_计算机软件及应用_IT/计算机_专业资料。哈夫曼...(1)哈夫曼树建立、编码 在初始化(I)的过程中间, 要用输入的字符和权值建立...

设计一个利用哈夫曼算法的编码系统

12页 1下载券 哈夫曼编译码系统的设计... 5页 2下载券喜欢此文档的还喜欢 ...个字符和 n 个权值,建立哈夫曼树; 编码:利用建好的哈夫曼树生成哈夫曼编码; ...

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

二叉树基本操作以及哈夫曼编码译码系统_电脑基础知识_IT/计算机_专业资料。实验...运用 节点数量 后序遍历思想, 把树分解为左右子树 和跟结点 左右交换 本质就...

哈夫曼树编码以及译码——实验报告

与技术专业 姓名: 实验三:哈夫曼编/译码器 一. 实验目的掌握哈夫曼树编码原理...根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求赫夫曼编码, ...

哈夫曼编码译码实训报告

开始 启动哈夫曼编码译码系统 按1键 按2键 按3键 按0键 创建哈 夫曼树 创建哈 弗曼编 码 进行哈夫 曼译码 结束并退 出系统 结束 5 / 24 四、详细设计 ...

课程设计样板

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