算法实验报告三.doc

算法设计与分析课程实验报告专 业： 计算机科学与技术班 级： 学 号： 姓 名： 日期：2014年12月 1日一、 实验题目贪心算法二、 实验目的1、 掌握贪心算法的基本思想2、掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明3、掌握贪心算法求解问题的方法三、 实验内容1、 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。2、给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。3、设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。求G的最小生成树。四、 实验步骤1、 题目一(1) 问题分析算法Huffman Tree首先字符集C中的每一字符c的频率f(x)初始化优先队列Q。然后不断的从优先队列Q中取出具有最小频率的两棵树x和y，将它们合并为一棵新树z。z的频率是x和y的频率之和。新树z以x为其左孩子，y为有孩子。经过n-1次的合并后，优先队列中只剩一棵树，即所要求的树T。(2) 算法描述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 ArrayList();for(int i=0;i=2)QuickSort(Tree,start,Tree.size()-1);TreeNode newNode=new TreeNode(TreeNode)Tree.get(start).getNodeValue()+(TreeNode)Tree.get(start+1).getNodeValue(),null);newNode.setLeftNode(TreeNode)Tree.get(start);newNode.setRightNode(TreeNode)Tree.get(start+1);Tree.add(newNode);freeNodeNum-;buildTree(Tree,start+2,freeNodeNum);public void QuickSort(List Tree,int p,int 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-1;for(int j=p;j=r-1;j+)if(TreeNode)Tree.get(j).getNodeValue()=x)i+;Object temp=Tree.get(i);Tree.set(i, Tree.get(j);Tree.set(j, temp);Object temp=Tree.get(i+1);Tree.set(i+1, Tree.get(r);Tree.set(r, temp);return i+1;class TreeNodeTreeNode leftNode;TreeNode rightNode;int nodeValue;String charValue;public TreeNode(int nodeValue,String charValue )this.nodeValue=nodeValue;this.charValue=charValue;public String getCharValue() return charValue;public void setCharValue(String charValue) this.charValue = charValue;public TreeNode getLeftNode() return leftNode;public void setLeftNode(TreeNode leftNode) this.leftNode = leftNode;public TreeNode getRightNode() return rightNode;public void setRightNode(TreeNode rightNode) this.rightNode = rightNode;public int getNodeValue() return nodeValue;public void setNodeValue(int nodeValue) this.nodeValue = nodeValue;(3) 运行结果 2、 题目二(1) 问题分析Dijkstra算法是解决单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断的做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短路径长度。Dijkstra算法每次从V-S中取出具有最短路径长度的顶点u，将u添加到S中，同时对数组dist进行必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。(2) 算法描述import java.util.Scanner;public class Dijkstra private static int n;private static int distent = null;private static int previous = null;public static void Dijkstras(int v, int a, int dist, int prev)int n = dist.length - 1;if (v n)return;boolean s = new booleann + 1; for (int i = 1; i = n; i+) disti = avi; si = false; if(disti =Float.MAX_VALUE) previ = 0; else previ = v;distv = 0;sv = true;for (int i = 1; i n; i+) float temp = Float.MAX_VALUE;int u = v;for (int j = 1; j = n; j+)if (!sj) & (distj temp)u = j;temp = distj;su = true;for (int j = 1; j = n; j+)if (!sj) & (aujFloat.MIN_VALUE)int newdist = distu + auj;if (newdist distj ) distj = newdist;prevj = u;for(int k = 2;k n;k+)System.out.print(distk+ );System.out.println(distn);public static void main(String args) int v = 1;Scanner sc = new Scanner(System.in);System.out.println(请输入定点个数:);String line = sc.nextLine();n = Integer.parseInt(line);distent = new int n + 1;previous = new int n + 1;int a = new int n + 1n + 1;System.out.println(请输入顶点的权重:);for(int i = 1;i = n;i+)line = sc.nextLine();String str = line.split( );for(int j=1;j=str.length;j+)aij=Integer.parseInt(strj - 1);Dijkstras(v,a,distent,previous);(3) 运行结果 3、 题目三(1) 问题分析Prim算法，设G=（V,E）是连通带权图，V=1，2,n。其基本思想是：首先置S=1，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i属于S，j属于V-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V为止。算法结束时，T中包含G的n-1条边。T中的所有边构成了G的一棵最小生成树。(2) 算法描述import java.util.Scanner;import java.util.Arrays;import java.util.ArrayList;public class Primprivate static int MAX = 100;private double cost = new doubleMAXMAX;private ArrayList edge = new ArrayList();private int near = new intMAX;private static double INFINITY = 99999999.99;private double mincost = 0.0;private int n;public Prim()public static void main(String args)Prim sp = new Prim();sp.init();sp.prim();sp.print();public void init()Scanner scan = new Scanner(System.in);int p,q,w;System.out.println(spanning tree begin!Input the node number:);n = scan.nextInt();for(int i = 0; i MAX; +i)Arrays.fill(costi,INFINITY);System.out.println(Input the graph(-1,-1,-1 to exit);while(true)p = scan.nextInt();q = scan.nextInt();w = scan.nextInt();if(p 0 | q 0 | w 0)break;costpq = w;costqp = w;Edge tmp = getMinCostEdge();edge.add(tmp);p = tmp.start;q = tmp.end;mincost = costpq;for(int i = 1; i = n; +i)if(costip costiq)neari = p;elseneari = q;nearp = nearq = 0;public Edge getMinCostEdge()Edge tmp = new Edge();double min = INFINITY;for(int i = 1; i n; +i)for(int j = i+1; j = n; +j)if(costij min)min = costij;tmp.start = i;tmp.end = j;/System.out.println(min);return tmp;public void prim()for(int i = 2; i n; +i)double min = INFINITY;Edge tmp = new Edge();for(int j = 1; j = n; +j)if(nearj != 0 & costjnearj min)tmp.start = j;tmp.end = nearj;min = costjnearj;mincost += costtmp.starttmp.end;edge.add(tmp);neartmp.start = 0;for(int k = 1; k costktmp.start)neark = tmp.start;if(mincost = INF