算法实验报告三

《算法实验报告三》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》课程实验报告专业：计算机科学与技术班级：学号：日期：2014年12月1日一、实验题目贪心算法二、实验目的1、掌握贪心算法的基本思想2、掌握贪心算法屮贪心选择性质和最优子结构性质的分析与证明3、掌握贪心算法求解问题的方法三、实验内容1、哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。2、给定带权有向图G二(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。3、设G二(V,E)

2、是无向连通带权图，即一个网络。E中每条边(v,、v)的权为c[v][w]o如果G的子图G'是一棵包含G的所有顶点的树，则称V为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。求G的最小生成树。四、实验步骤1、题目一(1)问题分析算法HuffmanTree首先字符集C中的每一字符c的频率f(x)初始化优先队列Q。然后不断的从优先队列Q中取出具有最小频率的两棵树x和y,将它们合并为一棵新树肌z的频率是x和y的频率之和。新树z以x为其左孩子，y为有孩子。经过叶1次的合并后，优先队列中只剩一棵树，即所

3、要求的树T。(2)算法描述importjava.util.ArrayList;importjava.util.List;publicclassHoffmann{publicstaticvoidmain(String[]args){int[]A二{1,2,3,5};char

4、]C={'a'b,,,c,；d,);ListTree=newArrayListO:for(inti=O;i

5、nn()).buildTree(Tree,0,A.length);TreeNodetreeNode=(TreeNode)Tree.get(Tree.size()-1);(newHoffmann()).seekTree(treeNode/,H);)publicvoidseekTree(TreeNodetreeNode,Stringcode){if(treeNode!=null)1scckTrcc(trccNodc.gctLcftNodc(),codc+nOM);if(treeNode.getCharValue()!=null)System.ou/.pri

6、ntlnC字符:”+treeNode・getCharValue()+"频数："+ireeNode・geiNodeValue()+”编码:H+code);seekTree(treeNode.getRightNode(),code+n1");))publicvoidbuildTree(ListTree,intstart,intfreeNodeNum)if(Tree!=null&&freeNodeNum>=2)QuickSort(Tree,start,Tree.size()-1);TreeNodenewNode=newTreeNode(((TreeNode)

7、Tree.get(start)).getNodeValue()+((TreeNode)Tree.get(start+l)).getNodeValue(),null);ncwNodc.sctLcftNodc((TrccNodc)Trcc.gct(start));ncvvNodc.sctRightNodc((TrccNodc)Trcc.gct(start+l));Tree.add(newNode);freeNodeNum—;buildTree(Tree,start+2,freeNodeNum);))publicvoidQuickSort(ListTree,

8、intpjntr){intq=0;if(p

9、c・sct(i、T「cc.gct(i)):Tree.seMi,(emp):)}Objectte