课程设计样板

《课程设计样板》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计题目哈弗曼树编码译码器系(部)电子与信息工程系班级2011级计算机科学与技术姓名杨佩学号2011222243指导教师王克刚2010年01月07日电子与信息工程系数据结构课程设计任务书设计题目哈夫曼编译码器已知技术参数和设计要求题目的基本要求是：1.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。2.编码，利用建好的huffman树生成huffman编码；3.输出编码；4.译码功能；5.字符和频度如下：字符空格ABCDEFGHIJKLMNOPQ频度18664132232103211547571232205763151字符RSTUVWXYZ频度4851802

2、3818116设计内容与步骤1、选择合适的数据结构2、结点结构的设计3、算法设计与分析4、程序设计、实现、调试5、课程设计说明书设计工作计划与进度安排1、设计工作4学时2、实现与调试16学时3、课程设计说明书8学时设计考核要求1、考勤30%2、课程设计说明书70%计算机教研室制2011222243杨佩72011222243杨佩哈夫曼树编码译码器杨佩安康学院计算机科学与技术11级陕西省安康市725000摘要：本文采用了哈弗曼算法，通过对编码与译码技术的探究，利用C语言实现了从文件中读取数据，并进行编码和译码的功能，同时克服了C语言下数组长度的有限性。经实验验证，效果良好。关键字：哈夫曼树；

3、哈夫曼编码；数据的带权路径长度；译码1.引言数据编码技术在计算机数字通信中一直占据着重要的地位。而在数据通信过程中往往存在很多问题：每次对数据编码量有限，传递的数据编码的长度和数据译码容易产生二义性等。以上问题使得数据编码技术的优劣在很大程度上影响着通信质量。在信息编码领域中，哈弗曼树即最优二叉树的应用十分广泛，其权值被赋为某个符号出现的频率，利用哈夫曼树对每个数据进行不等长编码，频率越高的数据其编码越短，使得数据带权路径长度WPL最小，这样就保证了整个电文的编码长度达到最短。“哈夫曼编码”是一种一致性编码，其编码唯一，解决了传递的数据编码长度和数据译码产生的二义性，并在一定程度上提高了

4、传递速度。要实现哈弗曼编码，必须由用户输入数据及每个数据出现的频率。本文给出了一个完整的哈弗曼编码系统，且能自动产生哈夫曼树叶结点及相对应权值的，能对数据迅速准确的输出数据所对应的二进制编码，并能对文件中任意长度字符进行编码，克服了C语言下数组长度的有限性。2.哈弗曼编码与译码2.1基本术语（1）路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。（2）结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为

5、：从根结点到该结点之间的路径长度与该结点的权的乘积。72011222243杨佩（3）树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。2.2哈夫曼树哈夫曼树即最优二叉树，给定一组权值，即可构造出具有最小带权路径长度WPL的二叉树。权值越大的叶结点离根结点越近，权值越小的结点离根结点越远。哈夫曼树中不存在度为1的结点。2.3哈弗曼编码哈夫曼编码是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种，有时称之为最佳编码，一般就叫作最优编码。即应用哈夫曼树对传送中的数据进行二进制编码。在所构造出来的哈夫曼树中，规定从根结点到叶结点的路径上每经过一条左树枝取一个

6、二进制0，每经过一条右树枝则取一个二进制1。这样从根结点到某一叶结点的路径上所得到的由0和1组成的二进制位序列定义为此叶结点的哈弗曼编码。这个编码不唯一，由构造出来的哈夫曼树决定。1.哈弗曼编码、译码算法描述3.1哈夫曼树的构造算法3.1.1提取哈夫曼树叶结点及统计哈夫曼树各叶结点的权值（1）从文件中读取一定长度的字符，将这些字符进行统计并存储。（2）重复步骤（1），将每次统计字符与上一次统计结果中字符相同的进行累加，直到统计出文件中所有字符。3.1.2构造哈夫曼树（1）根据所统计的哈弗曼树n个叶结点的权值（W1，W2，W3，…，Wn），对应结点构成n棵二叉树的森林T=（T1，T2，T3

7、，…，Tn），其中每棵二叉树Ti（0