《数据结构实验次课赫夫曼编译码器》由会员分享，可在线阅读，更多相关《数据结构实验次课赫夫曼编译码器（19页珍藏版）》请在金锄头文库上搜索。
1、 二叉树用于编码设每种字符在电文中出现的次数 为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=15
2、150001 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 *CharPoi
3、nter;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 FAVORIT
4、E“; 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, Char
5、Array,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
6、(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) c
7、d-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;
