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

《数据结构课程设计哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、软件学院课程设计报告书课程名称数据结构设计题目哈夫曼编码系统专业班级学号姓名指导教师192012年1月目录1设计时间42设计目的43设计任务44设计内容44.1需求分析44.1.1程序所能达到的功能44.1.2输入的形式和输入值范围44.1.3输出的形式44.1.4测试数据44.2总体设计54.2.1抽象数据类型的定义54.2.2主程序流程及各程序模块之间的层次关系图64.3详细设计74.3.1主函数及其他函数伪码算法74.3.2函数的调用关系图114.4测试与分析124.4.1测试124.4.2分析14194.5附录145总结与展望18参考文献19成绩评定20191设计时间2012年

2、1月2日-2012年1月6日2设计目的哈弗曼的设计，编码，译码输出。数据结构主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。3设计任务从键盘输入一串电文字符能输出对应的哈夫曼编码。同时，能翻译由哈夫曼编码生成的代码串，输出相应的电文字符串。4设计内容4.1需求分析4.1.1程序所能达到的功能:(1)从终端读入字符集大小n，以及n个字符和n个权

3、值，建立哈夫曼树及哈夫曼编码。(2)利用已经建好的哈夫曼树，对输入的字符串进行编码，输出编码序列。(3)利用已建好的哈夫曼树对输入的二进制编码进行译码，并输出结果。4.1.2输入的形式和输入值的范围：输入的形式:数字；n>=0;4.1.3输出的形式：输出的形式：字符和数字4.1.4测试数据：正确的输入：19输入构造哈夫曼树的数据个数：4输入第1个元素权值：7输入第2个元素权值：5输入第3个元素权值：2输入第4个元素权值：4输出：输出哈夫曼编码元素权值7编码为0元素权值5编码为10元素权值2编码为110元素权值4编码为111错误的输入：输入构造哈夫曼树的数据个数：4输出：输入数据个数不合

4、法4.2总体设计4.2.1抽象数据类型的定义:(1)typedefstructtree{intweight;//权值intparent;//双亲结点intlchild;//左孩子结点intrchild;//右孩子结点}tree;(2)typedefstructcode19{charcd[max];//存放哈夫曼码ntstart;//从start开始读cd中的哈夫曼码}code;4.2.2主程序流程及各程序模块之间的层次（调用）关系图：翻译结果字符对应代码字符总数num建立哈夫曼树哈夫曼编码哈夫曼译码输入字符开始否是图4-1：主程序流程及各程序模块之间的层次（调用）关系图19结束输入字符

5、建立哈夫曼树翻译成代码哈夫曼编码哈夫曼译码进行翻译哈夫曼树否是图4-2：各程序模块之间的层次（调用）关系图4.3详细设计4.3.1主函数及其他函数伪码算法：/*------赫夫曼树和赫夫曼编码的存储表示--------*/#definemax5019#include"stdio.h"typedefstructtree{intweight;//权值intparent;//双亲结点intlchild;//左孩子结点intrchild;//右孩子结点}tree;typedefstructcode{charcd[max];//存放哈夫曼码intstart;//从start开始读cd中的哈夫曼码

6、}code;/*----------------构造赫夫曼树-----------*/voidcreat(tree*ht,intn){inti;if(n<1)//判断输入值是否合法{printf("输入数据个数不合法");exit(0);}for(i=1;i<=n;i++)//循环输入元素权值{printf("输入第%d个元素权值:",i);scanf("%d",&((ht+i)->weight));19(ht+i)->parent=0;}for(;i<=2*n-1;i++)//按要求构建哈夫曼树(ht+i)->parent=(ht+i)->lchild=(ht+i)->rchild=

7、0;}/*---从叶子结点到根逆向求每个字符的赫夫曼编码---*/main(){structtreeht[2*max];//建立结构体structcodehcd[max],d;//建立结构体inti,k,n,c,s1,s2,m1,m2,f;printf("输入构造哈夫曼树的数据个数:");//建立哈夫曼树scanf("%d",&n);creat(ht,n);for(i=n+1;i<=2*n-1;i++)//从叶子结点到根逆向求每个字符的赫夫曼编