哈夫曼编码与译码.doc

哈夫曼编码与译码(1)输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码(2)给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件(3)用(2)的结果，按照哈夫曼树进行译码#include #include #include #define MAXLEN 10typedef struct int weight; int lchild; int rchild; int parent; char key; char mima100;htnode;typedef htnode hfmtMAXLEN;int n=0;typedef char elemtype;typedef struct elemtype 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(sizeof(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;ki;k+) if(tk.key=ch) break; if(k=i) ti.weight=0; ti.key=ch; ti.weight+; i+; else tk.weight+; fclose(p); n=i; printf(nn=%d,n); for(i=0;i2*n-1;i+) ti.lchild=-1; ti.rchild=-1; ti.parent=-1; void selectmin(hfmt t,int i,int *p1,int *p2) long min1=999999; long min2=999999; int j; for(j=0;jtj.weight) min1=tj.weight; *p1=j; for(j=0;jtj.weight & j!=(*p1) min2=tj.weight; *p2=j; void creathfmt(hfmt t) int i,p1,p2; inithfmt(t); for(i=n;i2*n-1;i+) selectmin(t,i-1,&p1,&p2); tp1.parent=i; tp2.parent=i; ti.lchild=p1; ti.rchild=p2; ti.weight=tp1.weight+tp2.weight; void printhfmt(hfmt t) int i; printf(nthe hfmt is:n); printf(weighttparenttlchildtrchildtkeyt); for(i=0;i2*n-1;i+) printf(n); printf(%dt%dt%dt%dt%ct%s,ti.weight,ti.parent,ti.lchild,ti.rchild,ti.key); printf(nn); void hfnode1(hfmt t,int i,int j) int a,b; a=i; b=j=ti.parent; if(tj.parent!=-1) i=j; hfnode1(t,i,j); if(tb.lchild=a) printf(0); else printf(1); void huffmannode(hfmt t) int i,j,a; printf(the code is:); for(i=0;in;i+) j=0; printf(n); printf(%c(%d):,ti.key,ti.weight); hfnode1(t,i,j); void Encoding(hfmt t) char r1000,ch; int i=0,j; FILE *p; p=fopen(2.txt,r); if(fopen(2.txt,r)=NULL) printf(nnopen error.); while(ch=fgetc(p)!=EOF) ri+=ch; fclose(p); printf(nnth Encoding is:); for(j=0;rj!=0;j+) for(i=0;in;i+) if(rj=ti.key) hfnode1(t,i,j); void hfnode2(hfmt t,seqqueue *q,int i,int j) int a,b,c=0; char item; a=i; b=j=ti.parent; if(tj.parent!=-1) i=j; hfnode2(t,q,i,j); if(tb.lchild=a) item=0; enqueue(q,item); else item=1; enqueue(q,item); void decoding(hfmt t,seqqueue *q) char r100,ch; FILE *p; int i=0,j=0,len,x,y,s=0; x=2*n-2; p=fopen(3.txt,r); if(fopen(3.txt,r)=NULL) printf(nopen error.); while(ch=fgetc(p)!=EOF) ri+=ch; fclose(p); len=strlen(r); for(i=0;in;i+) hfnode2(t,q,i,j); for(j=0;jrear=q-front=0; for(i=0;in;i+) for(j=0;jn;j+) if(!(ti.mimaj=0 | ti.mimaj=1) ti.mimaj=0; printf(nthe Decoding is:); for(i=0;ilen;i+) if(ri=0) x=tx.lchild; if(tx.lchild=-1) printf(%c,tx.key); x=2*n-2; else if(ri=1) x=tx.rchild; if(tx.rchild=-1) printf(%c,tx.key); x=2*n-2; printf(n); int main() int i,j; hfmt ht; seqqueue *q; printf(*计算机1002-24号钱帆*nn); printf(*欢迎使用哈夫曼编码软件！*nn); printf(*nn); printf( 使用时请在桌面或C:Program FilesWINYESTC20HPROJECTn加载这3个文件：1.hfmTree.txt 2.hfmTreeTree.txt 3.Printing.txtnn); printf(*nn); creathfmt(ht); printhfmt(ht); huffmannode(ht); Encoding(ht); q=initqueue(q); decoding(ht,q); system(pause);题 目 ：哈夫曼编码和译码系统基本要求：(1) 能输入字符集和各字符频度建立哈夫曼树；(2) 产生各字符的哈夫曼编码，并进行解码。提高要求：(1) 能设计出简捷易操作的窗口界面； (2) 编码和译码存储在文件中。#include #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; /叶子结点的二进制码的长度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;ji;j+)if(chj=chi)tag=0;break;if(tag)CW+*p.c=chi;CW*p.weight=1;for(k=i+1;chk!=0;k+)if(chi=chk)CW*p.weight+;/权值累加*s=i;/字符串长度 /*创建HuffmanTree*/ void CreateHuffmanTree(Huffman ht,WeightNode w,int n) int i,j;int s1,s2;/初始化哈夫曼树for(i=1;i=n;i+) hti.weight =wi.weight; hti.parent=0; hti.LChild=0; hti.RChild=0;for(i=n+1;i=2*n-1;i+) hti.weight=0; hti.parent=0; hti.LChild=0; hti.RChild=0;for(i=n+1;i=2*n-1;i+)for(j=1;j=i-1;j+)if(!htj.parent)break;s1=j; /找到第一个双亲不为零的结点for(;jhtj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j=i-1;j+)if(!htj.parent)break;s2=j; /找到第二个双亲不为零的结点for(;jhtj.weight?j:s2;hts2.parent=i;hti.RChild=s2; hti.weight=hts1.weight+hts2.weight;/权值累加 /*叶子结点的编码*/ 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.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,&cdstart);/将二进制字符串拷贝到指针数组h中 free(cd);/释放cd内存system(pause);/*所有字符的编码*/void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,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);while(im)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!=0;j+)if(hcij=0) p=htp.LChild;else p=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;/*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,weight,&n);/*产生叶子结点信息，m为字符串ch的长度*/ printf(*WeightInformation*n Node ); for(i=1;i=n;i+)/*输出叶子结点的字符与权值*/printf(