《西安电子科技大学信息论与编码作业(共18页).docx》由会员分享，可在线阅读，更多相关《西安电子科技大学信息论与编码作业(共18页).docx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上Huffman#include #include #include #include #include /typedef int TElemType;const int UINT_MAX=1000;char str50;typedef struct int weight,K; int parent,lchild,rchild;HTNode,* HuffmanTree;typedef char *HuffmanCode;/-全局变量-HuffmanTree HT;HuffmanCode HC;int w50,i,j,n;char z50;int flag=0; int
2、numb=0;/ -求哈夫曼编码- struct cou char data; int count;cou50;int min(HuffmanTree t,int i) / 函数void select()调用 int j,flag; int k=UINT_MAX; / 取k为不小于可能的值,即k为最大的权值1000 for(j=1;j=i;j+) if(tj.weights2) j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / w存放n个字符的权值(均0),构造哈夫曼树HT
3、,并求出n个字符的哈夫曼编码HC int m,i,s1,s2,start; /unsigned c,f; 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中选择paren
4、t为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=
5、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); / 释放工作空间/- 获取报文并写入文件-int InputCode() /cout请输入你想要编
6、码的字符endl; FILE *tobetran; if(tobetran=fopen(tobetran.txt,w)=NULL) cout不能打开文件endl; return 0; cout请输入你想要编码的字符endl; gets(str); fputs(str,tobetran); cout获取报文成功endl; fclose(tobetran); return strlen(str);/-初始化哈夫曼链表-void Initialization() int a,k,flag,len; a=0; len=InputCode(); for(i=0;ik) if(stri=strk) a+;
7、 flag=0; k+; if(flag=0) break; if(flag) for(j=i+1;jlen;j+) if(stri=strj) +coui-a.count; n=len-a; for(i=0;in;i+) coutcoui.data ; coutcoui.countendl; for(i=0;i=n;i+) *(z+i)=coui.data; *(w+i)=coui.count; HuffmanCoding(HT,HC,w,n);/- 打印编码- cout字符对应的编码为:endl; for(i=1;i=n;i+) puts(HCi); /- 将哈夫曼编码写入文件- cout
8、下面将哈夫曼编码写入文件endl.endl; FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL) coutcan not open fileendl; return; fputs(z,htmTree); for(i=0;in+1;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout已将字符与对应编码写入根目录下文件htmT
9、ree.txt中endlendl;/-编码函数-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,1
10、00,tobetran)=NULL) cout不能打开文件endl; break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) cout字符错误，无法编码!endl; break; cout编码工作完成endl编码写入目录下的codefile.txt中endlendl; fclose(tobetran); fclose(codefile); free(tran);/-译码函数-void Decoding() cout下面对根目录下文件codefile.txt中的字符进行译码endl; FILE *codef,*txtfile; if(txtfile=fopen(t
11、xtfile.txt,w)=NULL) cout不能打开文件endl; if (codef=fopen(codefile.txt,r)=NULL) cout不能打开文件endl; 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+) i
12、2=*(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内容写入根目录下的文件txtfile.txt中endlendl; free(work); free(work2); fclose(txtfile); fclose(codef);/-打印编码的函数-void Code_printing(
13、) 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); do if(fgets(work3,51,codefile)=NULL) cout不能读取文件endl; br
14、eak; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); cout打印工作结束endlendl; fclose(CodePrin); fclose(codefile);/- 打印译码函数-void Code_printing1() cout下面打印根目录下文件txtfile.txt中译码字符endl; FILE * CodePrin1,* txtfile; if(CodePrin1=fopen(CodePrin1.txt,w)=NULL) cout不能打开文件endl; return; if(t
15、xtfile=fopen(txtfile.txt,r)=NULL) cout不能打开文件endl; return; char *work5; work5=(char*)malloc(51*sizeof(char); do if(fgets(work5,51,txtfile)=NULL) cout不能读取文件endl; break; fputs(work5,CodePrin1); puts(work5); while(strlen(work5)=50); free(work5); cout打印工作结束endlendl; fclose(CodePrin1); fclose(txtfile);/-打
16、印哈夫曼树的函数-void coprint(HuffmanTree start,HuffmanTree HT) 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
17、; cout下面打印哈夫曼树endl; coprint(p,HT); cout打印工作结束endl;/-主函数-void main() char choice; while(choice!=q) coutn*endl; cout 欢迎使用哈夫曼编码解码系统endl; cout*endl; cout(1)要初始化哈夫曼链表请输入iendl; cout(2)要编码请输入eendl; cout(3)要译码请输入dendl; cout(4)要打印编码请输入pendl; cout(5)要打印哈夫曼树请输入tendl; cout(6)要打印译码请输入yendl; if(flag=0)coutn请先初始化哈
18、夫曼链表,输入ichoice; switch(choice) case i: Initialization(); break; case e: Encoding(); break; case d: Decoding(); break; case p: Code_printing(); break; case t: Tree_printing(HT,2*n-1); break; case y: Code_printing1(); break; default: coutinput errorendl; free(z); free(w); free(HT);费诺#include#include#d
19、efine N 15int paNN;void fano(float p,int aNN,int n,int m,int k) float g=0.0,h=0.0,d,b,c; int i,j,flase; if(nm) for(i=n;i=m;i+) g=pi+g; g=g/2; for(i=n;ig) d=h-pi;b=h-g;c=g-d;if(cb) for(j=n;j=i;j+) ajk=0;fano(p,a,n,i,k+1);for(j=i+1;j=m;j+) ajk=1;fano(p,a,i+1,m,k+1);else for(j=n;j=i-1;j+) ajk=0;fano(p,
20、a,n,i-1,k+1);for(j=i;j=m;j+) ajk=1;fano(p,a,i,m,k+1);break; void main() int i,j,kN,n,flase=0; float pN,m,H=0.0,K=0.0,sum=0.0; cout输入信源符号个数n; cout输入各信源符号概率endl; for(i=1;ipi; for(i=1;i=n;i+) sum=sum+pi; for(i=1;i=n;i+) if(pi1.0|sum!=1.0) coutinput gai lv error!; flase=1;break; if(flase=0) for(i=0;i=n;
21、i+) for(j=0;j=n;j+) paij=10; fano(p,pa,1,n,1); cout信源费诺编码如下：n; for(i=1;i=n;i+) ki=0; coutxi=pit码字为t; for(j=1;j=n;j+) if(paij!=10) coutpaij;ki+; coutt码长为tkiendl; for(i=1;i=n;i+) H=-(pi*log(pi)/log(2)+H; cout信源熵 H(X)=H (比特/符号)endl; for(i=1;i=n;i+) K=pi*ki+K; cout平均码长 K=K (比特/符号)endl; cout编码效率为 (H/K)*1
22、00%endl; /if(flase=0) coutendl;/main()香农#include#include#include#includeclass Tpublic: T() T(); void Create(); void Coutpxj(); void Coutk(); void Coutz(); void Print();protected: int n; double *p; double *pxj; int *k; double *mz;void T:Create() coutn; p=new doublen; cout请分别输入这n个概率:n; for(int i=0;ipi
23、; pxj=new doublen; k=new intn; mz=new doublen; double sum=0.0; for(i=0;in;i+) sum+=pi; if(sum!=1.0) throw 1; else for(i=0;in;i+) int k=i; for(int j=i+1;jn;j+) if(pkpj) k=j; double m=pi; pi=pk; pk=m; T:T() delete p; delete pxj; delete k; delete mz;void T:Coutpxj() pxj0=0; for(int i=1;in;i+) pxji=0; f
24、or(int j=0;ji;j+) pxji+=pj; void T:Coutk() for(int i=0;i0) ki=(int)d+1; else ki=(int)d; void T:Print() coutXisetw(8)P(xi) setw(8)Pa(xj) setw(8)Ki setw(8)码字 endl; for(int i=0;in;i+) coutXi+1 setw(8)setprecision(2)pi setw(8)setprecision(2)pxji setw(8)ki ; mzi=pxji; for(int j=0;j=0) cout1; mzi=2*mzi-1; else cout0; mzi=2*mzi; coutendl; double K=0.0,H=0.0,Y; for(i=0;in;i+) K+=(double)pi*ki; H+=(-1)*pi*(log10(pi)/log10(2.0); Y=H/K; cout平均码长:Kendl; cout信源熵:Hendl; cout编码效率:Yendl;void main() T t;int e; try t.Create(); t.Coutpxj(); t.Coutk(); t.Print(); catch(int e) if(e=1) cout输入错误，请重新运行;专心-专注-专业