实验03 贪心算法

实验03贪心算法[实验目的]掌握贪心算法的基本思想掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明掌握贪心算法求解问题的方法[实验内容]哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。求G的最小生成树。[实验步骤]设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;应用设计的算法和程序求解问题;将程序整理成功能模块存盘备用.[实验报告要求]阐述实验目的和实验内容;阐述求解问题的算法原理;提交实验程序的功能模块;记录最终测试数据和测试结果。[实验结果]1.importjava.util.Scanner;publicclassHuffman{HuffmanCode[]codes;String[]huffstring;StringBufferbuffer=newStringBuffer();publicHuffman(Strings){for(inti=0;i<s.length();i++){if(buffer.indexOf(s.substring(i,i+1))==-1){buffer.append(s.charAt(i));}}System.out.println("字母："+buffer);huffstring=newString[buffer.length()];codes=newHuffmanCode[2*buffer.length()-1];for(inti=0;i<2*buffer.length()-1;i++)codes[i]=newHuffmanCode();for(inti=0;i<buffer.length();i++){codes[i].name=buffer.substring(i,i+1);codes[i].weight=haveNum(buffer.charAt(i),s);}getHuffstring();getCode(2*buffer.length()-2,huffstring,"");for(inti=0;i<huffstring.length;i++){System.out.println(codes[i].name+"code:"+huffstring[i]);}System.out.println("编码："+getHuffmanCode(s));System.out.println("平均码长为："+getLength());}publicdoublegetLength(){doublen=0;for(inti=0;i<buffer.length();i++){n+=huffstring[i].length();}returnn/buffer.length();}publicStringgetHuffmanCode(Strings){StringBufferbuf=newStringBuffer();for(inti=0;i<s.length();i++){buf.append(getEachCode(s.substring(i,i+1)));}returnbuf.toString();}publicStringgetEachCode(Stringname){for(inti=0;i<buffer.length();i++){if(name.equals(codes[i].name)){returnhuffstring[i];}}return"";}publicvoidgetCode(intn,String[]thecodes,Stringthebuffer){if(n<thecodes.length){thecodes[n]=thebuffer;return;}getCode(codes[n].lc,thecodes,thebuffer+"0");getCode(codes[n].rc,thecodes,thebuffer+"1");}publicvoidgetHuffstring(){int[]twos={0,0};for(inti=buffer.length();i<2*buffer.length()-1;i++){twos=findLastTwo(0,i);codes[i].lc=twos[0];codes[i].rc=twos[1];codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;}}publicint[]findLastTwo(intstart,intend){double[]weights={1.0,1.0};int[]t={-1,-1};for(inti=start;i<end;i++){if(codes[i].pa!=-1)continue;if(weights[0]>codes[i].weight){weights[0]=codes[i].weight;t[1]=t[0];t[0]=i;}elseif(weights[1]>codes[i].weight){weights[1]=codes[i].weight;t[1]=i;}}codes[t[0]].pa=end;codes[t[1]].pa=end;returnt;}publicdoublehaveNum(charc,Strings){doublen=0;for(inti=0;i<s.length();i++){if(c==s.charAt(i))n++;}returnn/s.length();}publicstaticvoidmain(String[]args){System.out.print("输入编码字符串：");Scannersr=newScanner(System.in);newHuffman(sr.nextLine());}}publicclassEdgeimplementsComparable{publicinti,j,w;publicEdge(inti,intj,intw){this.i=i;this.j=j;this.w=w;}publicintcompareTo(Objecto){Edgeto=(Edge)o;if(this.w>to.w)return1;elseif(this.w==to.w)return0;elsereturn-1;}publicStringtoString(){return"start="+i+"||end="+j+"||w="+w;}}importjava.util.Scanner;publicclassHuffman{HuffmanCode[]codes;String[]huffstring;StringBufferbuffer=newStringBuffer();publicHuffman(Strings){for(inti=0;i<s.length();i++){if(buffer.indexOf(s.substring(i,i+1))==-1){buffer.append(s.charAt(i));}}System.out.println("字母："+buffer);huffstring=newString[buffer.length()];codes=newHuffmanCode[2*buffer.length()-1];for(inti=0;i<2*buffer.length()-1;i++)codes[i]=newHuffmanCode();for(inti=0;i<buffer.length();i++){codes[i].name=buffer.substring(i,i+1);codes[i].weight=haveNum(buffer.charAt(i),s);}getHuffstring();getCode(2*buffer.length()-2,huffstring,"");for(inti=0;i<huffstring.length;i++){System.out.println(codes[i].name+"code:"+huffstring[i]);}System.out.println("编码："+getHuffmanCode(s));System.out.println("平均码长为："+getLength());}publicdoublegetLength(){doublen=0;for(inti=0;i<buffer.length();i++){n+=huffstring[i].length();}returnn/buffer.length();}publicStringgetHuffmanCode(Strings){StringBufferbuf=newStringBuffer();for(inti=0;i<s.length();i++){buf.append(getEachCode(s.substring(i,i+1)));}returnbuf.toString();}publicStringgetEachCode(Stringname){for(inti=0;i<buffer.length();i++){if(name.equals(codes[i].name)){returnhuffstring[i];}}return"";}publicvoidgetCode(intn,String[]thecodes,Stringthebuffer){if(n<thecodes.length){thecodes[n]=thebuffer;return;}getCode(codes[n].lc,thecodes,thebuffer+"0");getCode(codes[n].rc,thecodes,thebuffer+"1");}publicvoidgetHuffstring(){int[]twos={0,0};for(inti=buffer.length();i<2*buffer.length()-1;i++){twos=findLastTwo(0,i);codes[i].lc=twos[0];codes[i].rc=twos[1];codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;}}publicint[]findLastTwo(intstart,intend){double[]weights={1.0,1.0};int[]t={-1,-1};for(inti=start;i<end;i++){if(codes[i].pa!=-1)continue;if(weights[0]>codes[i].weight){weights[0]=codes[i].weight;t[1]=t[0];t[0]=i;}elseif(weights[1]>codes[i].weight){weights[1]=codes[i].weight;t[1]=i;}}codes[t[0]].pa=end;codes[t[1]].pa=end;returnt;}publicdoublehaveNum(charc,Strings){doublen=0;for(inti=0;i<s.length();i++){if(c==s.charAt(i))n++;}returnn/s.length();}publicstaticvoidmain(String[]args){System.out.print("输入编码字符串：");Scannersr=newScanner(System.in);newHuffman(sr.nextLine());}}publicclassEdgeimplementsComparable{publicinti,j,w;publicEdge(inti,intj,intw){this.i=i;this.j=j;this.w=w;}publicintcompareTo(Objecto){Edgeto=(Edge)o;if(this.w>to.w)return1;elseif(this.w==to.w)return0;elsereturn-1;}publicStringtoString(){return"start="+i+"||end="+j+"||w="+w;}}2.importjava.util.ArrayList;importjava.util.Arrays;importjava.util.HashSet;importjava.util.Set;publicclassMiniSpanTree{publicstaticvoidPRIM(int[][]graph,intstart,intn){int[][]mins=newint[n][2];for(inti=0;i<n;i++){if(i==start){mins[i][0]=-1;mins[i][1]=0;}elseif(graph[start][i]!=-1){mins[i][0]=start;mins[i][1]=graph[start][i];}else{mins[i][0]=-1;mins[i][1]=Integer.MAX_VALUE;}System.out.println("mins["+i+"][0]="+mins[i][0]+"||mins["+i+"][1]="+mins[i][1]);}for(inti=0;i<n-1;i++){intminV=-1,minW=Integer.MAX_VALUE;for(intj=0;j<n;j++){if(mins[j][1]!=0&&minW>mins[j][1]){minW=mins[j][1];minV=j;}}mins[minV][1]=0;System.out.println("最小生成树的第"+i+"条最小边=<"+(mins[minV][0]+1)+","+(minV+1)+">，权重="+minW);for(intj=0;j<n;j++){if(mins[j][1]!=0){System.out.println("MINV="+minV+"||tree[minV][j]="+tree[minV][j]);if(graph[minV][j]!=-1&&graph[minV][j]<mins[j][1]){mins[j][0]=minV;mins[j][1]=graph[minV][j];}}}}}publicstaticvoidKRUSKAL(int[]V,Edge[]E){Arrays.sort(E);ArrayList<HashSet>sets=newArrayList<HashSet>();for(inti=0;i<V.length;i++){HashSetset=newHashSet();set.add(V[i]);sets.add(set);}System.out.println("++++++++++++++++++++++size="+sets.size());for(inti=0;i<E.length;i++){intstart=E[i].i,end=E[i].j;intcounti=-1,countj=-2;for(intj=0;j<sets.size();j++){HashSetset=sets.get(j);if(set.contains(start)){counti=j;}if(set.contains(end)){countj=j;}}if(counti<0||countj<0)System.err.println("没有在子树中找到节点，错误");if(counti!=countj){System.out.println("输出start="+start+"||end="+end+"||w="+E[i].w);HashSetsetj=sets.get(countj);sets.remove(countj);HashSetseti=sets.get(counti);sets.remove(counti);seti.addAll(setj);sets.add(seti);}else{System.out.println("他们在一棵子树中，不能输出start="+start+"||end="+end+"||w="+E[i].w);}}}publicstaticvoidmain(String[]args){int[][]tree={{-1,6,1,5,-1,-1},{6,-1,5,-1,3,-1},{1,5,-1,5,6,4},{5,-1,5,-1,-1,2},{-1,3,6,-1,-1,6},{-1,-1,4,2,6,-1}};MiniSpanTree.PRIM(tree,0,6);System.out.println("++++++++++++++++++++++++++++");int[]V={1,2,3,4,5,6};Edge[]E=newEdge[10];E[0]=newEdge(1,2,6);E[1]=newEdge(1,3,1);E[2]=newEdge(1,4,5);E[3]=newEdge(2,3,5);E[4]=newEdge(2,5,3);E[5]=newEdge(3,4,5);E[6]=newEdge(3,5,6);E[7]=newEdge(3,6,4);E[8]=newEdge(4,6,2);E[9]=newEdge(5,6,6);MiniSpanTree.KRUSKAL(V,E);}}3.publicclassDijkstra{staticintM=10000;publicstaticvoidmain(String[]args){int[][]weight1={ {0,3,2000,7,M},{3,0,4,2,M},{M,4,0,5,4},{7,2,5,0,6},{M,M,4,6,0}};int[][]weight2={{0,10,M,30,100},{M,0,50,M,M},{M,M,0,M,10},{M,M,20,0,60},{M,M,M,M,0}};intstart=0;int[]shortPath=Dijsktra(weight2,start);for(inti=0;i<shortPath.length;i++)System.out.println("从"+start+"出发到"+i+"的最短距离为："+shortPath[i]);}pu