实验 树和二叉树2.docx

实验五 赫夫曼树编码基本实验：赫夫曼编码 【实验内容与要求】某通讯系统只使用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次合并操作，所以该数组的长度为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 and 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 when 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 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 he 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 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, and 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 November 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，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个叶结点的路径长度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,int &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); 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.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /从叶子到根逆向求每个字符的编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); / 分配编码表空间 cd=(char *)