文档介绍：数据结构课程设计设计题目:Huffmancoding年级专业:信息安全04-01班学生姓名:张栋学生学号: 20042623指导老师:胡学钢时间:2006/6/13目录摘要…………………………………………………3相关函数介绍………………………………………3概要设计:算法设计和数据结构设计……………4程序调试与测试……………………………………8设计心得……………………………………………9改进方向及创新应用方向…………………………10参考文献……………………………………………11程序清单……………………………………………11摘要:课题八:采用HUFFMAN编码思想实现文件的压缩和恢复功能,并提供压缩前后的占用空间之比。要求:描述压缩基本符号的选择方法;运行时的压缩原文件的规模应不小于5K;提供恢复文件与原文件的相同性的对比功能;关键词:Haffman算法,压缩,解压缩KeyWords:HaffmanAlgorithm,Zip,UnZip核心算法---HUFFMAN算法:(1)根据给定的n个权值{w1,w2,……,wn}构成n棵二叉树的集合F={T1,T2,……,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空。(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。(3)在F中删除这两棵树,同时将所得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是HUFFMAN树。HUFFMAN树可用于构造代码总长度最短的编码方案。方法如下:设需要编码的字符集合为{d1,d2,……,dn},各个字符在电文中出现的次数集合为{w1,w2,……,wn},以d1,d2,……,dn作为叶结点,以w1,w2,……,wn作为各叶结点的权值构造一棵二叉树,规定HUFFMAN树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称为HUFFMAN编码。相关函数介绍压缩模块voidfile_change(charchar_data[])目标压缩文件读取函数huffbitrechange_list(char*char_data)整理输入的字符串函数huffbitrepaixu_increasing(huffbitrebitre)递增排序函数huffbitrebuildhufftree(huffbitrebitre)排完序的字符串建立huffman树函数voidcodeHTree(huffbitretree,KEY*KEY)对huffman树进行编码,并转换储存结构,获得编码字典函数voidhuffmancode(char*char_data,KEY*KEY,char*codestring)将整个字符串转化为0-1的字符串函数voidwriteKey(huffbitretree)保存编码后的解码树voidwriteCode(char*a)保存编码后的压缩文件voiddeleteNode(huffbitretree)释放huffman树所占用的空间解压缩模块:voidreadKey(huffbitretree)读取编码树voidreadCode(constchar*char_bits)读取压缩文件并转换为0-1字符串huffbitrebuildhufftree(huffbitrebitre)建立huffman树voidcodeHTree(huffbitretree,KEY*KEY)对huffman树进行编码,并转换储存结构,获得编码字典voiddecodeHTree(huffbitretree,char*code,char*filestring)解码,即将0-1码转化为字符串voidwriteFile(char*char_data)保存解码后的文件voiddeleteNode(huffbitretree)释放huffman树所占用的空间占空比计算模块:pared()占空比计算主调函数streamoffget_length()计算文件大小函数主函数调用的几个功能函数:mand()//从键盘读入指令概要设计:算法设计和数据结构设计压缩部分构建huffman树部分即摘要中介绍的算法数据结构设计(注:此结构分析来自信息论设计实验册)对于HUFFMAN树编码问题,在构造HUFFMAN树时要求能方便地实现从双亲结点到左右孩子结点的操作,在进行HUFFMAN编码时又要求能方便地实现从孩子结点到双亲结点的操作。因此,设计HUFFMAN树的结点存储结构为双亲孩子存储结构。二叉树结点的双亲孩子存储结构既可以采用常规指针实现,也可以用仿指针实现。在本程序中我们采用的是仿真指针实