数据结构课程设计.doc

长安大学信息学院数据结构课程设计报告课 题： 赫哈曼编码的应用 姓 名： 王宝宝 学 号： 2402100305 专业班级： 24021003 指导教师： 张少博 2011 年 6月14日19 目 录一、需求分析3二、设计原理与概要4三、程序流程图.5四、程序源代码8 五、运行结果与验证.16六、设计总结.18 第一部分 需求分析本设计要求是对输入的一串字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。在当今信息爆炸的时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。赫夫曼编码的应用很广泛，如在音乐、电影、摄影、通信等领域都有它应用的身影，存储、分析、加工、处理是它们制作的第二阶段，怎样使制作出来的作品质量最好、体积最少，是关系产品受到青睐的原因之一。体积的大小也就是它所占据存储空间，在保证文件质量最好，又有效的节省存储空间，需要用最好的压缩存储解码算法，而赫夫曼编码是一种将信息转换成二进制编码有效的方法之一，赫夫曼编码是利用赫夫曼树求得的用于通信的二进制编码。而这次我们的课程设计对编码译码的要求不是太高，只是将大写字母或小写字母转化成二进制编码，或将二进编码转化成大写字母或小写字母，虽然功能有一点局限，但也是一次成功的尝试，能满足一般的需求。根据设计要求和分析，要实现本设计，必须实现以下几个方面的功能：（1）赫夫曼树的建立；（2）赫夫曼的编码生成；（3）编码文件的译码； 二 设计原理与概要 树中从根到每个叶子都有一条路径，对路径上的个分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符编码，这就是赫夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程就是解码。电报通信是传递文字的二进制形式的字符串。但在信息传递时，总希望长度尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码的长度为Li，电文中有n种字符，则电文编码的总长度为WiLi,若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，wiLi恰好为二叉树上带权路径的长度。设计要求：1. 初始化。根据下表给出的英文字母的使用频度，建立哈夫曼树。空格：0.2 E：0.105 T：0.071 O：0.0644A：0.063 N：0.059 I：0.054 R：0.053S：0.052 H：0.047 D：0.035 L：0.029C：0.023 U：0.0225 F：0.0221 M：0.021P：0.0175 Y、W：0.012 G：0.011 B：0.0105V：0.008 K：0.003 X：0.002 J、Q：0.001Z：0.0012. 编码。利用已建好的哈夫曼树，对电报正文进行编码。3. 译码。对编码好的内容进行译码。4. 打印编码。5. 打印哈夫曼树。 运行环境：Windows 95/98环境，Microsot Visual C+ 6.0 (简称VC)总流程图：输入需要编码的字符串（为大写或小写）统计字符的种类及各种字符出现的频率建立赫夫曼树 生成赫夫曼编码 建立各种字符的赫夫曼编码及编码文件从文件中读编码文件译码输出译码后的字符串定义各种变量 图（1）建立正文的编码文件的流程图： 图 （2）代码文件的译码流程图： 图（3） 程序源代码:#include stdio.h#include string.h#include malloc.h/权重信息数组static float weights=0.2,0.105,0.071,0.0644, 0.063,0.059,0.054,0.053, 0.052,0.047,0.035,0.029, 0.023,0.0225,0.0221,0.021, 0.0175,0.012,0.012,0.011, 0.0105,0.008,0.003,0.002, 0.001,0.001,0.001;/字符信息数组static char values= ,E,T,O,A,N,I, R,S,H,D,L,C,U, F,M,P,Y,W,G,B, V,K,X,J,Q,Z;/动态分配数组存储赫夫曼树typedef struct/节点权重值float weight;/节点对应的父节点unsigned int parent;/左子节点的索引值unsigned int lchild;/右子节点的索引值unsigned int rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼编码表typedef char *HuffmanCode;/返回i个节点中权值最小的树的根节点序号int min(HuffmanTree t,int i)int j,flag;float k=1.0;/逐个迭代求解最小权重for(j=1;j=i;j+)if(tj.weights2)temp=s1;s1=s2;s2=temp;/根据节点的权重值数组，构造赫夫曼树，同时求解每个节点的编码void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,float *w,int n)/中间变量int m,i,s1,s2,start;unsigned c,f;HuffmanTree p;char *cd;/节点个数至少为2if(n=1)/直接返回return;/所需节点总数m=2*n-1;/创建存储赫夫曼树的数组，0号单元留空HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/初始化终端节点for(p=HT+1,i=1;i=n;+i,+p,+w)(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;/初始化非终端节点for(;i=m;+i,+p)(*p).weight=0.0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;/创建赫夫曼树，核心算法for(i=n+1;i=m;+i)select(HT,i-1,s1,s2);/更新终端节点的信息HTs1.parent=HTs2.parent=i;/更新非终端节点的子节点的索引值HTi.lchild=s1;HTi.rchild=s2;/更新非终端节点的权重值HTi.weight=HTs1.weight+HTs2.weight;/创建存储节点赫夫曼编码的数组HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/中间变量cd=(char*)malloc(n*sizeof(char);/字符串结束符cdn-1=0;for(i=1;i=n;i+)start=n-1;/根据节点的父节点索引值求解节点的赫夫曼编码for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)/左分支为0cd-start=0;else/右分支为1cd-start=1;/动态分配对应编码存储空间大小HCi=(char*)malloc(n-start)*sizeof(char);/字符串拷贝strcpy(HCi,&cdstart);/释放内存空间free(cd);/将电报正文进行编码void coding(HuffmanCode HC)/索引变量int index;/电报正文索引值int textIndex;/电报正文字符的索引值int valueIndex;/电报正文包含的字符个数int teleLength;/电报正文字符对应的赫夫曼编码表中的索引int *codeIndex;/中间变量，存储电报正文char *teleText;/中间变量，用于存储电报正文的赫夫曼编码char *huCoding; /电报正文对应赫夫曼编码的总长度,初始化长度为0int codeLength=0;/编码，根据已建好的赫夫曼树，对电报正文进行编码printf(please input telegram text length,eg.len(ASD)=3:);scanf(%d,&teleLength);/分配用于存储编码表索引值的存储空间codeIndex=(int*)malloc(teleLength*sizeof(int);/分配用于存储电文字符的存储空间teleText=(char*)malloc(teleLength*sizeof(char);printf(please input telegram text,eg.ASD:);/输入电报正文字符串scanf(%s,teleText);/根据赫夫曼编码表对电报正文进行编码for(textIndex=0;textIndex96)textChar=textChar-32;/如果电报正文中包含非法字符直接返回if(textChar=64)|(textChar=91)|(textChar=123)printf(something wrong with your input telegram text %s!n,teleText);return;/依次查找对应字符for(valueIndex=1;valueIndex=27;valueIndex+)if(valuesvalueIndex-1=textChar)/累计编码的索引值codeIndextextIndex=valueIndex;/找到对应字符,累计编码长度值codeLength+=strlen(HCvalueIndex);/终止内层循环break;/动态分配存储电文编码的内存空间huCoding=(char*)malloc(codeLength+1)*sizeof(char);/初始化上述内存数据for(index=0;index=codeLength;index+)/字符串结束符huCodingindex=0;/组装电文编码信息for(textIndex=0;textIndexstrlen(teleText);textIndex+)/编码字符串的连接huCoding=strcat(huCoding,HCcodeIndextextIndex);printf(telegram Huffman code:%sn,huCoding);/释放内存空间free(teleText);free(codeIndex);free(huCoding);/将电报正文的赫夫曼编码进行译码操作void decoding(HuffmanTree HT)/索引变量int index;/记录临时索引值int tempIndex=53;/单个编码char huCode;/电文编码的长度int huCodeLen;/电文字符串（字符数组）char *huCodes;/赫夫曼树的节点HTNode htNode;/编码，根据已建好的赫夫曼树，对电报正文进行编码printf(please input telegram Huffman code length,eg.len(10110110)=8:);scanf(%d,&huCodeLen);/分配用于存储电文字符编码的存储空间huCodes=(char*)malloc(huCodeLen*sizeof(char);printf(please input telegram Huffman code,eg.10110110=AI:);/输入电报正文的编码字符串scanf(%s,huCodes);/获取根节点htNode=HT53;/遍历赫夫曼树,依次检索编码信息for(index=0;indexstrlen(huCodes);index+)/获取单个编码字符huCode=huCodesindex;/没有找到对应的编码字符if(tempIndex=0)printf(something wrong with your input telegram Huffman code %s!n,huCodes);return;if(huCode=1)/向右遍历if(HThtNode.rchild.lchild=0 & HThtNode.rchild.rchild=0)/遍历至叶子节点,找到一个电文子字符tempIndex=htNode.rchild;printf(%c,valuestempIndex-1);/再次指向根节点htNode=HT53;else/继续遍历，记录当前节点的信息tempIndex=htNode.rchild;htNode=HTtempIndex;else if(huCode=0)/向左遍历if(HThtNode.lchild.lchild=0 & HThtNode.lchild.rchild=0)/遍历至叶子节点,找到一个电文子字符tempIndex=htNode.lchild;printf(%c,valuestempIndex-1);/再次指向根节点htNode=HT53;else/继续遍历，记录当前节点的信息tempIndex=htNode.lchild;htNode=HTtempIndex;else/输入电文编码有误，结束本次译码操作printf(something wrong with your input telegram Huffman code %s!n,huCodes);return;printf(n);/打印赫夫曼树void printHuffmanTree(HuffmanTree HT)int index;/赫夫曼树节点HTNode htNode;printf(Huffman tree table:n);printf( WEIGHT PARENT LCHILD RCHILDn);/m=2*n-1for(index=1;index54;index+)/获取当前树节点htNode=HTindex;/依次输出节点的权重值和孩子节点的索引值printf(%12.4f%5d%6d%7dn,htNode.weight,htNode.parent,htNode.lchild,htNode.rchild);void printHuffmanCode(HuffmanCode HC)/索引变量int index;printf(Huffman code table:n);/依次打印每个关键字对应的赫夫曼编码for(index=1;index=27;index+)/显示空格字符if(index=1)printf(%7c - ,_);elseprintf(%7c - ,valuesindex-1);/打印对应的赫夫曼编码 printf(%sn,HCindex);void main()/电文的赫夫曼编码char c;HuffmanTree HT;HuffmanCode HC; /创建赫夫曼树，同时求解赫夫曼编码HuffmanCoding(HT,HC,weights,27);/printf(Huffman tree has been created!);/scanf(