哈夫曼编码译码程序源代码.doc

数据结构课程设计哈夫曼编码译码程序源代码#include #include #include #include #include #include #include const int UINT_MAX=10000;typedef struct int weight; int parent,lchild,rchild;HTNode,* HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表/-全局变量-HuffmanTree HT;HuffmanCode HC;int *w,i,j;const int n=26;char *z;int flag=0;int numb=0;/ -求赫夫曼编码-int min(HuffmanTree t,int i) / 此函数将要被void select()调用 int j,flag; int k=UINT_MAX; / 取k为不小于可能的值 for(j=1;j=i;j+) if(tj.weights2) j=s1; s1=s2; s2=j; / -参考课本算法6.12-void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n=1) return;/检测结点数是否可以构成树 m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 /在HT1i-1中选择parent=0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / 从叶子到根逆向求每个字符的赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i=n;i+) / 逐个字符求赫夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间/-初始化赫夫曼链表-void Initialization() flag=1; int num2; cout下面初始化赫夫曼链表endl; w=(int*)malloc(n*sizeof(int); / 为第26个字符权值分配空间 z=(char*)malloc(n*sizeof(char); / 为第26个字符分配空间 coutn依次显示n个字符与其权值和编码nendl; char base2;/?ifstream fin(abc.txt); for(i=0;ibase; *(z+i)=*base;/? finnum2;/上面123行 *(w+i)=num2; HuffmanCoding(HT,HC,w,n); /-打印编码- cout字符setw(6)权值setw(11)编码endl; for(i=1;i=n;i+) coutsetw(3)*(z+i-1); coutsetw(6)*(w+i-1)setw(12)HCiendl; /-将赫夫曼编码写入文件- cout下面将赫夫曼编码写入文件endl.endl; FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL) cout不能打开文件 endl; return; for(i=0;in;i+) fputc(*(z+i),htmTree); fputs(r,htmTree); for(i=0;in;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout已将字符与对应编码写入根目录下文件htmTree.txt中endlendl;/-获取报文并写入文件-void InputCode() FILE *tobetran; char str100; if(tobetran=fopen(tobetran.txt,w)=NULL) cout不能打开文件endl; return; cout请输入你想要编码的字符endl; /字符个数应当小于100 gets(str); fputs(str,tobetran); cout获取报文成功endl; fclose(tobetran);cout.endl报文存入根目录下的tobetran.txt文件中endl;/-编码函数-void Encoding() cout下面对目录下文件tobetran.txt中的字符进行编码endl; FILE *tobetran,*codefile; if(tobetran=fopen(tobetran.txt,rb)=NULL) cout不能打开文件endl; if(codefile=fopen(codefile.txt,wb)=NULL) cout不能打开文件endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) cout不能打开文件endl; break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) cout字符错误，无法编码!endl; break; cout编码完成endl；cout编码写入目录下的codefile.txt中endlendl; fclose(tobetran); fclose(codefile); free(tran);/-译码函数-void Decoding() cout下面对根目录下文件codefile.txt中的字符进行译码endl; FILE *codef,*txtfile; if(txtfile=fopen(Textfile.txt,w)=NULL) cout不能打开文件endl; txtfile=fopen(Textfile.txt,w); if (codef=fopen(codefile.txt,r)=NULL) cout不能打开文件endl; codef=fopen(codefile.txt,r); char *work,*work2,i2; int i4=0,i,i3; unsigned long length=10000; work=(char*)malloc(length*sizeof(char); fgets(work,length,codef); work2=(char*)malloc(length*sizeof(char); i3=2*n-1; for(i=0;*(work+i-1)!=0;i+) i2=*(work+i); if(HTi3.lchild=0) *(work2+i4)=*(z+i3-1); i4+; i3=2*n-1; i-; else if(i2=0) i3=HTi3.lchild; else if(i2=1) i3=HTi3.rchild; *(work2+i4)=0; fputs(work2,txtfile); cout译码完成endl；cout内容写入根目录下的文件textfile.txt中endlendl; free(work); /释放工作区 free(work2); /释放工作区 fclose(txtfile); /关闭文件txtfile.txt fclose(codef); /关闭文件codef.txt/-打印编码的函数-void Code_printing() cout下面打印根目录下文件CodePrin.txt中编码字符endl; FILE * CodePrin,* codefile; if(CodePrin=fopen(CodePrin.txt,w)=NULL) cout不能打开文件endl; return; if(codefile=fopen(codefile.txt,r)=NULL) cout不能打开文件endl; return; char *work3; work3=(char*)malloc(51*sizeof(char);if(fgets(work3,51,codefile)=NULL) cout不能读取文件endl; else do fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50&fgets(work3,51,codefile)!=NULL); free(work3); cout打印结束endlendl; fclose(CodePrin); fclose(codefile);/-打印赫夫曼树的函数-void coprint(HuffmanTree start,HuffmanTree HT) /start=ht+26这是一个递归算法 if(start!=HT) FILE * TreePrint; if(TreePrint=fopen(TreePrint.txt,a)=NULL) cout创建文件失败rchild,HT); /递归先序遍历 coutsetw(5*numb)weightweight); coprint(HT+start-lchild,HT); numb-; fclose(TreePrint); void Tree_printing(HuffmanTree HT,int w) HuffmanTree p; p=HT+w; /p=HT+26 cout下面打印赫夫曼树endl; coprint(p,HT); /p=HT+26 cout打印工作结束endl;/-主函数-void main() coutendl; cout 此程序经晓光修改 endl; cout 实现赫夫曼编码解码功能 endl; char choice; while(choice!=q) coutn*endl; cout 赫夫曼编码解码 endl; cout* endl; cout(i)初始化赫夫曼表 endl; cout(w)输入待编码的字符 endl; cout(e)进行编码、译码、打印编码 endl; cout(t)打印赫夫曼树 endl; cout(q)离开 endl; if(flag=0)coutn请先初始化赫夫曼链表,输入iendl;cout(程序将从根目录下的abc.txt文件中读出26个字母及其权值并对字母进行编码)choice; switch(choice) case i: Initialization();/初始化赫夫曼表 break; case w: InputCode(); /输入待编码的字符 b