哈夫曼编码与译码

《哈夫曼编码与译码》由会员分享，可在线阅读，更多相关《哈夫曼编码与译码（20页珍藏版）》请在金锄头文库上搜索。

1、哈夫曼编码与译码哈夫曼编码与译码(1)输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码(2)给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件(3)用(2)的结果，按照哈夫曼树进行译码#include #include #include #define MAXLEN 10typedef structint weight;int lchild;int rchild;int parent;char key;char mima100;htnode;typedef htnode hfmtMAXLEN;int n=0;typedef char ele

2、mtype;typedef structelemtype dataMAXLEN;int front,rear;seqqueue;void enqueue(seqqueue *q,char item)q-dataq-rear=item;q-rear=q-rear+1;elemtype dequeue(seqqueue *q)elemtype item;if(q-rear!=q-front) item=q-dataq-front;q-front=q-front+1;return item;seqqueue *initqueue(seqqueue *q)q=(seqqueue *)malloc(si

3、zeof(seqqueue);q-front=q-rear=0;return q; void inithfmt(hfmt t)int i,j,k;FILE *p;char ch;i=0;p=fopen(“1.txt“,“r“);if(fopen(“1.txt“,“r“)=NULL) printf(“open error.“);while(ch=fgetc(p)!=EOF) for(k=0;ktj.weight)min1=tj.weight;*p1=j; for(j=0;jtj.weight *p2=j; void creathfmt(hfmt t)int i,p1,p2;inithfmt(t)

4、;for(i=n;irear=q-front=0;for(i=0;i#include #include #define N 100#define M 2*N-1typedef char * HuffmanCode2*M;/haffman 编码typedef structint weight;/权值int parent;/父节节点int LChild;/左子节点int RChild;/右子节点HTNode,HuffmanM+1;/huffman 树typedef struct Nodeint weight; /叶子结点的权值 char c; /叶子结点int num; /叶子结点的二进制码的长度

5、WNode,WeightNodeN;/*产生叶子结点的字符和权值*/ void CreateWeight(char ch,int *s,WeightNode CW,int *p)int i,j,k;int tag; *p=0;/叶子节点个数/统计字符出现个数,放入 CWfor(i=0;chi!=0;i+) tag=1;for(j=0;jhtj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;jhtj.weight?j:s2;hts2.parent=i;hti.RChild=s2; hti.weight=hts1.weight+hts2.weigh

6、t;/权值累加 /*叶子结点的编码*/ void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n) int i,c,p,start;char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;/末尾置 0for(i=1;i=n;i+) start=n-1; /cd 串每次从末尾开始 c=i; p=hti.parent;/p 在 n+1 至 2n-1 while(p) /沿父亲方向遍历,直到为 0 start-;/依次向前置值 if(htp.

7、LChild=c)/与左子相同,置 0 cdstart=0; else /否则置 1 cdstart=1; c=p; p=htp.parent; weighti.num=n-start; /二进制码的长度(包含末尾 0) hi=(char *)malloc(n-start)*sizeof(char); strcpy(hi,/将二进制字符串拷贝到指针数组 h 中 free(cd);/释放 cd 内存system(“pause“);/*所有字符的编码*/void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weigh

8、t,int n,int m)int i,k;for(i=0;im;i+)for(k=1;k=n;k+) /*从 weightk.c 中查找与chi相等的下标 K*/if(chi=weightk.c) break;hci=(char *)malloc(weightk.num)*sizeof(char);strcpy(hci,hk); /拷贝二进制编码 /*解码*/ void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)int i=0,j,p;printf(“*StringInformation*n“);whi

9、le(im)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!=0;j+)if(hcij=0)p=htp.LChild;elsep=htp.RChild;printf(“%c“,wp.c); /*打印原信息*/i+; /*释放 huffman 编码内存*/ void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)int i;for(i=1;i=n;i+)/释放叶子结点的编码free(hi);for(i=0;im;i+) /释放所有结点的编码free(hci);void main() int i,n=0;

10、/*n 为叶子结点的个数*/ int m=0;/*m 为字符串 ch的长度*/char chN;/*chN存放输入的字符串*/ Huffman ht;/*Huffman 二叉数 */HuffmanCode h,hc;/*h 存放叶子结点的编码，hc 存放所有结点的编码*/WeightNode weight;/*存放叶子结点的信息*/ printf(“t*HuffmanCoding*n“); printf(“please input information :“);gets(ch);/*输入字符串*/ CreateWeight(ch,/*产生叶子结点信息，m 为字符串 ch的长度*/ print

11、f(“*WeightInformation*n Node “); for(i=1;i=n;i+)/*输出叶子结点的字符与权值*/printf(“%c “,weighti.c);printf(“nWeight “);for(i=1;i=n;i+)printf(“%d “,weighti.weight); CreateHuffmanTree(ht,weight,n); /*产生 Huffman树*/ printf(“n*HuffamnTreeInformation*n“); printf(“titweighttparenttLChildtRChildn“);for(i=1;i=2*n-1;i+) /*打印 Huffman树的信息*/ printf(“t%dt%dt%dt%dt%dn“,i,hti.weight,hti.parent,hti.LChild,hti.RChild); CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/printf(“ *NodeCode*n“); /*打印叶子结点的编码*/ for(i=1;i=n;i+) printf(“t%c:“,weighti.c); printf(“%sn“,hi);CrtHuffmanCode(ch,h,hc,w