武漢紡織大學(xué)《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告

武漢紡織大學(xué)《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告班級(jí)：管工類班級(jí)：管工類專業(yè)班:序號(hào)：實(shí)驗(yàn)時(shí)間：2014年5月16日指導(dǎo)教師:實(shí)驗(yàn)三：圖的基本操作與應(yīng)用一、實(shí)驗(yàn)?zāi)康模?、掌握?qǐng)D的幾種主要存儲(chǔ)方法及基本操作21、掌握?qǐng)D的幾種主要存儲(chǔ)方法及基本操作2、掌握?qǐng)D的兩種遍歷方法3、4、掌握利用普里姆算法和克魯斯卡爾算法求取最小生成樹的方法掌握求取AOE網(wǎng)關(guān)鍵路徑的方法，以實(shí)現(xiàn)項(xiàng)目時(shí)間管理二、實(shí)驗(yàn)內(nèi)容：3、4、1、編寫程序，輸出圖的鄰接矩陣，輸出兩種遍歷序列，并求出最小生成樹。實(shí)驗(yàn)步驟：、在Java語言編輯環(huán)境中新建程序，輸入頂點(diǎn)集合和邊集合，構(gòu)造一個(gè)圖7-15所示的帶權(quán)圖，可參考書本225頁示例程序；、對(duì)該帶權(quán)圖，進(jìn)行插入頂點(diǎn)、插入邊、刪除頂點(diǎn)、刪除邊操作，并輸出操作后的鄰接矩陣，可參考書本226-228頁示例程序；、輸出從頂點(diǎn)'A'開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的序列，可參考書本238、240頁示例程序；、輸出運(yùn)用普里姆算法求出的最小生成樹，可參考書本245頁示例程序。2、設(shè)計(jì)一個(gè)程序求出完成整項(xiàng)工程至少需要多少時(shí)間以及整項(xiàng)工程中的關(guān)鍵活動(dòng)。實(shí)驗(yàn)步驟：、在Java語言編輯環(huán)境中新建程序，輸入如下圖所示的AOE網(wǎng)；、按照關(guān)鍵路徑求取步驟，求出各個(gè)頂點(diǎn)的最早開始時(shí)間和最遲開始時(shí)間；、求出各個(gè)活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間；、找出該AOE網(wǎng)的關(guān)鍵路徑，并計(jì)算出該項(xiàng)目的完成時(shí)間。關(guān)鍵路徑相關(guān)時(shí)間知識(shí)點(diǎn)：設(shè)活動(dòng)ai由弧<j,k>(即從頂點(diǎn)j到k)表示，其持續(xù)時(shí)間記為dut(<j,k>),則：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)求ve(i)和vl(j)分兩步：(1).從ve(1)二0開始向前遞推ve⑴=Max{ve(i)+dut(<i,j>)}<i,j>ET,2<=j<=n，其中，T是所有以j為弧頭的弧的集合。(2).從vl(n)=ve(n)開始向后遞推vl(i)=Min{vl(j)-dut(<i,j>)}<i,j>ES,1<=i<=n-1,其中，S是所有以i為弧尾的弧的集合。求關(guān)鍵路徑的算法：、輸入￡條弧<j,k>,建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)；、從起始點(diǎn)出發(fā)，令ve[0]=0,按拓?fù)漤樞蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間ve[i](1<=i<=n-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n,則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止，否則轉(zhuǎn)到步驟③；、從終結(jié)點(diǎn)vn出發(fā)，令vl[n-1]=ve[n-1],按逆拓?fù)漤樞蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vl[i](n-2>=i>=0)；、根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時(shí)間e(s)和最遲開始時(shí)間l(s)。若某弧滿足條件e(s)=l(s)，則為關(guān)鍵活動(dòng)。三、操作步驟：Testi代碼:Graphi.javapackageFrist;publicclassGraphl{publicstaticvoidmain(String[]args){String[]vertices={"A","B","C","D","E"};Edgeedges[]={newEdge(0,1,5),newEdge(0,3,2),TOC\o"1-5"\h\znewEdge(1,0,5),newEdge(1,2,7),newEdge(1,3,6),newEdge(2,1,7),newEdge(2,3,8),newEdge(2,4,3),newEdge(3,0,2),newEdge(3,1,6),newEdge(3,2,8),newEdge(3,4,9),newEdge(4,2,3),newEdge(4,3,9)};AdjMatrixGraph<String>graph二newAdjMatrixGraph<String>(vertices,edges);System.out.println("帶權(quán)無向圖,"+graph.toString());System.out.println("插入頂點(diǎn)「,插入邊(A,F,20),刪除頂點(diǎn)C,刪除邊(D,E)");inti二graph.insertVertex("F");graph.insertEdge(0,i,20);graph.insertEdge(i,0,20);graph.removeVertex(2);graph.removeEdge(2,3);graph.removeEdge(3,2);System.out.println(graph.toString());AdjMatrixGraph<String>graph1二newAdjMatrixGraph<String>(vertices,edges);System.out.print("深度優(yōu)先遍歷序列為:");graph1.DFSTraverse(0);System.out.print("廣度優(yōu)先遍歷序列為:");graph1.BFSTraverse(0);AdjMatrixGraph<String>graph2二newAdjMatrixGraph<String>(vertices,edges);System.out.print("帶權(quán)無向圖,"+graph2.toString());graph2.minSpanTree_prim();}}LList.javapackageFrist;publicinterfaceLList<T>{booleanisEmpty();intlength();Tget(inti);voidset(inti,Tx);voidinsert(inti,Tx);Tremove(inti);voidremoveAll();}QQueue.javapackageFrist;publicinterfaceQQueue<T>{booleanisEmpty();voidenqueue(Tx);Tdequeue();}SeqList.javapackageFrist;publicclassSeqList<T>implementsLList<T>{privateObject[]element;privateintlen;publicSeqList(intsize){this.element二newObject[size];this.len=0;}publicSeqList(){this(64);}publicbooleanisEmpty(){returnthis.len二二0;}publicintlength(){returnthis.len;}publicTget(inti){if(i>=0&&i<this.len)return(T)this.element[i];returnnull;}publicvoidset(inti,Tx){if(x二二null)return;if(i>=0&&i<this.len)this.element[i]=x;elsethrownewIndexOutOfBoundsException(i+"");}publicStringtoString(){Stringstr="(''；if(this.len>0)str+=this.element[0].toString();for(inti=1;i<this.len;i++)str+=",'’+this.element[i].toString();returnstr+')';}publicvoidinsert(inti,Tx){if(x二二null)return;if(this.len二二element.length){Object[]temp=this.element;this.element二newObject[temp.length*2];for(intj=0;j<temp.length;i++)

this.element[i]=temp[j];}if(i<0)i=0;if(i>this.len)i二this.len;for(intj二this.len-1;j>=i;j--)this.element[j+1]二this.element[j];this.element[i]二x;this.len++;}publicvoidappend(Tx){insert(this.len,x);}publicTremove(inti){if(this.len二二0||i<0||i>=this.len)returnnull;Told二(T)this.element[i];for(intj=i;j<this.len-1;j++)this.element[j]=this.element[j+1];this.element[this.len-1]=null;this.len--;returnold;}publicvoidremoveAll(){this.len=0;}}SeqQueue.javapackageFrist;publicclassSeqQueue<T>implementsQQueue<T>{privateObjectelement[];privateintfront,rear;publicSeqQueue(intlength){if(length<64)length=64;this.element二newObject[Math.abs(length)];this.front二this.rear=0;}publicSeqQueue(){this(64);}publicbooleanisEmpty(){returnthis.front二二this.rear;}publicvoidenqueue(Tx){if(x二二null)return;if(this.front二二(this.rear+1)%this.element.length){Object[]temp=this.element;this.element二newObject[temp.length*2];inti二this.front,j二0;while(i!二this.rear){this.element[j]二temp[i];i=(i+1)%temp.length;j++;}this.front=0;this.rear二j;}this.element[this.rear]=x;this.rear=(this.rear+1)%this.element.length;}publicTdequeue(){if(isEmpty())returnnull;Ttemp=(T)this.element[this.front];this.front=(this.front+1)%this.element.length;returntemp;}publicStringtoString(){Stringstr="(''；if(!isEmpty()){str+=this.element[this.front].toString();inti=(this.front+1)%this.element.length;while(i!=this.rear){str+=",'’+this.element.length;}}returnstr+')';}}GGraph.javapackageFrist;publicinterfaceGGraph<T>{publicstaticfinalintMAX_WEIGHT=99999;intvertexCount();Tget(inti);intgetWeight(inti,intj);intinsertVertex(Tx);voidinsertEdge(inti,intj,intweight);voidremoveEdge(inti,intj);voidremoveVertex(inti);intgetNextNeighbor(inti,intj);voidDFSTraverse(inti);voidBFSTraverse(inti);}AbstractGraph.javapackageFrist;publicabstractclassAbstractGraph<T>implementsGGraph<T>{publicabstractintvertexCount();publicabstractTget(inti);publicabstractintgetNextNeighbor(inti,intj);publicvoidDFSTraverse(inti){boolean[]visited二newboolean[this.vertexCount()];intj二i;do{if(!visited[j]){System.out.print("{'');this.depthfs(j,visited);System.out.print("}'');}j=(j+1)%this.vertexCount();}while(j!=i);System.out.println();}privatevoiddepthfs(inti,boolean[]visited){System.out.print(this.get(i)+"'');visited[i]=true;intj二this.getNextNeighbor(i,-1);while(j!=-1){if(!visited[j])depthfs(j,visited);j二this.getNextNeighbor(i,j);}}publicvoidBFSTraverse(inti){boolean[]visited二newboolean[this.vertexCount()];intj二i;do{if(!visited[j]){System.out.print("{'');breadthfs(j,visited);System.out.print("}'');}j=(j+1)%this.vertexCount();}while(j!二i);System.out.println();}privatevoidbreadthfs(inti,boolean[]visited){System.out.print(this.get(i)+'''');visited[i]=true;SeqQueue<Integer>que=newSeqQueue<Integer>(this.vertexCount());que.enqueue(newInteger(i));while(!que.isEmpty()){i二que.dequeue().intValue();intj二this.getNextNeighbor(i,-1);while(j!二-1){if(!visited[j]){System.out.print(this.get(j)+"'');visited[j]=true;que.enqueue(newInteger(j));}j二this.getNextNeighbor(i,j);}}}publicabstractintgetWeight(inti,intj);publicvoidminSpanTree_prim(){Edge[]mst=newEdge[vertexCount()-1];for(inti=0;i<mst.length;i++)mst[i]=newEdge(0,i+1,this.getWeight(0,i+1));for(inti=0;i<mst.length;i++){intminweight=MAX_WEIGHTintmin二i;for(intj=i;j<mst.length;j++)if(mst[j].weight<minweight){minweight二mst[j].weight;min二j;}Edgetemp二mst[i];mst[i]二mst[min];mst[min]二temp;inttv=mst[i].dest;for(intj=i+1;j<mst.length;j++){intv=mst[j].dest;if(this.getWeight(tv,v)<mst[j].weight){mst[i].weight二this.getWeight(tv,v);mst[j].start二tv;}}}System.out.print("\n最小生成樹邊的集合:")；intmincost=0;for(inti=0;i<mst.length-1;i++){System.out.print(mst[i]+"'');mincost+=mst[i].weight;}System.out.print(",最小代價(jià)為"+mincost);}}publicclassAdjMatrixGraph<T>extendsAbstractGraph<T>{protectedSeqList<T>vertexlist;protectedint[][]adjmatrix;privatefinalintMAX_WEIGHT=99999;publicAdjMatrixGraph(intsize){size=size<10?10:size;this.vertexlist二newSeqList<T>(size);this.adjmatrix二newint[size][size];for(inti=0;i<size;i++)for(intj=0;j<size;j++)this.adjmatrix[i][j]=(i二二j)?0:MAX_WEIGHT;}publicAdjMatrixGraph(T[]vertices,Edge[]edges){this(vertices.length);if(vertices二二null)return;for(inti=0;i<vertices.length;i++)insertVertex(vertices[i]);if(edges!=null)for(intj=0;j<edges.length;j++)insertEdge(edges[j]);}publicvoidinsertEdge(inti,intj,intweight){intn二this.vertexCount();if(i>0&&i<n&&j>=0&&j<n&&i!二j&&this.adjmatrix[i][j]二二MAX_WEIGHT)this.adjmatrix[i][j]=weight;}publicvoidinsertEdge(Edgeedge){this.insertEdge(edge.start,edge.dest,edge.weight);}publicintinsertVertex(Tx){this.vertexlist.append(x);if(this.vertexCount()>this.adjmatrix.length){inttemp[][]=adjmatrix,i,j;this.adjmatrix二newint[temp.length*2][temp.length*2];for(i=0;i<temp.length;i++){for(j=0;j<temp.length;j++)this.adjmatrix[i][j]二temp[i][j];for(j=temp.length;j<temp.length*2;j++)this.adjmatrix[i][j]=MAX_WEIGHT;}for(i=temp.length;i<temp.length*2;i++)for(j=0;j<temp.length*2;j++)this.adjmatrix[i][j]=(i二二j)?0:MAX_WEIGHT;}returnthis.vertexlist.length()-1;}publicintvertexCount(){returnthis.vertexlist.length();}publicTget(inti){returnthis.vertexlist.get(i);}publicintgetWeight(inti,intj){returnthis.adjmatrix[i][j];}publicStringtoString(){Stringstr="頂點(diǎn)集合："+this.vertexlist.toString()+"\n鄰接矩陣：\n";intn二this.vertexCount();for(inti=0;i<n;i++){for(intj=0;j<n;j++)str+=this.adjmatrix[i][j]二二MAX_WEIGHT?"od:""+this.adjmatrix[i][j];str+="\n";}returnstr;}publicvoidremoveEdge(inti,intj){if(i>=0&&i<vertexCount()&&j>=0&&j<vertexCount()&&i!二j)this.adjmatrix[i][j]=MAX_WEIGHT;}publicvoidremoveVertex(inti){intn二this.vertexCount();if(i<0||i>n)return;this.vertexlist.remove(i);for(intj=0;j<i;j++)for(intk=i+1;k<n;k++)this.adjmatrix[j][k-1]=this.adjmatrix[j][k];for(intj=i+1;j<n;j++)for(intk=0;k<i;k++)this.adjmatrix[j-1][k]二adjmatrix[j][k];for(intj=i+1;j<n;j++)for(intk=i+1;k<n;k++)this.adjmatrix[j-1][k-1]=this.adjmatrix[j][k];}OverridepublicintgetNextNeighbor(inti,intj){intn二this.vertexCount();if(i>=0&&i<n&&j>=-1&&j<n&&i!=j)for(intk=j+1;k<n;k++)if(this.adjmatrix[i][k]>0&&this.adjmatrix[i][k]<MAX_WEIGHT)returnk;return-1;}}Edge.javapackageFrist;publicclassEdgeimplementsComparable<Edge>{publicintstart,dest,weight;publicEdge(intstart,intdest,intweight){super();this.start二start;this.dest二dest;this.weight二weight;}publicStringtoString(){return"(''+start+",''+dest+",''+weight+")'';}publicintcompareTo(Edgee){if(this.start!=e.start)returnthis.start二e.start;returnthis.dest二e.dest;}}運(yùn)行結(jié)果：qMarkers口Properties聚Servers[罵DataSourceExplorer白Snippets手ConcoleS3戰(zhàn)ETrninEiMcImGraphl[JavdApplicatiDn]C;\Progranri]Files\Ji3va,iijdlkl.7.0_40\bin，J-av-3W.eK.e帶眼?Z向因由/IS點(diǎn)握含.（A」日j^AE）生炎t:M：@caca5^7?7e26Sco68檔人H點(diǎn)FpW、*3,F,明)'皂送耳M原卷過《D,E}而成定臺(tái)：0E5e2EMC-320叫如網(wǎng)合拜!:尤豹法E申月為.{A}(BCDE}"?st元汽也元中ri打：(A){KDE；耳無同股-I!巨至音：(A^B^C,&hE)蒂垸E主，0?a5e037伊8■JO?□6MS309取，瑚硬iU索臺(tái)：七QL剝律t*娘Test2代碼;packageSecond;publicclassGraphT2{publicstaticvoidmain(String[]args){Graphgraph二newGraph(9);graph.add("T');graph.add("2'');graph.add("3'');graph.add("4'');graph.add("5'');graph.add("6'');graph.add(''7'');graph.add(''8'');graph.add('9');graph.addEdge(0,T,6);graph.addEdge(0,2,4);graph.addEdge(0,3,5);graph.addEdge(T,4,T);graph.addEdge(2,4,T);graph.addEdge(3,5,2);graph.addEdge(4,6,9);graph.addEdge(4,7,7);graph.addEdge(5,7,4);graph.addEdge(6,8,2);graph.addEdge(7,8,4);if(graph.topo()){graph.calculate();int[]e=graph.getE();int[]l=graph.getL();int[]key=graph.getKey();int[]ve二graph.getVE();int[]vl二graph.getVl();System.out.println(H事件的最早發(fā)生時(shí)間：’);for(intw=0;w<ve.length;w++){System.out.print(ve[w]+‘‘‘‘)；}System.out.println();System.out.println(“事件的最晚發(fā)生時(shí)間：“);for(intw=0;w<vl.length;w++){System.out.print(vl[w]+‘‘‘‘)；}System.out.println();System.out.println(“活動(dòng)的最早發(fā)生時(shí)間：‘‘);for(intw=0;w<e.length;w++){System.out.print(e[w]+"");}System.out.println();System.out.println("活動(dòng)的最遲發(fā)生時(shí)間：");for(intw=0;w<l.length;w++){System.out.print(l[w]+"");}System.out.println();System.out.println("關(guān)鍵活動(dòng)有：")；for(intw=0;w<graph.getKNum();w++){System.out.print(key[w]+"");}System.out.println();}}}Graph.javapackageSecond;publicclassGraph{privateVertex[]vertexs;privateLink[]adjTab;privateintpos=-1;privateStackstack;privateStackrestack;privateStackbackstack;privateintvertexNum;privateNodestart;privateintedgeCount;privateintkNum;privateint[]ve;privateint[]vl;privateint[]e;privateint[]l;privateint[]key;publicintcacuTotalTime(){NodecurrNode二adjTab[0].head();intcurrNodeNum=0;booleanisSameLink二false;intcurrKeyNum二0;inttotalTime二0;for(intcurrLink=0;currLink<adjTab.length-1;){currNode二currNode.getNext();if(key[currKeyNum]二二currNodeNum&&(!isSameLink)){totalTime+=currNode.getWeight();currKeyNum++;isSameLink二true;if((Integer)currNode.getData()二二(adjTab.length-1))break;}elseif(key[currKeyNum]二二currNodeNum&&isSameLink){currKeyNum++;}currNodeNum++;if(currNode.getNext()二二null){currLink++;if(currLink<adjTab.length-1){currNode二adjTab[currLink].head();isSameLink二false;}}}returntotalTime;}publicStringgetVertexValue(inti){return(String)vertexs[i].value();}publicGraph(intsize){vertexNum二size;vertexs二newVertex[size];adjTab二newLink[size];stack二newStack(size);restack二newStack(size);backstack二newStack(size);for(inti=0;i<size;i++){adjTab[i]=newLink(i);}ve二newint[size];vl二newint[size];for(intd=0;d<size;d++){vl[d]=-1;}edgeCount=0;}voidadd(Objectobj){assertpos<vertexs.length;vertexs[++pos]=newVertex(obj);voidaddEdge(intfrom,intto,intweight){adjTab[from].addtail(to,weight);vertexs[to].in++;edgeCount++;}booleantopo(){intcount=0;for(inti=0;i<vertexNum;i++){if(vertexs[i].in二二0){stack.push(i);start二adjTab[i].head();}}while(!stack.isEmpty()){restack.push(stack.peek());intj二stack.pop();count++;Nodep二adjTab[j].head();Nodeearlyest二p;intpreweight=ve[j];while(p!二null){intk=((Integer)p.getData()).intValue();vertexs[k].in--;if(vertexs[k].in二二0)stack.push(k);p=p.getNext();if(p!二null){inttemp=((Integer)p.getData()).intValue();if(p.getWeight()+preweight>ve[temp]){

ve[temp]=p.getWeight()+preweight;}}}}if(count<vertexNum){System.out.println("有回路，無法得到關(guān)鍵路徑！")；returnfalse;}returntrue;}publicvoidcalculate(){ints二0;intt二0;e二newint[edgeCount];l二newint[edgeCount];key二newint[edgeCount];backstack.push(restack.peek());intz二restack.pop();vl[z]=ve[z];while(!restack.isEmpty()){backstack.push(restack.peek());intq二restack.pop();Nodevertex二adjTab[q].head();for(intk=0;k<backstack.getCount();k++){Nodever二vertex;while(ver.getNext()!二null){if(((Integer)ver.getNext().getData()).intValue()二二backstack.getElement(k)){intyuanxian=vl[((Integer)vertex.getData()).intValue()];intjiangyao=vl[backstack.getElement(k)]-ver.getNext().getWeight();if(jiangyao<yuanxian||yuanxian二二-1){vl[((Integer)vertex.getData()).intValue()]=vl[backstack.getElement(k)]-ver.getNext().getWeight();}}ver二ver.getNext();}}}for(inth=0;h<vertexNum;h++){Nodebegin二adjTab[h].head();Nodebackbegin二begin;if(begin!二null){while(begin.getNext()!二null){e[s++]=ve[((Integer)backbegin.getData()).intValue()];l[t++]=vl[((Integer)begin.getNext().getData()).intValue()]-begin.getNext().getWeight();begin二begin.getNext();}}}kNum二0;for(intw=0;w<e.length;w++){if(l[w]-e[w]<=0){key[kNum++]=w;}}publicint[]getVE(){returnve;}publicint[]getVl(){returnvl;}publicint[]getE(){returne;}publicint[]getL(){returnl;}publicint[]getKey(){returnkey;}publicintgetKNum(){returnkNum;}}Link.javapackageSecond;publicclassLink{privateNodehead;privateintlength;publicLink(intindex){head二newNode(index,null,0);length=0;}publicvoidaddhead(Objectitem,intweight){Nodenode二newNode(item,null,weight);node.setNext(head.getNext());head.setNext(node);length++;}publicvoidaddtail(Objectitem,intweight){Nodenode二newNode(item,null,weight);Nodetemp二head;while(null!=temp.getNext()){temp二temp.getNext();}temp.setNext(node);length++;}publicNodehead(){returnhead;}publicvoidfind(intindex){if(index<1||index>length){System.out.print("此位置空！");}Nodetemp二head;for(inti=0;i<index;i++){temp二temp.getNext();}System.out.println("鏈表中第"+index+"個(gè)位置的值為"+temp.getData());}publicvoiddelindex(intindex){if(index<1||index>length){System.out.print("位置不存在！");}Nodetemp二he