数据结构图的存储结构及基本操作.doc

1. 实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。2. 实验内容与要求 要求： 能根据输入的顶点、边/弧的信息建立图； 实现图中顶点、边/弧的插入、删除； 实现对该图的深度优先遍历；实现对该图的广度优先遍历。备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。3. 数据结构设计逻辑结构：图状结构存储结构：顺序存储结构、链式存储结构4. 算法设计#include #include #include #define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data2;/顶点就设置和书上V1等等一样吧ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;typedef struct int dataMAX_VERTEX_NUM+10; int front; int rear;queue;int visitedMAX_VERTEX_NUM;queue q;int main()ALGraph G;int CreateUDG(ALGraph &G);int DeleteUDG(ALGraph &G);int InsertUDG(ALGraph &G);void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v);int PrintElement(ALGraph G,ArcNode v);void menu();void depthfirstsearch(ALGraph *g,int vi);void travel(ALGraph *g);void breadfirstsearch(ALGraph *g);int i;G.arcnum = G.vexnum = 0;while(1)menu();doprintf ( 请输入要进行的操作n );scanf (%d,&i);if (i6)printf(错误数字，请重新输入n);while (i6);switch (i)case 1: CreateUDG(G); system(pause); system(cls); break;case 2: DeleteUDG(G); system(pause); system(cls); break;case 3: InsertUDG(G); system(pause); system(cls); break;case 4: travel(&G); system(pause); system(cls); break;case 5: breadfirstsearch(&G); system(pause); system(cls); break;case 6: exit(0); break;return 1;void enterqueue(int v) q.dataq.rear=v; q.rear+;int deletequeue() int t; t=q.dataq.front; q.front+; return(t);int empty() if(q.front=q.rear) return 1; return 0;int LocateVex(ALGraph G,char node2)int i;for(i = 0 ; i G.vexnum ; i+)if(strcmp(G.verticesi.data,node)=0)return i;return -1;int CreateUDG(ALGraph &G)int LocateVex(ALGraph G,char node2);void PrintUDG(ALGraph G);int i,j,k;char node12,node22;ArcNode *p,*q;printf(请输入顶点数和弧数n);printf(例如:5,6n);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(请输入各顶点n);for(i = 0 ; i G.vexnum ; i+)printf(第%d个n,i+1);scanf(%s,&G.verticesi);G.verticesi.firstarc = NULL;/这里开始构造边printf(请输入边的信息n);printf(例如:v1 v2n);for(i = 0 ; i adjvex = k;q-adjvex = j;p-nextarc = G.verticesj.firstarc;G.verticesj.firstarc = p;q-nextarc = G.verticesk.firstarc;G.verticesk.firstarc = q;PrintUDG(G);return 1;int DeleteUDG(ALGraph &G)int i,j;ArcNode *p,*q;char node2;int LocateVex(ALGraph G,char node2);void PrintUDG(ALGraph G);if(G.arcnum = 0)printf(请先生成图n);return 0;printf(请输入要删除的节点n);scanf(%s,&node);i = LocateVex(G,node);if(i = -1)printf(无此节点n);return 0;elseG.vexnum-;if(p = q = G.verticesi.firstarc) != NULL)G.arcnum-;p = p-nextarc;G.verticesi.firstarc = p;free(q);q = p;while(p != NULL)G.arcnum-;p = p-nextarc;G.verticesi.firstarc = p;free(q);q = p;for(j = 0 ; j = i)strcpy(G.verticesj.data , G.verticesj+1.data);G.verticesj.firstarc = G.verticesj+1.firstarc;if(G.verticesj.firstarc-nextarc != NULL)p = G.verticesj.firstarc;q = p-nextarc;if(p-adjvex = i)G.verticesj.firstarc = q;p = q;q = q-nextarc;continue;else if(p-adjvex i)p-adjvex-;while(q != NULL)if(q-adjvex = i)p-nextarc = q-nextarc;free(q);q = p-nextarc;else if(q-adjvex i)q-adjvex-;elsep = p-nextarc;q = q-nextarc;else if( (G.verticesj.firstarc-nextarc = NULL) & (G.verticesj.firstarc != NULL) )if( G.verticesj.firstarc-adjvex = i )G.verticesj.firstarc = NULL;PrintUDG(G);return 1;int InsertUDG(ALGraph &G)/默认一次插入一个节点吧,不然太麻烦int i,j,k,l;char node12,node22;ArcNode *p,*q;int LocateVex(ALGraph G,char node2);void PrintUDG(ALGraph G);if(G.arcnum = 0)printf(请先生成图n);return 0;printf(请输入插入节点的名称n);printf(WARNING:绝不可以和之前的节点重名!n);scanf(%s,&G.verticesG.vexnum.data);G.verticesG.vexnum.firstarc = NULL;printf(请输入需要插入的边的数目n);scanf(%d,&i);G.arcnum += i;G.vexnum+;printf(请输入边的信息n);printf(例如:v6 v2n);printf(WARNING:一定要包含刚加入的节点名称!n);for(j = 0 ; j adjvex = k;q-adjvex = l;p-nextarc = G.verticesl.firstarc;G.verticesl.firstarc = p;q-nextarc = G.verticesk.firstarc;G.verticesk.firstarc = q;PrintUDG(G);return 1;void depthfirstsearch(ALGraph *g,int vi) ArcNode *rear; printf(%st,g-verticesvi.data); visitedvi=1; rear=g-verticesvi.firstarc; while(rear!=NULL)&(!visitedrear-adjvex) depthfirstsearch(g,rear-adjvex); rear=rear-nextarc; void travel(ALGraph *g) int v; for(v=0;vvexnum;v+) if(!visitedv) depthfirstsearch(g,v);void breadfirstsearch(ALGraph *g) int v,t,i; ArcNode *rear;for(i = 0 ; i vexnum ; i+)visitedi = 0; for(v=0;vvexnum;v+) if(!visitedv) printf(%s,g-verticesv.data); visitedv=1; enterqueue(v); while(!empty() t=deletequeue(); rear=g-verticest.firstarc; while(rear!=NULL)&(!visitedrear-adjvex) printf(%st,g-verticesrear-adjvex.data); visitedrear-adjvex=1; enterqueue(rear-adjvex); rear=rear-nextarc; void menu() printf(*n);printf(* 作者：Dick *n);printf(* 信计1001 xxxxxxxxxx *n); printf(*MENU*n); printf(1 建立无向图n); printf(2 删除图中节点n); printf(3 插入节点n);printf(4 深