基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)告

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

拓?fù)渑判蛴邢蚓W(wǎng)的基本操作及應(yīng)用創(chuàng)建有向網(wǎng)的鄰接矩陣創(chuàng)建有向網(wǎng)的鄰接表關(guān)鍵路徑單源最短路徑每對(duì)頂點(diǎn)之間的最短路徑三、設(shè)計(jì)方案DOS界面的主菜單d:字呈l=?5?i-\Debl;g\程序設(shè)計(jì)，亡灼--.一(圖網(wǎng)圖網(wǎng)--.一(圖網(wǎng)圖網(wǎng)X..冋..冋..冋..冋"33一無無i'Qi'二12345二}it帝帝帝帝一弔用用用一應(yīng)應(yīng)應(yīng)應(yīng)一及及及及^￡￡￡FvoidShowMainMenu(){cout〈〈"\n";cout〈〈"*****************圖的基本操作及應(yīng)用****************\n";cout〈〈"*1無向圖的基本操作及應(yīng)用*\n";cout〈〈"*2無向網(wǎng)的基本操作及應(yīng)用*\n";cout〈〈"*3有向圖的基本操作及應(yīng)用*\n";cout〈〈"*4有向網(wǎng)的基本操作及應(yīng)用*\n";cout〈〈"*5退出*\n";pp-i—// \-iz-> ■|()|||\\ #r?#r?#r?#r? \II}voidUDG1(){do{cout〈〈"\n";cout〈〈"****************無向圖的基本操作及應(yīng)用*************\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<<"錯(cuò)誤，重新輸入\n";}}while(n!=5);}voidUDN1(){do{cout〈〈"\n";cout〈〈"***************無向網(wǎng)的基本操作及應(yīng)用**************\n";cout〈〈"*1創(chuàng)建無向網(wǎng)的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建無向網(wǎng)的鄰接表*\n";cout〈〈"*3最小生成樹*\n";cout〈〈"*4退出*\n";X-V .r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:創(chuàng)建無向網(wǎng)的鄰接矩陣break;case2:創(chuàng)建無向網(wǎng)的鄰接表break;case3:最小生成樹break;default:if(n!=4)cout〈〈"錯(cuò)誤，重新輸入\n";}}while(n!=4);}voidDG1(){do{cout〈〈"\n";cout〈〈"***************有向圖的基本操作及應(yīng)用**************\n";cout〈〈"*1創(chuàng)建有向圖的鄰接表*\n";cout〈〈"*2創(chuàng)建有向圖的鄰接矩陣*\n";cout〈〈"*3拓?fù)渑判?\n";cout〈〈"*4退出*\n";X-V.r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:創(chuàng)建有向圖的鄰接表break;case2:創(chuàng)建有向圖的鄰接矩陣break;case3:拓?fù)渑判騜reak;default:if(n!=4)cout〈〈"錯(cuò)誤，重新輸入\n";}}while(n!=4);}voidDN1(){do{cout〈〈"\n";cout〈〈"***************有向網(wǎng)的基本操作及應(yīng)用**************\n";cout〈〈"*1創(chuàng)建有向網(wǎng)的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建有向網(wǎng)的鄰接表*\n";cout〈〈"*3關(guān)鍵路徑*\n";cout〈〈"*4單源最短路徑*\n";cout〈〈"*5每對(duì)頂點(diǎn)間的最短路徑*\n";cout〈〈"*6退出*\n";X-V.r-?-4—// \ ■ff1III\\ \IIcin〉〉n;switch(n){case1:創(chuàng)建有向網(wǎng)的鄰接矩陣break;case2:創(chuàng)建有向網(wǎng)的鄰接表break;case3:關(guān)鍵路徑break;case4:單源最短路徑break;case5:每對(duì)頂點(diǎn)間的最短路徑print1(MK);break;default:if(n!=6)cout〈〈"錯(cuò)誤，重新輸入\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<<"錯(cuò)誤，重新輸入"；}}while(n!=5);}四、實(shí)現(xiàn)代碼：#include〈iostream〉#include〈stdlib.h〉#include〈iomanip〉#include〈stdio.h〉#include〈stack〉usingnamespacestd;#defineMAX_VERTEX_NUM100//最大頂點(diǎn)個(gè)數(shù)#defineINFINITY10000//最大值#defineFALSE0#defineTRUE1typedefintVRType; //頂點(diǎn)關(guān)系(表示是否相鄰)typedefcharVertexType;typedefintInfoType;//弧相關(guān)信息typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向圖，有向網(wǎng)，無向圖，無向網(wǎng)}typedefstructArcCellVRTypeadj;//權(quán)值InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量AdjMartixarcs; //鄰接矩陣intvexnum,arcnum; //圖當(dāng)前頂點(diǎn)數(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){//構(gòu)造無向網(wǎng)inti,j,w;charch;VertexTypev1,v2;cout〈〈"輸入頂點(diǎn)數(shù)，弧數(shù)："〈〈endl;cin〉〉G.vexnum〉〉G.arcnum; //輸入當(dāng)前頂點(diǎn)數(shù)弧數(shù)是否有弧信息cout〈〈"輸入頂點(diǎn)（字符型）："〈〈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〈〈〃個(gè)頂點(diǎn)：〃；cin〉〉ch;G.vexs[i]二ch;}for(intk=O;k〈G.arcnum;k++){cout〈〈〃輸入第〃〈〈k+1〈〈〃條?。骸ā础磂ndl;cin〉〉v1〉〉v2;cout〈〈〃輸入弧的權(quán)值：〃〈〈endl;cin〉〉w;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj二w;//對(duì)弧寫入權(quán)值G.arcs[j][i].adj二w;//對(duì)稱弧賦值}}return1;}voidCreatUDG(MGraph&G)inti,j,k;charch;VertexTypev1,v2;cout〈〈〃輸入頂點(diǎn)數(shù)，弧數(shù)：〃〈〈endl;cin〉〉G.vexnum〉〉G.arcnum;cout〈〈〃輸入頂點(diǎn)(字符型)：〃〈〈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++) //頂點(diǎn)信息cout〈〈〃輸入第〃〈〈i+1〈〈〃個(gè)頂點(diǎn)：〃；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;//對(duì)弧寫入權(quán)值G.arcs[j][i].adj=1;//對(duì)稱弧賦值}}}voidScanAll(MGraphG)inti;cout〈〈"圖中頂點(diǎn)信息如下："〈〈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;//該弧指向頂點(diǎn)的位置structArcNode*nextare;//指向下一條弧的指針I(yè)nfoType*info;//該弧相關(guān)信息的指針}ArcNode;typedefstructVNodeVertexTypedata;//頂點(diǎn)信息ArcNode*firstare;//指向第一條依附該頂點(diǎn)弧的指針}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;//************************創(chuàng)建無向圖的鄰接表**************************voidCreatALGUDG(ALGraph&G){inti,s,d;ArcNode*p,*q;cout〈〈"輸入圖的頂點(diǎn)數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=1;i〈二G.vexnum;i++){cout〈〈"\n輸入第"〈〈i〈〈"個(gè)頂點(diǎn)的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare二NULL;}for(i=l;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)(整數(shù))：〃；cin〉〉s〉〉d;p=newArcNode;p-〉adjvex=d;p-〉nextare二G.vertices[s].firstare;G.vertices[s].firstare=p;//將新建的以d為信息的表結(jié)點(diǎn)p插入s單鏈表的頭結(jié)點(diǎn)后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〈〈"最小生成樹的各個(gè)邊信息如下："〈〈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頂點(diǎn)并入U(xiǎn)集

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;}}}//***********************無向網(wǎng)鄰接表的創(chuàng)建**************************voidCreatALGUDN(ALGraph&G){inti,s,d,w;ArcNode*p,*q;cout〈〈〃輸入圖的頂點(diǎn)數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=l;i〈二G.vexnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃個(gè)頂點(diǎn)的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare二NULL;}for(i=1;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結(jié)點(diǎn)，尾結(jié)點(diǎn)和權(quán)值:〃；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為信息的表結(jié)點(diǎn)p插入s單鏈表的頭結(jié)點(diǎn)后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;}//***********************無向網(wǎng)鄰接表的輸出**************************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〈〈"輸入頂點(diǎn)數(shù)，弧數(shù)："〈〈endl;cin〉〉G.vexnum〉〉G.arcnum;cout〈〈"輸入頂點(diǎn)(字符型)："〈〈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++) //頂點(diǎn)信息{cout〈〈〃輸入第〃〈〈i+l〈〈〃個(gè)頂點(diǎn)：〃；cin〉〉ch;G.vexs[i]=ch;}for(k=0;k〈G.arcnum;k++){cout〈〈〃輸入第〃〈〈k+1〈〈〃條?。骸ā础磂ndl;cin〉〉v1〉〉v2;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=1;//對(duì)弧寫入權(quán)值//G.arcs[j][i].adj=1;//對(duì)稱弧賦值}}}voidCreatALDG(ALGraph&G)inti,s,d;ArcNode*p;cout〈〈〃輸入圖的頂點(diǎn)數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=1;i〈二G.vexnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃個(gè)頂點(diǎn)的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare=NULL;}for(i=1;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)（整數(shù)）：〃;cin〉〉s〉〉d;

p=newArcNode;p-〉adjvex=d;p-〉nextare二G.vertices[s].firstare;G.vertices[s].firstare=p;//將新建的以d為信息的表結(jié)點(diǎn)p插入s單鏈表的頭結(jié)點(diǎn)后/*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)建有向網(wǎng)的鄰接矩陣*1*intCreatMUDG(MGraph&G){inti,j,w;charch;VertexTypevl,v2;cout〈〈"輸入頂點(diǎn)數(shù)，弧數(shù)："〈〈endl;cin〉〉G.vexnum〉〉G.arcnum; //輸入當(dāng)前頂點(diǎn)數(shù)弧數(shù)是否有弧信息cout〈〈"輸入頂點(diǎn)(字符型)："〈〈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++) //頂點(diǎn)信息{cout〈〈〃輸入第〃〈〈i+1〈〈〃個(gè)頂點(diǎn)：〃；cin>>ch;G.vexs[i]=ch;}for(intk=O;k〈G.arcnum;k++){cout〈〈"輸入第"〈〈k+l〈〈"條?。?〈〈endl;cin〉〉vl〉〉v2;cout〈〈"輸入弧的權(quán)值："〈〈endl;cin〉〉w;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj二w;//對(duì)弧寫入權(quán)值//G.arcs[j][i].adj二w;//對(duì)稱弧賦值}}return1;}voidCreatALGUN(ALGraph&G)inti,s,d,w;ArcNode*p;cout〈〈"輸入圖的頂點(diǎn)數(shù)和邊數(shù):〃;cin〉〉G.vexnum〉〉G.arcnum;for(i=1;i〈二G.vexnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃個(gè)頂點(diǎn)的信息:";cin〉〉G.vertices[i].data;G.vertices[i].firstare二NULL;}for(i=1;i〈二G.arcnum;i++){cout〈〈〃\n輸入第〃〈〈i〈〈〃條邊的頭結(jié)點(diǎn)，尾結(jié)點(diǎn)和權(quán)值:〃；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為信息的表結(jié)點(diǎn)p插入s單鏈表的頭結(jié)點(diǎn)后/*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("長(zhǎng)度:％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("長(zhǎng)度:％d\n",d[i]);printf(〃\n〃)；}}}// f~.T*Z?-l-r屮/乂// —1\-KH~^rH-t^yz|—i-*intCriticalPath(ALGraphG)//??????????????????????????無法顯示最后一個(gè)結(jié)點(diǎn){//求//求ve int*indegree=newint[G.vexnum];for(inti=l;i〈二G.vexnum;++i)indegree[i]=0;//初始化FindDegree(G,indegree);//求各頂點(diǎn)入度stack<int〉S,T;for(inti=1;i〈二G.vexnum;++i)if(indegree[i]==O)S.push(i);//入度為進(jìn)棧int*ve=newint[G.vexnum];for(inti=1;i〈二G.vexnum;++i)ve[i]=0;//初始化各頂點(diǎn)事件的最早發(fā)生時(shí)間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);//入度為進(jìn)棧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];//初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間}while(!T.empty())//按拓?fù)淠嫘蚯蟾鞫c(diǎn)的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);}}// 判斷是否是關(guān)鍵活動(dòng) 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〈〈"*****************圖的基本操作及應(yīng)用****************\n";cout〈〈"*1無向圖的基本操作及應(yīng)用 *\n";cout〈〈"*2無向網(wǎng)的基本操作及應(yīng)用 *\n";cout〈〈"*3有向圖的基本操作及應(yīng)用 *\n";cout〈〈"*4有向網(wǎng)的基本操作及應(yīng)用 *\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<<"錯(cuò)誤，重新輸入\n";}while(n!=5);}voidUDN1(){MGraphMN;ALGraphALN;intn;VertexTypeu;do{cout〈〈"\n";cout〈〈"***************無向網(wǎng)的基本操作及應(yīng)用**************\n";cout〈〈"*1創(chuàng)建無向網(wǎng)的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建無向網(wǎ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〈〈"錯(cuò)誤，重新輸入\n";}while(n!=4);}voidDG1(){MGraphMH;ALGraphALH;intn;do{cout〈〈"\n";cout〈〈"***************有向圖的基本操作及應(yīng)用**************\n";cout〈〈"*1創(chuàng)建有向圖的鄰接表*\n";cout〈〈"*2創(chuàng)建有向圖的鄰接矩陣*\n";cout〈〈"*3拓?fù)渑判?\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〈〈"拓?fù)渑判颍?〈〈endl;TopologicalSort(ALH);break;default:if(n!=4)cout〈〈"錯(cuò)誤，重新輸入\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)建有向網(wǎng)的鄰接矩陣*\n";cout〈〈"*2創(chuàng)建有向網(wǎng)的鄰接表*\n";cout〈〈"*3關(guān)鍵路徑*\n";cout〈〈"*4單源最短路徑*\n";cout〈〈"*5每對(duì)頂點(diǎn)間的最短路徑*\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〈〈"關(guān)鍵路徑為："〈〈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＜〈"錯(cuò)誤，重新輸入\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〈〈"錯(cuò)誤，重新輸入"；}}while(n!=5);}=回?￡S五、測(cè)試一無向圖的基本操作及應(yīng)用d:疙序設(shè)計(jì)Qeb旳誼序設(shè)計(jì).exe研用用用用豁應(yīng)應(yīng)應(yīng)應(yīng)<及及及及.'r-二4二」丿二P二-.1$杠基基二.B.B.B.B”圖網(wǎng)圖網(wǎng)X..問..問..問..問-3^5杠無無有零一二724S的陣歷歷圖矩表奪向養(yǎng)先先-一〕4?|:?I?—耳rr-l、l—□*的的度度??圖圖探廣“向向*桿無無圖圖枠建建向向?qū)绺芰P無無退724S^***?*、無向圖鄰接矩陣的創(chuàng)建B060606BC0066囑點(diǎn)如下點(diǎn)（字符型）丄個(gè)頂點(diǎn)葉頂點(diǎn)才■?痂點(diǎn)1條?。狠斠翧B輸賀第童條弧BC輸矢第3條弧CD圖中頂點(diǎn)ABC?老陣：2、無向圖鄰接表的創(chuàng)建知入圖的頂點(diǎn)數(shù)和邊數(shù)詔3打入第1個(gè)頂點(diǎn)的信息皿冷入第2個(gè)頂點(diǎn)的信息：B打入第琦頂點(diǎn)的信息M打入第4個(gè)頂點(diǎn)的信息；D打入第1條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)（整數(shù)〉汽2打入第2條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)（整數(shù)〉汐3愉入第3條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)（整數(shù)〉澤4fi<A,B>B<B,CXB,A>C<C,DXC,B>[^<D,C>3、深度優(yōu)先遍歷蠱滅圖的頂點(diǎn)數(shù)和邊數(shù)活6頁入第1個(gè)頂點(diǎn)的信息油輸入第玄個(gè)頂點(diǎn)的信息=B輸入第了個(gè)頂點(diǎn)的信息乂頁入第4個(gè)頂點(diǎn)的信息:D卜第5個(gè)頂點(diǎn)的信息]輸入第石個(gè)頂點(diǎn)的信息=F輸入第丄條邊的頭結(jié)點(diǎn)和屋結(jié)點(diǎn)龍整數(shù)輸入第<條邊的去結(jié)點(diǎn)和屋結(jié)點(diǎn)龍整數(shù)山3彳入第=條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)龍整數(shù)〉汐4打入第4條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)￡整數(shù)〉汐5彳入第5條邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)￡整數(shù)〉汚64、廣度條邊的頭結(jié)點(diǎn)和屋結(jié)點(diǎn)龍整數(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

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

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

有14114(徑路短最1石I.1一路間一一向向點(diǎn)」??有頂一一建建鍵源對(duì)岀一一天單黒X1、有向網(wǎng)鄰接矩陣的創(chuàng)建舫V頂點(diǎn)｛字符型）:HB輸入弧的權(quán)值：4輸入第?條弧：畝I弧的權(quán)值：爲(wèi)入第琲?。籂?wèi)艮弧的權(quán)值：爲(wèi)入第4條?。篋A輸入弧的權(quán)值：8圖中頂點(diǎn)信息如下：flBCD鄰援疙庫如下:緬陣：ABA4BCDSC1迓觀觀時(shí)&1迓觀觀時(shí)2、有向網(wǎng)鄰接表的創(chuàng)建俞入圖的頂點(diǎn)數(shù)和邊數(shù)詢4俞入第1個(gè)頂點(diǎn)的信息:A俞入第3個(gè)頂點(diǎn)的信息:B新入第3個(gè)頂點(diǎn)的信息”爺k第4個(gè)頂點(diǎn)的信息:E新入第1條邊的冬結(jié)點(diǎn)「尾結(jié)點(diǎn)和權(quán)倚123新入第2條邊的冬結(jié)點(diǎn)「尾結(jié)點(diǎn)和權(quán)値汐34新入第3條邊的冬結(jié)點(diǎn)「尾結(jié)點(diǎn)和權(quán)倚345俞入第4條邊的頭結(jié)點(diǎn)「尾結(jié)點(diǎn)和權(quán)値：416I———*-<B,C>4——：—<C,E>5—1—<EfA>6——3、關(guān)鍵路徑4、單源最短路徑XU圖中頂點(diǎn)憎融陣如下,ABCD矩陣三AXU圖中頂點(diǎn)憎融陣如下,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長(zhǎng)度疤PathAtoB-100000長(zhǎng)度匸迥?迥PathAtoC101000長(zhǎng)度匸10PathAtoD;100110長(zhǎng)度匸50PathAtoE:100010長(zhǎng)度詣0PathAtoF:100111長(zhǎng)度*05、每對(duì)頂點(diǎn)之間的最短路徑E長(zhǎng)度;?長(zhǎng)度；10000長(zhǎng)度;10長(zhǎng)度長(zhǎng)度;30長(zhǎng)度長(zhǎng)度；10000長(zhǎng)度;?長(zhǎng)度；5長(zhǎng)度；55toB：000toE：010toF：111toB：000PathB010athA100PathA101PathA100PathA100PathA100toC■000toA:000toC■000PathB10PathB11toD：110toD：100toA:000EFathA00PattiBtoE：011111長(zhǎng)度：125PathB11F鄰接矩陣如下’A B1000010000101000030100100001000051000010