哈夫曼编译码器课程设计报告(完整版)
XXX学院本科
数据结构课程设计总结报告
设计题目：实验一、哈夫曼编/译码器
学生姓名：XXX
系别：XXX
专业：XXX
班级：XXX
学号：XXX
指导教师：XXX XXX
2012年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中读入，对文件中的正文进行编码，然后将结果存入文件code中。
4. coding
编码功能：对输入字符进行编码
5. Decoding
译码功能：利用已建好的哈夫曼树将文件code中的代码进行译码，结果存入文件text 中。
6. Print() 打印功能函数：输出哈夫曼树以及对应的编码。
七、源代码
//////////////////////////////////////////////////////////////////////////////// //////////
#include
#include
#include
//定义赫夫曼树结点的结构体
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 { 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 error!\n"); for (i=1;i<=2*n-1;i++) { if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中 printf(" 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 *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 *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 error!\n"); if((fw=fopen("code","wb+"))==NULL) printf("Open 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成功编码,并已存入code中！\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("code","rb"))==NULL) printf("Open error!\n"); if((fw=fopen("text","wb+"))==NULL) printf("Open 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'; // code文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char)); p=text; m=2*n-1; if(*code=='0') find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找 else find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找 for(i=0;p[i]!='\0';i++) //把译码好的字符存入文件text中 fputc(p[i],fw); fclose(fp); fclose(fw); printf("\n已将code文件成功译码，兵已存入text文件！\n\n"); } //将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 void Print_code() { FILE *fp,*fw; char temp; int i; if((fp=fopen("code","rb"))==NULL) printf("Open error!\n"); if((fw=fopen("codeprint.txt","wb+"))==NULL) printf("Open error!\n"); printf("\n文件codefi1e显示如下:\n"); fscanf(fp,"%c",&temp); //从文件读入一个字符 for (i=1;!feof(fp);i++) { printf("%c",temp); if(i%50==0) printf("\n"); fputc(temp,fw); //将该字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); //从文件读入一个字符 } printf("\n\n已将此字符形式的编码写入文件codeprint.txt中！\n\n"); fclose(fp); fclose(fw); } //将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入文件treeprint 中。 void Print_tree() { unsigned char T[100][100]; int i,j,m=0; FILE *fp; if(n==0) n=Read_tree(HT); //从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 Convert_tree(T,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中 if((fp=fopen("treeprint.txt","wb+"))==NULL) printf("Open error!\n"); printf("\n打印已建好的赫夫曼树：\n"); for(i=1;i<=2*n-1;i++) { for (j=0;T[i][j]!=0;j++) { if(T[i][j]==' ') {printf(" ");fputc(T[i][j],fp);} else {printf("%d",T[i][j]);fprintf(fp,"%d\n",T[i][j]);} } printf("\n"); } fclose(fp); printf("\n已将该字符形式的哈夫曼树写入文件treeprint.txt中！\n\n"); } //从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数 int Read_tree(HuffmanTree &HT) { FILE *fp; int i,n; HT=(HuffmanTree)malloc(sizeof(HTNode)); if((fp=fopen("hfmtree.txt","r"))==NULL) printf("Open error!\n"); for (i=1;!feof(fp);i++) { HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间 fread(&HT[i],sizeof(HTNode),1,fp); //读入一个节点信息 } fclose(fp); n=(i-1)/2; return n; } //译码时根据01字符串寻找相应叶子节点的递归算法 void find(HuffmanTree &HT,char *code,char *text,int i,int m) { if(*code!='\0') //若译码未结束 { code++; if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点 { *text=HT[i].ch; //将叶子节点的字符存入text中 text++; if((*code=='0')) find(HT,code,text,HT[m].lchild,m); //从根节点的左子树找 else find(HT,code,text,HT[m].rchild,m); //从根节点的右子树找 } else //如果不是叶子节点 if(*code=='0') find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找 else find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找 } else *text='\0'; //译码结束 } //将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来 void Convert_tree(unsigned char T[100][100],int s,int *i,int j) { int k,l; l=++(*i); for(k=0;k T[l][k]=' '; T[l][k]=HT[j].weight; if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild); if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); T[l][++k]='\0'; } //////////////////////////////////////////////////////////////////////////////// ////////////////// 八、运行结果分析 截图说明： 1、运行后界面如图（1）： 图（1） 选择要选择的操作序号可以运行各个步骤； 2、初始化赫夫曼树： 输入tobetrans.txt中各元素及其出现频率，如图（2） 图（2）3、编码及译码，如图（3） 图（3） 4、打印编码文件，如图（4） 图（4）5、打印赫夫曼树，如图（5） 图（5）6、各步骤所存的文件内容如图（6） 图（6） 九、收获及体会 课程设计是让我们充分利用我们专业课程所学知识的机会，也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。我这两天的课程设计，是让我学会脚踏实地迈开这一步，也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。 我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料，在写这个程序的时候也参考了网上的设计流程，写完刚运行时出现了很多问题。尤其是编码错误，导致内存无法read，通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解决问题的方法，更是解决问题的思想。课程设计本身也是一种相互学习的过程,/////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////// #include #include #include //哈夫曼树结点的结构 typedef struct { char ch; //该字符域用于存放节点的关键字 int weight; int parent, lchild, rchild; }HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表 void Menu(); //显示菜单 void HuffmanCoding(HuffmanTree &HT, char *character, int * w, int n); //建立哈夫曼树 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); //将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树 数据结构课程设计设计题目：哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12) 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 JAVA语言实验报告 学院计算机工程学院班级计算1013 姓名佐伊伦学号 201081xxxx 成绩指导老师 xxxx 2012年09月03日 目录 目录 (1) 1 课程设计的目的和意义 (2) 2 需求分析 (3) 3 系统（项目）设计 (5) ①设计思路及方案 (5) ②模块的设计及介绍 (5) ③主要模块程序流程图 (8) 4 系统实现 (11) ①主调函数 (12) ②建立HuffmanTree (12) ③生成Huffman编码并写入文件 (15) ④电文译码 (16) 5 系统调试 (17) 参考文献 (21) 附录源程序 (22) 1 课程设计的目的和意义 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 作为信息管理专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。 在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。 计算机与信息工程系 《实践环节名称》报告 专业：计算机科学与技术 班级：******** 学号：********* 姓名：杨明英 报告完成日期：2011/6/10 指导教师：*** 评语： 成绩： 批阅教师签名：批阅时间： 目录 1．问题描述 (1) 2．基本要求 (1) 3．数据结构 (1) 4．总体设计 (1) 5．详细设计 (2) 5.1主函数 void main() (2) 5.2建立文件 void jianliwenjian() (3) 5.3输入原文 void luruyuanwen() (4) 5.4创建哈夫曼树 void chuangjian() (5) 5.5编码 void bianma() (6) 5.6对哈夫曼码译码 void yiwen() (7) 5.7保存译文 void baocunyiwen() (8) 5.8输出原文 void duquyuanwen() (9) 5.9输出原文编码void duqubianma() (10) 5.10输出译文 void duquyiwen() (11) 6．测试与调试 (11) 7．源程序清单 (8) 8．实验心得 (28) 1.问题描述 打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。 2.基本要求 以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen 中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。 3.数据结构 char CH[N]; //记录原文字符数组 char YW[N]; //记录译文字符数组 typedef char * Hcode[m+1]; //存放哈夫曼字符编码串的头指针的数组 typedef struct { char a; int num; }dangenode; //记录单个字符的类别和出现的次数 typedef struct { dangenode b[m]; int tag; }jilunode; //统计原文出现的字符种类和数量 typedef struct node //静态三叉的哈夫曼树的定义 { int weight; //结点的权值 int parent; //双亲的下标 int Lchild; //左孩子结点的下标 int Rchild; //右孩子结点的下标 }htnode,hn[M+1]; // hn是结构数组类型，0号单元不用 4.总体设计 功能函数模块划分 void main() //主函数 void jianliwenjian() //建立存储原文的文件yuanwen void luruyuanwen() //通过程序录入原文到文件yuanwen中 void min_2(hn ht,int n,int *tag1,int *tag2) //选择权值较小的两个结点 void chuangjian(jilunode * jilu,hn ht) //建立哈夫曼树 void bianma(jilunode * jilu,hn ht,Hcode hc,int n) //对原文进行编码 void bianmabaocun(Hcode hc,jilunode * jilu) //保存编码在文件yiwen中 void yiwen(Hcode hc,jilunode * jilu) //读取yiwen中的编码，并将其翻译为原文 void baocunyiwen() //将翻译的译文保存到文件textfile中 void duqubianma() //在编码文件yiwen中读取编码 数据结构课程设计评阅书 2011—2012学年第一学期 专业：信息管理与信息系统学号： 1021024016 姓名：万永馨 课程设计名称：数据结构课程设计 设计题目：哈夫曼编码与译码的实现 完成期限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依据、要求及主要内容（可另加附页）： 该设计题目将按以下要求完成： 哈夫曼编码与译码是信息传输中应用的经典算法，运用C或VC++结合数据结构等基础知识，按 以下要求编程实现各种进制的转换。 任务要求：1）阐述设计思想,画出流程图;2）需要对哈夫曼编码/译码的相关原理有所了解，设计数 据结构，建立必要的信息数据文件（最好存储成外部文件），并分析完成用户所需的基本操作功能；3）实现给定信息的编码和译码功能；4）应有较好的界面设计，说明程序测试方法；5）按照格式要 求完成课程设计说明书。 设计要求: 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的 原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定 义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调 用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统 功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基 本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精， 写出数据存储结构的类型定义，写出函数形式的算法框架； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言， 使程序中逻辑概念清楚； 5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正 确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算 法的时间、空间复杂性分析； 7）编写课程设计报告； 以上要求前三个阶段的任务完成后，将设计说明书的草稿交指导老师面审，审查合格方可进入 后续阶段的工作。设计工作结束，经指导老师验收合格后将设计说明书装订，并答辩。 译码器实验报告 实验三译码器及其应用 一、实验目的 1、掌握译码器的测试方法。 2、了解中规模集成译码器的功能，管脚分布，掌握其逻辑功能。 3、掌握用译码器构成 组合电路的方法。4、学习译码器的扩展。 二、实验仪器 1、数字逻辑电路实验板1块 2、74hc138 3-8线译码器2片 3、74hc20 双4输入与非 门1片 三、实验原理 1、中规模集成译码器74hc138 74hc138是集成3线－8线译码器， 在数字系统中应用比较广泛。图3－1是其引脚排列。其中a2 、a1 、a0 为地址输入端，0y～7y为译码输出端，s1、2s 、3s 为使能端。74hc138真值表如下：74hc138引脚图为：74hc138工作原理为：当s1=1，s2+s3=0时，电路完成译码功能，输出低电平有效。其 中： 2、译码器应用 因为74hc138 三-八线译码器的输出包括了三变量数字信号的全部八种组合，每一个输出端表示一个最小项，因此可以利用八条输出线组合构成三变量的任意组合电路。 四、实验内容 1、译码器74hc138 逻辑功能测试（1）控制端功能测试测试电路如图：按上表所示条件输入开关状态。观察并记录译码器输出状态。led指示灯亮为0，灯不 亮为1。 （2）逻辑功能测试 将译码器使能端s1、2s 、3s 及地址端a2、a1、a0 分别接至逻辑电平开关输出口，八个输出端y7 ?????y0依次连接在逻辑电平显示器的八个输入口上，拨动逻辑电平开关，按 下表逐项测试74hc138的逻辑功能。 2、用74hc138实现逻辑函数y=ab+bc+ca 如果设a2=a，a1=b，a0=c，则函数y 的逻辑图如上所示。用74hc138和74hc20各一块 在实验箱上连接下图线路。并将测试结果下面的记录表中。 3、用两个3线-8线译码器构成4线-16线译码器。利用使能端能方便地将两个3/8译码器组合成一个4/16译码器，如下图所示。 五、实验结果记录：2、74hc138实现逻辑函数y=ab+bc+ca，实验结果记录： 六、实验注意事项 安徽大学 数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计 与实现 姓名：鉏飞祥 学号：E21414018 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院 1 .需求分析 1.1问题描述 ?问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。 1.2基本要求 (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能。 1.基本要求 （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data 中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data 及其原文Textfile.txt； 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1)数据结构 哈夫曼树的节点 struct huff 课程论文 题目：哈夫曼树及其应用课程设计报告学号： 201230210115 姓名：黄文宣 班级： 1232101 专业：信息安全 课程名称：数据结构 课程老师：王晓燕 二零一肆年一月 目录 1、课程设计的题目及简介 (3) 2、实验目的 (3) 3、设计说明 (4) 4、总体流图 (4) 5、详细设计 (5) 6、实现部分 (6) 7、测试程序 (9) 8、心得与体会 (10) 一、课程设计题目 哈夫曼树及其应用 数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理 建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。 二、实验目的 1 熟悉树的各种存储结构及其特点。 2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 三、设计说明 建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 四、总体流图 哈夫曼树编码系统 初始化 编码 重新建立哈夫 曼树 译码 打印编码 #include"stdafx.h" #include"stdio.h" #include"conio.h" #include EDA技术实验报告 —3-8译码器的设计 一．实验目的 1.通过一个简单的3-8译码器的设计，掌握组合逻辑电路的设 计方法。 2.掌握组合逻辑电路的静态测试方法。 3.初步了解QUARTUSⅡ软件的基本操作和应用。 4.初步了解可编程逻辑器件的设计全过程。 二．实验原理 3-8译码器的三输入，八输出。输入信号N用二进制表示，对应的输出信号N输出高电平时表示有信号产生，而其它则为 低电平表示无信号产生。其真值表如下图所示： 当使能端指示输入信号无效或不用对当前的信号进行译码时，输出端全为高电平，表示任何信号无效。 三．实验内容 用三个拨动开关来表示三八译码器的三个输入(A,B,C),用八个LED来表示三八译码器的八个输出（D0-D7）。通过与实验箱的FPGA接口相连，来验证真值表中的内容。 表1-2拨动开关与FPGA管脚连接表 表1-3LED 灯与FPGA管脚连接表 (当FPGA与其对应的接口为高电平时，LED会发亮) LED1 LED3 G14 从FPGA的G14至 LED1 LED4 H12 从FPGA的H12至 LED1 LED5 H11 从FPGA的H11至 LED1 LED6 J10 从FPGA的J10至LED1 LED7 L9 从FPGA的L9至LED1 LED8 H1O 从FPGA的H10至 LED1 四．实验歩骤 1.建立工程文件 2．建立图形设计软件 （1）将要选择的器件符号放置在图形编辑器的工作区域，用正 交节点工具将原件安装起来，然后定义端口的名称。结果如下图： 3.编 译 前 设 置 （1）选 择 目标芯片 （2）选择目标芯片的引脚状态 4.对设计文件进行编译 v .. . .. 安徽大学 数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计 与实现 姓名：鉏飞祥 学号：E21414018 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院 1 .需求分析 1.1问题描述 ?问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。 1.2基本要求 (1)输入的形式和输入值的范围； (2)输出的形式； (3)程序所能达到的功能。 1.基本要求 （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data 及其原文Textfile.txt； 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1)数据结构 哈夫曼树的节点 struct huff { int weight; int parent; int l; int r; }; 哈夫曼编码的存储 struct huff *hufftree; (2)程序模块 选择1到i-1中parent为0且权值最小的两个下标 void Select(struct huff *HT, int n, int &s1, int &s2) 构建哈夫曼树： void huffmancoding(struct huff *ht,int *w,int n) 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：实现哈夫曼编码和译码器 院（系）：计算机学院 专业：计算机科学与技术 班级：24010102 学号：2012040101082 姓名：尹伟和 指导教师：徐蕾 此页为任务书 目录 1.题目分析 (1) 1.1.题目重述 (1) 1.1.1.系统功能需求分析 (1) 2.程序设计 (2) 2.1.系统功能模块说明 (2) 2.1.1.系统功能模块结构 (2) 2.1.2.系统模块功能说明 (3) 2.2.数据结构说明 (3) 2.2.1.结构体定义说明 (3) 2.2.2.哈夫曼树 (4) 2.2.3.字符-哈夫曼编码对照表 (4) 2.3.函数说明 (4) 3.算法描述 (6) 3.1.哈夫曼树的构建 (6) 3.2.字符-哈夫曼编码对照表 (6) 3.3.编码 (6) 3.4.译码 (7) 4.程序测试 (9) 4.1.字符集输入 (9) 4.2.编码测试 (10) 4.3.译码测试 (11) 参考文献 (13) 附录（程序清单） (14) 沈阳航空航天大学课程设计报告 1.题目分析 1.1.题目重述 本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。 1.1.1.系统功能需求分析 通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下： 1)读取用户输入的字符集和相应字符出现的频率； 2)根据用户输入构建哈夫曼树； 3)根据哈夫曼树构建字符-哈夫曼编码对照表； 4)根据字符-哈夫曼编码对照表对明文字符串进行编码； 5)根据哈夫曼树对二进制密文进行译码。 XXX学院本科 数据结构课程设计总结报告 设计题目：实验一、哈夫曼编/译码器 学生姓名：XXX 系别：XXX 专业：XXX 班级：XXX 学号：XXX 指导教师：XXX XXX 2012年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++ 英文版 四、算法设计的思想 （1）初始化赫夫曼树，输入文件中各字符及其权值，并保存于文件中 （2）编码（Coding）。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile 中 （3）D：解码（Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。 （4）P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 中北大学 数据结构 课程设计说明书 学生姓名: 郝晨栋学号： 1021010933 软件学院学院: 软件开发与测试: 专业 哈夫曼编码/目题: 译码器 康珺教指导师 2011年12月20日 目录 1 问题描述.............................................................. 错误！未定义书签。 2 需求分析.............................................................. 错误！未定义书签。 3 概要设计 (1) 3．1抽象数据类型定义 (1) 3．2总体框图以及功能描述 (2) 4 详细设计 (2) 4．1数据类型的定义 (2) 4．2主要模块的算法描述 (3) 5 测试分析................................................................................................ 4 6 课程设计总结 (6) 附录（源程序清单） (7) - 1 - 1 问题描述 1.设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 (1) 将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)； (2) 分别采用动态和静态存储结构; 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树; (3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码； 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 2 需求分析 编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。比如需传送的电文为“A B A C C D A”假设将A,B,C,D分别编码为00、01、10、11.则上述电文遍为00010010101100，总长度为14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。 对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。 3 概要设计 3．1抽象数据类型定义 课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 2014年1月2日 课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将 数据结构 课程设计 题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组长： 小组成员： 指导教师： 二〇一二年十二月二十六日 目录 一、目标任务与问题分析 (2) 1.1目标任务 (2) 1.2问题分析 (2) 二、算法分析 (2) 2.1构造huffman树 (2) 2.1.1 字符的统计 (2) 2.1.2 huffman树节点的设计 (2) 2.2构造huffman编码 (3) 2.2.1 huffman编码的设计 (3) 2.3 压缩文件与解压文件的实现 (3) 三、执行效果 (4) 3.1界面 (4) 3.2每个字符的编码 (4) 3.3操作部分 (5) 3.4文件效果 (6) 四、源程序 (7) 五、参考文献 (16) huffman编码与解码实现文件的压缩与解压 一、目标任务与问题分析 1.1目标任务 采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 字符的统计 用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。 struct huffchar{ //存放读入字符的类； int Count;//字符出现的个数； char data;//字符； }; 函数实现： bool char_judge(char c)//判断字符出现的函数； void char_add(char c)//添加新出现的字符； void read_file_count() //文件的读取 2.1.2 huffman树节点的设计 用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。 目录 目录 (2) 1课程设计的目的和意义 (3) 2需求分析 (4) 3概要设计 (4) 4详细设计 (8) ￥ 5调试分析和测试结果 (11) 6总结 (12) 7致谢 (13) 8附录 (13) 参考文献 (20) . | ; 1 课程设计目的与意义 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 作为计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。 （ 在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们 可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。 2 需求分析 课题：哈夫曼编码译码器 ) 问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。问题补充：1. 从硬盘的一个文件里读出一段英语文章； 2. 统计这篇文章中的每个字符出现的次数； 3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储 结构的初态和终态进行输出； 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破 译。 具体介绍：在本课题中，我们在硬盘中预先建立一个文档，在里面编辑一篇文章。然后运行程序，调用函数读出该文章，显示在界面；再调用函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用函数构建哈夫曼树；并调用函数将哈夫曼的存储结构的初态和终态进行输出。然后调用函数对哈夫曼树进行编码，调用函数将编码写入文件；再调用对编码进行译码，再输出至界面。至此，整个工作就完成了 3 概要设计。 一、设计思想 程序要求： 利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。 实现方法： 输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算权值的函数（jsquanzhi()）进行字符统计，统计出现的字符种数以及每种字符出现的次数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。 重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。 哈夫曼编码译码器实验报告(免费) 问题解析与解题方法 问题分析： 设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。 （1）从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）； （2）统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码； （4）将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf） （5）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6）进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。 根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。 哈夫曼树的理论创建过程如下： 一、构成初始集合 对给定的n个权值 {W1,W2,W3,...,Wi,...,Wn}构成n棵二 叉树的初始集合 F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二 叉树Ti中只有一个权值为Wi的根结 点，它的左右子树均为空。 二、选取左右子树 在F中选取两棵根结点权值最小的树 作为新构造的二叉树的左右子树，新 二叉树的根结点的权值为其左右子树 的根结点的权值之和。 三、删除左右子树 从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步， 重复二和三两步，直到集合F中只有一棵二叉树为止。 因此，有如下分析： 1.我们需要一个功能函数对ASCII码的初始 化并需要一个数组来保存它们； 计算机学院信管专业 数据结构课程设计 题目：哈夫曼树的应用班级： 姓名：学号： 同组人姓名： 起迄日期： 课程设计地点: 指导教师： 评阅意见： 成绩评定： 评阅人：日期： 完成日期：2012年12月 目录 一、需求分析 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析和测试结果 (7) 五、心得体会和总结 (10) 六、参考文献 (10) 七、附录 (11) 一、需求分析 （一）实验要求 要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。 要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。 问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。 综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。 （二）实验任务 一个完整的系统应具有以下功能： 功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 （三）实验步骤 分步实施： 1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2）完成最低要求：完成功能1； 3）进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求： 1）界面友好，函数功能要划分好 2）总体设计应画一流程图 3）程序要加必要的注释 4) 要提供程序测试方案 5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。哈夫曼树编码译码实验报告(DOC)
数据结构哈夫曼编码译码器课程设计报告
《哈夫曼编码译码课程设计》报告
哈夫曼编码与译码的实现
译码器实验报告
哈夫曼编码译码系统实验报告,数据结构课程设计
哈夫曼树课程设计论文
哈夫曼树的编码和译码
3-8译码器课程设计报告
哈夫曼编码译码系统实验报告,数据结构课程设计报告
哈夫曼编码与译码器_数据结构课程设计报告
哈夫曼编译码器课程设计报告完整版
完整word版哈夫曼编码译码器试验报告
哈夫曼树课程设计报告(DOC)
huffman编码译码实现文件的压缩与解压.
哈夫曼编码译码器---课程设计报告
哈夫曼编码与译码报告
哈夫曼编码译码器实验报告(免费)
数据结构课程设计实验报告哈夫曼树的应用