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 日指导教师签名：课程负责人签名：、设计题目（任选其一）实验一、哈夫曼编/ 译码器二、实验目的1 巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；2012 年 6 月21 日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 &); // 从文件中读入赫夫曼树voidfind(HuffmanTree &HT,char *code,char *text,int i,int m); // 译码时根据01 字符串寻找相应叶子节点的递归算法voidConvert_tree(unsigned char T[100][100],int s,int *i,int j); // 将存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; // 全局变量int n=0; // 全局变量，存放赫夫曼树叶子结点的数目建立赫夫从已建好的{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 中的正文进行编码，然后将结果存入文件voidcodefile 中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))}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]); // 从文件读入下一个字符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); //在赫夫曼树中查找字符所在的位置将字符对应的编码存入文件从文件读入下一个字符}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 个代码。