数据结构第三次实验报告概论

实验报告课程名称实验名称数据结构班级实验时间姓名实验环境C实验目的和内容要求图的操作算法一、实验要求与内容实现图的常用操作算法：包括建立图的存储结构、深度优先搜索和广度优先搜索，求图、实验目的2．掌握有关图的操作算法并用高级语言实现。．熟练掌握图的两种搜索路径的遍历方法。实验过程记录#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];//节点数组AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前节点数和弧数MGraphtypedefstructPnode//用于普利姆算法{charadjvex;//节点doublelowcost;//权值UtypedefstructKnode其对应的2个节点{doublevalue;//权值}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)//构造无向加权图的邻接矩阵{intijkcin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)//初始化数组{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;//节点//doublelowcost;//权值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];//标记数组for(i=0;i<G.vexnum;i++)//标记数组初始化bj[i]=i;Sortdge(dgevalue,G);//将所有权值按从小到大排序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)//对dgevalue中各元素按权值按从小到大排序{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;//我们依然用邻接表来作图的存储结构typedefstructArcNode{tadjvexstructArcNode*nextarc;nfo}ArcNode;//表结点类型typedefstructVNode{VertexTypedata;untArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];//头结点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(以回车隔开各个数据):\n");for(i=0;i<G.vexnum;i++){scanf("%c%c",&enter,&G.vertices[i].data);//注意点，解说G.vertices[i].firstarc=NULL;printf("InputArcs(v1,v2,w)以回车分开各个数据:\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;//前插法,即每次都插入到头结点的后面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;}深度优先搜索和广度优先搜索深度优先搜索：图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索广度优先搜索：图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。重复定义************************/destdiohdemallochdewindowsh#defineMAX_VERTEX_NUM20cNodecInfoType*info;*****************************创建栈或是队列***************************/inkNodeArcNode*parc;odeArcNode*firstarc;该点的边AXVERTEXNUMtypedefstruct{AdjListvertices;*****************************认正确性*******************/{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结点的位置ppagverticesstartfirstarc;{NodesnextarcpagverticesstartfirstarcpagverticesstartfirstarcarcNodes;}extarcarcNodesextarcNULL}endstart的关系生成arcNodeeadjvexstart的位置ppagverticesendfirstarc;{NodeenextarcpagverticesendfirstarcpagverticesendfirstarcarcNodee;}extarcarcNodeeextarcNULL}return1;}****************************递归方式接采用了LinkNode构成的链表，从而也可以完成栈的功能tacknextNULL**************************/idDFSTraverseALGraphagintstart{LinkNodeStackLinkNodemallocsizeofLinkNode));//链表头结点，用做栈LinkNodepStackLinkNodemallocsizeofLinkNode));//对栈操作的指针LinkNode*temp;//临时存储ArcNode*p;NULLpagverticesstartfirstarcprintf("%c",ag.vertices[start].cData);//访问第一个点while(1)//正常情况下执行一次，为了打印孤立结点{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;//结点建立不成功pStackparcp;pStacknextStack>next;pStackerpagverticespadjvex.firstarc;}}tackknexttempnextptempparcnextarcr}for(i=0;i<ag.vexnum;i++)//打印出孤立点{printfcagverticesicDatapagverticesifirstarc}}ntfnn****************************递归方式直接采用了LinkNode构成的链表前插法进行删除L**************************/idBFSTraverseALGraphagintstart{LinkNodepQueueLinkNodemallocsizeofLinkNode));//对队列操作的指针LinkNodetemp临时存储LinkNodelast指向最后一个元素的指针ArcNode*p;printfcag.vertices[start].cData);pagverticesstartfirstarcVisited[start]=1;while)//正常情况下执行一次循环{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++)//打印出孤立点{printfcagverticesicDatapagverticesifirstarc}}ntfnn}******************************作边初始化*****************************/{ALGraphag;printf("说明:采用邻接表的存储结构，生成无向图\n\n\n");while(1)//结点个数有效性验证{printf(请"输入图的结点个数,并回车:");scanf("%d",&n);输入数据请回车确认}numnfor(i=0;i<ag.vexnum;i++)//图的结点数据{printfNod=",i);sicDatacesifirstarcNULL}while(1)//边的数量有效性验证{printf"请输入边的数量:");i}ag.arcnum=i;foriiagarcnumi+){while(1)//起点有效性验证{printf%d>条边的起点:",i);eprintf}while(1)//终点有效性验证{printf%d>条边的终点:",i);eprintf}ntfneGraphagstartend}PrintCheck(&ag);//打印出生成的图while(1)//起始点有效性验证{printf遍历的开始结点:");seprintf}DFSTraverseagchoose//深度优先遍历whileVisitedi]!='\0'){Visited[i]=0;}while(1)//起始点有效性验证{printf遍历的开始结点:");seprintf}BFSTraverseagchoose//广度优先遍历}streamhlloch#defineMAX100defineMAXINT1000fstructnode{{xnumi{xnumj{mgarcsi