编译器实验报告.doc

文档介绍：编译器实验报告甘肃政法学院本科学生实验报告姓名学院专业班级试验时间2016年12月20日指导教师及职称实验成绩开课时间2016-2016学年1学期实验课程名称编译原理甘肃政法学院实验管理中心印制深圳大学实验报告课程名称:实验项目名称:学院:计算机与软件学院班级:实验时间:实验报告提交时间:教务处制2342、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。5实****报告题目:哈弗曼编译码器班级:电信系通信工程0902班完成日期:一、需求分析1、编写哈弗曼编译码器,其主要功能有I:初始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。E:编码。利用已建好的哈夫曼树),对从终端输入的正文进行编码,然后从终端输出。D:译码P:印哈夫曼树。将已编码的的哈夫曼树显示在终端上,同时将此字符形式的哈夫曼树。2、测试数据:输入的字符={a,b,c,d,e}其对应的权值={5,29,7,8,14}二、概要设计1、二哈弗曼树的抽象数据类型定义为:ADTHuffmanTree{数据对象D:D是具有相同性质的数据元素的集合数据关系R:若D=Φ,则R=Φ,哈弗曼树为空若D≠Φ,则R={H},H是如下二元关系:在D中存在唯一的称为根的数据元素root,它在关系H下无前驱若D-{root}≠Φ,则存在D-{root}={Dl,Dr}。且Dl∩Dr=Φ若Dl≠Φ,则Dl中存在唯一的数据元素Xl,属于H,且存在Dl上的关系H1属于H。若Dr≠Φ,则Dr中存在唯一的数据元素Xr,属于H,且存在Dr上的关系Hr属于HH={,,Hl,Hr};是一棵符合本定义的哈弗曼树,称为根的左子树。是一棵符合本定义的哈弗曼树,称为根的右子树。基本操作:HuffmanCoding哈弗曼树每个节点的定义:typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;charelemt[20];}HTNode,*HuffmanTree;定义指向哈弗曼树的指针,用于动态分配空间typedefchar**HuffmanCode;哈弗曼树的基本操作VoidHuffmanCoding{//建立哈弗曼树,求出哈弗曼编码ifreturn;m=2*n-1;//n个叶子的HuffmanTree共有2n-1个结点HT=malloc*sizeof);for*p={*w,0,0,0};//给前n个单元初始化for*p={0,0,0,0};//从叶子之后的存储单元清零for{//建Huffman树Select;//选择parent为0且weight最小的两个结点,HT[s1].parent=i;HT[s2].parent=i;//给双亲分量赋值HT[i].lchild=s1;HT[i].rchild=s2;//给合并后的内结点赋孩子值HT[i].weight=HT[s1].weight+HT[s2].weight;}//以上建立了哈弗曼树,以下求哈弗曼编码HC=malloc*sizeof);//分配n个字符编码的头指针向量cd=malloc);//分配求编码的临时最长空间cd[n-1]=“\0”;//编码结束符for//逐个字符求Huffman编码{start=n-1;//编码结束符位置for//从叶子到根逆向求编码ifcd[--start]=“