数据结构课程设计哈夫曼编码

数据结构与算法数据结构与算法 课程设计课程设计 2009 2010 学年第二学期第学年第二学期第 20 周 周 指导教师 指导教师 王王老师老师 班级 班级 计算机科学与技术 计算机科学与技术 3 班 班 学号 学号 姓名 姓名 2 数据结构与算法数据结构与算法 课程设计课程设计 目目 录录 一 前言 1 摘要 2 数据结构与算法 课程设计任务书 二 实验目的 三 题目 赫夫曼编码赫夫曼编码 译码器译码器 1 问题描述 2 基本要求 3 测试要求 4 实现提示 四 需求分析 具体要求 五 概要设计 六 程序说明 七 详细设计 八 实验心得与体会 3 前言前言 1 1 摘要摘要 随着计算机的普遍应用与日益发展 其应用早已不局限于简单的数值运算 而涉及到问题的分析 数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作 算法与数据结构的学习就是为以 后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论 方法和技术基础 算法与数据结构旨在分析研究计算机加工的数据对象的特性 以便选择适当的数据结构和存储结 构 从而使建立在其上的解决问题的算法达到最优 数据结构是在整个计算机科学与技术领域上广泛被使用的术语 它用来反映一个数据的内部构成 即一个数据由那些成分数据构成 以什么方式构成 呈什么结构 数据结构有逻辑上的数据结构和物 理上的数据结构之分 逻辑上的数据结构反映成分数据之间的逻辑关系 而物理上的数据结构反映成 分数据在计算机内部的存储安排 数据结构是数据存在的形式 数据结构 主要介绍一些最常用的数据结构 阐明各种数据结构内在的逻辑关系 讨论其在计 算机中的存储表示 以及在其上进行各种运算时的实现算法 并对算法的效率进行简单的分析和讨论 数据结构是介于数学 计算机软件和计算机硬件之间的一门计算机专业的核心课程 它是计算机程序 设计 数据库 操作系统 编译原理及人工智能等的重要基础 广泛的应用于信息学 系统工程等各 种领域 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理 通过课 程设计可以提高学生的思维能力 促进学生的综合应用能力和专业素质的提高 2 2 数据结构与算法数据结构与算法 课程设计任务书课程设计任务书 数据结构与算法 是计算机专业重要的核心课程之一 在计算机专业的学习过程中占有非常重 要的地位 数据结构与算法课程设计 就是要运用本课程以及到目前为止的有关课程中的知识和技 术来解决实际问题 特别是面临非数值计算类型的应用问题时 需要选择适当的数据结构 设计出满 足一定时间和空间限制的有效算法 本课程设计要求同学独立完成一个较为完整的应用需求分析 并在设计和编写具有一定规模程序 的过程中 深化对 数据结构与算法 课程中基本概念 理论和方法的理解 训练综合运用所学知识 处理实际问题的能力 强化面向对象的程序设计理念 使自己的程序设计与调试水平有一个明显的提 高 4 二 实验目的二 实验目的 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构 以及对数据的各种操作 因此 主要有三个方面的内容 数据的逻辑结构 数据的物理存储结构 对数据的操作 或算法 通常 算 法的设计取决于数据的逻辑结构 算法的实现取决于数据的物理存储结构 数据结构是信息的一种组 织方式 其目的是为了提高算法的效率 它通常与一组算法的集合相对应 通过这组算法集合可以对 数据结构中的数据进行某种操作 在当今信息时代 信息技术己成为当代知识经济的核心技术 我们时刻都在和数据打交道 比如 人们在外出工作时找最短路径 在银行查询存款 通过互联网查新闻 以及远程教育报名等 所有这 些都在与数据发生关系 实际上 现实世界中的实体经过抽象以后 就可以成为计算机上所处理的数 据 数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的 关系和操作的学科 数据结构是介于数学 计算机软件和计算机硬件之间的一门计算机专业的核心课 程 它是计算机程序设计 数据库 操作系统 编译原理及人工智能等的重要基础 广泛的应用于信 息学 系统工程等各种领域 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理 通过课 程设计可以提高学生的思维能力 促进学生的综合应用能力和专业素质的提高 通过此次课程设计主 要达到以下目的 了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力 初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方法和技能 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 训练用系统的观点和软件开发一般规范进行软件开发 培养软件工作者所应具备的科学的 工作方法和作风 5 三 题目三 题目 赫夫曼编码赫夫曼编码 译码器译码器 1 问题描述问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率 缩短信息传输时间 降低传输成本 这要求 在发送端通过一个编码系统对待传输数据预先编码 在接收端将传来的数据进行译码 复原 对于 双工信道 即可以双向传输信息的信道 每端都需要一个完整的编 译码系统 试为这样的信息收发 站编写一个赫夫曼码的编 译码系统 2 基本要求基本要求 一个完整的系统应具有以下功能 1 I 初始化 Initialization 从终端读入字符集大小 n 以及 n 个字符和 n 个权值 建立赫夫曼树 并将它存于文件 hfmTree 中 2 E 编码 Encoding 利用已建好的赫夫曼树 如不在内存 则从文件 hfmTree 中读入 对文件 ToBeTran 中的正文进行编码 然后将结果存入文件 CodeFile 中 3 D 译码 Decoding 利用已建好的赫夫曼树将文件 CodeFile 中的代码进行译码 结果存入文件 Textfile 中 以下为选做 以下为选做 4 P 印代码文件 Print 将文件 CodeFile 以紧凑格式显示在终端上 每行 50 个代码 同时将此字 符形式的编码文件写入文件 CodePrin 中 5 T 印赫夫曼树 Tree printing 将已在内存中的赫夫曼树以直观的方式 比如树 显示在终端上 同时将此字符形式的赫夫曼树写入文件 TreePrint 中 3 测试要求测试要求 1 已知某系统在通信联络中只可能出现八种字符 其频率分别为 0 05 0 29 0 07 0 08 0 14 0 23 0 03 0 11 试设计赫夫曼编码 2 用下表给出的字符集和频度的实际统计数据建立赫夫曼树 并实现以下报文的编码和译码 THIS PROGRAME IS MY FAVORITE 字符ABCDEFGHIJKLM 频度1866413223210321154757153220 字符NOPQRSTUVWXYZ 频度5763151485180238181161 4 实现提示实现提示 1 编码结果以文本方式存储在文件 Codefile 中 2 用户界面可以设计为 菜单 方式 显示上述功能符号 再加上 Q 表示退出运行 Quit 请用 户键入一个选择功能符 此功能执行完毕后再显示此菜单 直至某次用户选择了 Q 为止 3 在程序的一次执行过程中 第一次执行 I D 或 C 命令之后 赫夫曼树已经在内存了 不必再读入 每次执行中不一定执行 I 命令 因为文件 hfmTree 可能早已建好 6 四 四 具体要求具体要求 课程设计成果的内容必须由以下四个部分组成 缺一不可 1 上交源程序 学生按照实验题目的具体要求所开发的所有源程序 应该放到一个文件夹中 2 上交程序的说明文件 保存在 txt 中 在说明文档中应该写明上交程序所在的目录 上交程 序的主程序文件名 如果需要安装 要有程序的安装使用说明 3 设计报告 保存在 word 文档中 文件名要求 按照 姓名 学号 设计题目 起名 如文 件名为 张三 XXX 赫夫曼编码 doc 打印稿用 A4 纸 其中包括 题目 实验目的 需求分析 在该部分中叙述实现的功能要求 概要设计 在此说明每个部分的算法设计说明 可以是描述算法的流程图 每个程序中使用的存储结构设 计说明 如果指定存储结构请写出该存储结构的定义 详细设计 各个算法实现的源程序 对每个题目要有相应的源程序 可以是一组源程序 每个功能模块采用 不同的函数实现 源程序要按照写程序的规则来编写 要结构清晰 重点函数的重点变量 重点功 能部分要加上清晰的程序注释 调试分析 测试数据 测试输出的结果 时间复杂度分析 和每个模块设计和调试时存在问题的思考 问题 是哪些 问题如何解决 算法的改进设想 总结 总结可以包括 设计过程的收获 遇到问题及解决问题过程的思考 程序调试能力的思考 对数 据结构这门课程的思考 在设计过程中对 数据结构 课程的认识等内容 4 考核成绩评定标准 本课程设计的评价由三部分组成 包括程序演示 50 课程设计报告 30 回答教师提问 20 1 程序演示 优功能完善 全部测试正确 并且能够对局部进行完善 良功能完善 但测试欠缺 中功能基本完善 但程序尚有部分错误 及格完成内存中赫夫曼编码 译码 但不涉及文件操作 不及格功能不完善 且程序错误较多 无法运行 2 课程设计报告 7 1 优包括设计内容 设计思想 已经完成的任务及达到的目标 设计思路清晰 书写 条理清楚 源程序结构合理 清晰 注释说明完整 有对本次课程设计的心得体会 2 良包括设计内容 设计思想 已经完成的任务及达到的目标 设计思路基本清晰 书写条理基本清楚 源程序结构合理 清晰 注释说明基本完整 有对本次课程设计的心得 体会 3 中课程设计报告内容基本完整 思路较清晰 书写基本清楚 源程序结构尚可 有 注释说明但不完整 4 及格课程设计报告内容基本完整 思路较差 书写尚清楚 5 5 不及格 课程设计报告内容不完整 书写没有条理 3 回答教师提问 1 优能回答教师提出的所有问题 并完全正确 思路清晰 2 2 良基本能回答教师提出的所有问题 有些小错误 3 3 中基本能回答教师提出的问题 少数问题回答错误或不清楚 4 4 及格能回答教师提出的问题 但较多问题回答错误或不能回答 5 5 不及格基本不能回答教师提出的问题 8 4 概要设计 1 问题分析哈夫曼树的定义 1 哈夫曼树节点的数据类型定义为 typedef struct 赫夫曼树的结构体 char ch int weight 权值 int parent lchild rchild htnode hfmtree 2 所实现的功能函数如下 1 void hfmcoding hfmtree int weight 权值 int parent lchild rchild htnode hfmtree typedef char hfmcode void Select hfmtree for j 1 j a j if HT j parent 0 x j break for i j 1 i a i if HT i weight HT x weight 选出最小的节点 for j 1 j a j if HT j parent 0 break 10 for i j 1 i a i if HT i weighty p1 y p2 x else p1 x p2 y void hfmcoding hfmtree int p1 p2 char cd z if n 1 return m 2 n 1 HT hfmtree malloc m 1 sizeof htnode for i 1 i n i 初始化 n 个叶子结点 printf 请输入第 d 字符信息和权值 i scanf c d while getchar n continue HT i ch z HT i weight w HT i parent 0 HT i lchild 0 HT i rchild 0 for i m i 初始化其余的结点 11 HT i ch 0 HT i weight 0 HT i parent 0 HT i lchild 0 HT i rchild 0 for i n 1 i m i 建立赫夫曼树 Select HT i 1 HT p1 parent i HT p2 parent i HT i lchild p1 HT i rchild p2 HT i weight HT p1 weight HT p2 weight HC hfmcode malloc n 1 sizeof char cd char malloc n sizeof char cd n 1 0 for i 1 i n i 给 n 个字符编码 start n 1 for c i f HT i parent f 0 c f f HT f parent if HT f lchild c cd start 0 else cd start 1 HC i char malloc n start sizeof char strcpy HC i free cd int main char code 100 h 100 hl 100 int n i j k l ifstream input file 文件输入输出流 ofstream output file 12 char choice str 100 hfmtree HT hfmcode HC cout n cout 计算机 3 班 Q XXX n while choice Q cout I Init E Encoding D Decoding Q Exit n cout choice if choice I choice i 初始化赫夫曼树 cout n hfmcoding HT HC n for i 1 i n i cout HT i ch HC i endl output file open hfmTree txt if output file cout can t oen file endl return 1 for i 1 i n i output file HT i ch HC i output file close cout 赫夫曼树已经创建完毕 并且已经放入 hfmTree txt 文件中 endl else if choice E choice e 进行编码 并将字符放入 ToBeTran txt 码值放 入 CodeFile txt 中 printf 请输入字符 gets str output file open ToBeTran txt if output file cout can t oen file endl return 1 13 output file str endl output file close output file open CodeFile txt if output file cout can t oen file endl return 1 for i 0 i strlen str i for j 0 j n j if HT j ch str i output file HC j break output file close cout n cout 编码完毕 并且已经存入 CodeFile txt 文件 n input file open CodeFile txt 从 CodeFile txt 中读入编码 输出在终端 if input file cout can t oen file code cout 编码码值为 code endl input file close else if choice D choice d 读入 CodeFile txt 中的编码进行译码 将译出来的字符 放入 Textfile txt 中 input file open CodeFile txt if input file cout can t oen file h input file close output file open Textfile txt if output file cout can t oen file endl return 1 14 k 0 while h k 0 先用编码中的前几个和字符的编码相比较 然后往后移 for i 1 i n i l k for j 0 j strlen HC i j l hl j h l hl j 0 if strcmp HC i hl 0 output file HT i ch k k strlen HC i break output file close input file open Textfile txt if input file cout can t oen file h cout h endl input file clo