《数据结构课程设计哈弗曼编码、译码器.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计哈弗曼编码、译码器.doc（19页珍藏版）》请在三一办公上搜索。
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
26、(); 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*哈弗曼编/译码器系统*endl; cout请选择您所需功能：endl; cout:初始化哈弗曼树endl; cout:输入待编码字符串endl; cout:利用已建好的哈夫曼树进行编码endl; cout:利用已建好的哈夫曼树进行译码end
27、l; cout:打印代码文件endl; cout:打印哈夫曼树endl; cout:退出endl; if(flag=0) cout请先初始化哈夫曼树,输入Iendl; coutchoice; switch(choice) case I:Initialization();break; case W:Input();break; case E:Encoding();break; case D:Decoding();break; case P:Code_printing();break; case T:Tree_printing(HT,n);break; case Q:;break; default
28、:cout输入的命令出错，请重新输入！endl; while(choice!=Q); free(w); free(info); free(HT); free(HC); system(pause); return 0;七、 序设计总结本次试验中所遇到的主要问题为哈弗曼编码的算法，以及整个变量的控制。通过学习课本上的基础编码方法，再加上老师所讲的内容，整理修改后得到这个编码系统。通过本次试验，掌握了树和哈夫曼树的基本操作，以及各个程序的算法。也复习了前面所学习的参数调用和控制变量范围。这次课程设计，在编辑中犯了不应有的错误，统计字符时忘记了应该怎样保存数据，对文件的操作也很生疏，在不断的分析后明确并改正了错误和疏漏，是程序有了更高的质量。总的来说，不仅是实验的结果，更重要的是过程和思考，是我学到了很多的知识，真的是受益匪浅。八、 致谢我能完成这个课程设计要感谢老师的辛勤帮助九、参考文献：【1】 严蔚敏.数据结构（C语言版），清华大学出版社谭浩强.C语言程序设计教程，高
