C语言程序设计课程设计报告——尹航、赵增阳组

哈尔滨工业大学英才学院哈尔滨工业大学英才学院 2012 本科本科 C 语言程序设计课程设计语言程序设计课程设计 报告报告 项目题目 项目题目 哈弗曼编码问题哈弗曼编码问题 班班 级 级 1236007 项目组编号 项目组编号 班班 第第 组组 项目组成员 项目组成员 姓名姓名 学号学号 尹航尹航 6123310701 赵增阳赵增阳 6123310704 指导教师 指导教师 赵玲玲赵玲玲 开始日期 开始日期 2013 年年 5 月月 28 日日 完成日期 完成日期 2013 年年 6 月月 20 日日 哈工大软件学院 2008 级本科 综合课程设计 报告 目 录 2012 级本科 C 语言程序设计课程设计 评价表 I 哈尔滨工业大学课程设计任务书 II 第 1 部分 项目开发计划 1 第 2 部分 系统分析 2 第 3 部分 系统设计 3 第 4 部分 系统实现及测试 4 第 5 部分 项目总结 5 参考文献 6 附录 7 哈工大软件学院 2008 级本科 综合课程设计 报告 1 2012 级本科 C 语言程序设计课程设计 评价表 题题 目目哈夫曼编码问题哈夫曼编码问题指导老师指导老师 赵玲玲赵玲玲 项项 目目 内内 容容 简简 介 介 250 字 字 本项目所编写程序用以实现以哈夫曼树 即最优二叉树的形式进行数据压缩 特点 在于每种字符长度是根据每一个源字符出现的估算概率而建立起来的 出现概率高的字 符使用较短的编码 反之出现概率低的则使用较长的编码 这便使编码之后的字符串的 平均期望长度降低 项目旨在于提高我们编写程序应用于解决具体问题的能力 项目的执行分为学习相关介绍性资料 大致编写框架 分工完成具体程序块 共同 解决难以完成的程序功能并 debug 改善并简化程序细节来提高程序可读性与简约程度 五个过程 最终得到的项目成果为可以将文本格式文档中的数据 压缩为哈弗曼编码表 示数据文件的程序 学学 号号姓姓 名名项目组内角色职责项目组内角色职责贡献排名贡献排名 平时扣分平时扣分成成 绩绩 6123310701尹航尹航程序编写和精简 程序编写和精简 50 报告填写报告填写 6123310704赵增阳赵增阳 程序框架制作和汇总 程序框架制作和汇总 PPT 制作 制作 50 报告填写报告填写 评评 委委 评评 分分 评选项评选项得分得分评选项评选项得分得分 项目规模 技术难度 工作量 20 分 项目文档及报告 20 分 项目实现结果 可运行演示 20 分 答辨表现 30 分 团队分工与协作情况 10 分 项目总分 100 分 项目评 价 项目规模及工作量 饱满 达到要求 不饱满 项目实现结果 良 好 有小问题 错误较多 项目文档及报告撰写 规范 较规范 不规范 未提交 答辩表示 优秀 良好 一般 较差 团队分工 及协作 很好 较好 一般 较差 签字签字课程负责人签字课程负责人签字 答辩日期答辩日期 年年 月月 日日 哈工大软件学院 2008 级本科 综合课程设计 报告 2 哈尔滨工业大学课程设计任务书 姓姓 名 名 尹航 赵增阳 院院 系 系 英才学院 专专 业 业 土木工程 班 号 1236007 任务起至日期 任务起至日期 2013 年 5 月 28 日 至 2013 年 6 月 20 日 课程设计题目 课程设计题目 哈弗曼编码问题 项目简介 项目简介 工作量 工作量 本项目所编写程序用以实现以哈夫曼树 即最优二叉树的形式进行数据压 缩 特点在于每种字符长度是根据每一个源字符出现的估算概率而建立起来的 出现概率高的字符使用较短的编码 反之出现概率低的则使用较长的编码 这便使编码之后的字符串的平均期望长度降低 项目旨在于提高我们编写程 序应用于解决具体问题的能力 项目的执行分为学习相关介绍性资料 大致编写框架 分工完成具体程序 块 共同解决难以完成的程序功能并 debug 改善并简化程序细节来提高程序 可读性与简约程度五个过程 最终得到的项目成果为可以将文本格式文档中的 数据 压缩为哈弗曼编码表示数据文件的程序 1 学习资料 确定方案思路 时间 约 3 小时 2 编写程序框架 时间 约 1 5 小时 代码量 78 行 3 编写哈弗曼树构建函数 编码输出函数 时间 约 7 小时 代码量 66 39 行 4 解决程序难点及程序出问题 时间 约 4 小时 代码量 难点处 40 行 5 连接程序块 时间 约 1 小时 代码量 连接部分 34 行代码 程序的整理 和精简 时间 约 3 5 小时 代码量 由 215 行代码简化到 140 行 6 分工完成报告的填写和 PPT 的制作 约 4 5 小时 总计 24 5 小时 编写 168 行 更改 89 行 最终完善结果 130 行 哈工大软件学院 2008 级本科 综合课程设计 报告 3 工作计划安排 工作计划安排 同组设计者及分工 同组设计者及分工 1 资料学习中 赵增阳 查找利用哈夫曼编码进行数据压缩的特点 原理 优势 尹航 学习哈夫曼树的编程思路并确定自己的编写方案 2 程序编写中 赵增阳 负责编写主函数及程序主体框架 尹航 负责编写哈夫曼树构建函数 哈夫曼编码的输出函数程序块 3 程序改进中 赵增阳 负责串联整体程序 将 main 函数与其他函数相关联 并整理 代码 提高程序的可读性 尹航 负责进行程序的精简 使代码更加简约 用高效的算法替代效率 低的算法 4 后期工作 赵增阳 负责 PPT 的制作 尹航 负责课程设计报告的填写 1 5 月 28 日 6 月 2 日 通过相关资料学习构建哈夫曼树的编程方法 并整理思路确定我们实现程序功能的方案 2 6 月 3 日 6 月 4 日 编写程序框架和主函数 并完成程序所需所有 变量的声明工作及实形参的关联 3 6 月 4 日 6 月 11 日 分工完成哈弗曼树构建函数 编码输出函数两 大主体程序块 4 6 月 12 日 6 月 14 日 共同讨论并解决程序难点及程序出现问题 5 6 月 15 日 6 月 16 日 整理代码 完成模块之间的连接 6 6 月 17 日 6 月 20 日 反复进行程序的精简 7 6 月 21 日 6 月 25 日 分工完成报告的填写和 PPT 的制作 哈工大软件学院 2008 级本科 综合课程设计 报告 4 第 1 部分 项目开发计划 1 1 项目要完成的工作 1 根据用户给出的文件 book txt 将其中的数据压缩为哈弗曼编码表示 数据文件 本项目要完成实现此功能程序的制作 2 生成字符与哈夫曼编码的对照表 以及用哈夫曼编码表示数据的文件 1 2 项目分工 表 1 2 1 项目分工 赵增阳1 查找题目的背景与内涵资料 2 编写程序结构主体框架 3 制作展示 ppt 尹航1 确定程序制作思路 2 编写哈夫曼树函数和代码输出函数 3 完成课程设计报告 1 3 项目计划安排 表 1 3 1 项目计划安排 5 月 28 日 6 月 2 日通过互联网 图书查找资料 向计算机 专业的同学和学长请教 以更深入的了 解题目的背景与内涵 6 月 3 日 6 月 4 日整理所得到的资料和素材 得出可行的 设计方案 并初步写出程序框架 6 月 4 日 6 月 11 日编写程序主体 哈夫曼树函数 输出函 数 6 月 15 日 6 月 20 日整理并精简代码 6 月 21 日 6 月 25 日完成课程设计报告 制作展示 ppt 准 备展示和答辩 哈工大软件学院 2008 级本科 综合课程设计 报告 5 第 2 部分 系统分析 2 1 系统需要的功能与性能 2 1 1 系统需要的功能系统需要的功能 1 可以根据用户给出的文件生成对应的哈夫曼码 2 根据生成的哈夫曼码压缩用户给出的文件 3 将生成的哈夫曼码和压缩后的文件分别打印到文件 2 1 2 系统需要的性能系统需要的性能 1 快速生成所需的哈夫曼码 2 根据生成的哈夫曼码快速无误的压缩指定文件 2 2 系统重点 难点 哈夫曼树构建 1 对哈夫曼树的理解 2 确定父代和它的两个儿代结点关系与位置的确定 3 找到合适的变量储存哈夫曼树 4 根据给定的文章构建哈夫曼树 文件输出 1 确定每个字符对应的哈弗曼编码每一位的值 由子代节点块与其父代 的关系 leftchild or rightchild 来确定子代层到父代层的路径应取 0 leftchild 还是 1 rightchild 以此类推直到没有父代 结果可以得到每种 字符对应 0 1 构成的字符串 2 输出结果如何表现 输出源文件中每种字符和生成的哈夫曼码的对照表 输出用生成的哈弗曼编码压缩的文件 哈工大软件学院 2008 级本科 综合课程设计 报告 6 第 3 部分 系统设计 3 1 总体设计 main 函数 定义相关变量和文 件 功能 构建哈夫曼树 输出 1 字符对照 表 2 压缩后文件 3 2详细设计 3 21 构建哈夫曼树 构建哈夫曼树 1 定义哈夫曼树中节点块的结构体 N 种字符时有 2N 1 个节点块 2 找到最小的两个频数的值及对应字符的 ASC 值 3 将找到的 sort 种字符的频数和 ASC 码存入结构体对应位置中 4 初始化余下 N 1 个父代节点块的信息 5 找到这些字符中频数第一第二低的两个字符的频数和 ASC 码 6 定义父代节点块中表示的字符组合的标号定义成类似 ASC 码的形式 7 重复 5 6 直到找完所有的字符 3 22 输出字符对照表 输出字符对照表 从结点结构体 value 中读取并输出字符的 ASC 码 判断该字符是其父代的 左儿子还是右儿子 若为左该位编码输出 0 为右输出 1 3 23 输出压缩文件 输出压缩文件 哈工大软件学院 2008 级本科 综合课程设计 报告 7 根据字符对照表和结点结构体 通过循环逐次输出压缩后的文 0 1 3 3 时序 1 进入函数 2 定义四个数组分别存储 每种字符的出现频数 整型数组 原始文件信 息 字符数组 字符的哈夫曼编码 二维整型数组 哈夫曼树 结构体数组 3 定义其他变量 以及相关文件 两个 分别存储字符对照表和压缩文件 4 存入原始信息 5 调用函数构建哈夫曼树 6 生成哈夫曼码 7 输出字符对照表 8 输出哈夫曼代码文件 哈工大软件学院 2008 级本科 综合课程设计 报告 8 第 4 部分 系统实现及测试 4 1 核心算法流程图 1 构建哈夫曼树 调用函数 HuffmanTree 传入相应形参 定义最小的两 个频数和他们 的编号 w1 w2 x1 x2 初始化 前 N 项 for i 0 i N i t i value i t i tweight weight i t i parent 1 t i lchild 1 t i rchild 1 读入出现的字符和其 ASCll 码 初始化后三项为 1 初始化 后 N 1 项 for i N i 2 N 1 i t i value 1 t i tweight 0 t i parent 1 t i lchild 1 t i rchild 1 存储几个字符的组合结点 初始化 w1 w2 为最大频数 的值 1000000 x1 x2 为 1 进入一层循环 循环 sort 文章中出现字符种类数 次 构建处所需的哈夫曼树 存在结构体数 组中 哈工大软件学院 2008 级本科 综合课程设计 报告 9 4 2 测试及运行结果 1 用户在 book txt 中输入想要压缩的文件 2 运行 encode c 3 生成两个文件 code txt 存储哈夫曼码 encode txt 存储压缩后文件 示例示例 运行前 进入二层循环判断 t j tweight w2 w1 x1 j w1 t j tweight 或 x2 j w2 t j tweight 循环 N i 次 找到此次大循环中的频数最 小的两个字符 包括多个字 符组合 w1 w2 w1 最小 给他们的父亲节点赋值 t x1 parent N i t x2 parent N i t N i tweight w1 w2 t N i rchild x1 t N i lchild x2 哈工大软件学院 2008 级本科 综合课程设计 报告 10 要压缩的文件 运行程序 哈工大软件学院 2008 级本科 综合课程设计 报告 11 生成文件 code txt 哈工大软件学院 2008 级本科 综合课程设计 报告 12 result txt 哈工大软件学院 2008 级本科 综合课程设计 报告 13 第 5 部分 项目总结 5 1 项目开发感想与收获 当今计算机应用在生活中可以说得是无处不在 因此作为二十一世纪的大学来说掌握程序开发技术 是十分重要的 而 C 语言又是最常见 功能最强大的一种高级语言 因此做好 C 语言课程设计是十分必 要的 而这次的课程设计实验正是对我们进入大学以来学习 C 语言结果的一次大考验 通过自己动手 发现问题和解决问题 同时认清许多自己的不足 平时没掌握的知识在实践中暴漏 但我们小组经过不 断的思考 查阅书籍和上网查资料 请教老师和学长 结合上机运行操作解决了许多问题 在课程设计过程中 收获知识 提高能力的同时 我也学到了很多人生的哲理 懂得怎么样去制定 计划 怎么样去实现这个计划 并掌握了在执行过程中怎么样去克服心理上的不良情绪 因此在以后的 生活和学习的过程中 我一定会把课程设计的精神带到自己的日常生活中 5 2 项目开发收获 我们不仅巩固 C 语言程序设计 课程学习的内容 掌握设计的基本方法 强化上机动手能力 还 进一步掌握了 数据类型 分支控制 循环控制 函数的定义及调用 结构体及数组 文件操作等 通 过课程设计 掌握了程序的局部测试 调试方法 建立程序系统调试 测试的基本概念和思想 学会较 大程序的系统测试和调试方法 通过这次课程设计使我们懂得了理论与实际相结合是很重要的 只有理论知识是远远不够的 只有 把所学的理论知识与实践相结合起来 从理论中得出结论 才能真正为社会服务 从而提高自己的实际 动手能力和独立思考的能力 哈工大软件学院 2008 级本科 综合课程设计 报告 14 参考文献 1 苏小红 王宇颖 孙志岗 C 语言程序设计 高等教育出版社