codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <stdio.h> #include <stdlib.h> typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; char c; } HTNode, *HuffmanTree; void Select (HuffmanTree HT, int n, int *s1, int *s2) { int i, t1, t2, w1=HT[1].weight, w2=HT[1].weight; for (i=2;i<=n;++i) if (HT[i].weight<w1 && HT[i].parent==0) {w1=HT[i].weight; t1=i;} for (i=2;i<=n;++i) if (HT[i].weight<w2 && i!=t1 && HT[i].parent==0) {w2=HT[i].weight; t2=i;} s1=&t1;s2=&t2; } void HuffmanCode(HuffmanTree HT, int n) { int i, start, d, f, t; char ch, *cd; cd=NULL; FILE *fp, *fq; if ((fp=fopen("file1","rb"))==NULL) printf ("file1 can't be opened!\n"); if ((fq=fopen("file2","ab"))==NULL) printf ("file2 can't be opened!\n"); ch=fgetc(fp); while (ch!=EOF) { for (i=1;i<=n;++i) if (ch==HT[i].c) break; start=n+1; for (d=i,f=HT[i].parent;f!=0;d=f,f=HT[f].parent) if (HT[f].lchild==d) cd[--start]='0'; else cd[--start]='1'; for (t=start;t<=n;++t) fputc(cd[t],fq); ch=fgetc(fq); } fclose(fp); fclose(fq); } void HuffmanDecode(HuffmanTree HT, int n) { int i, m, root; char ch; FILE *fp, *fq; if ((fp=fopen("file3","rb"))==NULL) printf ("file3 can't be opened!\n"); if ((fq=fopen("file4","ab"))==NULL) printf ("file4 can't be opened!\n"); m=2*n-1; for (i=1;i<=m;++i) if (HT[i].parent==0) root=i; ch=fgetc(fp); while (ch!=EOF) { if (ch=='0') root=HT[root].lchild; else root=HT[root].rchild; if (HT[root].lchild==0 && HT[root].rchild==0) { fputc(HT[root].c,fq); root=i; } ch=fgetc(fp); } fclose(fp); fclose(fq); } int main() { HuffmanTree HT; int i, n, m ,w[128]={0}, d[128]={0}, *s1, *s2; char ch, a[128]={0}; s1=(int *)malloc(sizeof(int)); s2=(int *)malloc(sizeof(int)); FILE *fp; if ((fp=fopen("file1","rb"))==NULL) printf("file1 can't be opened!\n"); ch = fgetc(fp); while (ch!=EOF) { for (i=0;i<128;++i) if (i==ch) d[i]++; ch=fgetc(fp); } for (i=0,n=0;i<128;++i) if (d[i]) {w[n]=d[i];a[n]=i;n++;} m=2*n-1; HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); for (i=1;i<=n;++i) {HT[i].weight=w[i];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].c=a[i];} for (;i<=m;++i) {HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].c=-1;} for (i=n+1;i<=m;++i) { Select(HT,i-1,s1,s2); HT[*s1].parent=i; HT[*s2].parent=i; HT[i].lchild=*s1; HT[i].rchild=*s2; HT[i].weight=HT[*s1].weight+HT[*s2].weight; } free(s1);free(s2); fclose(fp); HuffmanCode(HT,n); HuffmanDecode(HT,n); return 0; }
Private
[
?
]
Run code
Submit