数据结构_实验六_报告

1、.实验报告实验六 图的应用及其实现 一、实验目的1进一步功固图常用的存储结构。2熟练掌握在图的邻接表实现图的基本操作。3理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。二、实验内容 一.基础题目：(本类题目属于验证性的，要求学生独立完成) 题目一：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。题目二：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。 试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。测试数

2、据：教材图7.29 【题目五】连通 OR 不连通描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作：D x y 从原图中删除连接x，y节点的边。Q x y 询问x，y节点是否连通 输入第一行两个数n,m（5=n=40000,1=m=100000）接下来m行，每行一对整数 x y （x,y=n）,表示x,y之间有边相连。保证没有重复的边。接下来一行一个整数 q（q=100000）以下q行每行一种操作，保证不会有非法删除。输出按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D样例输入331213235Q12D12Q12D32Q12样例输出CCD【题目六】 Sort Proble

3、mAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A B, B C and C D. in this problem, we will give you a set of relations of the form A B a

4、nd ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 = n = 26. The objects to be sort

5、ed will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A B which will be given in this problem instance. 1 = m = 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, th

6、e character and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.【Output】For each problem instance, output consists of one line. This line should be one of the following three:Sorted sequence determined:

7、y y y y.Sorted sequence cannot be determined.Inconsistency found.y y y y is the sorted, ascending sequence.Sample Input Sample Output 4 6 Sorted sequence determined: A B C D.AB Inconsistency found.AC Sorted sequence cannot be determined.BCCDBDAB3 2ABBA26 2AZDadjvex!=wp=p-nextarc;p-nextarc=NULLreturn

8、 p-nextarc-adjvex;Return -1; 否 否 是 是 否开始输入图的顶点和弧的个数cinG.vexnumG.arcnum;输入顶点值存入图中i=1is; a=LocateVertices(G,s);cins; b=LocateVertices(G,s);构造结点p=new ArcNode;将此结点插入适当的位置p-adjvex=b;p-nextarc=G.verticesa.firstarc;G.verticesa.firstarc=p;i+结束利用邻接表存储结构构造有向图void CreateGraph(ALGraph &G) 否 是查找图中位置v的第一个邻接点在图中所在

9、的位置int FirstAdjVex(ALGraph G,int v)开始G.verticesv.firstarc=NULLreturn G.verticesv.firstarc-adjvex;return -1; 是 否对图进行拓扑排序，并输出相应的拓扑序列开始求各定点入度FindInDegree(G,indegree);找到入度为0的顶点并入栈栈是否为空栈顶元素出栈并输出i；计数器count+；求i顶点的第一个邻接点wW大于等于0吗if(!(-indegreew)PushStack(stack,w);求下一邻接点w=NextAdjVex(G,i,w)if(countG.vexnum)ret

10、urn -1;return 1;int TopologicalSort(ALGraph G) 是 否 否 是 2、程序清单 题目一：#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNode/弧结点定义int adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针/InfoType *info;ArcNode;typedef struct VNode/顶点结点定义char data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode

11、,AdjListMAX_VERTEX_NUM;typedef struct/图的定义AdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph;ALGraph G; /定义图变量bool visitedMAX_VERTEX_NUM; /访问标志数组int indegree20; /各结点入度数组struct Stack/栈类型定义int s21;int top;Stack stack; /定义一个栈int LocateVertices(ALGraph G,char a)/查找字符a在图中的位置for(int i

12、=0;iG.vexnum;i+)if(G.verticesi.data=a)return i;return -1;void CreateGraph(ALGraph &G)/利用邻接表存储结构构造有向图int a,b;char s;ArcNode *p;coutendl现在要构造一个有向图endl;cout请输入顶点个数和图中弧的个数G.vexnumG.arcnum;cout请输入各个顶点的值，顶点的值类型为字符类型endl;for(int i=0;iG.verticesi.data;G.verticesi.firstarc=NULL;cout请输入图中各个弧endl（每一个弧用其所依附的两个顶

13、点值表示，先输入弧尾顶点值，再输入弧头顶点值）endl;for(i=1;is;a=LocateVertices(G,s);cins;b=LocateVertices(G,s);p=new ArcNode;if(!p)return;p-adjvex=b;p-nextarc=G.verticesa.firstarc;G.verticesa.firstarc=p;int FirstAdjVex(ALGraph G,int v)/查找图中位置v的第一个邻接点在图中所在的位置if(G.verticesv.firstarc)return G.verticesv.firstarc-adjvex;return

14、 -1;int NextAdjVex(ALGraph G,int v,int w)/查找相对于图中位置v的邻接点w的下一邻接点在图中的位置ArcNode *p;p=G.verticesv.firstarc;while(p-adjvex!=w)p=p-nextarc;if(p-nextarc)return p-nextarc-adjvex;return -1;void DestroyGraph(ALGraph &G)/销毁图ArcNode *p,*p1;for(int i=0;inextarc;while(p)delete p;p=p1;if(p1)p1=p1-nextarc;void Init

15、Stack(Stack &stack)/初始化栈stack.top=0;void PushStack(Stack &stack,int i)/元素i入栈stack.sstack.top+=i;void PopStack(Stack &stack,int &i)/栈顶元素出栈i=stack.s-stack.top;int StackEmpty(Stack stack)/判断栈是否为空，若为空则返回1，否则返回0if(!stack.top)return 1;return 0;void FindInDegree(ALGraph G,int *indegree)/求图中各个顶点的入度，并相应的存入入度

16、数组中indegreeArcNode *p;for(int i=0;iG.vexnum;i+)indegreei=0;for(i=0;iadjvex+;p=p-nextarc;int TopologicalSort(ALGraph G)/对图进行拓扑排序，并输出相应的拓扑序列int count=0,w;FindInDegree(G,indegree);for(int i=0;iG.vexnum;i+)if(!indegreei)PushStack(stack,i);while(!StackEmpty(stack)PopStack(stack,i);coutG.verticesi.data=0;

17、w=NextAdjVex(G,i,w)if(!(-indegreew)PushStack(stack,w);if(countG.vexnum)return -1;return 1;void main()CreateGraph(G);coutendl拓扑排序的结果如下：endl;if(!TopologicalSort(G)cout图中存在有环endl;coutendl;DestroyGraph(G);题目二：#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNode/弧结点定义int adjvex; /该弧所指向的顶点的位置st

18、ruct ArcNode *nextarc;/指向下一条弧的指针int info;ArcNode;typedef struct VNode/顶点结点定义char data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct/图的定义AdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph;ALGraph G; /定义图变量bool visitedMAX_VERTEX_NUM; /访问标志数组in

19、t indegree20; /各结点入度数组int ve20; /定义顶点最早开始时间存储数组int vl20; /定义顶点最迟开始时间存储数组struct Stack/栈类型定义int s21;int top;Stack stack; /定义一个栈，用于拓扑排序时存储入度为0的顶点Stack stack1; /存储逆拓扑排序有序序列Stack stack2; /存储关键路径int LocateVertices(ALGraph G,char a)/查找字符a在图中的位置for(int i=0;iG.vexnum;i+)if(G.verticesi.data=a)return i;return

20、-1;void CreateGraph(ALGraph &G)/利用邻接表存储结构构造有向图int a,b;char s;ArcNode *p;coutendl现在要构造一个有向图endl;cout请输入顶点个数和图中弧的个数G.vexnumG.arcnum;cout请输入各个顶点的值，顶点的值类型为字符类型endl;for(int i=0;iG.verticesi.data;G.verticesi.firstarc=NULL;cout请输入图中各个弧endl（每一个弧用其所依附的两个顶点值表示，先输入弧尾顶点值，再输入弧头顶点值）endl;for(i=1;is;a=LocateVertice

21、s(G,s);cins;b=LocateVertices(G,s);p=new ArcNode;if(!p)return;p-adjvex=b;cout请输入该弧的长度p-info;p-nextarc=G.verticesa.firstarc;G.verticesa.firstarc=p;void DestroyGraph(ALGraph &G)/销毁图ArcNode *p,*p1;for(int i=0;inextarc;while(p)delete p;p=p1;if(p1)p1=p1-nextarc;void InitStack(Stack &stack)/初始化栈stack.top=0

22、;void PushStack(Stack &stack,int i)/元素i入栈stack.sstack.top+=i;void PopStack(Stack &stack,int &i)/栈顶元素出栈i=stack.s-stack.top;int StackEmpty(Stack stack)/判断栈是否为空，若为空则返回1，否则返回0if(!stack.top)return 1;return 0;int GetTopStack(Stack stack)/获得栈顶元素return stack.sstack.top-1;void FindInDegree(ALGraph G,int *ind

23、egree)/求图中各个顶点的入度，并相应的存入入度数组中indegreeArcNode *p;for(int i=0;iG.vexnum;i+)indegreei=0;for(i=0;iadjvex+;p=p-nextarc;int TopologicalSort(ALGraph G)/对图进行拓扑排序，并输出相应的拓扑序列int count=0;ArcNode *p;FindInDegree(G,indegree);InitStack(stack);InitStack(stack1);for(int i=0;iG.vexnum;i+)vei=0;for(i=0;inextarc)if(!(

24、-indegreep-adjvex)PushStack(stack,p-adjvex);if(vei+p-infovep-adjvex)vep-adjvex=vei+p-info;if(countG.vexnum)return -1;return 1;int CriticalPath(ALGraph G)/求关键活动，并输出所有活动，关键活动用*标志，同时获得关键路径的逆序序列char tag;int j,sum=0;ArcNode *p;InitStack(stack2);PushStack(stack2,0);if(TopologicalSort(G)=-1)return -1;for(i

25、nt i=0;inextarc)if(vlp-adjvex-p-infoadjvex-p-info;for(j=0;jnextarc)tag=(vej=vlp-adjvex-p-info)?*: ;coutG.verticesj.data adjvex.data info vej adjvex-p-adjvex tagadjvex);sum+=p-info;coutendl关键路径的长度为：sumendl;return 1;void main()CreateGraph(G);CriticalPath(G);cout该图其中之一的关键路径为：endl;int i;while(!StackEmpt

26、y(stack2)PopStack(stack2,i);coutG.verticesi.data ;coutendl;DestroyGraph(G);题目五：#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针/InfoType *info;ArcNode;typedef struct VNodechar data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode

27、,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph;ALGraph G; /定义图变量bool visitedMAX_VERTEX_NUM; /访问标志数组int num=0;bool found=false;int LocateVertices(ALGraph G,char a)/查找字符a在图中的位置for(int i=0;i=0)p=G.verticesLocateVertices(G,a).firstarc;while(p

28、&p-adjvex!=LocateVertices(G,b)p=p-nextarc;if(p)return 1;return 0;return 0;void CreateGraph(ALGraph &G)/利用邻接表存储结构构造有向图int a,b;char s1,s2;ArcNode *p;for(int i=0;iG.vexnum;i+)G.verticesi.data=#;G.verticesi.firstarc=NULL;for(i=1;is1;a=LocateVertices(G,s1);if(as2;b=LocateVertices(G,s2);if(badjvex=b;p-nex

29、tarc=G.verticesa.firstarc;G.verticesa.firstarc=p;p=new ArcNode;if(!p)return;p-adjvex=a;p-nextarc=G.verticesb.firstarc;G.verticesb.firstarc=p;int FirstAdjVex(ALGraph G,int v)/查找图中位置v的第一个邻接点在图中所在的位置if(G.verticesv.firstarc)return G.verticesv.firstarc-adjvex;return -1;int NextAdjVex(ALGraph G,int v,int

30、w)/查找相对于图中位置v的邻接点w的下一邻接点在图中的位置ArcNode *p;p=G.verticesv.firstarc;while(p-adjvex!=w)p=p-nextarc;if(p-nextarc)return p-nextarc-adjvex;return -1;void DestroyGraph(ALGraph &G)/销毁图ArcNode *p,*p1;for(int i=0;inextarc;while(p)delete p;p=p1;if(p1)p1=p1-nextarc;void DFSearch(ALGraph G,int i,int s)/查找i与s之间是否有路

31、径，以此来判断二者是否连通，若连通found=true，否则found=falseint w;/for(int x=0;x=0&!found;w=NextAdjVex(G,i,w)if(w=s)found=true;visiteds=true;else if(!visitedw)DFSearch(G,w,s);void DeleteArc(ALGraph &G,char a,char b)/删除有向边abArcNode *p,*p1;if(LocateVertices(G,a)=0)p1=G.verticesLocateVertices(G,a).firstarc;while(p1&p1-ad

32、jvex!=LocateVertices(G,b)p=p1;p1=p1-nextarc;if(!p1)return;if(p1=G.verticesLocateVertices(G,a).firstarc)G.verticesLocateVertices(G,a).firstarc=p1-nextarc;free(p1);elsep-nextarc=p1-nextarc;free(p1);return;void main()char a,b,k;int n;cinG.vexnumG.arcnum;CreateGraph(G);cinn;for(int i=1;ik;switch(k)case

33、Q:cinab;int x;for(x=0;xG.vexnum;x+)visitedx=false;DFSearch(G,LocateVertices(G,a),LocateVertices(G,b);if(found)coutCendl;elsecoutDab;DeleteArc(G,a,b);DeleteArc(G,b,a);break;default:cout输入有误endl;break;DestroyGraph(G);题目六：#include#include#define MAX_VERTEX_NUM 28typedef struct ArcNode/弧结点定义int adjvex;

34、/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针/InfoType *info;ArcNode;typedef struct VNode/顶点结点定义char data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct/图的定义AdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph;ALGraph G; /定义图变量bool visitedMAX_VERTEX_NUM; /访问标志数组int indegree28; /各结点入度数组int num=0; /记录顶点字符种类数char a28; /存储拓扑排序序列struct Stack/栈类型定义int s21;int top;Stack stack; /定义一个栈int LocateVertices(ALGraph G,char a)/查找字符a在图中的