信息論實驗報告1

InformationTheoty&Coding-PAGE1-信息論與編碼信息論與編碼實驗報告實驗報告學生姓名學生姓名***學號***專業(yè)班級信息安全0701HuffmanandShannoncodingHuffmanandShannoncoding指導教師指導教師***學院***完成時間2009年4月三、詳細設計1.Huffman編碼#include<iostream.h>#include<stdio.h>#include<malloc.h>typedefstructnode{node*lchild;node*rchild;chardata;intweight;}*tree;structelemtype{charch;intweight;intcode[10];};intN=0,m=0;voidsavetree(char*str){FILE*fp=fopen("1.txt","w");for(inti=0;i<m;i++){fputc(str[i],fp);}fclose(fp);}voidcreatehuffman(tree&T,elemtype**a,intn){inti=0,j,k1,k2;btree*b;btreeq;b=(btree*)malloc(n*sizeof(tree));for(i=0;i<n;i++){b[i]=(bnode*)malloc(sizeof(node));b[i]->data=a[i]->ch;b[i]->weight=a[i]->weight;b[i]->lchild=b[i]->rchild=NULL;}for(i=1;i<n;i++){k1=-1;for(j=0;j<n;j++){if(b[j]!=NULL&&k1==-1){k1=j;continue;}if(b[j]!=NULL){k2=j;break;}}for(j=0;j<n;j++){if(b[j]!=NULL){if(b[j]->weight<=b[k1]->weight){k1=j; }}}if(k1==k2){for(j=0;j<n;j++){if(b[j]!=NULL&&j!=k1){k2=j;break;}}}for(j=0;j<n;j++){if(b[j]!=NULL&&j!=k1){if(b[j]->weight<=b[k2]->weight){k2=j;}}}q=(bnode*)malloc(sizeof(bnode));q->data='#';q->lchild=b[k1];q->rchild=b[k2];q->weight=b[k1]->weight+b[k2]->weight;b[k1]=q;b[k2]=NULL;}free(b);T=q;}voidhuffmancoding(btreeT,intlen,elemtype**codes){staticinta[10];if(T!=NULL){if(T->lchild==NULL&&T->rchild==NULL){inti;printf("%c",T->data);codes[N]=(elemtype*)malloc(sizeof(elemtype));codes[N]->ch=T->data;codes[N]->weight=0;for(i=0;i<10;i++)codes[N]->code[i]=2;for(i=0;i<len;i++){printf("%d",a[i]);codes[N]->code[i]=a[i];}N++;printf("\n");}else{a[len]=0;huffmancoding(T->lchild,len+1,codes);a[len]=1;huffmancoding(T->rchild,len+1,codes);}}}voidinitlize(char*str,btree&T,elemtype**codes,char*s){inti=0,j,n=0,k=0,h;elemtype*a[20];for(j=0;j<20;j++)a[j]=NULL;while(str[i]!=0){for(j=0;j<i;j++){if(str[j]==str[i]){for(h=0;h<n;h++){if(a[h]->ch==str[j])break;}a[h]->weight++;break;}}if(j>=i){a[k]=(elemtype*)new(elemtype);a[k]->ch=str[i];a[k]->weight=1;n++;k++;}i++;}cout<<n<<endl;createhuffman(T,a,n);cout<<endl;savetree(s);k=0;cout<<"所求哈夫曼編碼表如下："<<endl;huffmancoding(T,k,codes);}voidmain(){btreet=NULL;elemtype*b[26];charstr[100];chars[50];cout<<endl;cout<<"**哈夫曼編碼程序**"<<endl;cout<<end