数据结构huffman编码作业报告.doc

哈夫曼编码与解码一、设计思想在设计本程序时，主要用到的算法有如下三个：一、创建哈夫曼树算法；二、求哈夫曼编码算法；三、求哈夫曼解码算法。l 创建哈夫曼树算法如下：1) 存储结构：构造由信息元素与对应的权值组成的信息元素结构体来存储已给定的字母与其权重信息；构造由信息元素、权值、当前结点的父结点、左结点、右结点组成的哈夫曼树结点结构体来存储树结点的信息，还会很方便地帮助创建哈夫曼树；构造由信息元素与对应的哈夫曼编码结构体来存储哈夫曼编码信息；方便进行对数据的编码。2) 结构体数组处理：哈夫曼树没有度为 1 的结点，若一个哈夫曼树由 n 个叶子结点，则该哈夫曼树共有2n-1个结点。应用以上的原理，根据用户输入的信息元素的个数n开辟大小为2n-1的哈夫曼树数组来满足创建哈夫曼树的需要，并对此数组进行初始化，叶子结点的信息元素与权值即给定的的信息元素与权值；非叶子结点的信息元素与权值设置为空值；所有哈夫曼树结点的父结点、左结点、右结点设置为 0 。3) 选择权值最小与次小：在进行比较的过程中循环取出权值进行比较，设置两个s1，s2分别记录本次循环最小与次小的权值，进行下一次的比较选择。返回权值最小与次小的哈夫曼树结点信息。4) 生成小树：应用3)中想法，在用户输入的信息元素中选择权值中最小与次小的元素分别赋值给右叶子结点与左叶子结点，并把这两个权值之和赋值给这两个结点的父结点，记录父结点位置。5) 生成哈夫曼树：再应用3) 4)把这些小树的父结点的权值进行比较选择，选择权值比较大的设置为新的右结点的权值，权值比较小的设置为左结点，把这两个权值的和赋值给新的父结点；以此重复进行，最终生成哈夫曼树。l 求哈夫曼编码算法如下1) 采用无栈非递归遍历哈夫曼树：每次站在根结点遍历哈夫曼树，直至到达某一个叶子结点为止，并临时用一个数组记录遍历过程中每个结点的状态。编码完成后再复制给哈夫曼编码结构体中的编码数组。2) 遍历与编码：在逻辑上，遍历时向左子时，编码为0，向右子为1，将每次的结点状态记录连接即哈夫曼编码；站在根结点上，若到左子上记录此时的结点状态为0，并把指针指向左子，进行下一次的遍历，若到右结点上记录此时的结点状态1，并把指针指向右子，进行下一次的判断遍历；重复进行，到达某一个叶子结点为止，完毕后，将每次遍历的结点状态标志进行连接组成临时状态数组；将此叶子结点的元素信息作为哈夫曼编码的信息元素，把遍历时的状态数组赋值给哈夫曼编码结构体的编码。由此，经遍历哈夫曼树所形成的哈夫曼编码数组就是通信中的简单码表。3) 输出01编码：读入指定文件中的信息后要求输出01编码，在此过程中，要对每个字符进行扫描，并输出01编码。重复进行，每次都无间隔输出，最后所形成的01串就是用户所需要的01编码信息。并将结果写入指定文件。l 求哈夫曼解码算法：1) 前提：哈夫曼解码是哈夫曼编码的逆运算，因此哈夫曼解码需要用哈夫曼编码时的哈夫曼树。2) 哈夫曼解码：从文件中获得已进行编码的哈夫曼码，因为01编码串中仅0与1两种符号，当是1时去左子结点上，当是0时去右结点。在解码时，每次均需要站在根结点上，在对01码进行依次扫描时，遇到1就去左子结点，遇到0就去右结点，直至到达叶子结点上结束。再次站到根结点上，继续进行；每次到达结点上，就输出此结点上的信息元素，因为只有叶子结点上有信息元素，而其他结点上的信息元素为空值，则在输出时，仅仅是所需要的明文信息。二、算法流程图下图为哈夫曼树的生成过程中的主要算法（如图1）：图1 生成哈夫曼树下面是哈夫曼编码过程的大致过程（如图2）：图2 为huffman树的各节点进行编码下面是对指定文件内信息编码的大致过程（如图3）：图3 信息的编码下面是对文件内信息解码码的大致过程（如图4）：图4 信息的解码三、源代码#include stdio.h#include string.h#include stdlib.htypedef struct/*声明储存信息的结构体*/ char letter;/*字母*/ int weight;/*权值*/ int parent;/*父节点*/ int lchild;/*左子节点*/ int rchild;/*右子节点*/htnode,* huffmantree;typedef char * huffmancode;void select(huffmantree &ht,int i,int &s1,int &s2) int j,k;/*找出第一个单节点树*/ for(k=1;k=i;k+) if(htk.parent!=0)continue; s1=k; break; /*找出其中权重最小的树*/ for(j=1;j=i;j+) if(htj.parent!=0) continue; if(htj.weighthts1.weight) s1=j; /*找出第二个单节点树*/ for(k=1;k=i;k+) if(htk.parent!=0|k=s1) continue; s2=k; break; /*找出其中权重次小的树*/ for(j=1;j=i;j+) if(htj.parent!=0) continue; if(htj.weighthts2.weight&j!=s1) s2=j; void HuffmanTree(huffmantree &ht,int *w,char *zi,int n) int m,i,s1,s2; m=n*2-1;/*计算需要生成huffman树的节点数目*/ ht=new htnodem+1;/*因为起始从1开始，则为m+1*/for(i=1;i=n;i+)/*将26个英文字母付给26节点*/hti.letter=zii-1; for(i=1;i=m;i+) hti.weight=(i=n?wi-1:NULL);/*给前26个节点附上相应的权值，其余为空*/ hti.lchild=hti.rchild=hti.parent=0;/*初始化*/ for(i=n+1;i=m;i+)/*不断循环组合最终生成Huffman树*/ select(ht,i-1,s1,s2);/*找出其中权重最小的两个节点s1,s2*/ hti.lchild=s1; hti.rchild=s2;/*组合树左右子分别为s1,s2*/ hti.weight=hts1.weight+hts2.weight;/*组合树根节点权重为左右子之和*/ hts1.parent=hts2.parent=i;/*新树加入数组*/ void huffmancoding(huffmantree &ht,huffmancode &hc,int n) int i,f,c; int Istart=1; char *cd; hc=(huffmancode)malloc(n+1)*sizeof(char *);/*为hc动态分配内存*/ cd=(char*)malloc(n*sizeof(char);/*临时的code存储*/ cdn-1=0;/*在最后添加结束符*/ for(i=1;i=n;+i) Istart=n-1; /*按已生成的哈夫曼树，按照左0右1得到各个字符的哈夫曼编码*/ for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) if(htf.lchild=c)/*左0*/ cd-Istart=0; else/*右1*/ cd-Istart=1; hci=(char *)malloc(n-Istart)*sizeof(char); strcpy(hci, &cdIstart);/*将临时储存的code拷贝至hc中*/ free(cd);/*释放cd*/void main() char text300;/*声明储存源码或Huffman码的临时数组*/ int i,j,count,choice;/*储存字母数组*/ char zi26=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;/*储存字母对应权重的数组*/ int w26=64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; huffmantree ht; huffmancode hc; HuffmanTree(ht,w,zi,26);/*生成huffman树*/ huffmancoding(ht,hc,26);/*根据huffman树生成huffman码*/ FILE *fp;printf(1Encoding.n);printf(2Decoding.n); printf(Please choice function:);/*选择编码还是译码*/scanf(%d,&choice);if(choice=1)/*1为编码*/char file20;printf(Please choice the file:);/*输入需要编码的文件名*/scanf(%s,file);printf(*从%s文件读取字符串*n,file);if(fp=fopen(file,r)=NULL)printf(cannot open this filen); fgets(text,300,fp);/*从文件中读取字符串*/fclose(fp);printf(Source code is:);/*输出读取的字符串*/puts(text);printf(*Huffman编码见CodeFile.txt文件*n);if(fp=fopen(CodeFile.txt,w)=NULL)printf(cannot open this filen);for(i=0;istrlen(text);i+)/*将编码后的huffman码写入CodeFile.txt中*/fputs(hc(texti-A+1),fp);fclose(fp);else if(choice=2)/*2为译码*/printf(*从CodeFile.txt文件读取Huffman码并译码*n);if(fp=fopen(CodeFile.txt,r)=NULL)printf(cannot open this filen); fgets(text,10000,fp);/*从CodeFile.txt文件获取huffman码*/printf(The Huffman code is:);/*输出huffman码*/puts(text);j=strlen(text);count=51;/*总节点数量，即2n-1*/i=1;printf(The text is:);/*将huffman码翻译成对应字母并输出*/while(i=j)while(htcount.lchild!=0)/*因为是完全二叉树*/if(texti-1=0)/*用哈夫曼树，将输入的电码（变量c表示的）翻译成文本说明：变量名c在程序中*/ count=htcount.lchild;i+;continue;if(texti-1=1)count=htcount.rchild;i+;continue;/*显示由部分电码译码得到的字符，并准备对后面的电码进行译码*/printf(%c,htcount.letter);count=51;printf(n);四、运行结果下图是对SourceCode.txt文件信息进行编码，所得到的效果图（如图5所示）：图5 对SourceCode.txt文件进行编码下图是对CodeFile.txt文件中Huffman码进行译码，所得到的效果图（如图6所示）：图6 对CodeFile.txt文件中Huffman码进行译码五、遇到的问题及解决这部分我主要遇到了如下几个问题，其内容与解决方法如下所列：l 问题一：在生成Huffman tree时怎样寻找最小的和次小的单节点树？这个问题纠结了很久，最后通过上网查阅相关文档后我想出了以下解决方案。解决方法：首先通过一个for循环找出第一个单节点树，将其记为s1。接着又使用一个for循环不断地将26个英文字母与s1的权值比较，如果其小于s1的权值，则将其赋给s1，这样当出了这个for循环，s1即找出的最小单节点树。重复以上步骤，即可找出次小的单节点树s2。l 问题二：如何读取指定文件中的信息以及将信息写入指定文件？出现这个问题说明在学习C语言时基础掌握的不牢，对文件读写这部分知识不是很熟，在查阅过相关资料后，我发现这个问题真的很简单。解决方法：首先需要声明文件指针FILE *fp。根据输入文件名判断文件是否存在，如存在则打开相应文件，将其付给指针fp。通过fgetc方法获得文件中单个字符，fputc方法写入单个字符到文件中。也可以通过fgets方法获得字符串，fputs方法写入字符串到文件中。l 问题三：从文件中获取Huffman码进行译码时，发现不是预期的结果，而是打印出其他字母。首先我怀疑是不是在编码时就出现了问题，但是在打开储存Huffman码的CodeFile.txt后发现文件中的Huffman码并无错误。于是我确定了是在译码时产生的错误。解决方法：经过对代码进行检查，因为上文中索引变量i都是人为地让其从1开始，以便于与节点对应，但是在译码的循环体内，i需要从0开始，也就是说始终漏掉了开头一个数字，自然出现了这个问题。数组下标改为i-1结果就正确了。六、心得体会经历这次作业，我的收获颇多：首先，加深了对C语言运用的理解，学会不是目的，运