数据结构课程设计哈弗曼编码、译码器

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 哈弗曼编码、译码器 专业 计算机科学与技术 班级 10计本2班 学号 10012080 姓名 联系方式 指导教师 20 11 年 12 月 29 日一实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二实验环境 microsoft visual c+三、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编

2、码/译码系统。试为这样的信息收发站写一个哈夫曼编码的编码/译码器。四、需求分析（1）初始化;从终端输入字符集的大小n，以及n个字符和n个权值建立哈夫曼树。 （2）输出哈夫曼树，及各字符对应的编码。 （3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。 （4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。五、概要设计#include #include #include #include #include /typedef int telemtype;const int uint_max=1000;char str50;typedef s

3、truct int weight,k; int parent,lchild,rchild;htnode,* huffmantree;typedef char *huffmancode;/-全局变量-huffmantree ht;huffmancode hc;int w50,i,j,n;char z50;int flag=0; int numb=0/ -求哈夫曼编码- struct cou char data; int count;cou50;int min(huffmantree t,int i) / 函数void select()调用 int j,flag; int k=uint_max;

4、/ 取k为不小于可能的值,即k为最大的权值1000 for(j=1;j=i;j+) if(tj.weights2) j=s1; s1=s2; s2=j; / -算法6.12-void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n) / w存放n个字符的权值(均0),构造哈夫曼树ht,并求出n个字符的哈夫曼编码hc int m,i,s1,s2,start; /unsigned c,f; int c,f; huffmantree p; char *cd; if(n=1) return;/检测结点数是否可以构成树 m=2*n-1

5、; ht=(huffmantree)malloc(m+1)*sizeof(htnode); / 0号单元未用 for(p=ht+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建哈夫曼树 / 在ht1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(ht,i-1,s1,s2); hts1.parent=hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts

6、1.weight+hts2.weight; / 从叶子到根逆向求每个字符的哈夫曼编码 hc=(huffmancode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i=n;i+) / 逐个字符求哈夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) / 从叶子到根逆向求编码 if(htf.lchild=c) cd-st

7、art=0; else cd-start=1; hci=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(hci,&cdstart); / 从cd复制编码(串)到hc free(cd); / 释放工作空间/- 获取报文并写入文件-int inputcode() /cout请输入你想要编码的字符endl; file *tobetran; if(tobetran=fopen(tobetran.txt,w)=null) cout不能打开文件endl; return 0; cout请输入你想要编码的字符endl; gets(str);

8、 fputs(str,tobetran); cout获取报文成功endl; fclose(tobetran); return strlen(str);/-初始化哈夫曼链表-void initialization() int a,k,flag,len; a=0; len=inputcode(); for(i=0;ik) if(stri=strk) a+;为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：adt huffmantree数据对象：d=ai| aicharset,i=1,2,n, n0数据关系：r= ai-1, aid, ai-1ai ,i

9、=2，3，n基本操作p：huffmantree(); 构造函数 huffmantree(); 析构函数initialization(int weightnum);操作结果：构造哈夫曼树。encoder()初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。操作结果：对字符串进行编码decoder();初始条件：哈夫曼树已存在且已编码。操作结果：对二进制串进行译码print()初始条件：编码文件已存在。操作结果：把已保存好的编码文件显示在屏幕2.本程序包含三个模块：1)主程序模块：void main() 初始化；do 接受命令； 处理命令；while(“命令”=”退出”)2)、建树模块实现定义的抽

10、象数据类型3)、编/译码模块实现字符串的编/译码六、源程序#include#include#include#includeusing namespace std;# define maxn 100/初始设定的最大结点数# define maxc 1000/最大编码长度 # define impossibleweight 10000/结点不可能达到的权值 # define n 26/字符集的个数/-哈夫曼树的结点结构类型定义-typedef struct /定义哈夫曼树各结点 int weight;/权值 int parent;/双亲结点下标 int lchild;/左孩子结点下标 int rc

11、hild;/右孩子结点下标htnode,*huffmantree;/动态分配数组存储哈夫曼树typedef char*huffmancode;/动态分配数组存储哈夫曼编码表 /-全局变量- huffmantree ht;huffmancode hc;int *w;/权值数组 /const int n=26;/字符集的个数 char *info;/字符值数组 int flag=0;/初始化标记 /* /初始化函数/函数功能： 从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree中/函数参数： /向量ht的前n个分量表示叶子结点，最后一个分量表示根结点，各

12、字符的编码长度不等，所以按实际长度动态分配空间void select(huffmantree t,int i,int &s1,int &s2) /s1为最小的两个值中序号最小的那个 int j; int k=impossibleweight;/k的初值为不可能达到的最大权值 for(j=1;j=i;j+) if(tj.weightk&tj.parent=0) k=tj.weight; s1=j; ts1.parent=1; k=impossibleweight; for(j=1;j=i;j+) if(tj.weight0），构造哈夫曼树ht，并求出n个字符的哈弗曼编码hc int i,m,c,

13、s1,s2,start,f; huffmantree p; char* cd; if(num=1) return; m=2*num-1;/m为结点数，一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中 ht=(huffmantree)malloc(m+1)*sizeof(htnode);/0号单元未用 /-初始化哈弗曼树- for(p=ht+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(i=num+1;iweight=0; p-parent=0; p-lchild=0; p-rchild

14、=0; /-建哈夫曼树- for(i=num+1;i=m;i+) select(ht,i-1,s1,s2);/在ht1.i-1选择parent为0且weight最小的两个结点，其序号分别为s1和s2 hts1.parent=i; hts2.parent=i; hti.lchild=s1; hti.rchild=s2;/左孩子权值小，右孩子权值大 hti.weight=hts1.weight+hts2.weight; /-从叶子到根逆向求每个字符的哈弗曼编码- hc=(huffmancode)malloc(num+1)*sizeof(char *);/指针数组:分配n个字符编码的头指针向量 cd

15、=(char*)malloc(n*sizeof(char*);/分配求编码的工作空间 cdn-1=0;/编码结束符 for(i=1;i=n;i+)/逐个字符求哈弗曼编码 start=n-1;/编码结束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/从叶子到跟逆向求哈弗曼编码 if(htf.lchild=c) cd-start=0;/判断是左孩子还是右孩子(左为0右为1) else cd-start=1; hci=(char*)malloc(num-start)*sizeof(char*);/按所需长度分配空间 int j,h; strcpy(hc

16、i,&cdstart); free(cd);/*初始化函数*void initialization() flag=1;/标记为已初始化 int i; w=(int*)malloc(n*sizeof(int);/为26个字符权值分配空间 info=(char*)malloc(n*sizeof(char);/为26个字符分配空间 ifstream infile(abc.txt,ios:in); if(!infile) cerr打开失败endl; exit(1); for(i=0;iinfoi; infilewi; infile.close(); cout读入字符成功！endl; huffmanco

17、ding(ht,hc,w,n); /-打印编码- cout依次显示各个字符的值,权值或频度,编码如下endl; cout字符setw(6)权值setw(11)编码endl; for(i=0;in;i+) coutsetw(3)infoi; coutsetw(6)wisetw(12)hci+1endl; /-将建好的哈夫曼树写入文件- cout下面将哈夫曼树写入文件endl; ofstream outfile(hfmtree.txt,ios:out); if(!outfile) cerr打开失败endl; exit(1); for(i=0;in;i+,w+) outfileinfoi ; out

18、filewi ; outfilehci+1 ; outfile.close(); cout已经将字符与对应的权值，编码写入根目录下文件hfmtree.txtendl;/*输入待编码字符函数* void input() char string100; ofstream outfile(tobetran.txt,ios:out); if(!outfile) cerr打开失败endl; exit(1); cout请输入你想要编码的字符串(字符个数应小于100),以#结束string; for(int i=0;stringi!=0;i+) if(stringi=0) break; outfilestr

19、ingi; cout获取报文成功endl; outfile.close(); cout-已经将报文存入根目录下的tobetran.txt文件endl;/*编码函数* void encoding() int i,j; char*string; string=(char*)malloc(maxn*sizeof(char); cout下面对根目录下的tobetran.txt文件中的字符进行编码endl; ifstream infile(tobetran.txt,ios:in); if(!infile) cerr打开失败endl; exit(1); for(i=0;istringi; for(i=0;

20、i100;i+)if(stringi!=#) coutstringi;else break; infile.close(); ofstream outfile(codefile.txt,ios:out); if(!outfile) cerr打开失败endl; exit(1); for(i=0;stringi!=#;i+) for(j=0;jn;j+) if(stringi=infoj) outfilehcj+1; outfile#; outfile.close(); free(string); cout编码完成-; cout编码已写入根目录下的文件codefile.txt中endl; /*译码

21、函数* void decoding() int j=0,i; char *code; code=(char*)malloc(maxc*sizeof(char); char*string; string=(char*)malloc(maxn*sizeof(char); cout下面对根目录下的codefile.txt文件中的代码进行译码endl; ifstream infile(codefile.txt,ios:in); if(!infile) cerr打开失败endl; exit(1); for( i=0;icodei; if(codei!=#) coutcodei; else break;

22、infile.close(); int m=2*n-1; for(i=0;codei-1!=#;i+) if(htm.lchild=0) stringj=infom-1; j+; m=2*n-1; i-; else if(codei=1) m=htm.rchild; else if(codei=0) m=htm.lchild; stringj=#; ofstream outfile(textfile.txt,ios:out); if(!outfile) cerr打开失败endl; exit(1); cout的译码为-endl; for( i=0;stringi!=#;i+) outfilest

23、ringi; coutstringi; outfile#; outfile.close(); cout-译码完成-endl; cout译码结果已写入根目录下的文件textfile.txt中endl; free(code); free(string); /*打印编码函数*void code_printing() int i; char *code; code=(char*)malloc(maxc*sizeof(char); cout下面打印根目录下文件codefile.txt中的编码endl; ifstream infile(codefile.txt,ios:in); if(!infile) c

24、err打开失败endl; exit(1); for( i=0;icodei; if(codei!=#) coutcodei; else break; infile.close(); coutendl; ofstream outfile(codeprin.txt,ios:out); if(!outfile) cerr打开失败endl; exit(1); for(i=0;codei!=#;i+) outfilecodei; outfile.close(); free(code); cout-打印结束-endl; cout该字符形式的编码文件已写入文件codeprin.txt中endl;/*打印哈夫

25、曼树函数*int numb=0;void coprint(huffmantree start,huffmantree ht) /start=ht+26这是一个递归算法 if(start!=ht) ofstream outfile(treeprint.txt,ios:out); if(!outfile) cerr打开失败rchild,ht); /递归先序遍历 coutsetw(5*numb)weightrchild=0) coutinfostart-ht-1endl; outfileweight; coprint(ht+start-lchild,ht); numb-; outfile.close(); void tree_printing(huffmantree ht,int num) huffmantree p; p=ht+2*num-1; /p=ht+26 cout下面打印赫夫曼树endl; coprint(p,ht); /p=ht+26 cout打印工作结束endl;/*主函数*int main() char choice; do cout*哈弗曼编/译码器系统