图的邻接表存储结构实验报告(共9页).doc

《图的邻接表存储结构实验报告(共9页).doc》由会员分享，可在线阅读，更多相关《图的邻接表存储结构实验报告(共9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上图的邻接表存储结构实验报告1.需解决的的问题 利用邻接表存储结果，设计一种图。2.数据结构的定义typedef struct node/边表结点int adj;/边表结点数据域struct node *next;node;typedef struct vnode/顶点表结点char name20;node *fnext;vnode,AListM;typedef structAList List;/邻接表int v,e;/顶点树和边数*Graph;3.程序的结构图求个点度数退出程序下一次操作建立新图（有向或无向）根据序号求节点值选择操作菜单求第一、二个邻接点的序号深度遍

2、历广度遍历4.函数的功能1）建立无向邻接表Graph Create1( )/建立无向邻接表Graph G;int i,j,k;node *s;G=malloc(M*sizeof(vnode);printf(输入图的顶点数和边数：);scanf(%d%d,&G-v,&G-e);/读入顶点数和边数for(i=0;iv;i+)/建立顶点表printf(请输入图第%d个元素:,i+1);scanf(%s,&G-Listi.name);/读入顶点信息G-Listi.fnext=NULL;/边表置为空表for(k=0;ke;k+)/建立边表-建立了2倍边的结点printf(请输入边的两顶点序号：（从0考试

3、）);scanf(%d%d,&i,&j);/读入边（Vi,Vj）的顶点对序号s=(node *)malloc(sizeof(node);/生成边表结点s-adj=j;s-next=G-Listi.fnext;G-Listi.fnext=s;/将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node);s-adj=i;/邻接点序号为is-next=G-Listj.fnext;G-Listj.fnext=s;/ 将新结点*s插入顶点Vj的边表头部 return G;2）建立有向邻接图Graph Create2() /有向邻接图Graph G;int i,j,k;n

4、ode *q;G=malloc(M*sizeof(vnode);printf(请输入顶点数和弧数：);scanf(%d%d,&G-v,&G-e); for (i=0;iv;i+) /建立有n个顶点的顶点表printf(请输入图第%d个元素：,i+1);scanf(%s,&G-Listi.name); /读入顶点信息G-Listi.fnext=NULL; for (k=0;ke;k+) /建立边表printf(请输入两顶点的序号：（从0开始）);scanf(%d%d,&i,&j); q=(node *)malloc(sizeof(node); /生成新边表结点sq-adj=j; /邻接点序号为j

5、q-next=G-Listi.fnext; G-Listi.fnext=q; return G;3）输出无向图的邻接表void Print1(Graph G)/输出无向图的邻接表int i;node *p;printf(nttt邻接表n);for(i=0;iv;i+)p=G-Listi.fnext;printf(ttt%d | %3s,i,G-Listi.name);while(p)printf(-%d,p-adj);p=p-next;printf(n);4）输出个元素的度数void Du(Graph G)/输出各元素的度数int i,j;node *p;printf(nttt各点度数n);f

6、or(i=0;iv;i+)p=G-Listi.fnext;printf(ttt顶点%2s的度为：,G-Listi.name);j=0;while(p)j+;p=p-next;printf(%dn,j);5）返回图结点在的序号int LocateVex(Graph G,char *u)/初始条件：图G存在，u和G中顶点有相同的特征/操作结果：若G中存在顶点u，则返回该顶点在图中的位置;否则返回-1int i;for(i=0;iv;+i)if(strcmp(u,G-Listi.name)=0)return i;return -1;6）返回序号为v的图结点的值char *VertexGet(Grap

7、h G,int v)if(v=G-v|vListv.name;7）返回图结点v的第一个邻接顶点的序号int FirstAdjVex(Graph G,char *v)/初始条件：图G存在，v是G中的某个顶点/操作结果：返回v中第一个邻接顶点的序号。若顶点在G中没有邻接顶点/则返回-1node *p;int v1;v1=LocateVex(G,v);p=G-Listv1.fnext;if(p)return p-adj;elsereturn -1;8）找到图结点v的第二个邻接顶点的序号void NextAdjVex(Graph G,char *v,char *w)/初始条件：图G存在，v是G中某个顶

8、点，w是v得邻接点/操作结果：输出v的（相对于w的）下一个邻接点的序号node *p;int v1,w1;v1=LocateVex(G,v);w1=LocateVex(G,w);p=G-Listv1.fnext;while(p&p-adj!=w1)p=p-next;if(!p|!p-next)printf(没有第二个邻接点!n);elseprintf(第二个邻接点序号是：%dn,p-next-adj);9）深度优先遍历图void DFS(Graph G,int i,int flag)node *p;printf(%2s ,G-Listi.name);flagi=1;p=G-Listi.fnex

9、t;while(p)if(!flagp-adj)DFS(G,p-adj,flag);p=p-next;void DFSTravel(Graph G)/深度优先遍历int i;int flagM;/标志数组for(i=0;iv;i+)flagi=0;for(i=0;iv;i+)if(!flagi)DFS(G,i,flag);10）广度优先遍历void BFSTravel(Graph G)/广度优先遍历Queue Q;node *p;int i,j=0;int flagM;/标志数组Q=malloc(sizeof(M);InitQueue(Q);for(i=0;iv;i+)flagi=0;for(

10、i=0;iv;i+)if(flagi=0)/此点未被访问flagi=1;printf(%2s ,G-Listi.name);Enter(Q,i);while(Q-front!=Q-rear)Leave(Q,j);/队头元素出队并置为jp=G-Listj.fnext;while(p!=NULL)if(flagp-adj=0)printf(%2s ,G-Listp-adj.name);flagp-adj=1;Enter(Q,p-adj);/ifp=p-next;/while/while/if5.输入/输出数据1）选择操作2）选择“1”然后输入“3 3”输入“a”，“b”，“c”输入“0 1”，“1 2”，“2 0”3）选择“2”跟选择“1”类似4）选择“3”5）选择“4”输入“1”6）选择“5”输入“a”7）选择“6”8）选择“7”9）选择“0”退出程序6.总结 此次实验要求熟练掌握关于图的各项基本操作，重点在利用邻接表存储图的结构，以及深度、广度优先遍历图的方法。专心-专注-专业