logo资料库

数据结构课程设计 哈夫曼编码的数据压缩解压.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.83M 资料格式：doc 举报 版权申诉
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
资料共24页，剩余部分请下载后查看
    1.1课程设计目的
    1.2课程设计名称及内容
    1.3任务和要求
    二、算法设计
    2.1设计思想：
    2.2 算法思想：
    2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树
    2.2.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩
    2.2.5解码压缩即根据Huffman树进行译码
    2.3 主要模块说明
    2.4 部分重要函数的实现：
    三、用户手册
    四、测试结果
    4.1 压缩过程：
    4.2 解压过程
    4.4 显示帮助界面：
    五、总结
    六、参考资料
    七、附录
    7.1源代码
    7.2 运行结果
    合肥学院 计算机科学与技术系 课程设计报告 2010～2011 学年第二学期 课 程 课 程 设 计 名 称 C++课程设计 基于哈夫曼编码的数据压缩/解压程序 学 生 姓 名 龚天棚 学 号 专 业 班 级 1012091010 网络工程（1）班 指 导 教 师 项响琴、徐静 2011 年 6 月
    目 录 一、需求分析....................................................................................................... - 3 - 1.1 课程设计目的........................................................................................... - 3 - 1.2 课程设计名称及内容...............................................................................- 3 - 1.3 任务和要求.............................................................................................. - 3 - 二、算法设计....................................................................................................... - 4 - 2.1 设计思想：............................................................................................... - 4 - 2.2 算法思想：.............................................................................................. - 5 - 2.3 主要模块说明.......................................................................................... - 5 - 2.4 部分重要函数的实现：..........................................................................- 6 - 三、用户手册....................................................................................................... - 6 - 四、测试结果....................................................................................................... - 8 - 4.1 压缩过程：............................................................................................ - 8 - 4.2 解压过程................................................................................................ - 9 - 4.3 显示文本内容.......................................................................................... - 9 - 4.4 显示帮助界面：....................................................................................- 10 - 五、总结............................................................................................................. - 10 - 六、参考资料..................................................................................................... - 11 - 七、附录............................................................................................................. - 12 - 7.1 源代码..................................................................................................... - 12 - - 2 -
    7.2 运行结果................................................................................................ - 22 - 一、需求分析 1.1 课程设计目的 将理论教学中涉及到的知识点贯穿起来，对不同的数据类型、程序控制结构、数据结 构作一比较和总结，结合设计题目进行综合性应用，对所学知识达到融会贯通的程度。通 过课程设计，学生在下述各方面的能力应该得到锻炼： （1）进一步巩固、加深学生所学专业课程《C++程序设计语言》的基本理论知识，理 论联系实际，进一步培养学生综合分析问题，解决问题的能力。 （2）全面考核学生所掌握的基本理论知识及其实际业务能力，从而达到提高学生素 质的最终目的。 （3）利用所学知识，开发小型应用系统，掌握运用 C++语言编写调试应用系统程序， 训练独立开发应用系统，进行数据处理的综合能力。 （4）对于给定的设计题目，如何进行分析，理清思路，并给出相应的数学模型。 （5）掌握结构化程序设计方法，熟悉面向对象程序设计方法。 （6）熟练掌握 C++语言的基本语法，灵活运用各种数据类型。 （7） 进一步掌握在集成环境下如何调试程序和修改程序。 1.2 课程设计名称及内容 课程设计名称：基于哈夫曼编码的数据压缩/解压程序 设计内容：将任意一个指定的文本文件中的字符进行哈夫曼编码,生成一个编码文件 (压缩文件);反过来,可将一个压缩文件解码还原为一个文本文件。 1.3 任务和要求 1)可设计一个菜单: Q----Quit L----List Text Document D----Decoding C----Coding 2)选择 C 时: 输入一个待压缩的文本文件名称(可带路径)。 如:D:\lu\lu.txt 统计文本文件中各字符的个数作为权值,生成哈夫曼树； 将文本文件利用哈夫曼树进行编码,生成压缩文件。 压缩文件名称=文本文件名.COD 如:D:\lu\lu.COD 压缩文件内容=哈夫曼树的核心内容+编码序列 3) 选择 D 时: 输入一个待解压的压缩文件名称(可带路径 ) 如:D:\lu\lu.COD - 3 -
    从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码； 生成(还原)文本文件。 文件文件名称=压缩文件名+"_new.txt" 如:D:\lu\lu_new.txt 4)选择 L 时： 输入一个待压缩的文本文件名称(可带路径)。 如:D:\lu\lu_new.txt 显示出该文本文件的内容 5)功能扩展(自己定制)： 编码使用二进制位,利用位运算进行真正的数据压缩。 可对任何文件进行压缩。 显示出各种重要信息,如压缩率,各字符的哈夫曼编码表。 2.1 设计思想： 二、算法设计 建立哈夫曼 树 统计字符，得出统 计出字符 的权 值 n 生成哈夫曼树 根据哈夫曼树编 根据哈夫曼树解 码 码 对编码进行压缩 对二进制文件进 行解码 生成二进制文件 生成对应文件 - 4 -
    2.2 算法思想： 2.2.1 输入要压缩的文件 首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择 所要执行的 项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的 名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进 行压缩。若打不开，则继续输入。 2.2.2 读文件并计算字符频率 文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组 空间， 用读取的字符减去字符结束符作为下标记录字符的频率。 2.2.3 根据字符的频率，利用 Huffman 编码思想创建 Huffman 树 将所记录的字符的频率作为权值来创建 Huffman 树，依次选择权值最小的两个字符 作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶 子结点。 2.2.4 由创建的 Huffman 树来决定字符对应的编码，进行文件的压缩 根据创建的 Huffman 树来确定个字符的 01 编码，左孩子为 0，右孩子为 1。读取文 件，依次将每个字符用他们的编码表示，即完成一次编码。 2.2.5 解码压缩即根据 Huffman 树进行译码 读取编码文件，依据创建的 Huffman 树，定义一个指针指向根结点。从根结点开始， 每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩 子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点 为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输 出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件 2.3 主要模块说明 下面是该系统的模块 首先定义一个结构体： struct head { unsigned char b; long count; int parent,lch,rch; char bits[256]; } header[512],tmp; 然后是实现各个功能的函数： //记录字符 //权重 //定义双亲，左孩子，右孩子 //存放哈夫曼编码的数组 //头部一要定设置至少 512 个,因为结点最多可 达 256,所有结点数最多可达 511 显示文本文件的内容 void show() unsigned char ctoa(char a[]) 将数组的前八位转成二进制形式 bit 位 char *code(unsigned char temp,int leafnum) 寻找对应字符的编码串，并返回 void compress(char *infilename,char *outfilename) 对文本编码函数 void uncompress(char *infiname,char *outfilename) 对压缩文件解码 void ctoa(unsigned char a,char code[]) int strcmp1(char buf[],struct head head[],int n,unsigned char &c) 字符转为二进制形式存入 8 位数组 - 5 -
    将 buf 字符串与 header[i].bits[]中匹配，成功后对应的字符由 c 带回 void strcpy1(char buf[],char a[],int) 将字符串 a 中长度为 j 的部分复制到 buf 数组中 最后是主函数： 在主函数中含有菜单函数 void MainMenu()和帮助函数 void help()，最后通过 switch 语句，调用各种函数，分别完成各自的功能。 2.4 部分重要函数的实现： void compress(char *infilename,char *outfilename)的实现： 1）记录文件中字符频度； 2）根据频度建树； 3）根据哈夫曼树编码； 4）对文件进行编码，写入新文件(核心)； 5）将字符编码对照表写入文件； 6) 将文件的哈夫曼编码输出到显示器上。 void compress(char *infilename,char *outfilename)的实现： 1）读入必要的数据； 2) 读入编码对照表，放入 header[i].bits[]数组中； 3) 对读入的编码对照表进行排序，长度短的排在前面； 4) 将编码读入内容，进行解码工作。 三、用户手册 运行后的主界面会提示用户进行想要的操作。 1）编码（压缩文件）操作。 若用户想要对某一文件进行压缩，则按主界面的提示按“C”，然后界面提示输入进行 压缩操作的文件路径和文件名，输入完成后按回车键，此时界面会提示输入压缩后文件的 保存路径及其文件名，输入完成后再按回车键，便可完成编码，同时会显示出各字符的哈 夫曼编码，系统也会提示用户压缩文件过程结束。 - 6 -
    2）译码（还原文件）操作 若用户想对某一压缩文件进行解压操作，则按主界面的提示按“D”，然后界面提示输 入进行解压操作的文件路径和文件名，完成输入后按回车键，此时界面会提示输入解压后 的文件的保存路径及其文件名，输入完成后再按回车键，便可完成译码，系统提示用户还 原文件过程结束。 3） 显示数据内容 若用户想知道文本输入的内容，可输入“L”， 然后界面提示输入文本文件的路径 和文件名，完成输入后按回车键，界面会出现文本的内容。 4）帮助操作 若用户不知道怎么使用该软件，则按主界面的提示按“H”，然后界面会出现教您怎 么使用该软件的界面。 - 7 -
    5）操作失败后的界面提示，若用户输入的文件路径和文件名错误，则界面会提示用 户输出文件打开失败。 用户根据需求，在操作过程中按“Q”可随时退出系统。 四、测试结果 4.1 压缩过程： 在 D 盘中建立一个文本文档，并命名为 123.txt。 通过程序编译： - 8 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料