數(shù)據(jù)結(jié)構(gòu)第三次實(shí)驗(yàn)報(bào)告概論

實(shí)驗(yàn)報(bào)告課程名稱實(shí)驗(yàn)名稱數(shù)據(jù)結(jié)構(gòu)班級(jí)實(shí)驗(yàn)時(shí)間姓名實(shí)驗(yàn)環(huán)境C實(shí)驗(yàn)?zāi)康暮蛢?nèi)容要求圖的操作算法一、實(shí)驗(yàn)要求與內(nèi)容實(shí)現(xiàn)圖的常用操作算法：包括建立圖的存儲(chǔ)結(jié)構(gòu)、深度優(yōu)先搜索和廣度優(yōu)先搜索，求圖、實(shí)驗(yàn)?zāi)康?．掌握有關(guān)圖的操作算法并用高級(jí)語言實(shí)現(xiàn)。．熟練掌握?qǐng)D的兩種搜索路徑的遍歷方法。實(shí)驗(yàn)過程記錄#include<stdio.h>#include<stdlib.h>#include<iostream>#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineMAX1000usingnamespacestd;typedefstructArcell{doubleadj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//節(jié)點(diǎn)數(shù)組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前節(jié)點(diǎn)數(shù)和弧數(shù)MGraphtypedefstructPnode//用于普利姆算法{charadjvex;//節(jié)點(diǎn)doublelowcost;//權(quán)值UtypedefstructKnode其對(duì)應(yīng)的2個(gè)節(jié)點(diǎn){doublevalue;//權(quán)值}Knode,Dgevalue[MAX_VERTEX_NUM];//-----------------------------------------------------------------------------------intCreateUDG(MGraph&G,Dgevalue&dgevalue);intLocateVex(MGraphG,charch);intMinimum(MGraphG,Closedgeclosedge);voidMiniSpanTree_PRIM(MGraphG,charu);voidSortdge(Dgevalue&dgevalue,MGraphG);//-----------------------------------------------------------------------------------intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構(gòu)造無向加權(quán)圖的鄰接矩陣{intijkcin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)//初始化數(shù)組{for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=MAX;}}for(k=0;k<G.arcnum;++k){cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;i=LocateVex(G,dgevalue[k].ch1);j=LocateVex(G,dgevalue[k].ch2);G.arcs[i][j].adj=dgevalue[k].value;G.arcs[j][i].adj=G.arcs[i][j].adj;}returnOK;}{inta;for(inti=0;i<G.vexnum;i++){if(G.vexs[i]==ch)ai}returna;}//typedefstructPnode//用于普利姆算法{//charadjvex;//節(jié)點(diǎn)//doublelowcost;//權(quán)值voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成樹{intijkClosedgeclosedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;j++){ifjk){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}}closedge[k].lowcost=0;for(i=1;i<G.vexnum;i++){k=Minimum(G,closedge);cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j){if(G.arcs[k][j].adj<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}}{jdoublek=1000;for(i=0;i<G.vexnum;i++){if(closedge[i].lowcost!=0&&closedge[i].lowcost<k){k=closedge[i].lowcost;j=i;}}returnj;}voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克魯斯卡爾算法求最小生成樹{intp1,p2,i,j;intbj[MAX_VERTEX_NUM];//標(biāo)記數(shù)組for(i=0;i<G.vexnum;i++)//標(biāo)記數(shù)組初始化bj[i]=i;Sortdge(dgevalue,G);//將所有權(quán)值按從小到大排序for(i=0;i<G.arcnum;i++){p1=bj[LocateVex(G,dgevalue[i].ch1)];p2=bj[LocateVex(G,dgevalue[i].ch2)];ifp!=p2){cout<<"("<<dgevalue[i].ch1<<","<<dgevalue[i].ch2<<","<<dgevalue[i].value<<")"<<endl;for(j=0;j<G.vexnum;j++){if(bj[j]==p2)bj[j]=p1;}}}}voidSortdge(Dgevalue&dgevalue,MGraphG)//對(duì)dgevalue中各元素按權(quán)值按從小到大排序{jdoubletemp;charch1,ch2;for(i=0;i<G.arcnum;i++){for(j=i;j<G.arcnum;j++){if(dgevalue[i].value>dgevalue[j].value){temp=dgevalue[i].value;dgevalue[i].value=dgevalue[j].value;dgevalue[j].value=temp;ch1=dgevalue[i].ch1;dgevalue[i].ch1=dgevalue[j].ch1;dgevalue[j].ch1=ch1;ch2=dgevalue[i].ch2;dgevalue[i].ch2=dgevalue[j].ch2;dgevalue[j].ch2=ch2;}}}}voidmain(){jMGraphG;charu;Dgevaluedgevalue;CreateUDG(G,dgevalue);for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)cout<<G.arcs[i][j].adj<<"";cout<<endl;}cout<<"=============普利姆算法===============\n";cin>u;MiniSpanTree_PRIM(G,u);cout<<"============克魯斯科爾算法=============\n";MiniSpanTree_KRSL(G,dgevalue);}#include"stdio.h"#defineMAX_VERTEX_NUM20#include"conio.h"#include"stdlib.h"#defineSTACK_INIT_SIZE16#defineSTACKINCREMENT5typedefintSElemType;typedefcharVertexType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;//我們依然用鄰接表來作圖的存儲(chǔ)結(jié)構(gòu)typedefstructArcNode{tadjvexstructArcNode*nextarc;nfo}ArcNode;//表結(jié)點(diǎn)類型typedefstructVNode{VertexTypedata;untArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//頭結(jié)點(diǎn)typedefstruct{AdjListvertices;//鄰接表intvexnum,arcnum;}ALGraph;intInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(-1);S.stacksize=STACK_INIT_SIZE;return1;}//InitStackintPush(SqStack&S,SElemTypee){if((S.top-S.base)>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top)=e;S.top++;return1;shintPop(SqStack&S,SElemType&e){if(S.top==S.base)return0;return1;pintStackEmpty(SqStack&S){if(S.top==S.base)return1;elsereturn0;}//StackEmptyintLocateVex(ALGraphG,charu){tifor(i=0;i<G.vexnum;i++){if(u==G.vertices[i].data)returni;}if(i==G.vexnum){printf("Erroru!\n");exit(1);}return0;}voidCreateALGraph_adjlist(ALGraph&G){inti,j,k,w;charv1,v2,enter;ArcNode*p;printf("Inputvexnum&arcnum:\n");scanf("%d",&G.vexnum);scanf("%d",&G.arcnum);printf("InputVertices(以回車隔開各個(gè)數(shù)據(jù)):\n");for(i=0;i<G.vexnum;i++){scanf("%c%c",&enter,&G.vertices[i].data);//注意點(diǎn)，解說G.vertices[i].firstarc=NULL;printf("InputArcs(v1,v2,w)以回車分開各個(gè)數(shù)據(jù):\n");for(k=0;k<G.arcnum;k++){scanf("%c%c",&enter,&v1);scanf("%c%c",&enter,&v2);//scanf("%d",&w);i=LocateVex(G,v1);j=LocateVex(G,v2);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;//p->info=w;p->nextarc=G.vertices[i].firstarc;//前插法,即每次都插入到頭結(jié)點(diǎn)的后面G.vertices[i].firstarc=p;printf("Next\n");return;}//CreateALGraph_adjlistvoidFindInDegree(ALGraph&G){jfor(i=0;i<G.vexnum;i++){G.vertices[i].count=0;for(j=0;j<G.vexnum;j++){//G.vertices[i].count++;for(ArcNode*p=G.vertices[j].firstarc;p;p=p->nextarc)G.vertices[p->adjvex].count++;}//FindInDegreeintTopoSort(ALGraph&G){SqStackS;FindInDegree(G);InitStack(S);for(inti=0;i<G.vexnum;i++)if(G.vertices[i].count==0)Push(S,i);intcountt=0;while(!StackEmpty(S)){mm=Pop(S,i);printf("%c",G.vertices[i].data);++countt;for(ArcNode*p=G.vertices[i].firstarc;p;p=p->nextarc)k=p->adjvex;if(!(--G.vertices[k].count))Push(S,k);whileif(countt<G.vexnum)return0;elsereturn1;}//TopoSortmain{ALGraphG;CreateALGraph_adjlist(G);TopoSort(G);return1;}深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索：圖的深度優(yōu)先遍歷類似于樹的前序遍歷。采用的搜索方法的特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。這種搜索方法稱為深度優(yōu)先搜索廣度優(yōu)先搜索：圖的廣度優(yōu)先遍歷BFS算法是一個(gè)分層搜索的過程，和樹的層序遍歷算法類同，它也需要一個(gè)隊(duì)列以保持遍歷過的頂點(diǎn)順序，以便按出隊(duì)的順序再去訪問這些頂點(diǎn)的鄰接頂點(diǎn)。重復(fù)定義************************/destdiohdemallochdewindowsh#defineMAX_VERTEX_NUM20cNodecInfoType*info;*****************************創(chuàng)建?；蚴顷?duì)列***************************/inkNodeArcNode*parc;odeArcNode*firstarc;該點(diǎn)的邊AXVERTEXNUMtypedefstruct{AdjListvertices;*****************************認(rèn)正確性*******************/{ArcNode*p;printfnChecktheGraphn;printfNotdatatnexttnext\t.....\n");foriipagvexnumi+){printfdtct,i,pag->vertices[i].cData);ppagverticesifirstarc;whilep{printfdtpadjvex);nextarc}ntfn}return1;}**************************/intstartintend{ArcNodearcNodes=(ArcNode*)malloc(sizeof(ArcNode));ArcNodearcNodee=(ArcNode*)malloc(sizeof(ArcNode));ArcNode*p;eereturnarcNodesadjvexend結(jié)點(diǎn)的位置ppagverticesstartfirstarc;{NodesnextarcpagverticesstartfirstarcpagverticesstartfirstarcarcNodes;}extarcarcNodesextarcNULL}endstart的關(guān)系生成arcNodeeadjvexstart的位置ppagverticesendfirstarc;{NodeenextarcpagverticesendfirstarcpagverticesendfirstarcarcNodee;}extarcarcNodeeextarcNULL}return1;}****************************遞歸方式接采用了LinkNode構(gòu)成的鏈表，從而也可以完成棧的功能tacknextNULL**************************/idDFSTraverseALGraphagintstart{LinkNodeStackLinkNodemallocsizeofLinkNode));//鏈表頭結(jié)點(diǎn)，用做棧LinkNodepStackLinkNodemallocsizeofLinkNode));//對(duì)棧操作的指針LinkNode*temp;//臨時(shí)存儲(chǔ)ArcNode*p;NULLpagverticesstartfirstarcprintf("%c",ag.vertices[start].cData);//訪問第一個(gè)點(diǎn)while(1)//正常情況下執(zhí)行一次，為了打印孤立結(jié)點(diǎn){stackpStackparcp;tacknextStacknextxtpStackerwhile(p&&(Stack->next)){whilep{if(Visited[p->adjvex])p=p->nextarc;{Visitedpadjvex=1;printf("%c",ag.vertices[p->adjvex].cData);//VisitFunctionstackpStackLinkNodemallocsizeofLinkNode));if(!pStack)return;//結(jié)點(diǎn)建立不成功pStackparcp;pStacknextStack>next;pStackerpagverticespadjvex.firstarc;}}tackknexttempnextptempparcnextarcr}for(i=0;i<ag.vexnum;i++)//打印出孤立點(diǎn){printfcagverticesicDatapagverticesifirstarc}}ntfnn****************************遞歸方式直接采用了LinkNode構(gòu)成的鏈表前插法進(jìn)行刪除L**************************/idBFSTraverseALGraphagintstart{LinkNodepQueueLinkNodemallocsizeofLinkNode));//對(duì)隊(duì)列操作的指針LinkNodetemp臨時(shí)存儲(chǔ)LinkNodelast指向最后一個(gè)元素的指針ArcNode*p;printfcag.vertices[start].cData);pagverticesstartfirstarcVisited[start]=1;while)//正常情況下執(zhí)行一次循環(huán){pQueueparcp;enextpQueueuenextNULLeoverwhile(p&&Queue->next){whilep{{Visited[p->adjvex]=1;printf("%c",ag.vertices[p->adjvex].cData);//VisitFunctionpQueueLinkNodemallocsizeofLinkNode));if(!pQueue)return;ueparcpuenextNULLnextpQueuelastnextueueover}nextarc}pagverticestempparc>adjvex].firstarc;Queuenexttempnext;eover}for(i=0;i<ag.vexnum;i++)//打印出孤立點(diǎn){printfcagverticesicDatapagverticesifirstarc}}ntfnn}******************************作邊初始化*****************************/{ALGraphag;printf("說明:采用鄰接表的存儲(chǔ)結(jié)構(gòu)，生成無向圖\n\n\n");while(1)//結(jié)點(diǎn)個(gè)數(shù)有效性驗(yàn)證{printf(請(qǐng)"輸入圖的結(jié)點(diǎn)個(gè)數(shù),并回車:");scanf("%d",&n);輸入數(shù)據(jù)請(qǐng)回車確認(rèn)}numnfor(i=0;i<ag.vexnum;i++)//圖的結(jié)點(diǎn)數(shù)據(jù){printfNod=",i);sicDatacesifirstarcNULL}while(1)//邊的數(shù)量有效性驗(yàn)證{printf"請(qǐng)輸入邊的數(shù)量:");i}ag.arcnum=i;foriiagarcnumi+){while(1)//起點(diǎn)有效性驗(yàn)證{printf%d>條邊的起點(diǎn):",i);eprintf}while(1)//終點(diǎn)有效性驗(yàn)證{printf%d>條邊的終點(diǎn):",i);eprintf}ntfneGraphagstartend}PrintCheck(&ag);//打印出生成的圖while(1)//起始點(diǎn)有效性驗(yàn)證{printf遍歷的開始結(jié)點(diǎn):");seprintf}DFSTraverseagchoose//深度優(yōu)先遍歷whileVisitedi]!='\0'){Visited[i]=0;}while(1)//起始點(diǎn)有效性驗(yàn)證{printf遍歷的開始結(jié)點(diǎn):");seprintf}BFSTraverseagchoose//廣度優(yōu)先遍歷}streamhlloch#defineMAX100defineMAXINT1000fstructnode{{xnumi{xnumj{mgarcsi