哈夫曼编译码器课程设计报告(完整版)

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生姓名：XXX系别：XXX专业：XXX班级：XXX学号：XXX指导教师：XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx 姓名xxx主要内容、基本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。

要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。

对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站写一个哈夫曼的编/译码系统。

2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。

对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。

利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。

（3）P：打印代码文件（Print）。

将文件codefile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件codeprint中。

（4）T：打印哈夫曼树（Tree Printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012年6月21 日指导教师签名：课程负责人签名：2012年6月21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。

三、运行环境（软、硬件环境）Windows xp sp3，Visual C++ 6.0英文版四、算法设计的思想（1）初始化赫夫曼树，输入文件tobetrans.txt中各字符及其权值，并保存于hfmtree.txt文件中（2）编码（Coding）。

对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中（3）D：解码（Decoding）。

利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。

（4）P：打印代码文件（Print）。

将文件codefile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件codeprint中。

（5）T：打印哈夫曼树（Tree Printing）。

将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

五、流程图六、算法设计分析1.赫夫曼树节点的数据类型定义为：typedef struct{ //赫夫曼树的结构体char ch;int weight; //权值int parent,lchild,rchild;}HTNode,*HuffmanTree;2.void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼树的算法，此函数块调用了Select（）函数。

void select(HuffmanTree HT,int j,int *x,int *y);从已建好的赫夫曼树中选择parent为0，weight最小的两个结点。

3．利用已建好的哈夫曼树从文件hfmtree.txt中读入，对文件中的正文进行编码，然后将结果存入文件codefile.txt中。

4. coding编码功能：对输入字符进行编码5. Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.txt 中。

6. Print() 打印功能函数：输出哈夫曼树以及对应的编码。

七、源代码////////////////////////////////////////////////////////////////////////////// ////////////#include <stdio.h>#include <stdlib.h>#include <string.h>//定义赫夫曼树结点的结构体typedef struct{char ch; //增加一个域，存放该节点的字符int weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode; //指向赫夫曼编码的指针void tips(); //打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int); //建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *x,int *y); //从已建好的赫夫曼树中选择parent为0，weight最小的两个结点void Init();void Coding(); //编码void Decoding(); //译码void Print_code(); //打印译码好的代码void Print_tree(); //打印哈夫曼树int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m); //译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T[100][100],int s,int *i,int j); //将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; //全局变量int n=0; //全局变量，存放赫夫曼树叶子结点的数目int main(){char select;while(1){tips();scanf("%c",&select);switch(select) //选择操作，根据不同的序号选择不同的操作{case '1':Init();break;case '2':Coding();break;case '3':Decoding();break;case '4':Print_code();break;case '5':Print_tree();break;case '0':exit(1);default :printf("Input error!\n");}getchar();}return 0;}void tips() //操作选择界面{printf(" -----------------------------------------------------\n");printf(" -- 请选择操作--\n"); printf(" -----------------------------------------------------\n");printf(" \n"); printf(" ---------------------1初始化赫夫曼树---------------\n"); printf(" ---------------------2编码---------------\n");printf(" ---------------------3译码---------------\n"); printf(" ---------------------4打印代码文件---------------\n"); printf(" ---------------------5打印赫夫曼树---------------\n"); printf(" ---------------------0退出---------------\n"); printf(" -----------------------------------------------------\n");}//初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中void Init(){FILE *fp;int i,n,w[52]; //数组存放字符的权值char character[52]; //存放n个字符printf("\n输入字符个数n:");scanf("%d",&n); //输入字符集大小printf("输入%d个字符及其对应的权值:\n",n);for (i=0;i<n;i++){char b=getchar();scanf("%c",&character[i]);scanf("%d",&w[i]); //输入n个字符和对应的权值}HuffmanCoding(HT,character,w,n); //建立赫夫曼树if((fp=fopen("hfmtree.txt","w"))==NULL)printf("Open file hfmtree.txt error!\n");for (i=1;i<=2*n-1;i++){if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中printf("File write error!\n");}printf("\n赫夫曼树建立成功，并已存于文件hfmtree.txt中\n");fclose(fp);}//建立赫夫曼树的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n) {int m,i,x,y;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++character,++w){p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild =0;}for(;i<=m;++i,++p){p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i){select(HT,i-1,&x,&y);HT[x].parent=i;HT[y].parent=i;HT[i].lchild=x;HT[i].rchild=y;HT[i].weight=HT[x].weight+HT[y].weight;}}//从HT[1]到HT[j]中选择parent为0，weight最小的两个结点，用x和y 返回其序号void select(HuffmanTree HT,int j,int *x,int *y){int i;//查找weight最小的结点for (i=1;i<=j;i++)if (HT[i].parent==0){*x=i;break;}for (;i<=j;i++)if ((HT[i].parent==0)&&(HT[i].weight<HT[*x].weight))*x=i;HT[*x].parent=1;//查找weight次小的结点for (i=1;i<=j;i++)if (HT[i].parent==0){*y=i;break;}for (;i<=j;i++)if ((HT[i].parent==0)&&(i!=*x)&&(HT[i].weight<HT[*y].weight)) *y=i;}//对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中void Coding(){FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n==0)n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数//求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中{HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]='0';else cd[--start]='1';HC[i]=(char *)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}if((fp=fopen("tobetrans.txt","rb"))==NULL)printf("Open file tobetrans.txt error!\n");if((fw=fopen("codefile.txt","wb+"))==NULL)printf("Open file codefile.txt error!\n");char temp;fscanf(fp,"%c",&temp); //从文件读入第一个字符while(!feof(fp)){for(i=1;i<=n;i++)if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置for(int r=0;HC[i][r]!='\0';r++) //将字符对应的编码存入文件fputc(HC[i][r],fw);fscanf(fp,"%c",&temp); //从文件读入下一个字符}fclose(fw);fclose(fp);printf("\n已将文件hfmtree.txt成功编码,并已存入codefile.txt中！\n\n"); }//将文件codefile中的代码进行译码，结果存入文件textfile中void Decoding(){FILE *fp,*fw;int m,i;char *code,*text,*p;if(n==0)n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if((fp=fopen("codefile.txt","rb"))==NULL)printf("Open file codefile.txt error!\n");if((fw=fopen("textfile.txt","wb+"))==NULL)printf("Open file textfile.txt error!\n");code=(char *)malloc(sizeof(char));fscanf(fp,"%c",code); //从文件读入一个字符for(i=1;!feof(fp);i++){code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间fscanf(fp,"%c",&code[i]); //从文件读入下一个字符}code[i-1]='\0';// codefile.txt文件中的字符已全部读入，存放在code数组中text=(char *)malloc(100*sizeof(char));p=text;m=2*n-1;if(*code=='0')find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找elsefind(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找for(i=0;p[i]!='\0';i++) //把译码好的字符存入文件textfile.txt中fputc(p[i],fw);fclose(fp);fclose(fw);printf("\n已将codefile.txt文件成功译码，兵已存入textfile.txt文件！\n\n"); }//将文件codefi1e以紧凑格式显示在终端上,每行50个代码。