数据结构课程设计-赫夫曼编码系统

数据结构课程设计报告课程名称赫夫曼编码系统姓名学号专业班级指导教师二一二年十二月目录CONTENTS1课程小组211小组成员及分工22设计目的和要求23需求分析24设计说明241文件编码（加密）242文件解码（解密）35详细设计351程序主体结构352主要算法说明3521HUFFMAN树3522HUFFMAN编码5523字符权重计算6524字符解码96实验结果1061实验结果说明1062程序运行截图117设计体会128参考文献139附程序代码131课程小组11小组成员及分工2设计目的和要求通过课程设计，让学生进一步熟悉与巩固数据结构中常用算法，加深体会利用数据结构的算法解决实际问题的能力,培养学生进行复杂程序设计的技能，提高学生的思维能力、并促进其综合应用能力、分析能力和团队合作能力的提高。3需求分析随着网络信息科技的不断高速发展，网络上的问题也不断显露出来，特别是人们特别关注的安全隐私问题，所以文件的传输安全性要特别地亟待解决和提高。本次的课程设计以赫夫曼编码为题，设计出赫夫曼文件编码系统，旨在对文件中的内容进行分析、统计、处理，进而按照赫夫曼编码的理论，对文件进行简单加密。特别是，不同的文本文件有不同的字符处理形式，所以因此每一个文本都会有一个相应的密钥，用于对文本的解码。4设计说明本次编写的程序按着对文件的编码（加密）和解码（解密）的两大步骤展开。41文件编码（加密）首先选择文件编码程序。进入程序后，会要求操作人员选择将要编码的文件，并将其导入到程序中，程序正确导入文件后将会对文件从开始至结束扫描一遍，对文件中的字符进行统计，在最后计算出每个字符出现的频率，并将频率换算成每个字符相应的权重。然后根据得到的字符权重，构造赫夫曼树并因此完成赫夫曼编码（至此，文件的导入分析过程已完成）。然后让操作人员选择对文件进行编码。此时，程序将会继续打开文件，继续扫描一遍，并在扫描的过程中将扫描到得字符根据刚才编好的赫夫曼编码进行对照，将对应的赫夫曼编码写入另一个文件（即加密的文件），所以，如果用户代开加密的文件即看到里面全是二进制代码，并不能分析出里面究竟是什么内容。（至此，加密的文件应经生成）。最后，因为每个文件中的内容不同，所以每个文件的赫夫曼编码也不同，而赫夫曼编码是根据字符的权重生成的，所以每个文件都对应一个字符权重系列（即密钥），如果失去这个密钥，即使对文件进行了加密，也不同解密文件的内容，即文件加密失效，所以在生成加密文件后，一定要导出文件的字符权重（即密钥），以待之后的解码使用。（至此，文件的加密工作应经全部完成）。42文件解码（解密）文件的解码程序是一步完成的，即要求操作者首先将之前生成的字符权重（即密钥）导入程序，程序根据获取到得字符权重，调用赫夫曼编码子程序，进行赫夫曼编码。然后程序会提示操作者将加密后的文件导入程序中，程序会根据在程序中获取到的二进制编码与赫夫曼编码进行对照识别，显示出对应的字符，因此，文件的解密工作完成。5详细设计51程序主体结构程序主体结构分为文件编码与文件解码两个子程序。文件编码后分别导出编码后文件与文件密钥。文件解码需导入编码文件与文件密钥，然后显示文本内容。52主要算法说明521HUFFMAN树/HUFFMANTREELISTLIST为赫夫曼树TYPEDEFSTRUCTCHARDATA/存放字符数据INTWEIGHT/存放字符权重INTPARENT,LCHILD,RCHILD/分别为根、左子树、右子树HUFFMANTREE/STATICINFOINFO为存放字符权重的数组指针TYPEDEFSTRUCTCHARDATA/存放字符数据INTWEIGHT/存放字符权重STATIC/INTCODESIZECODESIZE为字符种类个数VOIDCREATHUFFMANTREEHUFFMANTREEINTLNODE,RNODEINTVALUE1,VALUE2HUFFMANTREEPTRLIMITCODESIZE21/LIMIT为赫夫曼树结点个数IFLISTHUFFMANTREEMALLOCSIZEOFHUFFMANTREELIMITNULLPRINTF“内存不足,操作失败N“EXIT0/初始化赫夫曼树各结点信息/FORI0,PTRLISTIDATAINFOIDATAPTRWEIGHTINFOIWEIGHTPTRPARENTPTRLCHILDPTRRCHILD1FORIDATA0PTRWEIGHT0PTRPARENTPTRLCHILDPTRRCHILD1/开始建立赫夫曼树/FORICODESIZEIDATACHPTRNUMBER1PTRNEXTCHARACTERLISTNEXTCHARACTERLISTNEXTPTRTYPENUMBERELSEWHILECURRENTNULLCURRENTCURRENTNEXTIFCURRENTNULLCURRENTNUMBERCHARACTERNUMBERELSEIFPTRDATAMALLOCSIZEOFDATANULLPRINTF“内存不足,操作失败N“EXIT0PTRDATACHPTRNUMBER1PTRNEXTCURRENTPREVIOUSNEXTPTRTYPENUMBERCHARACTERNUMBERFCLOSEFPCODESIZETYPENUMBERINFOSTATICMALLOCSIZEOFSTATICCODESIZECURRENTCHARACTERLISTNEXT/将统计好的字符权重信息存入权重文件中FORINTI0IDATAINFOIWEIGHTINTCURRENTNUMBER1000/CHARACTERNUMBERCURRENTCURRENTNEXT524字符解码/此代码用于比较查找赫夫曼编码BOOLCOMPAREDATACHARTEMPCODE,INTPOSITIONINCLUDEINCLUDEINCLUDE/赫夫曼树结构TYPEDEFSTRUCTCHARDATAINTWEIGHTINTPARENT,LCHILD,RCHILDHUFFMANTREE/字符权重结构TYPEDEFSTRUCTCHARDATAINTWEIGHTSTATIC/统计字符时所用到的链表结构TYPEDEFSTRUCTNODECHARDATAINTNUMBERSTRUCTNODENEXTDATA/赫夫曼代码结构TYPEDEFCHARHUFFMANCODE/创建赫夫曼树VOIDCREATHUFFMANTREEHUFFMANTREE/创建赫夫曼代码VOIDCREATHUFFMANCODEHUFFMANTREELIST,HUFFMANCODE/从文件中读取数据并计算各字符出现频率VOIDDATACOUNTSTATIC/文件编码程序VOIDFILEENCODING/创建文件编码VOIDCREATFILECODING/导出编码后文件VOIDEXPORTFILEENCODINGHUFFMANTREELIST,HUFFMANCODECODE,INTCODESIZE/导出文件中字符权重VOIDEXPORTCHARACTERWEIGHT/文件译码程序VOIDFILEDECODING/导入编码后的文件VOIDINPORTFILECODING/导入文件中字符权重VOIDINPORTCHARACTERWEIGHT/显示译码后的文件内容VOIDDISPLAYCONTEXTBOOLCOMPAREDATACHARTEMPCODE,INTVOIDBOUNDCHARCHARACTER,INTSIZE/赫夫曼树HUFFMANTREELIST/赫夫曼代码HUFFMANCODECODE/字符权重信息STATICINFO/字符种数INTCODESIZE/文件名CHARFILENAME30INTMAINCHARCHOICEWHILETRUESYSTEM“CLS“PRINTF“赫夫曼编码加密程序N“BOUND,25PRINTF“1文件编码N“PRINTF“2文件译码N“PRINTF“0退出程序N“BOUND,25PRINTF“请选择“FFLUSHSTDINCHOICEGETCHARSWITCHCHOICECASE1FILEENCODINGBREAKCASE2FILEDECODINGBREAKCASE0PRINTF“N“SYSTEM“PAUSE“RETURN0BREAKDEFAULTPRINTF“N您的输入有误,按任意键后请从新输入“GETCHBREAKVOIDCREATHUFFMANTREEHUFFMANTREEINTLNODE,RNODEINTVALUE1,VALUE2HUFFMANTREEPTRLIMITCODESIZE21IFLISTHUFFMANTREEMALLOCSIZEOFHUFFMANTREELIMITNULLPRINTF“内存不足,操作失败N“EXIT0FORI0,PTRLISTIDATAINFOIDATAPTRWEIGHTINFOIWEIGHTPTRPARENTPTRLCHILDPTRRCHILD1FORIDATA0PTRWEIGHT0PTRPARENTPTRLCHILDPTRRCHILD1FORICODESIZEIDATACHPTRNUMBER1PTRNEXTCHARACTERLISTNEXTCHARACTERLISTNEXTPTRTYPENUMBERELSEWHILECURRENTNULLCURRENTCURRENTNEXTIFCURRENTNULLCURRENTNUMBERCHARACTERNUMBERELSEIFPTRDATAMALLOCSIZEOFDATANULLPRINTF“内存不足,操作失败N“EXIT0PTRDATACHPTRNUMBER1PTRNEXTCURRENTPREVIOUSNEXTPTRTYPENUMBERCHARACTERNUMBERFCLOSEFPCODESIZETYPENUMBERINFOSTATICMALLOCSIZEOFSTATICCODESIZECURRENTCHARACTERLISTNEXTFORINTI0IDATAINFOIWEIGHTINTCURRENTNUMBER1000/CHARACTERNUMBERCURRENTCURRENTNEXTVOIDFILEENCODINGCHARCHOICEWHILETRUESYSTEM“CLS“PRINTF“文件编码程序N“BOUND,25PRINTF“1创建文件编码N“PRINTF“2导出文件编码N“PRINTF“3导出文件密钥N“PRINTF“0返回主菜单N“BOUND,25PRINTF“请选择“FFLUSHSTDINCHOICEGETCHARSWITCHCHOICECASE1CREATFILECODINGBREAKCASE2EXPORTFILEENCODINGLIST,CODE,CODESIZEBREAKCASE3EXPORTCHARACTERWEIGHTBREAKCASE0RETURNDEFAULTPRINTF“N您的输入有误,按任意键后请从新输入“GETCHBREAKVOIDCREATFILECODINGDATACOUNTINFOCREATHUFFMANTREELIST,INFO,CODESIZECREATHUFFMANCODELIST,CODE,CODESIZEPRINTF“N创建文件编码成功按任意键继续“GETCHVOIDEXPORTFILEENCODINGHUFFMANTREELIST,HUFFMANCODECODE,INTCODESIZEINTICHARCHCHAROUTFILENAME30FILEINFILE,OUTFILESYSTEM“CLS“INFILEFOPENFILENAME,“RB“PRINTF“N请创建导出文件名“FFLUSHSTDINGETSOUTFILENAMEIFOUTFILEFOPENOUTFILENAME,“WB“NULLPRINTF“输出文件创建失败N“EXIT0WHILECHFGETCINFILEEOFFORI0IDATADATAPTRNUMBERWEIGHTPTRNEXTCHARACTERLISTNEXTCHARACTERLISTNEXTPTRCHARACTERNUMBERFCLOSEFPCODESIZECHARACTERNUMBERIFINFOSTATICMALLOCSIZEOFSTATICCODESIZENULLPRINTF“内存不足,操作失败N“EXIT0PTRCHARACTERLISTNEXTFORINTICODESIZE1I0IINFOIDATAPTRDATAINFOIWEIGHTPTRNUMBERPTRPTRNEXTPRINTF“N文件导入成功下一步N“BOOLCOMPAREDATACHARTEMPCODE,INTPOSITIONCODESIZEPOSITIONIFSTRCMPTEMPCODE,CODEPOSITION0RETURNTRUERETURNFALSEVOIDDISPLAYCONTEXTINPORTCHARACTERWEIGHTCREATHUFFMANTREELIST,INFO,CODESIZECREATHUFFMANCODELIST,CODE,CODESIZEINPORTFILECODINGFILEFPINTPOSITIONINTENDCHARTEMPCODECHARCHFPFO