数据结构课程设计---哈夫曼编码器.doc

数据结构课程设计程序设计(大作业)报告课程名称：数据结构课程设计 设计题目：哈夫曼编码器 院 系：信息技术学院 班 级：计算机科学与技术2 班设 计 者：郭彩丁 学 号：201011010205 指导教师：王亚宁 设计时间：2012.1.9-2012.1.11 昆明学院昆明学院课程设计（大作业）任务书姓 名：郭彩丁 院 系：信息技术学院专 业：计算机科学与技术专业 学 号：201011010205 任务起止日期：2012.1.9-2012.1.11 课程设计题目：哈夫曼编码器 课程设计要求：（1）初始化：键盘输入n个字符和n个权值，建立哈夫曼树（2）编码：利用建好的huffman树生成huffman编码（3）输出编码（4）字符和频度如下： 字符：空格 A B C D E F G H I J K L M N O P Q 频度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 字符：R S T U V W X Y Z 频度：48 51 80 23 8 18 1 16工作计划及安排（1）在上机之前选题（2）选择合适的数据结构（3）结点结构的设计（4）算法设计与分析（5）程序设计、实现、调试（6）提交课程设计报告指导教师签字 年 月 日 课程设计（大作业）成绩学号：201011010205 姓名：郭彩丁 指导教师：王亚宁 老师课程设计题目： 哈夫曼编码器 总结： 通过此次的课程设计使我认识了哈夫曼树的建立与应用，复习了数据结构中的树的存储结构，怎样构造哈夫曼树以及用哈夫曼树进行编码。学习数据结构能使我们为其它课程打好基础，而课程设计作为数据结构中一个重要环节能更好的使我们加深对它的了解。指导教师评语：成绩：填表时间：指导教师签名： 目录程序设计(大作业)报告1昆明学院课程设计（大作业）任务书21.问题描述52.基本要求53.数据结构54.总体设计55.详细设计65.1程序流程图65.2初始化哈夫曼树75.3输入权值函数75.4选择根结点，存放权值最小和次小序号75.5构造哈夫曼树75.6根据哈夫曼树求哈夫曼编码76.测试与调试76.1程序步骤演示76.1.1输入各字符的权值76.1.2输入字符86.1.3得到哈夫曼编码86.2程序测试结果87.源程序清单108.实验心得131.问题描述 构造一棵哈夫曼树，根据所需输入的字符数目，分别输入字符的频度和字符，得到它们相应的编码，也就是设计一个哈夫曼编码器。2.基本要求以字符的频度为权值，建立哈夫曼树，求哈夫曼编码。根据字符及权值得到其相应的编码。3.数据结构typedef struct int weight; /*结点的权值*/int lchild,rchild,parent; /*左、右孩子及双亲的下标*/htnode;typedef htnode huffmantreem+1; /* huffmantree是结构数组类型,其0号单元不用，存储哈夫曼树 */typedef structchar ch; /*存储字符*/ char coden+1; /*存放编码位串*/codenode;typedef codenode huffmancoden+1; /*huffmancode是结构数组类型,其0号单元不用,存储哈夫曼编码*/4.总体设计功能模块划分void main() /主函数void inithuffmantree(huffmantree ht) /初始化哈夫曼树函数inithuffmantree()void inputweight(huffmantree ht) /输入权值函数 void selectmin(huffmantree ht, int i, int *p1, int *p2)void createhuffmantree(huffmantree ht) /构造huffman树，htm为其根结void huffmancodes(huffmantree ht,huffmancode hcd) /*根据huffman树ht求huffman编5.详细设计5.1程序流程图开始设置字符数目n输入权值若输入=n，输入字符 N Y输出编码数结束5.2初始化哈夫曼树 void inithuffmantree(huffmantree ht)5.3输入权值函数void inputweight(huffmantree ht)5.4选择根结点，存放权值最小和次小序号void selectmin(huffmantree ht, int i, int *p1, int *p2)5.5构造哈夫曼树void createhuffmantree(huffmantree ht)5.6根据哈夫曼树求哈夫曼编码void huffmancodes(huffmantree ht,huffmancode hcd)6.测试与调试 6.1程序步骤演示 6.1.1输入各字符的权值6.1.2输入字符6.1.3得到哈夫曼编码6.2程序测试结果字符：R S T U V W X Y Z频度：48 51 80 23 8 18 1 16 10字符: A B C D E F G H I J K L M N O P Q频度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 17.源程序清单#include#include / 用到系统标准输出函数的#include#include /用到像getch()这种键盘输入函数/* Huffman 树的存储结构*/#define n 9 /*叶子数目根据需要设定*/#define m 2*n-1 /* Huffman 树中结点总数 */* Huffman 树的存储结构*/typedef struct /*结构体定义*/int weight; /*结点的权值*/int lchild,rchild,parent; /*左、右孩子及双亲的下标*/htnode; /*哈夫曼树结点类型*/typedef htnode huffmantreem+1; /* huffmantree是结构数组类型,其0号单元不用，存储哈夫曼树 */typedef structchar ch; /*存储字符*/ char coden+1; /*存放编码位串*/codenode; /*编码结点类型*/typedef codenode huffmancoden+1; /*huffmancode是结构数组类型,其0号单元不用,存储哈夫曼编码*/void inithuffmantree(huffmantree ht) /*初始化哈夫曼树函数inithuffmantree()*/int i; for(i=0;i=m;i+) hti.weight=0; hti.lchild=hti.rchild=hti.parent=0; void inputweight(huffmantree ht) /*输入权值函数 */int i; for(i=1;i=n;i+) printf( 请输入第%d个权值: ,i);scanf(%d,&hti.weight); printf(n); void selectmin(huffmantree ht, int i, int *p1, int *p2)/* 在ht1.i中选两个权值最小的根结点，其序号为*p1和*p2，*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号*/int j,min1,min2; /* min1,min2分别是最小权值和次小权值*/ min1=min2=32767; *p1=*p2=0; for(j=1;j=i;j+) if(htj.parent=0) /* j 为根结点*/ if(htj.weightmin1|min1=32767) if(min1!=32767) min2=min1; *p2=*p1; min1=htj.weight; *p1=j; else if(htj.weightmin2|min2=32767) min2=htj.weight; *p2=j; void createhuffmantree(huffmantree ht) /*构造huffman树，htm为其根结点*/ int i,p1,p2; inithuffmantree(ht); /* 将ht初始化*/ inputweight(ht); /* 输入叶子权值至ht 1.n的weight域*/ for(i=n+1;i=m;i+) /* 共进行n-1次合并，新结点依次存于hti中*/ selectmin(ht,i-1,&p1,&p2); /*在ht 1. i-1中选择两个权值最小的根结点，其序号分别为p1和p2*/ htp1.parent=htp2.parent=i; hti.lchild=p1; /* 最小权值的根结点是新结点的左孩子*/ hti.rchild=p2; /* 次小权值的根结点是新结点的右孩子*/ hti.weight=htp1.weight+htp2.weight; void huffmancodes(huffmantree ht,huffmancode hcd) /*根据huffman树ht求huffman编码*/int c,p,i; /* c和p分别指示 ht中孩子和双亲的位置 */char cdn+1; /* 临时存放编码*/int start; /* 指示编码在cd 中的起始位置*/cdn=0; getchar(); /* 编码结束符*/printf(2.请依次输入字符:); for(i=1;i=n;i+) /* 依次求叶子ht i的编码*/ hcdi.ch=getchar(); /* 读入叶子ht i对应的字符*/ start=n; /* 编码起始位置的初值*/ c=i; /* 从叶子ht i开始上溯*/ while(p=htc.parent)!=0) /* 直至上溯到ht c是树根为止*/ cd-start=(htp.lchild=c)?0:1; /*若ht c是htp的左孩子，则生成代码0，否则生成代码1*/ c=p; /* 继续上溯*/ strcpy(hcdi.code,&cdstart); /* 复制编码位串*/ printf(n);printf(3.哈夫曼编码结果为：n);printf(n);for(i=1;i=n;i+)printf( 第%d个字符%c的编码为：%sn,i,hcdi.ch,hcdi.code);void main()huffmantree t; huffmancode h; printf(|*#*|n); printf(|*欢迎使用哈弗曼编码系统！*|n); printf(|*#*|n); printf(n); printf(1.请输入%d个权值:n,n); printf(n); createhuffmantree(t); /* 构造huffman树*/ huffmancodes(t,h