基礎數(shù)據(jù)結構程序設計報告

算法與數(shù)據(jù)結構課程設計報告系（院）：計算機科學學院專業(yè)班級：計科11101姓名：學號：##########指導教師：%%%%%%%%%設計時間：2014618-2012629?、設計目的…錯誤！未定義書簽。二、 設計任務及要求錯誤！未定義書簽。三、 設計方案…錯誤！未定義書簽。四、 代碼實現(xiàn)…錯誤！未定義書簽。五、 測試六、 可改進的的地方七、難點與收獲一?設計目的能根據(jù)實際問題的具體情況，結合數(shù)據(jù)結構課程中的基本理論和基本算法，分析并正確確定數(shù)據(jù)的邏輯結構，合理地選擇相應的存儲結構，并能設計出解決問題的有效算法。提高程序設計和調試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改。初步掌握軟件開發(fā)過程中問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。培養(yǎng)根據(jù)選題需要選擇學習書籍，查閱文獻資料的自學能力。二、設計任務：設計一個基于DOS菜單的應用程序。要利用多級菜單實現(xiàn)各種功能。內容如下：無向圖的基本操作及應用創(chuàng)建無向圖的鄰接矩陣創(chuàng)建無向圖的鄰接表無向圖的深度優(yōu)先遍歷無向圖的廣度優(yōu)先遍歷無向網的基本操作及應用創(chuàng)建無向網的鄰接矩陣創(chuàng)建無向網的鄰接表求最小生成樹有向圖的基本操作及應用創(chuàng)建有向圖的鄰接矩陣創(chuàng)建有向圖的鄰接表

拓撲排序有向網的基本操作及應用創(chuàng)建有向網的鄰接矩陣創(chuàng)建有向網的鄰接表關鍵路徑單源最短路徑每對頂點之間的最短路徑三、設計方案DOS界面的主菜單d:字呈l=?5?i-\Debl;g\程序設計，亡灼--.一(圖網圖網--.一(圖網圖網X..冋..冋..冋..冋"33一無無i'Qi'二12345二}it帝帝帝帝一弔用用用一應應應應一及及及及^￡￡￡FvoidShowMainMenu(){cout〈〈"\n";cout〈〈"*****************圖的基本操作及應用****************\n";cout〈〈"*1無向圖的基本操作及應用*\n";cout〈〈"*2無向網的基本操作及應用*\n";cout〈〈"*3有向圖的基本操作及應用*\n";cout〈〈"*4有向網的基本操作及應用*\n";cout〈〈"*5退出*\n";pp-i—// \-iz-> ■|()|||\\ #r?#r?#r?#r? \II}voidUDG1(){do{cout〈〈"\n";cout〈〈"****************無向圖的基本操作及應用*************\n";TOC\o"1-5"\h\zcout〈〈"*1創(chuàng)建無向圖的鄰接矩陣 *\n";cout〈〈"*2創(chuàng)建無向圖的鄰接表 *\n";cout〈〈"*3無向圖的深度優(yōu)先遍歷 *\n";cout〈〈"*4無向圖的廣度優(yōu)先遍歷cout〈〈"*5退出*\n";*\n";X-V .r-?-4—// \*~\ ■ff1III\\ *T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?\IIcin〉〉n;switch(n){case1:創(chuàng)建無向圖的鄰接矩陣break;case2:創(chuàng)建無向圖的鄰接表break;case3:無向圖的深度優(yōu)先遍歷break;case4:無向圖的廣度優(yōu)先遍歷break;default:if(n!=5)cout<<"錯誤，重新輸入\n";}}while(n!=5);}voidUDN1(){do{cout〈〈"\n";cout〈〈"***************無向網的基本操作及應用**************\n";cout〈〈"*1創(chuàng)建無向網的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建無向網的鄰接表*\n";cout〈〈"*3最小生成樹*\n";cout〈〈"*4退出*\n";X-V .r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:創(chuàng)建無向網的鄰接矩陣break;case2:創(chuàng)建無向網的鄰接表break;case3:最小生成樹break;default:if(n!=4)cout〈〈"錯誤，重新輸入\n";}}while(n!=4);}voidDG1(){do{cout〈〈"\n";cout〈〈"***************有向圖的基本操作及應用**************\n";cout〈〈"*1創(chuàng)建有向圖的鄰接表*\n";cout〈〈"*2創(chuàng)建有向圖的鄰接矩陣*\n";cout〈〈"*3拓撲排序*\n";cout〈〈"*4退出*\n";X-V.r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:創(chuàng)建有向圖的鄰接表break;case2:創(chuàng)建有向圖的鄰接矩陣break;case3:拓撲排序break;default:if(n!=4)cout〈〈"錯誤，重新輸入\n";}}while(n!=4);}voidDN1(){do{cout〈〈"\n";cout〈〈"***************有向網的基本操作及應用**************\n";cout〈〈"*1創(chuàng)建有向網的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建有向網的鄰接表*\n";cout〈〈"*3關鍵路徑*\n";cout〈〈"*4單源最短路徑*\n";cout〈〈"*5每對頂點間的最短路徑*\n";cout〈〈"*6退出*\n";X-V.r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:創(chuàng)建有向網的鄰接矩陣break;case2:創(chuàng)建有向網的鄰接表break;case3:關鍵路徑break;case4:單源最短路徑break;case5:每對頂點間的最短路徑print1(MK);break;default:if(n!=6)cout〈〈"錯誤，重新輸入\n";}}while(n!=6);}voidmain(){intn;do{ShowMainMenu();cin〉〉n;switch(n){case1:UDG1();break;case2:UDN1();break;case3:DG1();break;case4:DN1();break;default:if(n!=5)cout<<"錯誤，重新輸入"；}}while(n!=5);}四、實現(xiàn)代碼：#include〈iostream〉#include〈stdlib.h〉#include〈iomanip〉#include〈stdio.h〉#include〈stack〉usingnamespacestd;#defineMAX_VERTEX_NUM100//最大頂點個數(shù)#defineINFINITY10000//最大值#defineFALSE0#defineTRUE1typedefintVRType; //頂點關系(表示是否相鄰)typedefcharVertexType;typedefintInfoType;//弧相關信息typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向圖，有向網，無向圖，無向網}typedefstructArcCellVRTypeadj;//權值InfoType*info;//該弧相關信息的指針}ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//頂點向量AdjMartixarcs; //鄰接矩陣intvexnum,arcnum; //圖當前頂點數(shù)，弧數(shù)GraphKindKind; //圖的類型}MGraph;intLocateVex(MGraphG,VertexTypev)//若圖中存在v,返回v在圖中的位置{for(inti=O;i〈G.vexnum;i++){if(v==G.vexs[i])returni;}return-2;}intCreatMUDN(MGraph&G){//構造無向網inti,j,w;charch;VertexTypev1,v2;cout〈〈"輸入頂點數(shù)，弧數(shù)："〈〈endl;cin〉〉G.vexnum〉〉G.arcnum; //輸入當前頂點數(shù)弧數(shù)是否有弧信息cout〈〈"輸入頂點（字符型）："〈〈endl;for(i=0;i〈G.vexnum;i++) //初始化鄰接矩陣{for(j=0;j〈G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info二NULL;}}COUt＜〈〃輸入第〃〈〈i+l〈〈〃個頂點：〃；cin〉〉ch;G.vexs[i]二ch;}for(intk=O;k〈G.arcnum;k++){cout〈〈〃輸入第〃〈〈k+1〈〈〃條?。骸ā础磂ndl;cin〉〉v1〉〉v2;cout〈〈〃輸入弧的權值：〃〈〈endl;cin〉〉w;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj二w;//對弧寫入權值G.arcs[j][i].adj二w;//對稱弧賦值}}return1;}voidCreatUDG(MGraph&G)inti,j,k;charch;VertexTypev1,v2;cout〈〈〃輸入頂點數(shù)，弧數(shù)：〃〈〈endl;cin〉〉G.vexnum〉〉G.arcnum;cout〈〈〃輸入頂點(字符型)：〃〈〈endl;for(i=O;i〈G.vexnum;i++){for(j=O;j〈G.vexnum;j++){G.arcs[i][j].adj=O;G.arcs[i][j].info二NULL;}}for(i=O;i〈G.vexnum;i++) //頂點信息cout〈〈〃輸入第〃〈〈i+1〈〈〃個頂點：〃；cin>>ch;G.vexs[i]二ch;for(k=0;k〈G.arcnum;k++){cout〈〈"輸入第"〈〈k+l〈〈"條弧："〈〈endl;cin〉〉vl〉〉v2;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=1;//對弧寫入權值G.arcs[j][i].adj=1;//對稱弧賦值}}}voidScanAll(MGraphG)inti;cout〈〈"圖中頂點信息如下："〈〈endl;for(i=0;i〈G.vexnum;i++)cout〈〈G.vexs[i]〈〈"";cout〈〈"鄰接矩陣如下："〈〈endl;cout〈〈setw(5)〈〈"矩陣："；for(i=0;i〈G.vexnum;i++)cout〈〈setw(8)〈〈G.vexs[i];cout〈〈endl;for(i=O;i〈G.vexnum;i++){cout〈〈setw(6)〈〈G.vexs[i];for(intj=O;j〈G.vexnum;j++)cout〈〈setw(8)〈〈G.arcs[i][j].adj;cout〈〈endl;}}typedefstructArcNode{intadjvex;//該弧指向頂點的位置structArcNode*nextare;//指向下一條弧的指針I(yè)nfoType*info;//該弧相關信息的指針}ArcNode;typedefstructVNodeVertexTypedata;//頂點信息ArcNode*firstare;//指向第一條依附該頂點弧的指針}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;//************************創(chuàng)建無向圖的鄰接表**************************voidCreatALGUDG(ALGraph&G){inti,s,d;ArcNode*p,*q;cout〈〈"輸入圖的頂點數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=1;i〈二G.vexnum;i++){cout〈〈"\n輸入第"〈〈i〈〈"個頂點的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare二NULL;}for(i=l;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結點和尾結點(整數(shù))：〃；cin〉〉s〉〉d;p=newArcNode;p-〉adjvex=d;p-〉nextare二G.vertices[s].firstare;G.vertices[s].firstare=p;//將新建的以d為信息的表結點p插入s單鏈表的頭結點后q=newArcNode;q-〉adjvex=s;q-〉nextare=G.vertices[d].firstare;G.vertices[d].firstare=q;}G.kind=UDG;}//***********************輸出鄰接表**********************voidPrintALGUDG(ALGraphG)ArcNode*p;inti;for(i=l;i〈二G.vexnum;i++){p=G.vertices[i].firstare;cout〈〈G.vertices[i].data;while(p!=NULL){cout〈〈"〈"〈〈G.vertices[i].data〈〈"，"〈〈G.vertices[p->adjvex].data〈〈"〉"；p=p-〉nextare;}printf(〃\n〃)；}intvisited[MAX_VERTEX_NUM];voidDFS(ALGraphG,intv){ArcNode*p;cout〈〈G.vertices[v].data;visited[v]=1;p=G.vertices[v].firstare;while(p!=NULL){if(visited[p-〉adjvex]==O)DFS(G,p-〉adjvex);p=p-〉nextare;}}voidDFSTraverse(ALGraphG){intv;for(v=1;v〈二G.vexnum;v++)visited[v]=0;for(v=1;v〈二G.vexnum;v++)if(visited[v]==0)DFS(G,v);}intFirstAdjvex(ALGraphG,intv){ArcNode*p;if(p=G.vertices[v].firstare)returnp—〉adjvex;return0;}intNextAdjVex(ALGraphG,intv,intw){ArcNode*p;p=G.vertices[v].firstare;while(p-〉adjvex!=w)p=p-〉nextare;if(p—>nextare)returnp—>nextarc—〉adjvex;elsereturn0;}typedefstructQnode{intdata;structQnode*next;}Qnode;typedefstruct{Qnode*front;Qnode*rear;}Linkqueue;intInitqueue(Linkqueue*Q){Q—>front=(Qnode*)malloc(sizeof(Qnode));Q—〉rear=Q—>front;if(!Q—>front)return0;Q—>front-〉next二NULL;return1;}intEnqueue(Linkqueue*Q,int*e){Qnode*p;p=(Qnode*)malloc(sizeof(Qnode));if(!p)return0;p-〉data=*e;p-〉next二NULL;Q—〉rear->next二p;Q->rear=p;return1;}voidDequeue(Linkqueue*Q,int*e){Qnode*p;if(Q->front==Q->rear)cout〈〈""空""〈〈endl;p=Q->front—〉next;*e=p-〉data;Q—〉front—〉next二p—〉next;if(Q-〉rear==p)Q—〉rear二Q—〉front;free(p);}voidBFSTraverse(ALGraphG){intv,w,u;for(v=l;v〈二G.vexnum;++v)visited[v]=0;LinkqueueQ;Initqueue(&Q);for(v=1;v〈二G.vexnum;v++)if(!visited[v]){visited[v]=1;cout〈〈G.vertices[v].data;Enqueue(&Q,&v);while(Q.front!=Q.rear){Dequeue(&Q,&u);for(w=FirstAdjvex(G,u);w〉=1;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=1;cout〈〈G.vertices[w].data;Enqueue(&Q,&w);}voidMiniSpanTree(MGraphG,VertexTypeu){intk;intj,i;intcount=0,min;struet{VertexTypeadjvex;intlowcost;}elosedge[MAX_VERTEX_NUM];k=LocateVex(G,u);for(j=0;j〈G.vexnum;j++)if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;};closedge[k].lowcost=0;count=l;cout〈〈"最小生成樹的各個邊信息如下："〈〈endl;while(count!二G.vexnum){min=1000;for(i=O;i〈G.vexnum;i++){if(closedge[i].lowcost==INFINITY||closedge[i].lowcost==0)continue;if(closedge[i].lowcost〈min){min=closedge[i].lowcost;k=i;}}cout〈〈closedge[k].adjvex〈〈"-"〈〈G.vexs[k]〈〈"："〈〈closedge[k].lowcost〈〈endl;closedge[k].lowcost二0; //第k頂點并入U集

count++;forcount++;for{(i=0;i〈G.vexnum;++i)if(closedge[i].lowcost==T){closedge[i].adjvex=G.vexs[k];closedge[i].lowcost二G.arcs[k][i].adj;continue;}if(closedge[i].lowcost==0)continue;if(G.arcs[k][i].adj==T)continue;if(G.arcs[k][i].adj<closedge[i].lowcost){closedge[i].adjvex=G.vexs[k];closedge[i].lowcost二G.arcs[k][i].adj;continue;}}}//***********************無向網鄰接表的創(chuàng)建**************************voidCreatALGUDN(ALGraph&G){inti,s,d,w;ArcNode*p,*q;cout〈〈〃輸入圖的頂點數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=l;i〈二G.vexnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃個頂點的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare二NULL;}for(i=1;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結點，尾結點和權值:〃；cin〉〉s〉〉d〉〉w;p=newArcNode;p->info=(InfoType*)malloc(sizeof(struetArcNode));p-〉adjvex=d;*(p—〉info)=w;p—>nextare二G.vertices[s].firstare;G.vertices[s].firstare=p;//將新建的以d為信息的表結點p插入s單鏈表的頭結點后q=newArcNode;q-〉info=(InfoType*)malloc(sizeof(struetArcNode));q-〉adjvex=s;*(q-〉info)=w;q—>nextare=G.vertices[d].firstare;}G.vertices[d].firstare=q;}//***********************無向網鄰接表的輸出**************************voidPrintALGUDN(ALGraphG){ArcNode*p;inti;for(i=l;i〈二G.vexnum;i++){p=G.vertices[i].firstare;cout〈〈G.vertices[i].data〈〈"--";while(p!=NULL){cout〈〈"〈"〈〈G.vertices[i].data〈〈"，"〈〈G.vertices[p->adjvex].data〈〈"〉"〈〈*(p-〉info)〈〈"--";p=p—〉nextare;}printf(〃\n〃)；}//************************有向圖的鄰接矩陣******************************voidCreatMDG(MGraph&G){inti,j,k;charch;VertexTypev1,v2;cout〈〈"輸入頂點數(shù)，弧數(shù)："〈〈endl;cin〉〉G.vexnum〉〉G.arcnum;cout〈〈"輸入頂點(字符型)："〈〈endl;for(i=0;i〈G.vexnum;i++){for(j=0;j〈G.vexnum;j++){G.arcs[i][j].adj=O;G.arcs[i][j].info二NULL;}}for(i=0;i〈G.vexnum;i++) //頂點信息{cout〈〈〃輸入第〃〈〈i+l〈〈〃個頂點：〃；cin〉〉ch;G.vexs[i]=ch;}for(k=0;k〈G.arcnum;k++){cout〈〈〃輸入第〃〈〈k+1〈〈〃條弧：〃〈〈endl;cin〉〉v1〉〉v2;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=1;//對弧寫入權值//G.arcs[j][i].adj=1;//對稱弧賦值}}}voidCreatALDG(ALGraph&G)inti,s,d;ArcNode*p;cout〈〈〃輸入圖的頂點數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=1;i〈二G.vexnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃個頂點的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare=NULL;}for(i=1;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結點和尾結點（整數(shù)）：〃;cin〉〉s〉〉d;

p=newArcNode;p-〉adjvex=d;p-〉nextare二G.vertices[s].firstare;G.vertices[s].firstare=p;//將新建的以d為信息的表結點p插入s單鏈表的頭結點后/*q=newArcNode;q-〉adjvex=s;q->nextare二G.vertices[d].firstare;G.vertices[d].firstare=q;*/}G.kind=UDG;}FindDegree(ALGraphG,intindegree]])//****************************^^向圖的拓扌卜排序******************************voidFindDegree(ALGraphG,intindegree]]){inti;ArcNode*p;for(i=l;i〈二G.vexnum;i++)indegree[i]=0;for(i=1;i〈二G.vexnum;i++){p=G.vertices[i].firstare;while(p){}int}int{TopologicalSort(ALGraphG)intcount,v,k;int*indegree=newint[G.vexnum];for(inti=1;i〈二G.vexnum;i++)indegree[i]=0;FindDegree(G,indegree);stack<int〉S;for(inti=1;i〈二G.vexnum;i++)if(indegree[i]==0)S.push(i);count=0;while(!S.empty()){v=S.top();S.pop();cout〈〈v〈〈"-"〈〈G.vertices[v].data〈〈"\n";++count;for(ArcNode*p=G.vertices[v].firstare;p;p=p-〉nextare){k=p-〉adjvex;if(!—indegree[k])S.push(k);}}if(count〈G.vexnum)return0;elsereturn1;}//****************************創(chuàng)建有向網的鄰接矩陣*1*intCreatMUDG(MGraph&G){inti,j,w;charch;VertexTypevl,v2;cout〈〈"輸入頂點數(shù)，弧數(shù)："〈〈endl;cin〉〉G.vexnum〉〉G.arcnum; //輸入當前頂點數(shù)弧數(shù)是否有弧信息cout〈〈"輸入頂點(字符型)："〈〈endl;for(i=0;i〈G.vexnum;i++) //初始化鄰接矩陣{for(j=0;j〈G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info二NULL;}}for(i=O;i〈G.vexnum;i++) //頂點信息{cout〈〈〃輸入第〃〈〈i+1〈〈〃個頂點：〃；cin>>ch;G.vexs[i]=ch;}for(intk=O;k〈G.arcnum;k++){cout〈〈"輸入第"〈〈k+l〈〈"條弧："〈〈endl;cin〉〉vl〉〉v2;cout〈〈"輸入弧的權值："〈〈endl;cin〉〉w;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj二w;//對弧寫入權值//G.arcs[j][i].adj二w;//對稱弧賦值}}return1;}voidCreatALGUN(ALGraph&G)inti,s,d,w;ArcNode*p;cout〈〈"輸入圖的頂點數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=1;i〈二G.vexnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃個頂點的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare二NULL;}for(i=1;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結點，尾結點和權值:〃；cin〉〉s〉〉d〉〉w;p=newArcNode;p-〉info=(InfoType*)malloc(sizeof(struetArcNode));p-〉adjvex=d;*(p-〉info)=w;p-〉nextare二G.vertices[s].firstare;G.vertices[s].firstare=p;//將新建的以d為信息的表結點p插入s單鏈表的頭結點后/*q=newArcNode;q-〉info=(InfoType*)malloc(sizeof(struetArcNode));q-〉adjvex=s;*(q-〉info)=w;q->nextare二G.vertices[d].firstare;G.vertices[d].firstare=q;*/}}voidShortestPath(MGraphg,intv0,intp[][MAX_VERTEX_NUM],intd[])intv;intw;intmin;inti,j;intfinal[MAX_VERTEX_NUM];for(v=O;v〈g.vexnum;++v){final[v]=FALSE;d[v]=g.arcs[vO][v].adjfor(w=O;w〈g.vexnum;++w){譏v][w]二FALSE;}if(d[v]〈INFINITY){譏v][vO]=TRUE;p[v][v]=TRUE;}}d[v0]=0;final[v0]=TRUE;for(i=l;i〈g.vexnum;++i){min=INFINITY;for(w=O;w〈g.vexnum;++w){if(!final[w]){if(d[w]〈min){v=w;min=d[w]}}}final[v]=TRUE;for(w=O;w〈g.vexnum;++w){if(!final[w]&&(min+g.arcs[v][w].adj〈d[w])){d[w]=min+g.arcs[v][w].adj;for(j=0;j〈g.vexnum;j++){p[w][j]=p[v][j];}p[w][w]=TRUE;}}}}voidprint(MGraphG){inti,j;int譏MAX_VERTEX_NUM][MAX_VERTEX_NUM];intd[MAX_VERTEX_NUM];intv0=0;ShortestPath(G,vO,p,d);for(i=0;i<G.vexnum;i++){printf("Path%cto%c:\n",G.vexs[vO],G.vexs[i]);if(p[i][v0]=TRUE)for(j=0;j<G.vexnum;j++)printf("%d",p[i][j]);printf("長度:％d\n",d[i]);printf(〃\n〃)；}}voidprintl(MGraphG)inti,j;int譏MAX_VERTEX_NUM][MAX_VERTEX_NUM];intd[MAX_VERTEX_NUM];intvO;for(v0=0;v0〈G.vexnum;v0++){ShortestPath(G,v0,p,d);for(i=0;i<G.vexnum;i++){printf("Path%cto%c:\n",G.vexs[v0],G.vexs[i]);if(p[i][v0]=TRUE)for(j=0;j<G.vexnum;j++)printf("%d",p[i][j]);printf("長度:％d\n",d[i]);printf(〃\n〃)；}}}// f~.T*Z?-l-r屮/乂// —1\-KH~^rH-t^yz|—i-*intCriticalPath(ALGraphG)//??????????????????????????無法顯示最后一個結點{//求//求ve int*indegree=newint[G.vexnum];for(inti=l;i〈二G.vexnum;++i)indegree[i]=0;//初始化FindDegree(G,indegree);//求各頂點入度stack<int〉S,T;for(inti=1;i〈二G.vexnum;++i)if(indegree[i]==O)S.push(i);//入度為進棧int*ve=newint[G.vexnum];for(inti=1;i〈二G.vexnum;++i)ve[i]=0;//初始化各頂點事件的最早發(fā)生時間while(!S.empty()){intv=S.top();S.pop();T.push(v);for(ArcNode*p=G.vertices[v].firstare;p!=NULL;p=p->nextare){if(--indegree[p-〉adjvex]==0)S.push(p-〉adjvex);//入度為進棧if(ve[v]+*(p-〉info)〉ve[p-〉adjvex])ve[p-〉adjvex]=ve[v]+*(p-〉info)// 求v[l] int*vl=newint[G.vexnum];for(inti=l;i〈二G.vexnum;++i){vl[i]=ve[G.vexnum];//初始化頂點事件的最遲發(fā)生時間}while(!T.empty())//按拓撲逆序求各定點的vl值{intv=T.top();T.pop();for(ArcNode*p=G.vertices[v].firstare;p!=NULL;p=p->nextare){if(vl[p-〉adjvex]-*(p-〉info)<vl[v])vl[v]=vl[p->adjvex]-*(p-〉info);}}// 判斷是否是關鍵活動 for(inti=1;i〈二G.vexnum;++i){for(ArcNode*p=G.vertices[i].firstarc;p;p=p-〉nextare){intk=p-〉adjvex;intdut二*(p-〉info);inte=ve[i];intl二vl[k]-dut;if(e==l)cout〈〈i〈〈"一"〈〈G.vertices[i].data〈〈"\n";}}return0;}voidShowMainMenu(){cout〈〈"\n";TOC\o"1-5"\h\zcout〈〈"*****************圖的基本操作及應用****************\n";cout〈〈"*1無向圖的基本操作及應用 *\n";cout〈〈"*2無向網的基本操作及應用 *\n";cout〈〈"*3有向圖的基本操作及應用 *\n";cout〈〈"*4有向網的基本操作及應用 *\n";cout〈〈"*5退出 *\n";X-V.r-?-4—// \*~\■ff1III\\ *T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?\II}voidUDG1(){MGraphMG;ALGraphALG;intn;do{cout<<"\n";cout<<"*1創(chuàng)建無向圖的鄰接矩陣*\n";cout<<"*2創(chuàng)建無向圖的鄰接表*\n";cout〈〈"*3無向圖的深度優(yōu)先遍歷*\n";cout〈〈"*4無向圖的廣度優(yōu)先遍歷*\n";cout〈〈"*5退出*\n";X-V.r-?-4—// \*~\■ff1III\\ *T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?*T?\IIcin〉〉n;switch(n){case1:CreatUDG(MG);ScanAll(MG);break;case2:CreatALGUDG(ALG);PrintALGUDG(ALG);break;case3:CreatALGUDG(ALG);PrintALGUDG(ALG);cout〈〈"深度優(yōu)先遍歷:"〈〈endl;DFSTraverse(ALG);break;case4:CreatALGUDG(ALG);PrintALGUDG(ALG);cout〈〈"廣度優(yōu)先優(yōu)先遍歷："〈〈endl;BFSTraverse(ALG);break;default:if(n!=5)cout<<"錯誤，重新輸入\n";}while(n!=5);}voidUDN1(){MGraphMN;ALGraphALN;intn;VertexTypeu;do{cout〈〈"\n";cout〈〈"***************無向網的基本操作及應用**************\n";cout〈〈"*1創(chuàng)建無向網的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建無向網的鄰接表*\n";cout〈〈"*3最小生成樹*\n";cout〈〈"*4退出*\n";X-V.r-?-4—// \■ff1III\\ \IIcin〉〉n;switch(n){case1:CreatMUDN(MN);ScanAll(MN);break;case2:CreatALGUDN(ALN);PrintALGUDN(ALN);break;case3:CreatMUDN(MN);ScanAll(MN);cin〉〉u;MiniSpanTree(MN,u);break;default:if(n!=4)cout〈〈"錯誤，重新輸入\n";}while(n!=4);}voidDG1(){MGraphMH;ALGraphALH;intn;do{cout〈〈"\n";cout〈〈"***************有向圖的基本操作及應用**************\n";cout〈〈"*1創(chuàng)建有向圖的鄰接表*\n";cout〈〈"*2創(chuàng)建有向圖的鄰接矩陣*\n";cout〈〈"*3拓撲排序*\n";cout〈〈"*4退出*\n";X-V.r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:CreatALDG(ALH);cout〈〈"鄰接表為"〈〈endl;PrintALGUDG(ALH);break;case2:CreatMDG(MH);ScanAll(MH);break;case3:CreatALDG(ALH);cout〈〈"鄰接表為"〈〈endl;PrintALGUDG(ALH);cout〈〈"拓撲排序："〈〈endl;TopologicalSort(ALH);break;default:if(n!=4)cout〈〈"錯誤，重新輸入\n";}}while(n!=4);}voidDN1(){MGraphMK;ALGraphALK;//int譏MAX_VERTEX_NUM][MAX_VERTEX_NUM];//intd[MAX_VERTEX_NUM];//intv0=0;intn;do{cout〈〈"\n";cout〈〈"*1創(chuàng)建有向網的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建有向網的鄰接表*\n";cout〈〈"*3關鍵路徑*\n";cout〈〈"*4單源最短路徑*\n";cout〈〈"*5每對頂點間的最短路徑*\n";cout〈〈"*6退出*\n";X-V.r-?-4—// \■ff1III\\ \IIcin〉〉n;switch(n){case1:CreatMUDG(MK);ScanAll(MK);break;case2:CreatALGUN(ALK);PrintALGUDN(ALK);break;case3:CreatALGUN(ALK);PrintALGUDN(ALK);cout〈〈"關鍵路徑為："〈〈endl;CriticalPath(ALK);break;case4:CreatMUDG(MK);ScanAll(MK);print(MK);break;case5:CreatMUDG(MK);ScanAll(MK);printl(MK);break;default:if(n!=6)cout＜〈"錯誤，重新輸入\n";}}while(n!=6);}voidmain(){intn;do{ShowMainMenu();cin〉〉n;switch(n){case1:UDG1();break;case2:UDN1();break;case3:DG1();break;case4:DN1();break;default:if(n!=5)cout〈〈"錯誤，重新輸入"；}}while(n!=5);}=回?￡S五、測試一無向圖的基本操作及應用d:疙序設計Qeb旳誼序設計.exe研用用用用豁應應應應<及及及及.'r-二4二」丿二P二-.1$杠基基二.B.B.B.B”圖網圖網X..問..問..問..問-3^5杠無無有零一二724S的陣歷歷圖矩表奪向養(yǎng)先先-一〕4?|:?I?—耳rr-l、l—□*的的度度??圖圖探廣“向向*桿無無圖圖枠建建向向岀杠罰無無退724S^***?*、無向圖鄰接矩陣的創(chuàng)建B060606BC0066囑點如下點（字符型）丄個頂點葉頂點才■?痂點1條?。狠斠翧B輸賀第童條弧BC輸矢第3條弧CD圖中頂點ABC?老陣：2、無向圖鄰接表的創(chuàng)建知入圖的頂點數(shù)和邊數(shù)詔3打入第1個頂點的信息皿冷入第2個頂點的信息：B打入第琦頂點的信息M打入第4個頂點的信息；D打入第1條邊的頭結點和尾結點（整數(shù)〉汽2打入第2條邊的頭結點和尾結點（整數(shù)〉汐3愉入第3條邊的頭結點和尾結點（整數(shù)〉澤4fi<A,B>B<B,CXB,A>C<C,DXC,B>[^<D,C>3、深度優(yōu)先遍歷蠱滅圖的頂點數(shù)和邊數(shù)活6頁入第1個頂點的信息油輸入第玄個頂點的信息=B輸入第了個頂點的信息乂頁入第4個頂點的信息:D卜第5個頂點的信息]輸入第石個頂點的信息=F輸入第丄條邊的頭結點和屋結點龍整數(shù)輸入第<條邊的去結點和屋結點龍整數(shù)山3彳入第=條邊的頭結點和尾結點龍整數(shù)〉汐4打入第4條邊的頭結點和尾結點￡整數(shù)〉汐5彳入第5條邊的頭結點和尾結點￡整數(shù)〉汚64、廣度條邊的頭結點和屋結點龍整數(shù)”4五A<A,CXA,B>B<B,EXB,DXB,A>C<C,A>D<D,FXD,B>fe<E,FXE,B>^<F,DXF,E>探度優(yōu)先遍歷：J^CBEFD

輸我圖的頂點數(shù)和邊數(shù)汰6輸以第1個頂點的信息:*輸以第盤個頂點的信息:B輸以第3個頂點的信息M輸入第4個頂點的信息:D諭以第召個頂點的信息:E輸入第氐個頂點的信息:F”第1條邊的頭結點和尾結點崖數(shù)心2”第瘵邊的頭結點和尾結點崖數(shù)心3眉A第3條邊的頭結點和尾結點崖數(shù)心4”第4條邊的頭結點和尾結點崖數(shù)心5”第呂條邊的頭結點和尾結點崖數(shù)小石輸人第石條邊的張結點和尾結點（整數(shù)〉詔6^<A,CXfi,B>二、無向網的<鎳本操d：l率序迓訪u/程■韋設計七疣障用用用用M應應應應U及及及及,￡□—匸廠匸匚一廠匸一??軟1-HI^工二障用用用用M應應應應U及及及及,￡□—匸廠匸匚一廠匸一??軟1-HI^工二.B.B.B.B=圖網圖網E..問..問..問..問-3^=無無有專I;45?****嚴_口1創(chuàng)建無回囤肉鄰搓筵2創(chuàng)建無向網的鄰按憲-小生成爲"XNXNXNXNXNXNKNK*4待頂頂頂弧丄/>1231待頂頂頂弧丄/>1231倔第魯?shù)?A'^^iAAAA礦■d刖比刖d刖d刖d刖d刖ABC俞入第2條弧:C俞入弧的權值匚4俞入第3條?。河酟弧的權值匚圖中頂點譽息如F：BC鄰按矩陣如下:TOC\o"1-5"\h\z陣： H 為A10000 3B 3 10000C 6 42、無向網鄰接表的創(chuàng)建俞入圖的頂點數(shù)和邊數(shù)汴3罰入第1個頂點的信息:A俞入第2個頂點的信息油；俞入第3個頂點的信息“前入第1條邊的頭結點'尾結點和權值注23兪入第2條邊的頭結點，尾結點和權值汐34；俞入第3條邊的頭結點，尾結點和權值注35I—<A,C>5—<A,B>3—J—<B,C>4—<B,A>3—；—<C,A>5—<C,B>4—2、最小生成樹

三、有向圖的基本操作及應用-Ji*的的的的圖網圖網..問..問..問..問無無有幕12345用用1 表丫加一**三、有向圖的基本操作及應用-Ji*的的的的圖網圖網..問..問..問..問無無有幕12345用用1 表丫加一****1、有向圖鄰接表的創(chuàng)建輸入圖的頂點數(shù)和邊數(shù)汴3￡［入第1個頂點的信息=?時入第2個頂點的信息=B■第3個頂點的信息述打入第1條邊的頭結點和尾結點（整數(shù)2百入第2條邊的頭結點和尾結點（整數(shù)3邊的頭結點和尾結點理數(shù)心3^<A.C><A.B>C2、有向圖鄰接矩陣的創(chuàng)建輸入頂點數(shù)，弧數(shù)；43點（字茜型）gAgi-■-頂點:a輸以黑沖噴電:B輸7頂點：DAB輸我第2條弧;BQ輸我第3條弧；CD圖中頂點信息如下:二ABCD嘟援矩庫如下;矩陣；ABA1BCD3、拓撲排序用用其r'四、I操M1H本平平不"M-'?M墓工.B.B.B.B??圖網圖網“..問..問.?m.?m-3^*無無有聶X12345X=#****..亠匚r7「：?r7「：?

有14114(徑路短最1石I.1一路間一一向向點」??有頂一一建建鍵源對岀一一天單黒X1、有向網鄰接矩陣的創(chuàng)建舫V頂點｛字符型）:HB輸入弧的權值：4輸入第?條弧：畝I弧的權值：爲入第琲?。籂戶藁〉臋嘀担籂懭氲?條?。篋A輸入弧的權值：8圖中頂點信息如下：flBCD鄰援疙庫如下:緬陣：ABA4BCDSC1迓觀觀時&1迓觀觀時2、有向網鄰接表的創(chuàng)建俞入圖的頂點數(shù)和邊數(shù)詢4俞入第1個頂點的信息:A俞入第3個頂點的信息:B新入第3個頂點的信息”爺k第4個頂點的信息:E新入第1條邊的冬結點「尾結點和權倚123新入第2條邊的冬結點「尾結點和權値汐34新入第3條邊的冬結點「尾結點和權倚345俞入第4條邊的頭結點「尾結點和權値：416I———*-<B,C>4——：—<C,E>5—1—<EfA>6——3、關鍵路徑4、單源最短路徑XU圖中頂點憎融陣如下,ABCD矩陣三AXU圖中頂點憎融陣如下,ABCD矩陣三ABCDEFA15^03315^033ltj1^0033fj趣B15^03315^03351^0031^0031^803C15^03315^0331^0395込1^0031^803D15^03315^0331^0391^0031^003ltjE1^0331^0331^039201^00360F1^0331^0331^0331^0031^0031^803PathAtoA:100000長度疤PathAtoB-100000長度匸迥?迥PathAtoC101000長度匸10PathAtoD;100110長度匸50PathAtoE:100010長度詣0PathAtoF:100111長度*05、每對頂點之間的最短路徑E長度;?長度；10000長度;10長度長度;30長度長度；10000長度;?長度；5長度；55toB：000toE：010toF：111toB：000PathB010athA100PathA101PathA100PathA100PathA100toC■000toA:000toC■000PathB10PathB11toD：110toD：100toA:000EFathA00PattiBtoE：011111長度：125PathB11F鄰接矩陣如下’A B1000010000101000030100100001000051000010