计算机体系结构实验-对指令操作码进行霍夫曼编码

CENTRALSOUTHUNIVERSITY计算机体系结构实验报告题目对指令操作码进行霍夫曼编码一、实验目的了解和掌握指令编码的基本要求和基本原理。二、实验环境EclipseIDEforJavaDevelopers（Version:KeplerRelease）Win7三、实验内容使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。问题描述以及问题分析：我们举例说明此问题，例如：最短编码长度为：H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95.要对指令的操作码进行HUFFMAN编码，只要根据指令的各类操作码的出现概率构造HUFFMAN树再进行HUFFAM编码。此过程的难点构造HUFFMAN树，进行HUFFAM编码只要对你所生成的HUFFMAN树进行中序遍历即可完成编码工作。四、关键代码哈夫曼树重点在于如何排列权值大小不同的结点的顺序privateintleafNum;//叶子结点个数privateHaffmanNode[]hnodes;//哈夫曼树的结点数组publicHaffManCode(double[]weight)//构造指定权值集合的哈夫曼树{intn=weight.length;//n个叶子结点this.leafNum=n;this.hnodes=newHaffmanNode[2*n-1];//n个叶子结点的哈夫曼树共有2n-1个结点for(inti=0;in;i++)//结点数组初始化有n个叶子结点this.hnodes[i]=newHaffmanNode(weight[i]);for(inti=0;in-1;i++)//构造n-1个2度结点，每循环一次，构造一个2度结点{doublemin1,min2;intx1,x2;min1=min2=Integer.MAX_VALUE;//选择最小和次最小权值，初值为最大权值x1=x2=-1;//记录两个无父母的最小权值结点下标for(intj=0;jn+i;j++)//查找两个无父母的最小权值结点{if(hnodes[j].weightmin1&&hnodes[j].parent==-1){min2=min1;x2=x1;min1=hnodes[j].weight;//min1记下最小权值x1=j;//x1记下最小权值结点的下标}elseif(hnodes[j].weightmin2&&hnodes[j].parent==-1){min2=hnodes[j].weight;x2=j;//x2记下次最小权值结点的下标}}五、运行截图及源代码源代码：package对指令操作码进行霍夫曼编码;classHaffmanNode//哈夫曼树的结点类{doubleweight;//权值intparent,left,right;//父母结点和左右孩子下标publicHaffmanNode(doubleweight){this.weight=weight;this.parent=-1;this.left=-1;this.right=-1;}publicHaffmanNode(){this(0);}publicStringtoString(){returnthis.weight++this.parent++this.left++this.right;}}publicclassHaffManCode{privateintleafNum;//叶子结点个数privateHaffmanNode[]hnodes;//哈夫曼树的结点数组publicHaffManCode(double[]weight)//构造指定权值集合的哈夫曼树{intn=weight.length;//n个叶子结点this.leafNum=n;this.hnodes=newHaffmanNode[2*n-1];//n个叶子结点的哈夫曼树共有2n-1个结点for(inti=0;in;i++)//结点数组初始化有n个叶子结点this.hnodes[i]=newHaffmanNode(weight[i]);for(inti=0;in-1;i++)//构造n-1个2度结点，每循环一次，构造一个2度结点{doublemin1,min2;intx1,x2;min1=min2=Integer.MAX_VALUE;//选择最小和次最小权值，初值为最大权值x1=x2=-1;//记录两个无父母的最小权值结点下标for(intj=0;jn+i;j++)//查找两个无父母的最小权值结点{if(hnodes[j].weightmin1&&hnodes[j].parent==-1){min2=min1;x2=x1;min1=hnodes[j].weight;//min1记下最小权值x1=j;//x1记下最小权值结点的下标}elseif(hnodes[j].weightmin2&&hnodes[j].parent==-1){min2=hnodes[j].weight;x2=j;//x2记下次最小权值结点的下标}}hnodes[x1].parent=n+i;//将找出的两棵权值最小的子树合并为一棵子树hnodes[x2].parent=n+i;this.hnodes[n+i]=newHaffmanNode();hnodes[n+i].weight=hnodes[x1].weight+hnodes[x2].weight;hnodes[n+i].left=x1;hnodes[n+i].right=x2;}}publicStringtoString(){Stringstr=;for(inti=0;ithis.hnodes.length&&hnodes[i]!=null;i++)str+=+i++this.hnodes[i].toString()+\n;returnstr;}String[]code1=null;publicString[]haffmanCode()//返回当前哈夫曼树的哈夫曼编码{code1=newString[this.leafNum];String[]code=newString[this.leafNum];for(inti=0;ithis.leafNum;i++)//求n个叶子结点的哈夫曼编码{code[i]=;intchild=i;intparent=hnodes[child].parent;while(parent!=-1)//由叶结点向上直到根结点循环{if(hnodes[parent].left==child){code[i]=0+code[i];//左孩子结点编码为0code1[i]=code[i];}else{code[i]=1+code[i];//右孩子结点编码为1code1[i]=code[i];}child=parent;parent=hnodes[child].parent;}}returncode;}publicdoubleshortestLong(){intlng;doubleweight,shortestlong=0;for(inti=0;ithis.leafNum;i++){lng=code1[i].length();weight=hnodes[i].weight;shortestlong=shortestlong+lng*weight;}returnshortestlong;}publicstaticvoidmain(String[]args){//int[]weight={186,64,13,22,32,103,21,15,47,57,1,5,32,20};//指定权值集合double[]weight={0.1,0.2,0.1,0.3,0.1,0.2};HaffManCodehtree=newHaffManCode(weight);System.out.println(指令权值父指左子右子\n+htree.toString());String[]code=htree.haffmanCode();System.out.println(哈夫曼编码:);for(inti=0;icode.length;i++){System.out.println(code[i]);}System.out.println(最短编码长度为:+htree.shortestLong());}}