数据结构图的存储结构及

数据结构图的存储结构及数据结构图的存储结构及全文共16页，当前为第1页。数据结构图的存储结构及全文共16页，当前为第1页。实验目的通过上机实验进一步掌握图的存储结构及基本操作的实现。实验内容与要求要求：⑴能根据输入的顶点、边/弧的信息建立图；⑵实现图中顶点、边/弧的插入、删除；⑶实现对该图的深度优先遍历；⑷实现对该图的广度优先遍历。备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。数据结构设计逻辑结构：图状结构存储结构：顺序存储结构、链式存储结构算法设计#include<stdio.h>#include<string.h>#include<stdlib.h>数据结构图的存储结构及全文共16页，当前为第2页。数据结构图的存储结构及全文共16页，当前为第2页。typedefstructArcNode{ intadjvex; structArcNode*nextarc;}ArcNode;typedefstructVNode{ chardata[2]; //顶点就设置和书上V1等等一样吧 ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{ AdjListvertices; intvexnum,arcnum;}ALGraph;typedefstruct{intdata[MAX_VERTEX_NUM+10];intfront;intrear;数据结构图的存储结构及全文共16页，当前为第3页。数据结构图的存储结构及全文共16页，当前为第3页。intvisited[MAX_VERTEX_NUM];queueq;intmain(){ ALGraphG; intCreateUDG(ALGraph&G); intDeleteUDG(ALGraph&G); intInsertUDG(ALGraph&G); voidBFSTraverse(ALGraphG,int(*Visit)(ALGraphG,ArcNodev)); intPrintElement(ALGraphG,ArcNodev); voidmenu(); voiddepthfirstsearch(ALGraph*g,intvi); voidtravel(ALGraph*g); voidbreadfirstsearch(ALGraph*g); inti; G.arcnum=G.vexnum=0; while(1) { menu(); do数据结构图的存储结构及全文共16页，当前为第4页。数据结构图的存储结构及全文共16页，当前为第4页。 printf("请输入要进行的操作\n"); scanf("%d",&i); if(i<1||i>6) printf("错误数字，请重新输入\n"); }while(i<1||i>6); switch(i) { case1:CreateUDG(G);system("pause");system("cls");break; case2:DeleteUDG(G);system("pause");system("cls");break; case3:InsertUDG(G);system("pause");system("cls");break; case4:travel(&G);system("pause");system("cls");break; case5:breadfirstsearch(&G);system("pause");system("cls");break; case6:exit(0);break; } } return1;}voidenterqueue(intv){q.data[q.rear]=v;q.rear++;}数据结构图的存储结构及全文共16页，当前为第5页。数据结构图的存储结构及全文共16页，当前为第5页。{intt;t=q.data[q.front];q.front++;return(t);}intempty(){if(q.front==q.rear)return1;return0;}intLocateVex(ALGraphG,charnode[2]){ inti; for(i=0;i<G.vexnum;i++) { if(strcmp(G.vertices[i].data,node)==0) returni; } return-1;}intCreateUDG(ALGraph&G){ intLocateVex(ALGraphG,charnode[2]); voidPrintUDG(ALGraphG); inti,j,k; charnode1[2],node2[2];数据结构图的存储结构及全文共16页，当前为第6页。数据结构图的存储结构及全文共16页，当前为第6页。 printf("请输入顶点数和弧数\n"); printf("例如:5,6\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); printf("请输入各顶点\n"); for(i=0;i<G.vexnum;i++) { printf("第%d个\n",i+1); scanf("%s",&G.vertices[i]); G.vertices[i].firstarc=NULL; } //这里开始构造边 printf("请输入边的信息\n"); printf("例如:v1v2\n"); for(i=0;i<G.arcnum;i++) { printf("第%d条边\n",i+1); scanf("%s%s",&node1,&node2); j=LocateVex(G,node1); k=LocateVex(G,node2); p=(ArcNode*)malloc(sizeof(ArcNode));数据结构图的存储结构及全文共16页，当前为第7页。 q=(ArcNode*)malloc(sizeof(ArcNode)数据结构图的存储结构及全文共16页，当前为第7页。 p->adjvex=k; q->adjvex=j; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; q->nextarc=G.vertices[k].firstarc; G.vertices[k].firstarc=q; } PrintUDG(G); return1;}intDeleteUDG(ALGraph&G){ inti,j; ArcNode*p,*q; charnode[2]; intLocateVex(ALGraphG,charnode[2]); voidPrintUDG(ALGraphG); if(G.arcnum==0) { printf("请先生成图\n"); return0; } printf("请输入要删除的节点\n"); scanf("%s",&node);数据结构图的存储结构及全文共16页，当前为第8页。数据结构图的存储结构及全文共16页，当前为第8页。 if(i==-1) { printf("无此节点\n"); return0; } else { G.vexnum--; if((p=q=G.vertices[i].firstarc)!=NULL) { G.arcnum--; p=p->nextarc; G.vertices[i].firstarc=p; free(q); q=p; while(p!=NULL) { G.arcnum--; p=p->nextarc; G.vertices[i].firstarc=p; free(q); q=p; } } for(j=0;j<G.vexnum;j++) { if(j>=i) { strcpy(G.vertices[j].data,G.vertices[j+1].data);数据结构图的存储结构及全文共16页，当前为第9页。 G.vertices[j].firstarc数据结构图的存储结构及全文共16页，当前为第9页。 } if(G.vertices[j].firstarc->nextarc!=NULL) { p=G.vertices[j].firstarc; q=p->nextarc; if(p->adjvex==i) { G.vertices[j].firstarc=q; p=q; q=q->nextarc; continue; } elseif(p->adjvex>i) p->adjvex--; while(q!=NULL) { if(q->adjvex==i) { p->nextarc=q->nextarc; free(q); q=p->nextarc; } elseif(q->adjvex>i)数据结构图的存储结构及全文共数据结构图的存储结构及全文共16页，当前为第10页。 else { p=p->nextarc; q=q->nextarc; } } } elseif((G.vertices[j].firstarc->nextarc==NULL)&&(G.vertices[j].firstarc!=NULL)) if(G.vertices[j].firstarc->adjvex==i) { G.vertices[j].firstarc=NULL; } } } PrintUDG(G); return1;}intInsertUDG(ALGraph&G){ //默认一次插入一个节点吧,不然太麻烦 inti,j,k,l; charnode1[2],node2[2]; ArcNode*p,*q; intLocateVex(ALGraphG,charnode[2]);数据结构图的存储结构及全文共16页，当前为第11页。数据结构图的存储结构及全文共16页，当前为第11页。 if(G.arcnum==0) { printf("请先生成图\n"); return0; } printf("请输入插入节点的名称\n"); printf("WARNING:绝不可以和之前的节点重名!\n"); scanf("%s",&G.vertices[G.vexnum].data); G.vertices[G.vexnum].firstarc=NULL; printf("请输入需要插入的边的数目\n"); scanf("%d",&i); G.arcnum+=i; G.vexnum++; printf("请输入边的信息\n"); printf("例如:v6v2\n"); printf("WARNING:一定要包含刚加入的节点名称!\n"); for(j=0;j<i;j++) { printf("第%d条边\n",j+1); scanf("%s%s",&node1,&node2); l=LocateVex(G,node1); k=LocateVex(G,node2); p=(ArcNode*)malloc(sizeof(ArcNode));数据结构图的存储结构及全文共16页，当前为第12页。数据结构图的存储结构及全文共16页，当前为第12页。 p->adjvex=k; q->adjvex=l; p->nextarc=G.vertices[l].firstarc; G.vertices[l].firstarc=p; q->nextarc=G.vertices[k].firstarc; G.vertices[k].firstarc=q; } PrintUDG(G); return1;} voiddepthfirstsearch(ALGraph*g,intvi){ArcNode*rear;printf("%s\t",g->vertices[vi].data);visited[vi]=1;rear=g->vertices[vi].firstarc;while((rear!=NULL)&&(!visited[rear->adjvex])){depthfirstsearch(g,rear->adjvex);rear=rear->nextarc;}}数据结构图的存储结构及全文共16页，当前为第13页。数据结构图的存储结构及全文共16页，当前为第13页。{intv;for(v=0;v<g->vexnum;v++)if(!visited[v])depthfirstsearch(g,v);}voidbreadfirstsearch(ALGraph*g){intv,t,i;ArcNode*rear; for(i=0;i<g->vexnum;i++) visited[i]=0;for(v=0;v<g->vexnum;v++){if(!visited[v]){printf("%s",g->vertices[v].data);visited[v]=1;enterqueue(v);}while(!empty()){t=deletequeue();rear=g->vertices[t].firstarc;数据结构图的存储结构及全文共16页，当前为第14页。数据结构图的存储结构及全文共16页，当前为第14页。{printf("%s\t",g->vertices[rear->adjvex].data);visited[rear->adjvex]=1;enterqueue(rear->adjvex);rear=rear->nextarc;}}}}voidmenu(){printf("*********************************************\n"); printf("*作者：Dick*\n"); printf("*信计1001xxxxxxxxxx*\n");printf("*****