数据结构课程设计总结报告 哈夫曼编码译码

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)对原文进行编码：void code(char *c)根据报文找到原文：void decoding(char *zifu)3. 详细设计核心技术分析：1：构建哈夫曼树及生成哈夫曼编码：根据每个字符权值不同，根据最优二叉树的构建方法，递归生成哈夫曼树，并且用数组存放哈夫曼树。

课程设计报告一.需求分析1、一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。

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

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

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

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

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

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

2、利用哈夫曼编译码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

3、用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quito。

请用户键入一个选择功能符。

此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。

4、在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。

每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

二、概要设计1、部分函数1）树与编码类型struct HTNode2）选两个最小的树组成二叉树Void Select(HNode *HT,int I,int &s1,int &s2)3)初始化哈夫曼树void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n)4)输出哈夫曼树void TreePrint(HTNode *HT,int n)5) 输出哈夫曼编码void CodePrint(HuffmanCode *HC,int n)2、主函数void main(){初始化;Switch(){ }end;}3、模块之间的调用关系三、详细设计1、树的结构体的建立struct HTNode{int weight,parent,lchild,rchild;char zifu;};struct HuffmanCode{char *code;char zifu;int size;};2、部分编码void Select(HTNode *HT,int i,int &s1,int &s2) {int k;for(k=1;k<=i;k++){if(HT[k].parent==0){s1=k;break;}}for(k=k+1;k<=i;k++){if(HT[k].parent==0){s2=k;break;}}for(k=k+1;k<=i;k++){if(HT[k].parent==0){if(HT[k].weight<HT[s1].weight){if(HT[k].weight<HT[s2].weight){if(HT[s2].weight<HT[s1].weight){s1=s2;s2=k;}else{s2=k;}}else{s1=s2;s2=k;}}else if(HT[k].weight<HT[s2].weight){s2=k;}}}}void HuffmanCoding(HTNode *&HT,HuffmanCode *&HC,char *x,int *w,int n) {if(n<=1)return;int m=2*n-1,i,s1,s2;HTNode *p;HT=(HTNode *)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;i++,p++,w++,x++)p->weight=*w,p->parent=0,p->lchild=0,p->rchild=0,p->zifu=*x;for(;i<=m;i++,p++)p->weight=0,p->parent=0,p->lchild=0,p->rchild=0,p->zifu='N';for(i=n+1;i<=m;i++){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}char *CD;int k,j;CD=(char *)malloc(n*sizeof(char));for(i=1;i<=n;i++){j=i;k=0;while(HT[j].parent!=0){if(HT[HT[j].parent].lchild==j)CD[k]='0';elseCD[k]='1';k++;j=HT[j].parent;}HC[i-1].code=(char *)malloc((k+1)*sizeof(char));HC[i-1].code[k]='\0';k--;int m=k;HC[i-1].size=m;for(int l=0;l<=m;l++){HC[i-1].code[l]=CD[k];k--;}HC[i-1].zifu=HT[i].zifu;}free(CD);}int Strsize(char *d){int i=0;while(*d!='\0'){d++;i++;}return i;}char* Bianma(HuffmanCode *&HC,char *d) {//哈夫曼树编码int n=Strsize(d),i,k,j,sum=0;char *a;a=(char *)malloc((10*n)*sizeof(char));for(i=0;i<n;i++){k=0;while(*d!=HC[k].zifu){k++;}j=0;while(HC[k].code[j]!='\0'){a[sum]=HC[k].code[j];j++;sum++;}d++;}a[sum]='\0';return a;}void Yima(HTNode *HT,char *&a,char *b,int n){int k=2*n-1,i=0;int m=k;while(*b!='\0'){if(*b=='0'){if(HT[HT[m].lchild].lchild==0){a[i]=HT[HT[m].lchild].zifu;i++;b++;m=k;}else{m=HT[m].lchild;b++;}}else{if(HT[HT[m].rchild].lchild==0){a[i]=HT[HT[m].rchild].zifu;i++;b++;m=k;}else{m=HT[m].rchild;b++;}}}a[i]='\0';}void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n) {//初始化哈夫曼树printf("输入字符集大小n\n");scanf("%d",&n);fflush(stdin);w=(int *)malloc(n*sizeof(int));x=(char *)malloc(n*sizeof(char));for(int i=0;i<n;i++){printf("输入第%d个字符和权值:\n",i+1);scanf("%c %d",&x[i],&w[i]);fflush(stdin);}HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode));HuffmanCoding(HT,HC,x,w,n);}void TreePrint(HTNode *HT,int n){//输出哈夫曼树for(int i=1;i<(2*n);i++)printf("%c %d %d %d %d\n",HT[i].zifu,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); }void CodePrint(HuffmanCode *HC,int n){//输出哈夫曼编码for(int i=0;i<n;i++){printf("%c ",HC[i].zifu);puts(HC[i].code);}}3、主程序void main(){HTNode *HT;HuffmanCode *HC;int n,*w;char *x,*y,Z;char *a,*b;a=(char *)malloc(100*sizeof(char));b=(char *)malloc(100*sizeof(char));start:printf("初始化i，编码e，译码d，印哈夫曼码p，印哈夫曼树t，退出q。

《数据结构》课程设计实验报告题目哈夫曼编码/译码器学院数理与信息学院专业计算机科学与技术班级计科132学生姓名刘海澍 5周弘杰8徐铭瑶 3指导教师编写日期数据结构课程设计目录1 问题描述.................................................................错误!未定义书签。

2 问题分析.................................................................错误!未定义书签。

3 算法设计 (2)3.1抽象数据类型定义 (2)3.2模块划分 (3)4 详细设计 (4)4.1数据类型的定义 (4)4.2主要模块的算法描述 (4)4.3 流程图 (6)5 测试分析 (9)6 课程设计总结 (10)7 成员分工 (10)参考文献 (11)附录（源程序清单） (12)1.问题描述设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

1) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；2) 编码：利用建好的哈夫曼树生成哈夫曼编码；3) 输出编码；4）显示哈夫曼树；5）界面设计的优化；6) 设字符集及频度如下表：字符空格 A B C D E F频度4 9 23 2 17 15字符G H I J K频度1 2 3 3 42.问题分析（1）定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht[60]存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。

数据结构设计性实验Huffman编码与译码学号姓名班级设计性实验—Huffman 编码与译码一．实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。

二．实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。

写出技术工作报告并附源程序。

三．实验内容及任务：1．设字符集为26个英文字母，其出现频度如下表所示。

2．建Huffman 树； 3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；4．对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。

实现步骤：1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；5． 译码器设计；51 48 1 15 63 57 20 32 5 1频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符四．分析以及算法描述1.分析问题1)首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。

2)认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法①又给定的n个权值{w1，w2，w3，……，w n}构造根节点的二叉树，从而得到一个二叉树森林F={T1，T2，T3，……T n}。

②在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。

③在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。

④重复②和③，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所构造的霍夫曼树。

3)练习通过普通树来构造霍夫曼树。