哈夫曼編譯碼

1、#include<stdio.h> /* for size_t, printf() */#include<conio.h> /* for getch() */#include<ctype.h> /* for tolower() */#include<malloc.h> /* for malloc(), calloc(), free() */#include<string.h> /* for memmove(), strcpy() */*樹結構和全局結構指針*/#define NODENUM 26/*-哈夫曼樹結點結構-*/struct

2、 node char ch; int weight; int parent; int lchild,rchild; *ht; /指向哈夫曼樹的存儲空間的指針變量/*-字符編碼結點結構-*/struct HuffmanCoding char ch; char codingNODENUM; ;/*-哈夫曼樹遍歷時棧的結點結構-*/struct stacknode int NodeLevel; int NodeElem; ;/*-常量文件名-*/ const char *TableFileName = "HfmTbl.txt" /哈夫曼樹數據文件 const char *Code

3、FileName = "CodeFile.txt" /字符編碼數據文件 const char *SourceFileName = "SrcText.txt" /需編碼的字符串文件 const char *EnCodeFileName = "EnCodeFile.txt" /編碼數據文件 const char *DecodeFileName = "DecodeFile.txt" /譯碼字符文件/*/* 釋放哈夫曼樹數據空間函數 */*/ void free_ht() if(ht != NULL) free(ht);h

4、t = NULL; /*/* 從文件讀取哈夫曼樹數據函數 */*/int ReadFromFile() int i; int m; FILE *fp; if(fp=fopen(TableFileName,"rb")=NULL) printf("cannot open %sn", TableFileName);getch();return 0; fread(&m,sizeof(int),1,fp); /m為數據個數 free_ht(); ht=(struct node *)malloc(m*sizeof(struct node); fread(ht

5、,sizeof(struct node),m,fp); fclose(fp); return m; /*/* 吃掉無效的垃圾字符函數函數 */* 從鍵盤讀字符數據時使用，避免讀到無效字符 */*/ void EatCharsUntilNewLine() while(getchar()!='n')continue;/*/* 選擇權值最小的兩個根結點函數 */*/void Select(struct node ht,int n, int *s1,int *s2) int i,j; /尋找第一個根結點 *s1=0; while (*s1<=n&&ht*s1.pa

6、rent!=-1) +(*s1); /尋找第一個權值最小的根結點 i=(*s1)+1; while(i<=n) if(hti.parent=-1&&hti.weight<ht*s1.weight) *s1=i; i+; /尋找第一個根結點，但不是第一個權值最小的根結點 *s2=0; while(*s2<=n&&(ht*s2.parent!=-1 | *s2=*s1) +(*s2); /尋找第二個權值最小的根結點 j=*s2+1; while(j<=n) if(j!=*s1&&htj.parent=-1&&h

7、tj.weight<ht*s2.weight) *s2=j; j+; return; /*/* 創(chuàng)建哈夫曼樹和產生字符編碼的函數 */*/void Initialization() int i=0,n,m,j,f,s1,s2,start; char cdNODENUM; struct HuffmanCoding codeNODENUM; FILE *fp; printf("輸入字符總數 n:"); scanf("%d",&n); EatCharsUntilNewLine(); m=2*n-1; ht=(struct node *)mallo

8、c(m*sizeof(struct node);/申請哈夫曼樹的存儲空間 for(i=0;i<n;i+)scanf("%c%d",&hti.ch,&hti.weight);fflush(stdin);hti.parent=hti.lchild=hti.rchild=-1;for(i=n;i<m;i+)hti.ch='*'hti.weight=0; hti.parent=hti.lchild=hti.rchild=-1;for(i=n;i<m;i+)Select(ht,i-1,&s1,&s2);hts1.par

9、ent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2; /*/ /* 創(chuàng)建哈夫曼樹 */ /* 1、輸入字符和權值 */ /* 2、初始化哈夫曼樹 */ /* 3、建立哈夫曼樹 */ /*/ /把哈夫曼樹的數據存儲到文件中 if(fp=fopen(TableFileName,"wb")=NULL) printf("cannot open %sn", TableFileName); getch(); return; fwrite(&m,sizeof(int),1,fp); fwrite(ht,sizeof(

10、struct node),m,fp); fclose(fp); /*/ /* 產生字符編碼 */ /* 從頁結點開始，沿父結點上升，直到根結點 ，若沿 */ /* 父結點的左分支上升，則得編碼字符“0”， 若沿父結 */ /* 點的右分支上升，則得編碼字符“1” */ /*/ cdn-1=0; for(i=0;i<n;i+) start=n-1; for(j=i,f=hti.parent;f!=-1;j=f,f=htf.parent) if(htf.lchild=j) cd-start='0' else cd-start='1' codei.ch=hti.

11、ch;strcpy(codei.coding,&cdstart); /把字符編碼數據存儲到文件中 if(!(fp=fopen(CodeFileName,"wb") printf("cannot open %sn", CodeFileName); getch(); return; fwrite(&n,sizeof(int),1,fp); fwrite(code,sizeof(struct HuffmanCoding),n,fp); fclose(fp); free_ht(); printf("nInitial successful

12、e!n"); getch(); /*/* 哈夫曼編碼的函數 */*/void Encode(void) int i,j,n; char Encodestr256; struct HuffmanCoding codeNODENUM; FILE *fp1, *fp2,*fp3; /*/ /* 字符編碼 */ /* 1、讀字符編碼數據 */ /* 2、讀需編碼的字符串 */ /* 3、存儲被編碼的字符串數據到文件中 */ /* 4、打開存儲編碼的數據文件 */ /* 5、字符編碼 */ /* 方法：依次從被編碼的字符串中取一個字符，然后 */ /* 字符編碼表中查找對應字符，若找到，則把對

13、應 */ /* 的編碼輸出到編碼數據文件中。 */ /*/printf("請輸入字符串:n");scanf("%s",Encodestr);if(!(fp1=fopen(CodeFileName,"rb")/打開字符編碼文件 printf("cannot open %sn", CodeFileName); getch(); return; fread(&n,sizeof(int),1,fp1);fread(code,sizeof(struct HuffmanCoding),n,fp1);if(!(fp2=f

14、open(SourceFileName,"wb") /打開文本串文件 printf("cannot open %sn", SourceFileName); getch(); return; if(!(fp3=fopen(EnCodeFileName,"wb")/打開字符編碼結果文件 printf("cannot open %sn", EnCodeFileName); getch(); return; for(i=0;Encodestri!='0'i+)/輸入的文本串存入文件fputc(Encodes

15、tri,fp2);for(i=0;Encodestri!='0'i+)/字符編碼for(j=0;j<n;j+)if(j=n)printf("Errorn");if(codej.ch=Encodestri)fprintf(fp3,"%s",codej.coding);break;fclose(fp1);fclose(fp2);fclose(fp3);return; /*/* 哈夫曼譯碼的函數 */*/void Decode() FILE *cfp, *tfp,*fp; char DeCodeStr256; char ch; int f

16、,m; /*/ /* 字符譯碼 */ /* 1、讀哈夫曼樹數據 */ /* 2、打開編碼數據文件 */ /* 3、打開存儲譯碼的數據文件 */ /* 4、字符譯碼 */ /* 方法：依次從編碼數據文件中讀取編碼字符，并從 */ /* 哈夫曼樹開始，若是數字字符“0”，則沿其左分 */ /* 支下降到孩子結點；若是數字字符“1”，則沿其 */ /* 右分支下降到孩子結點；如此反復，直到頁結點， */ /* 則輸出頁結點對應的字符到譯碼數據文件中，并 */ /* 顯式。每當譯出一個字符，又從頁結點開始，如 */ /* 此重復若找到，直到讀完編碼數據文件中所有字符。 */ /*/ m=ReadFro

17、mFile();/讀取哈弗曼樹數據文件 if(cfp=fopen(EnCodeFileName,"rb")=NULL)/讀取編碼數據文件 printf("cannot open %sn", EnCodeFileName); getch(); return; if(tfp=fopen(DecodeFileName,"wb")=NULL)/打開譯碼數據文件 printf("cannot open %sn", DecodeFileName); getch(); return; while(!feof(cfp) f=m-1

18、; while(!feof(cfp)&&htf.lchild!=-1) ch=fgetc(cfp); if(ch='0') f=htf.lchild; else f=htf.rchild; if(htf.lchild=-1) fputc(htf.ch,tfp); printf("%cn",htf.ch); if(feof(cfp) break; free_ht(); fclose(cfp); fclose(tfp); printf("n"); getch();/*/* 以凹式形式打印哈夫曼樹的函數 */*/void Pri

19、ntHuffmanTree() int i,node,child,level,m,top; struct stacknode stack80; m=ReadFromFile(); printf("n%10c Huffman TRee in Leveln",' '); printf("%10c-n",' '); top=0; node=m-1; level=1; while(node!=-1)|(top!=0) while(node!=-1) for(i=1;i<20+2*level;i+) printf("

20、 "); printf("%d-%d %cn",level,htnode.weight,htnode.ch); if(htnode.rchild!=-1) stacktop.NodeElem=htnode.rchild; stacktop.NodeLevel=level+1; top+; node=htnode.lchild; if(node!=-1) level+; if(top!=0) top-; node=stacktop.NodeElem; level=stacktop.NodeLevel; getch(); /*/* 打印哈夫曼字符編碼的函數 */*/v

21、oid PrintCharCoding() int i,n; struct HuffmanCoding codeNODENUM; FILE *fp; /*/ /* 打印字符編碼 */ /* 1、讀字符編碼數據 */ /* 2、打印字符編碼數據 */ /* 格式： */ /* charactor coding */ /* - */ /* charactor coding */ /* */ /* */ /*/ if(!(fp=fopen(CodeFileName,"r")/打開字符編碼結果文件 printf("cannot open %sn", CodeFi

22、leName); getch(); return; fread(&n,sizeof(int),1,fp); fread(code,sizeof(struct HuffmanCoding),n,fp); fclose(fp); printf( "charactor codingn"); printf("-n"); printf(" charactor codingn"); for(i=0;i<n;i+) printf("%7c%25sn",codei.ch,codei.coding); /*/* 以表的

23、形式打印哈夫曼樹的函數 */*/void PrintHuffmanTable() int i,m; FILE *fp; /*/ /* 打印字符編碼 */ /* 1、讀哈夫曼樹數據 */ /* 2、打印哈夫曼樹數據 */ /* 格式： */ /* Huffman Table */ /* - */ /* Number charactor weight Parent Lchild Rchild */ /* */ /* */ /*/ m=ReadFromFile(); printf(" Huffman Table n"); printf(" - n"); pri

24、ntf("Number charactor weight Parent Lchild Rchildn"); for(i=0;i<m;i+) printf("%d%8c%10d%12d%8d%8dn",i,hti.ch,hti.weight,hti.parent,hti.lchild,hti.rchild); free_ht(); int nemu() int num; printf("n * huffman arithmetic demonstration *n"); printf(" *%15c1-Initial%23cn",' ','*'); printf("