数据结构课程设计 一、目的 《数据结构》是一门实践性较强的软件基础课程,为了学好这门课程,必须在掌握理论知识的同时,加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能。 二、要求 通过这次设计,要求在数据结构析逻辑特性和物理表示,数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 三、内容 2 .哈夫曼编码/译码器 【问题描述】 设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。 【基本要求】 (1)初始化:键盘输入字符集大小n、n个字符和 n个权值 ,建 立 哈夫曼树 ; (2)编码:利用建 好的哈夫曼树 生 成 哈夫曼编码; (3)输出编码; (4)设字符集及频 度 如 下表: 字符 空 格 A B C D E F G H I J K L M 频 度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频 度 57 63 15 1 48 51 80 23 8 18 1 16 1 【选做 内容】 (1)译码功 能; (2)显示哈夫曼树 ; (3)界面设计的优 化。 哈夫曼编写编译码 一、问题描述 利用哈夫曼编码进 行 通信 可 以大大提 高 信 道 利用率 ,这要求在发 送 端通过一个编码系统对待 传 输预 先 编码,在接 收 端 将 传 来的数据进 行 译码。对于 双 工 通道 ,每 端 都 需 要一个完 整 的编/译码系统。试 为这样 的信 息 收 发站 写 一个哈夫曼码的编/译码系统。 二、概要设计 1.哈夫曼树的定义: 在一棵二叉树中,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。 2.哈夫曼树的构造: 假设有N个权值,则构造出的哈夫曼树有N个叶子结点。N个权值分别设为W1,W2,… … … .Wn,则哈夫曼树的构造规则为: (1) 将W1,W2,… … … .Wn看成有N棵树的森林; (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左,右子树,且新树的根结点为其左,右子树结点权值之和; (3) 从森林中删除选取取的两面三刀棵树,并将新树加入森林; (4) 重复(2)(3)步,直到森...