图的邻接表存储结构实验报告(共9页).doc
精选优质文档-倾情为你奉上图的邻接表存储结构实验报告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.程序的结构图求个点度数退出程序下一次操作建立新图（有向或无向）根据序号求节点值选择操作菜单求第一、二个邻接点的序号深度遍历广度遍历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;i<G->v;i+)/建立顶点表printf("请输入图第%d个元素:",i+1);scanf("%s",&G->Listi.name);/读入顶点信息G->Listi.fnext=NULL;/边表置为空表for(k=0;k<G->e;k+)/建立边表-建立了2倍边的结点printf("请输入边的两顶点序号：（从0考试）");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;node *q;G=malloc(M*sizeof(vnode);printf("请输入顶点数和弧数：");scanf("%d%d",&G->v,&G->e); for (i=0;i<G->v;i+) /建立有n个顶点的顶点表printf("请输入图第%d个元素：",i+1);scanf("%s",&G->Listi.name); /读入顶点信息G->Listi.fnext=NULL; for (k=0;k<G->e;k+) /建立边表printf("请输入两顶点的序号：（从0开始）");scanf("%d%d",&i,&j); q=(node *)malloc(sizeof(node); /生成新边表结点sq->adj=j; /邻接点序号为jq->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;i<G->v;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");for(i=0;i<G->v;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;i<G->v;+i)if(strcmp(u,G->Listi.name)=0)return i;return -1;6）返回序号为v的图结点的值char *VertexGet(Graph G,int v)if(v>=G->v|v<0)exit(0);return G->Listv.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中某个顶点，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.fnext;while(p)if(!flagp->adj)DFS(G,p->adj,flag);p=p->next;void DFSTravel(Graph G)/深度优先遍历int i;int flagM;/标志数组for(i=0;i<G->v;i+)flagi=0;for(i=0;i<G->v;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;i<G->v;i+)flagi=0;for(i=0;i<G->v;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.总结 此次实验要求熟练掌握关于图的各项基本操作，重点在利用邻接表存储图的结构，以及深度、广度优先遍历图的方法。专心-专注-专业
