算法实验报告三.docx

《算法设计与分析》课程实验报告 专业：计算机科学与技术 班级： 学号： 日期：2014年12月1日 一、实验题目 贪心算法 二、实验目的 1、 掌握贪心算法的基本思想 2、 掌握贪心算法屮贪心选择性质和最优子结构性质的分析与证明 3、 掌握贪心算法求解问题的方法 三、实验内容 1、 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字 符出现的频率，求各个字符的哈夫曼编码方案。 2、 给定带权有向图G二(V,E),其中每条边的权是非负实数。另外，还给定V中的一个 顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指 路上各边权之和。 3、 设G二(V,E)是无向连通带权图，即一个网络。E中每条边(v,、v)的权为c[v] [w]o如 果G的子图G是一棵包含G的所有顶点的树，则称V为G的生成树。生成树上各边 权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最 小生成树。求G的最小生成树。 四、实验步骤 1、题目一 问题分析 算法Huffman Tree首先字符集C中的每一字符c的频率f(x)初始化优先队列Q。然后不断的从优先队列Q 中取出具有最小频率的两棵树x和y,将它们合并为一棵新树肌z的频率是x和y的频率之和。新树z以 x为其左孩子，y为有孩子。经过叶1次的合并后，优先队列中只剩一棵树，即所要求的树T。 算法描述 import java.util.ArrayList; import java.util.List; public class Hoffmann { public static void main(String[] args) { int []A二{1,2,3,5}; char |]C={a\b,,,c,；d,); List Tree=new ArrayListO: for(int i=O;iA.length;i++) { TreeNode treeNode= new TreeNode(A[i],C[i]+nn); Trcc?add(t「ccNodc); 1 (new Hoffmann()).buildTree(Tree,0,A.length); TreeNode treeNode=(TreeNode)Tree.get(Tree.size()-1); (new Hoffmann()).seekTree(treeNode/,H); ) public void seekTree(TreeNode treeNode,String code) { if(treeNode!=null) 1 scckTrcc(trccNodc.gctLcftNodc(),codc+nOM); if(treeNode.getCharValue()!=null) System.ou/.printlnC字符:”+treeNode?getCharValue()+频数：+ireeNode?geiNodeValue()+” 编码: H+code); seekTree(treeNode.getRightNode(),code+n 1); )) public void buildTree(List Tree,int start,int freeNodeNum) if(Tree!=nullfreeNodeNum=2) QuickSort(Tree,start,Tree.size()-1); TreeNode newNode=new TreeNode(((TreeNode)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); )) public void QuickSort(List Tree,int pjnt r) { int q=0; if(pr) { q=partion(Tree?p,r); QuickSort(Tree,p,q-1); QuickSort(Tree,q+1 ,r); } } public int partion(List Tree,int p,int r) { int x=((TreeNode)Tree.get(r)).getNodeValue(); int i=p-l; for(int j=p;j=r-l ;j++) {