2022年实验五哈夫曼树与哈夫曼编码文件 .pdf

实验五 哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容 问题描述 已知 n 个字符在原文中出现的频率，求它们的哈夫曼编码。 基本要求 1. 初始化：从键盘读入n 个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法 6.12）2. 编码：根据建立的Huffman 树，求每个字符的Huffman 编码。对给定的待编码字符序列进行编码。 选作内容 . 译码：利用已经建立好的Huffman 树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。4. 打印 Huffman 树。【实验源程序】#include #include /malloc()等#include /INT_MAX等#include / NULL,puts typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表#define DEBUG 0 int min1(HuffmanTree t,int i) / 函数 void select()调用 int j,flag; unsigned int k=UINT_MAX; / 取 k 为不小于可能的值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - for(j=1;j=i;j+) if(tj.weight*s2) j=*s1; *s1=*s2; *s2=j; void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) / w存放 n 个字符的权值 (均0), 构造赫夫曼树 HT,并求出 n 个字符的赫夫曼编码 HC int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n=1)return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=*HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w; (*p).parent=(*p).lchild=(*p).rchild=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - for(;i=m;+i,+p) (*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0; for(i=n+1;i=m;+i) / 构造赫夫曼树 /在 HT1i-1 中选择 parent 为 0 且 weight 最小的两个结点 , 其序号分别为 s1 和 s2 select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /从叶子到根逆向求每个字符的赫夫曼编码 *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配 n 个字符编码的头指针向量(0 不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i1):); scanf(%d,&n); w=(int*)malloc(n*sizeof(int); printf(请依次输入 %d个权值 (整型):n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); printf(n); HuffmanCoding(&HT,&HC,w,n); printf(序号编码n); for(i=1;i=n;i+) printf( %2d ,i); puts(HCi); 三、调试结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -