《图的邻接表存储结构实验报告》1.需解决的的问题利用邻接表存储结果，设计一种图。

2.数据结构的定义typedef struct node{//边表结点int adj;//边表结点数据域struct node *next;}node;typedef struct vnode{//顶点表结点char name[20];node *fnext;}vnode,AList[M];typedef struct{AList 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->List[i].name);//读入顶点信息G->List[i].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->List[i].fnext;G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node));s->adj=i;//邻接点序号为is->next=G->List[j].fnext;G->List[j].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->List[i].name); //读入顶点信息G->List[i].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->List[i].fnext;G->List[i].fnext=q;}return G;}3）输出无向图的邻接表void Print1(Graph G)//输出无向图的邻接表{int i;node *p;printf("\n\t\t\t邻接表\n");for(i=0;i<G->v;i++){ p=G->List[i].fnext;printf("\t\t\t%d | %3s",i,G->List[i].name);while(p){printf("->%d",p->adj);p=p->next;}printf("\n");}}4）输出个元素的度数void Du(Graph G)//输出各元素的度数{int i,j;node *p;printf("\n\t\t\t各点度数\n");for(i=0;i<G->v;i++){ p=G->List[i].fnext;printf("\t\t\t顶点%2s的度为：",G->List[i].name);j=0;while(p){ j++;p=p->next;}printf("%d\n",j);}}5）返回图结点在的序号int LocateVex(Graph G,char *u){//初始条件：图G存在，u和G中顶点有相同的特征//操作结果：若G中存在顶点u，则返回该顶点在图中的位置;否则返回-1 int i;for(i=0;i<G->v;++i)if(strcmp(u,G->List[i].name)==0)return i;return -1;}6）返回序号为v的图结点的值char *VertexGet(Graph G,int v){if(v>=G->v||v<0)exit(0);return G->List[v].name;}7）返回图结点v的第一个邻接顶点的序号int FirstAdjVex(Graph G,char *v){//初始条件：图G存在，v是G中的某个顶点//操作结果：返回v中第一个邻接顶点的序号。

若顶点在G中没有邻接顶点//则返回-1node *p;int v1;v1=LocateVex(G,v);p=G->List[v1].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->List[v1].fnext;while(p&&p->adj!=w1)p=p->next;if(!p||!p->next)printf("没有第二个邻接点!\n");elseprintf("第二个邻接点序号是：%d\n",p->next->adj);}9）深度优先遍历图void DFS(Graph G,int i,int flag[]){node *p;printf("%2s ",G->List[i].name);flag[i]=1;p=G->List[i].fnext;while(p){if(!flag[p->adj])DFS(G,p->adj,flag);p=p->next;}}void DFSTravel(Graph G)//深度优先遍历{int i;int flag[M];//标志数组for(i=0;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(!flag[i])DFS(G,i,flag);}10）广度优先遍历void BFSTravel(Graph G)//广度优先遍历{ Queue Q;node *p;int i,j=0;int flag[M];//标志数组Q=malloc(sizeof(M));InitQueue(Q);for(i=0;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(flag[i]==0)//此点未被访问{flag[i]=1;printf("%2s ",G->List[i].name);Enter(Q,i);while(Q->front!=Q->rear){Leave(Q,j);//队头元素出队并置为jp=G->List[j].fnext;while(p!=NULL){ if(flag[p->adj]==0){printf("%2s ",G->List[p->adj].name);flag[p->adj]=1;Enter(Q,p->adj);}//ifp=p->next;}//while}//while}//if}5.输入/输出数据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.总结此次实验要求熟练掌握关于图的各项基本操作，重点在利用邻接表存储图的结构，以及深度、广度优先遍历图的方法。