资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
二叉树用于编码设每种字符在电文中出现的次数 为wi,其编码长度为li,电文中只 有n种字符,则电文的总长度为电文总长度=若置wi为叶子结点,li恰为从根到叶子的路径长度,则电文总长度 为二叉树上的带权路径长度。设计 电文总长度最短的二进制前缀编码 的问题,转换为以n种字符出现的频率作权,设计一棵赫夫曼树的问 题。 ACBD000111例:已知某系统在通信联络中只可能出现8种字符, 其概率分别是:0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11, 试设计赫夫曼编码归一化处理:W=5, 29, 7, 8, 14, 23, 3, 11,n=8, m=15150001 2290002 370003 480004 5140005 6230006 730007 8110008 9000 10000 11000 12000 13000 14000 15000HTweight parentlchildrchildHC建立赫夫曼树和生成赫夫曼编码一棵有n个叶子结点的赫夫曼树共有2n-1个结点,存储在一个大 小为2n-1的一维数组中。typedef structunsigned int weight;unsigned int parent, lchild, rchild;HTNode, *HuffmanTree; typedef char *CharPointer;typedef CharPointer *HuffmanCode; *动态分配数组存储赫夫曼编码注:在赫夫曼树的存储中,没有使用相对位置来描述结点之间 的相互关系,而是采用明示的方式来表示.void HuffmanCoding(HuffmanTree int weigth; CharSet;typedef structchar ch;int weigth;int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char *HuffmanCode;char ToBeTran100=“THIS PROGRAM IS MY FAVORITE“; char CodeFile1000;void ReadCharSet(int void Select(HuffmanTree HT,int up,int void HuffmanCoding(HuffmanTree void Encoding(HuffmanCode HC);void Decoding(HuffmanTree HT,int m);main()CharSet CharArray100; HuffmanTree HT;HuffmanCode HC;int n,m;ReadCharSet(n,CharArray);n=n+1;HuffmanCoding(HT,HC, CharArray,n,m);Encoding(HC);Decoding(HT,m);return(0);void ReadCharSet(int int i;if(fp=fopen(“data.txt“,“r“)=NULL)printf(“Cant open file!n“);exit(0);fscanf(fp,“%dn“,for(i=1;ich=CAi-1.ch; p-weigth=CAi-1.weigth;p-lchild=0; p-rchild=0; p-parent=0;for(;ich= ; p-weigth=0;p-lchild=0; p-rchild=0; p-parent=0;for(i=n+1;i=m;+i)Select(HT,i-1,s1, s2);HTs1.parent=i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weigth=HTs1.weigth+HTs2.weigth;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);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);strcpy(HCi,for(i=1;i=n;i+)printf(“%c“,HTi.ch);printf(“ %sn“,HCi);free(cd);return;void Select(HuffmanTree HT,int up,int s1=s2=0;for(i=1;i=up;i+)if(HTi.parent=0)if(HTi.weigthHTs1.weigth) s2=s1;s1=i;else if(HTi.weigthHTs2.weigth) s2=i;return;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号