树和二叉树.docx

《树和二叉树.docx》由会员分享，可在线阅读，更多相关《树和二叉树.docx（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、实验五 赫夫曼树编码基本实验：赫夫曼编码 【实验内容与要求】某通讯系统只使用8种字符a、b、c、d、e、f、g、h，在某篇电文中其使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23, 0.03,0.11，设想用何种编码方式对其进行编码，能使其在进行远程通信时电文长度最短且误码率最低。【实现提示】 利用Huffman编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度

2、为2n-1。在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。扩展实验：实际信息传输中的Huffman编码与译码【实验内容与要求】针对一段文本(推荐为英语)，就这段文本进行相应的哈夫曼编码和译码。基本要求： 完成文本的频率统计。 构造哈夫曼树。 编写编码程序和译码程序。补充实验：修理栅栏（Fence Repair）DescriptionFarmer John wants to repair a small length of the fence around the pasture. He measures the fence an

3、d finds that he needs N (1 N 20,000) planks of wood, each having some integer length Li (1 Li 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the kerf, the extra length lost to sawdust wh

4、en a sawcut is made; you should ignore it, too.FJ sadly realizes that he doesnt own a saw with which to cut the wood, so he mosies over to Farmer Dons Farm with this long board and politely asks if he may borrow a saw.Farmer Don, a closet capitalist, doesnt lend FJ a saw but instead offers to charge

5、 Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money h

6、e can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.InputLine 1: One integer N, the number of planks Lines 2.N+1: Each line contains a single integer

7、 describing the length of a needed plankOutputLine 1: One integer: the minimum amount of money he must spend to make N-1 cutsSample Input3858Sample Output34HintHe wants to cut a board of length 21 into pieces of lengths 8, 5, and 8. The original board measures 8+5+8=21. The first cut will cost 21, a

8、nd should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).SourceUSACO 2006 No

9、vember Gold【实验内容与要求】农夫John要修理牧场的一段栅栏，他测量了栅栏，发现需要N (1 N 20,000)块木头，每块木头长度为整数Li (1 Li 50,000)个单位。于是他购买了一条很长的，能锯成N块的木头（即该木头长度是Li的总和）。农夫John忽略“损耗”，即忽略的时候产生锯末而造成的长度损耗。农夫John没有锯子，于是他去找农夫Don，向他借锯子。Don是一个守财奴，他不把锯子借给John，而是要John为在木头上锯N-1次支付每一次锯的费用。锯一段木头要支付的费用等于这段木头的长度，即锯长度为21的木头就要支付21美分。（例如，要将长度为21的木头锯成长度为8，

10、5，8的三段。第一次锯木头，将木头锯成13和8，花费21；第二次将长度为13的那块木头锯成8和5，花费13，这样总的花费为21+13=34。）但是，如果将长度为21的木头第一次锯成16和5，第二次锯长度为16的木头，总的花费为21+16=37（大于34）。Don让John决定在木头上切的次序和位置。请你帮助John确定锯N块木头所要花费的最少的钱。【实现提示】 由于木块锯一次产生两块木块，因此锯木过程可以用一棵二叉树表示：根表示初始木板，初始木板的总长度为根结点的权，n段目标木板为n个叶结点，其中第i个叶结点的权为第i段目标木板的长度wi。从初始木板中锯下的第i段目标木板，锯木的次数为根至第i

11、个叶结点的路径长度pi。根据题意，锯下第i段目标木板的花费为pi*wi(1 i n),计算总花费最小的锯木方案，实际上是计算带权路径长度和最小的哈夫曼树。【基本实验的参考程序】#include#include#include#includetypedef struct int weight; int parent; int lchild; int rchild;HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode; /动态分配数组存储哈夫曼编码表void Select(HuffmanTree t,int i,int &s1,in

12、t &s2)/自己写代码，功能为在HT1.i-1 选择parent为0且weight最小的两个结点，/其序号分别为s1和s2。 void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,int *w, int n) /w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的哈夫曼编码HC HuffmanTree p; char *cd; int m,i,s1,s2,start,c,f; if (n=1) return; m=2* n-1; /m为赫夫曼树总结点数 HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode

13、); for (p=HT+1, i=1; i=n; +i, +p, +w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for (; i=m; +i, +p) (*p).weight=0; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for (i=n+1; i=m; +i) /建赫夫曼树 /在HT1.i-1 选择parent为0且weight最小的两个结点 /其序号分别为s1和s2。Select(HT,i-1,s1,s2); HTs1. parent =i; HTs2.p

14、arent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /从叶子到根逆向求每个字符的编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); / 分配编码表空间 cd=(char *)malloc(n*sizeof(char); cdn-1= 0; / 编码结束符 for(i=1;i1)：); scanf(%d,&n); w=(int*)malloc(n*sizeof(int); printf(请依次输入%d个权值(整数)：n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); HuffmanCoding(HT,HC,w,n); for(i=1;i=n;i+) puts(HCi);