大数据结构-实验六-报告材料

实用文案实用文案标准文档标准文档实验报告实验六 图的应用及其实现一、实验目的进一步功固图常用的存储结构。熟练掌握在图的邻接表实现图的基本操作。AOVAOE二、实验内容一>.基础题目：(本类题目属于验证性的，要求学生独立完成)AOV然后对该图拓扑排序,并输出拓扑序列.试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。[题目二]：从键盘上输入AOEAOE操作,完成上述功能。测试数据：教材图7.29【题目五】连通OR不连通描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作：Dxy从原图中删除连接x，y节点的边。Qxy询问x，y节点是否连通输入第一行两个数n,m（5<=n<=40000,1<=m<=100000）m行，每行一对整数xy（x,y<=n）x,y接下来一行一个整数q（q<=100000）以下q行每行一种操作，保证不会有非法删除。输出按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D样例输入331213235Q12D12Q12D32Q12样例输出CCD【题目六】 SortProblemAnascendingsortedsequenceofdistinctvaluesisoneinwhichsomeformofaless-thanoperatorisusedtoordertheelementsfromsmallesttolargest.Forexample,thesortedsequenceA,B,C,DimpliesthatA<B,B<CandC<D.inthisproblem,wewillgiveyouasetofrelationsoftheformA<Bandaskyoutodeterminewhetherasortedorderhasbeenspecifiedornot.【Input】Input consistsofmultipleprobleminstances. Each instancestartswith aline containing twopositiveintegersnandm. thefirstvalueindicatedthenumberof objectstosort, where2<=n<=26.Theobjectstobesortedwillbethefirstncharactersoftheuppercasealphabet.ThesecondvaluemindicatesthenumberofrelationsoftheformA<Bwhichwillbegiveninthisprobleminstance.1<=m<=100.Nextwillbemlines, eachcontainingonesuch relationconsistingofthree characters:anuppercaseletter,thecharacter"<"anda seconduppercaseletter.Noletterwillbeoutsidetherangeofthefirstnlettersofthealphabet.Valuesofn=m=0indicateendofinput.【Output】Foreachprobleminstance,outputconsistsofoneline.Thislineshouldbeoneofthefollowingthree:Sortedsequencedetermined:yyy…y.Sortedsequencecannotbedetermined.Inconsistencyfound.yyy…y isthesorted,ascendingsequence.SampleInput Sample Output46 Sortedsequencedetermined:ABCD.A<B Inconsistencyfound.A<C Sortedsequencecannotbedetermined.B<CC<DB<DA<B32A<BB<A262A<ZD<S00设计要求 ：1、上机前，认真学习教材，熟练掌握AOV网、AOE网的构造和拓扑排序算法。2、上机前，认真独立地写出本次程序清单，流程图，该程序包括图类型以及每一种操作的具体的函数定义和主函数。有关算法分别参阅讲义和参考教材事例三、实验步骤㈠、数据结构与核心算法的设计描述#defineMAX_VERTEX_NUM20//变量声明typedefstructArcNode//弧结点定义{intadjvex; //该弧所指向的顶点的位置structArcNode指向下一条弧的指针//InfoType*info;}ArcNode;typedefstructVNode//顶点结点定义{chardata; //顶点信息ArcNode*firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//图的定义{AdjListvertices;intvexnum,arcnum; //图的当前顶点数和弧intkind; //图的种类标志}ALGraph;ALGraphG; //定义图变量boolvisited[MAX_VERTEX_NUM]; //访问标志数intindegree[MAX_VERTEX_NUM]； 入度数组structStack栈类型定义{ints[21];inttop;};Stackstack;定义一个栈实用文案实用文案相关函数声明：void CreateGraph(MGraph&G)//v)//深度优先搜索遍历图voidBFSTraverse(GraphG,intv)//广度优先搜索遍历图intLocateVertices(ALGraphG,chara)//查找字符a在图中的位置intFirstAdjVex(ALGraphG,intv)//查找图中位置v的第一个邻接点在图中所在的位置intNextAdjVex(ALGraphG,intv,intw)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置voidDestroyGraph(ALGraph&G)//销毁图voidInitStack(Stack&stack)//初始化栈voidPushStack(Stack&stack,inti)//元素i入栈voidPopStack(Stack&stack,int&i)//栈顶元素出栈intStackEmpty(Stackstack)//判断栈是否为空，若为空则返回1，否则返回0voidFindInDegree(ALGraphG,int*indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[]intTopologicalSort(ALGraphG)//对图进行拓扑排序，并输出相应的拓扑序列㈡、函数调用及主函数设计调用CreateGraph(G);主函数调用TopologicalSort(G)标准文档

调用DestroyGraph(G)实用文案实用文案㈢程序调试及运行结果分析由于以前已经做过了关于图的一些算法设计，例如：图的深度优先遍历，广度优先遍历等，因此，这次试验基本没有什么错误。㈣实验总结这次的实验使得我对图的定义及其更多的操作有了更深入的了数据结构及算法实现，图的存储结构。这是我收获最大的地方。四、主要算法流程图及程序清单1、主要算法流程图：查找相对于图中位置v的邻接点w的下一邻接点在图中的位置intNextAdjVex(ALGraphG,intv,intw)开始p=G.vertices[v].firstarc;开始p=G.vertices[v].firstarc;否实用文案实用文案否是是否开始利 用 邻 接 表 存 储 结 构 构 造 有 向 CreateGraph(ALGraph&G)开始

void输入图的顶点和弧的个数cin>>G.vexnum>>G.arcnum;输入顶点值存入图中i=1否结束标准文档cin>>s; 实用文案实用文案开始开始求各定点入度FindInDegree(G,indegree);是查找图中位置v的第一个邻接点在图中所在的位置intFirstAdjVex(ALGraphG,intv)开始开始G.vertices[v].firstarc=NULL是return-1;否returnG.vertices[v].firstarc->adjvex;对图进行拓扑排序，并输出相应的拓扑序列intTopologicalSort(ALGraphG)标准文档实用文案实用文案标准文档标准文档是否否是2、程序清单题目一：#include<iostream.h>#include<stdlib.h>#defineMAX_VERTEX_NUM20typedefstructArcNode//弧结点定义{intadjvex; //该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针//InfoType*info;}ArcNode;typedefstructVNode//顶点结点定义{chardata; //顶点信息ArcNode*firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//图的定义{AdjListvertices;intvexnum,arcnum; //图的当前顶点数和弧intkind; //图的种类标志}ALGraph;ALGraphG; //定义图变量boolvisited[MAX_VERTEX_NUM]; //访问标志数intindegree[20]; //各结点入度数组structStack栈类型定义{ints[21];inttop;};Stackstack; //定义一个栈intLocateVertices(ALGraphG,chara)//查找字符a在图中的位置{for(inti=0;i<G.vexnum;i++)if(G.vertices[i].data==a)returni;return-1;}void CreateGraph(ALGraph&G)//利用邻接表存储结构构造有向图{inta,b;chars;ArcNode*p;cout<<endl<<"现在要构造一个有向图"<<endl;cout<<"请输入顶点个数和图中弧的个数"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"请输入各个顶点的值，顶点的值类型为字符类型"<<endl;for(inti=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}cout<<"请输入图中各个弧"<<endl<<"（每一个弧用其所依附的两个顶点值表示，先输入弧尾顶点值，再输入弧头顶点值）"<<endl;for(i=1;i<=G.arcnum;i++){cin>>s;a=LocateVertices(G,s);cin>>s;b=LocateVertices(G,s);p=newArcNode;if(!p)return;p->adjvex=b;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;}}intFirstAdjVex(ALGraphG,intv)//查找图中位置v的第一个邻接点在图中所在的位置{if(G.vertices[v].firstarc)returnG.vertices[v].firstarc->adjvex;return-1;}intNextAdjVex(ALGraphG,intv,intw)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置{ArcNode*p;p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc;if(p->nextarc)returnp->nextarc->adjvex;return-1;}voidDestroyGraph(ALGraph&G)//销毁图{ArcNode*p,*p1;for(inti=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){deletep;p=p1;if(p1)p1=p1->nextarc;}}}voidInitStack(Stack&stack)//初始化栈{stack.top=0;}voidPushStack(Stack&stack,inti)//元素i入栈{stack.s[stack.top++]=i;}voidPopStack(Stack&stack,int&i)//栈顶元素出栈{i=stack.s[--stack.top];}intStackEmpty(Stackstack)//判断栈是否为空，若为空则返回1，否则返回0{if(!stack.top)return1;return0;}voidFindInDegree(ALGraphG,int*indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[]{ArcNode*p;for(inti=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}intTopologicalSort(ALGraphG)//对图进行拓扑排序，并输出相应的拓扑序列{intcount=0,w;FindInDegree(G,indegree);for(inti=0;i<G.vexnum;i++)if(!indegree[i])while(!StackEmpty(stack)){PopStack(stack,i);cout<<G.vertices[i].data<<"";count++;for(w=FirstAdjVex(G,i);w>=0;w=NextAdjVex(G,i,w))if(!(--indegree[w]))PushStack(stack,w);}if(count<G.vexnum)return-1;return1;}voidmain(){CreateGraph(G);cout<<endl<<"拓扑排序的结果如下："<<endl;if(!TopologicalSort(G))cout<<"图中存在有环"<<endl;cout<<endl;DestroyGraph(G);}题目二：#include<iostream.h>#include<stdlib.h>#defineMAX_VERTEX_NUM20typedefstructArcNode//弧结点定义{intadjvex; //该弧所指向的顶点的位置structArcNode指向下一条弧的指针intinfo;}ArcNode;typedefstructVNode//顶点结点定义{chardata; //顶点信息ArcNode*firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//图的定义{AdjListvertices;intvexnum,arcnum; //图的当前顶点数和弧intkind; //图的种类标志}ALGraph;ALGraphG; //定义图变量boolvisited[MAX_VERTEX_NUM]; //访问标志数intindegree[20]; //各结点入度数组intve[20]; //定义顶点最早开始时间存储数组intvl[20]; //定义顶点最迟开始时间存储数组structStack栈类型定义{ints[21];inttop;};Stackstack; //定义一个栈，用于拓扑排序时存储入度为0的顶点Stackstack1; //存储逆拓扑排序有序序列Stackstack2; //intLocateVertices(ALGraphG,chara)//查找字符a在图中的位置{for(inti=0;i<G.vexnum;i++)if(G.vertices[i].data==a)returni;return-1;}void CreateGraph(ALGraph&G)//利用邻接表存储结构构造有向图{inta,b;chars;ArcNode*p;cout<<endl<<"现在要构造一个有向图"<<endl;cout<<"请输入顶点个数和图中弧的个数"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"请输入各个顶点的值，顶点的值类型为字符类型"<<endl;for(inti=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}cout<<"请输入图中各个弧"<<endl<<"（每一个弧用其所依附的两个顶点值表示，先输入弧尾顶点值，再输入弧头顶点值）"<<endl;for(i=1;i<=G.arcnum;i++){cin>>s;a=LocateVertices(G,s);cin>>s;b=LocateVertices(G,s);p=newArcNode;if(!p)return;p->adjvex=b;"<<endl;cin>>p->info;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;}}voidDestroyGraph(ALGraph&G)//销毁图{ArcNode*p,*p1;for(inti=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){deletep;p=p1;if(p1)p1=p1->nextarc;}}}voidInitStack(Stack&stack)//初始化栈{stack.top=0;}voidPushStack(Stack&stack,inti)//元素i入栈{stack.s[stack.top++]=i;}voidPopStack(Stack&stack,int&i)//栈顶元素出栈{i=stack.s[--stack.top];}intStackEmpty(Stackstack)//判断栈是否为空，若为空则返回1，否则返回0{if(!stack.top)return1;return0;}intGetTopStack(Stackstack)//获得栈顶元素{returnstack.s[stack.top-1];}voidFindInDegree(ALGraphG,int*indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[]{ArcNode*p;for(inti=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}intTopologicalSort(ALGraphG)//对图进行拓扑排序，并输出相应的拓扑序列{intcount=0;ArcNode*p;FindInDegree(G,indegree);InitStack(stack);InitStack(stack1);for(inti=0;i<G.vexnum;i++)ve[i]=0;for(i=0;i<G.vexnum;i++)if(!indegree[i])PushStack(stack,i);while(!StackEmpty(stack)){PopStack(stack,i);PushStack(stack1,i);count++;for(p=G.vertices[i].firstarc;p;p=p->nextarc){if(!(--indegree[p->adjvex]))PushStack(stack,p->adjvex);if(ve[i]+p->info>ve[p->adjvex])ve[p->adjvex]=ve[i]+p->info;}}if(count<G.vexnum)return-1;return1;}intCriticalPath(ALGraphG)//求关键活动，并输出所有活动，关键活动用*标志，同时获得关键路径的逆序序列{chartag;intj,sum=0;ArcNode*p;InitStack(stack2);PushStack(stack2,0);if(TopologicalSort(G)==-1)return-1;for(inti=0;i<G.vexnum;i++)vl[i]=ve[G.vexnum-1];while(!StackEmpty(stack1))for(PopStack(stack1,j),p=G.vertices[j].firstarc;p;p=p->nextarc)if(vl[p->adjvex]-p->info<vl[j])vl[j]=vl[p->adjvex]-p->info;for(j=0;j<G.vexnum;j++)for(p=G.vertices[j].firstarc;p;p=p->nextarc){tag=(ve[j]==vl[p->adjvex]-p->info)?'*':'';cout<<G.vertices[j].data<<""<<G.vertices[p->adjvex].data<<" "<<vl[p->adjvex]-p->adjvex<<""<<tag<<endl;if(j==GetTopStack(stack2)&&tag=='*'){

"<<ve[j]<<"PushStack(stack2,p->adjvex);sum+=p->info;}}cout<<endl<<"关键路径的长度为："<<sum<<endl;return1;}voidmain(){CreateGraph(G);CriticalPath(G);cout<<"该图其中之一的关键路径为："<<endl;inti;while(!StackEmpty(stack2)){PopStack(stack2,i);cout<<G.vertices[i].data<<"";}cout<<endl;DestroyGraph(G);}题目五：#include<iostream.h>#include<stdlib.h>#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex; //该弧所指向的顶点的位置structArcNode指向下一条弧的指针//InfoType*info;}ArcNode;typedefstructVNode{chardata; //顶点信息ArcNode*firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum; //图的当前顶点数和弧intkind; //图的种类标志}ALGraph;ALGraphG; //定义图变量boolvisited[MAX_VERTEX_NUM]; //intnum=0;boolfound=false;intLocateVertices(ALGraphG,chara)//查找字符a在图中的位置{for(inti=0;i<G.vexnum;i++)if(G.vertices[i].data==a)returni;return-1;}intLocateArc(ALGraphG,chara,charb)//判断弧ab是否已经存在于图中，若已经存在则返回1，否则返回0{ArcNode*p;if(LocateVertices(G,a)>=0){p=G.vertices[LocateVertices(G,a)].firstarc;while(p&&p->adjvex!=LocateVertices(G,b))p=p->nextarc;if(p)return1;return0;}return0;}void CreateGraph(ALGraph&G)//利用邻接表存储结构构造有向图{inta,b;chars1,s2;ArcNode*p;for(inti=0;i<G.vexnum;i++){G.vertices[i].data='#';G.vertices[i].firstarc=NULL;}for(i=1;i<=G.arcnum;i++){cin>>s1;a=LocateVertices(G,s1);if(a<0){num++;G.vertices[num-1].data=s1;a=LocateVertices(G,s1);}cin>>s2;b=LocateVertices(G,s2);if(b<0){num++;G.vertices[num-1].data=s2;b=LocateVertices(G,s2);}if(!LocateArc(G,s1,s2)){p=newArcNode;if(!p)return;p->adjvex=b;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;p=newArcNode;if(!p)return;p->adjvex=a;p->nextarc=G.vertices[b].firstarc;G.vertices[b].firstarc=p;}}}intFirstAdjVex(ALGraphG,intv)//查找图中位置v的第一个邻接点在图中所在的位置{if(G.vertices[v].firstarc)returnG.vertices[v].firstarc->adjvex;return-1;}intNextAdjVex(ALGraphG,intv,intw)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置{ArcNode*p;p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc;if(p->nextarc)returnp->nextarc->adjvex;return-1;}voidDestroyGraph(ALGraph&G)//销毁图{ArcNode*p,*p1;for(inti=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){deletep;p=p1;if(p1)p1=p1->nextarc;}}}voidDFSearch(ALGraphG,inti,ints)//查找i与s之间是否有路径，以此来判断二者是否连通，若连通found=true，否则found=false{intw;//for(intx=0;x<G.vexnum;x++)// visited[i]=true;for(w=FirstAdjVex(G,i);w>=0&&!found;w=NextAdjVex(G,i,w)){if(w==s){found=true;visited[s]=true;}elseif(!visited[w])DFSearch(G,w,s);}}voidDeleteArc(ALGraph&G,chara,charb)//删除有向边ab{ArcNode*p,*p1;if(LocateVertices(G,a)>=0){p1=G.vertices[LocateVertices(G,a)].firstarc;while(p1&&p1->adjvex!=LocateVertices(G,b)){p=p1;p1=p1->nextarc;}if(!p1)return;if(p1==G.vertices[LocateVertices(G,a)].firstarc){}else{}}

free(p1);p->nextarc=p1->nextarc;free(p1);return;}voidmain(){chara,b,k;intn;cin>>G.vexnum>>G.arcnum;CreateGraph(G);cin>>n;for(inti=1;i<=n;i++){found=false;cin>>k;{case'Q':cin>>a>>b;intx;for(x=0;x<G.vexnum;x++)visited[x]=false;DFSearch(G,LocateVertices(G,a),LocateVertices(G,b));if(found){}else{}

cout<<"C"<<endl;cout<<"D"<<endl;break;case'D':cin>>a>>b;DeleteArc(G,a,b);DeleteArc(G,b,a);break;default:cout<<"输入有误"<<endl;break;}}DestroyGraph(G);}题目六：#include<iostream.h>#include<stdlib.h>#defineMAX_VERTEX_NUM28typedefstructArcNode//弧结点定义{intadjvex; //该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针//InfoType*info;}ArcNode;typedefstructVNode//顶点结点定义{chardata; //顶点信息ArcNode*firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//图的定义{AdjListvertices;intvexnum,arcnum; //图的当前顶点数和弧intkind; //图的种类标志}ALGraph;ALGraphG; //定义图变量boolvisited[MAX_VERTEX_NUM]; //访问标志数intindegree[28]; //各结点入度数组intnum=0; //记录顶点字符种类chara[28]; //存储拓扑排序序列structStack栈类型定义{ints[21];inttop;};Stackstack; //intLocateVertices(ALGraphG,chara)//查找字符a在图中的位置{for(inti=0;i<G.vexnum;i++)if(G.vertices[i].data==a)returni;return-1;}intLocateArc(ALGraphG,chara,charb)//判断弧ab是否已经存在于图中，若已经存在则返回1，否则返回0{ArcNode*p;if(LocateVertices(G,a)>=0){p=G.vertices[LocateVertices(G,a)].firstarc;while(p&&p->adjvex!=LocateVertices(G,b))p=p->nextarc;if(p)return1;return0;}return0;}void CreateGraph(ALGraph&G)//利用邻接表存储结构构造有向图{inta,b;chars1,s2;ArcNode*p;for(inti=0;i<G.vexnum;i++){G.vertices[i].data='#';G.vertices[i].firstarc=NULL;}for(i=1;i<=G.arcnum;i++){cin>>s1;a=LocateVertices(G,s1);if(a<0){num++;G.vertices[num-1].data=s1;a=LocateVertices(G,s1);}cin>>s2;cin>>s2;b=LocateVertices(G,s2);if(b<0){num++;G.vertices[num-1].data=s2;b=LocateVertices(G,s2);}if(!LocateArc(G,s1,s2)){p=newArcNode;if(!p)return;p->adjvex=b;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;}}}intFirstAdjVex(ALGraphG,intv)//查找图中位置v的第一个邻接点在图中所在的位置{if(G.vertices[v].firstarc)returnG.vertices[v].firstarc->adjvex;return-1;}intNextAdj