计算机体系结构报告..docVIP

中南大学 计算机体系结构 实验报告 学生姓名 代巍 指导教师 雷向东 学 院 信息科学与工程学院 专业班级 信安1201班 学 号 0909121615 完成时间 2014年11月20日 实验 1 对指令操作码进行霍夫曼编码 一、实验目的 了解和掌握指令编码的基本要求和基本原理 二、实验要求 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。 问题描述以及问题分析： 我们举例说明此问题，例如： 有一组指令的操作码共分七类，它们出现概率如 下表所示： P1 P2 P3 P4 P5 P6 P7 0.45 0.30 0.15 0.05 0.03 0.01 0.01 对此组指令进行 HUFFMAN 编码正如下图所示： 首先将建立哈弗曼树，将权重最小的放在二叉树的最低端，将权重最大的放置在离根结点最近的位置，这样就可以使权重大的结点的编码较短，权重小的结点的编码较长。实际上是建立一个表格，中间有结点的权重，父亲和孩子的信息。 建立好哈弗曼树之后，要使得哈弗曼的左子树的编码为0，右子树的编码为1。可以通过这个来确定字符的哈弗曼编码。 四、实验原理 构造 HUFFMAN 树所要做的工作： 1、先对各指令操作码的出现概率进行排序，构造一个有序链表。 2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。 3、在对链表进行排序，链表是否只有一个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。为此设计一个工作链表（链表的元素时类，此类的功能相当结构。）、HUFFMAN 树节点、HUFFMAN 编码表节点 五、实验结果 输入的n为4，各节点的权重为23,34,54,65 六、源程序代码 #include stdio.h #includestdlib.h #include malloc.h #include string.h #include conio.h #define MAXBIT 100 #define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2 -1 typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; int parent; int lchild; int rchild; int value; } HNodeType; /* 结点结构体 */ /* 构造一颗哈夫曼树 */ void HuffmanTree (HNodeType HuffNode[MAXNODE], int n) { /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ for (i=0; i2*n-1; i++) { HuffNode[i].weight = 0;//权值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; HuffNode[i].value=i; //实际值，可根据情况替换为字母 } /* end for */ /* 输入 n 个叶子结点的权值 */ for (i=0; in; i++) { printf (Please input weight of leaf node %d: \n, i); scanf (%d, HuffNode[i].weight); } /* end for */ /