算法设计哈夫曼编码

1、宁夏师范学院数学与计算机科学学院算法分析与设计实验报告实验序号： 7 实验项目名称：哈夫曼编码学号姓名专业、班实验地点指导教师时 间一、实验目的及要求（1） 掌握贪心算法的基本思想和组成要素；（2） 掌握使用贪心方法解决实际问题的基本方法和步骤；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：Windows XP操作系统、VC+6.0编程环境。2、实验要求：(1) 独立完成实验，源代码书写规范；(2) 程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确；(3) 实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤#i

2、nclude <stdio.h>#include <stdlib.h>#include <string.h>#define N 7 /编码字符个数#define M (2*N-1)/哈夫曼树结点个数typedef struct char c;/字符 float f;/指定字符出现的频率 int i;/序号 int parent,lchild,rchild;/分别指向父亲、左孩子、右孩子序号 char *code;/指定字符的哈夫曼前缀编码huffmanNode,*huffman;typedef struct huffmanNode *element;/ in

3、t capacity;/优先队列最大容量 int size;/优先队列中已经具有的结点数量heapNode,*priorityqueue;/判断优先队列是否为空，如果为空，则返回1，否则返回0int isEmpty(priorityqueue h) return h->size=0;/判断优先队列是否已满，如果满，则返回1，否则0int isFull(priorityqueue h) return h->capacity=h->size;/功能：向队列中插入指定的元素，插入后的队列具有小队性质/先判断队列是否已满，如果已经满了，则给出提示信息，并返回/否则采用上滤法，即先生成

4、一个空穴，然后把比自己大的父结点向下移，直到找到插入位置为止/把队列中最小的元素出队列，同时队列应该保持小堆特性/优先队列初始化void pushPrioQueue(priorityqueue h,huffmanNode x)int i;if(isFull(h) printf("队列已满n"); return;for(i=+h->size;h->elementi/2.f>x.f;i/=2) h->elementi=h->elementi/2;/父结点向下移h->elementi=x;/功能：将队列中出现频率最小的元素出队，并取下滤法使剩下

5、的保持小堆性质/首先，判断队列是否已空，如果空，提示，并返回，否则把和一个元素和队列/中最后一个元素取回，然后按下滤法使剩下的保持小堆性质/最后将第一个元素返回（即最小元素返回）huffmanNode popPrioQueue(priorityqueue h) huffmanNode minNode,lastNode;int i,child;if(isEmpty(h) printf("队列已经空"); return h->element0;/哨兵元素minNode=h->element1;lastNode=h->elementh->size-; fo

6、r(i=1;2*i<=h->size;i=child) child=i*2;if(child!=h->size&&h->elementchild.f>h->elementchild+1.f) /如果右孩子结点的频率小于左孩子结点的频率则child的取值为右孩子child+;if(h->elementchild.f<lastNode.f) h->elementi=h->elementchild;else break;h->elementi=lastNode;return minNode;/*初始化优先队列，将哈夫曼

7、树中叶子结点入队*/priorityqueue initializePrioQueue(int n,huffman tree) /将tree中n个元素按字符出现的频率生成堆/tree中前n个元素是树中的叶子结点priorityqueue h;int i;h=(priorityqueue)malloc(sizeof(heapNode);if(h=NULL) printf("out of space"); exit(-1);h->capacity=n;/最大容量h->size=0;/目前具有的元素个数h->element=(huffman)malloc(siz

8、eof(huffmanNode)*(n+1);/*其中第0个元素为哨兵元素，由于元素出现的频率必须大于等于零 因此给此元素的频率设置为小于零便可,主要有入队时用到*/if(h->element=NULL) printf("out of space"); exit(-1); h->element0.f=-1;for(i=1;i<=n;i+) pushPrioQueue(h,treei);/入队列return h;/*功能：用于生成哈夫曼树*/huffman ctrHuffmanTree(int n)int m=2*n-1;/1n存储叶子结点，n+1m存储树的

9、n-1个内部结点huffman tree=(huffman)malloc(sizeof(huffmanNode)*(m+1);/用于存储哈夫曼树各结点priorityqueue h;/用于存储优先队列首地址int i;if(tree=NULL) printf("out of space"); exit(-1);/*生成叶子结点*/for(i=1;i<=n;i+) printf("enter %d chara and weight:",i); scanf("%c%f",&treei.c,&treei.f); tre

10、ei.i=i; treei.parent=treei.lchild=treei.rchild=-1; treei.code=NULL; getchar();/吸收回车/*初始化优先队列*/ h=initializePrioQueue(n,tree); /*生成n-1个内部结点*/for(i=n+1;i<=m;i+) huffmanNode x,y,z; x=popPrioQueue(h); y=popPrioQueue(h); z.f=x.f+y.f; z.lchild=x.i; z.rchild=y.i; z.parent=-1; z.i=i; treex.i.parent=i; tr

11、eey.i.parent=i; treei=z; pushPrioQueue(h,z);/*前缀码生成*/for(i=1;i<=n;i+) char *c=(char *)malloc(sizeof(n); int start=n-1; int j=i; if(c=NULL) printf("out of space"); exit(-1); cn-1='0' while(treej.parent!=-1) if(treetreej.parent.lchild=j)c-start='0' else c-start='1'

12、 j=treej.parent; /*给编码申请空间*/ treei.code=(char *)malloc(sizeof(char)*(n-start); strcpy(treei.code,c+start);/*释放优先队列空间*/free(h->element);free(h);return tree;main() huffman tree=ctrHuffmanTree(N); int i,j; char s20,ch,encoding100; for(i=1;i<=N;i+) printf("character:%c,weight:%f,父结点序号:%d,前缀编码

13、:%sn",treei.c,treei.f,treei.parent,treei.code); printf("nninput the string to encoding:"); /输入要编码的串 gets(s); /输出编码 for(ch=si,i=0;ch!='0'i+) int j; for(j=1;j<=N;j+) if(treej.c=ch) printf("%s",treej.code); break; ch=si; printf("nn"); /输入编码，输出字符串 printf(&qu

14、ot;input the binary string to deencoding:"); gets(encoding); j=0; /源码为： printf("源码为"); puts(encoding); printf("解码结果为："); while(encodingj!='0') i=M;/从根开始遍历，至到叶子结点 while(treei.lchild!=-1 |treei.rchild!=-1) if(encodingj='1') i=treei.rchild;/指向右孩子 else i=treei.lchild;/左孩子 j+; printf("%c",treei.c); /释放树空间 for(i=1;i<=N;i+) free(treei.code); free(tree); printf("n");四、实验结果与数据处理五、分析与讨论哈夫曼编码是广泛的用于数据文件压缩的十分有效的编码方法，其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法