数据结构课程设计——赫夫曼编码.doc
课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：哈夫曼编码问题 院（系）：专 业：班 级：学 号：姓 名：指导教师：目 录1课程设计介绍11.1 课程设计内容与要求11.2 课程设计分析与描述12 系统功能模块结构图及功能介绍22.1 系统功能模块结构图22.2 模块功能介绍32.2.1 统计频数32.2.2 建树32.2.3 生成编码33 使用的数据结构的描述43.1 栈43.2 二叉树54 主要函数的描述及流程图64.1 creatHuffamnTree()（创建哈夫曼树）64.2 huffmanCode()（生成哈夫曼编码）75 程序的测试与运行8参考文献10附 录（关键部分程序清单）111 课程设计介绍1.1 课程设计内容与要求利用哈夫曼编码来解决由A、B、C、D四个字符组成的字符串子啊压缩时产生的译码二义性问题，对字符串进行编码时，其中任一字符的编码都不能是其他字符的前缀。即要求编码为前缀编码。实现：1：创建哈夫曼树的结构；2：生成哈夫曼编码；要求：1：使用C语言或其他面向对象语言实现；2：按要求写出课程设计报告；1.2 课程设计分析与描述根据问题的要求，我们需要做以下的工作：1 录入一字符串，统计A、B、C、D四个字符在字符串中出现的频数，把它当作字符的权值；2 根据四个字符各自的权值建立哈夫曼树；3 根据已建立的哈夫曼树生成每个字符的哈夫曼编码；2 系统功能模块结构图及功能介绍2.1 系统功能模块结构图本系统含有统计频数、建树、生成编码四个模块，各模块之间的关系如下图1所示：统计频数建树生成编码 图 1：模块图2.2 模块功能介绍2.2.1 统计频数 在给定的字符串中统计A、B、C、D四个字符在其中出现的频数，并且把它作为该字符的权值；2.2.2 建树 根据各个字符的权值根据哈夫曼算法建立哈夫曼树；2.2.3 生成编码 根据建立的哈夫曼树，生成哈夫曼编码；3 使用的数据结构的描述3.1 栈栈的顺序存储表示： typedef structSElemType * base;/栈底SElemType * top;/栈顶int stacksize;/栈的容量SqStack;栈的用法说明： 栈又称为后进先出的线性表（LIFO结构），特点如下图2所示： 出栈 进栈 栈顶 栈底 图 2：栈的示意图3.2 二叉树 二叉树的二叉链表存储表示：typedef struct BiTNode int data;/数据域 struct BiTNode * lchild,* rchild;/左、右孩子BiTNode,* BiTree;二叉树的用法说明： 二叉树是一种树型结构，特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能颠倒。如下图3：BACDE图 3：二叉树的示意图4 主要函数的描述及流程图4.1 creatHuffamnTree()（创建哈夫曼树）集合F：根据给定的n个权值w1,w2,.wn构成n棵二叉树的集合F=T1,T2,.Tn，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子开始F中只含一棵树结束T在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树的根节点的权值之和F在F中删除这两棵树，同时将新得到的二叉树加入F中图 4:创建哈夫曼树的流程图树均空。创建哈夫曼树的流程如下图4所示：4.2 huffmanCode()（生成哈夫曼编码）创建一空栈S，让T指向哈夫曼树的根节点。生成哈夫曼编码的流程如下图5所示：开始T=NULL结束T->lchild=NULL&&T->rchild=NULL从栈底到栈顶依次输出栈中的元素，得到该结点所对应字符的前缀编码将0入栈huffmanCode（T->lchild）将1入栈huffmanCode（T->lchild）TFFT出栈图 5：生成哈夫曼编码的流程图5 程序的测试与运行1.程序开始界面（如下图6所示）： 图6：开始界面2.程序的输入（如图7所示）： 输入一个只含A、B、C、D四个字符的字符串，回车结束。 图7：输入界面3.程序的运行（如下图8、9所示）：图8：运行界面1图9：运行界面2参考文献1 严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007 2 戴艳等.零基础学算法（第二版）北京：机械工业出版社，2012.23 谭浩强.C语言程序设计（第三版） 北京：清华大学出版社，20054 张清国.C语言程序设计教程（第二版）.北京：清华大学出版社，20095 张长海.C语言程序设计M.北京:高等教育出版社,20066 吴文虎.程序设计基础（第二版）.北京：清华大学出版社，2004BiTree creatHuffmanTree(BiTree * & Head,BiTree * &Tail)BiTree p,q,H;p=minValue(Head,Tail);q=minValue(Head,Tail);/在其中找出两个权值最小的；if(q=NULL)return(p);if(!(H=(BiTree)malloc(sizeof(BiTNode)exit(-1);H->data=p->data+q->data;H->lchild=p;H->rchild=q;/建立一个新结点，使其左右孩子为那两个结点，权值为二者之和；Tail+;*Tail=H;return(creatHuffmanTree(Head,Tail);Status huffmanCode(BiTree T,SqStack & S,Status(* visit)(SqStack & S),Huff H)SElemType x;if(T=NULL)Pop(S,x);return(0);if(!T->lchild)&&(!T->rchild)/如果其左右孩子为空，则说明是叶子结点，输出它的前缀编码；int i=0;while(i<4)if(Hi.Node=T)printf("%c的前缀编码是:",Hi.Ch);附 录（关键部分程序清单）break;i+;visit(S);printf("n");Push(S,0);huffmanCode(T->lchild,S,StackTraverse,H);Push(S,1);huffmanCode(T->rchild,S,StackTraverse,H);Pop(S,x);return(0);课程设计总结：通过此次课程设计，使我更加扎实的掌握了有关哈夫曼编码方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手编写和调试，使我们掌握的知识不再是纸上谈兵。我认为，在这学期的实验中，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在课程设计中，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践、再学习、再实践。这对于我们的将来也有很大的帮助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩
