【学生版】实验六 图基本操作的编程实现.doc

实验六 图基本操作的编程实现【实验目的】图基本操作的编程实现要求：图基本操作的编程实现（2学时，验证型），掌握图的建立、遍历、插入、删除等基本操作的编程实现，存储结构可以在顺序结构、链接结构、联合使用多种结构等中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】编程对图进行存储（邻接矩阵或邻接表都可以，由学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。设计一个将图形转成邻接链表的程序。设计一个深度优先搜索法来查找图形的程序。设计一个广度优先搜索法来查找一个图形的程序。鼓励开发出难度更高的程序。【思考问题】1. 图的定义和特性？2. 图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？3. 图的主要遍历思路是哪些？4. 举出图的应用范例？【参考代码】（一）基础篇/将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历/程序构思：/用户键盘输入结点与各条边，再将边转成邻接链表。/然后对采用邻接表表示的图进行深度优先遍历。#include#include #define vertexnum 100 /定义最大可输入的结点个数typedef struct node /定义图形的顶点结构 int vertex; /图中的顶点信息为数字 struct node *next;Graph;Graph headvertexnum; /邻接表的表头结点int Visitedvertexnum; /遍历记录void Create_l_Graph(int Vertex1,int Vertex2,int no) /以邻接链表建立图形 Graph *searchP; /结点声明 Graph *New; /新结点声明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New-vertex=Vertex2; New-next=NULL; searchP=&(headVertex1); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New-vertex=Vertex1; New-next=NULL; searchP=&(headVertex2); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New; void showmenu() /显示菜单printf( 欢迎使用图的操作演示软件n);printf(t1、创建图的邻接表n);printf(t2、图的输出n);printf(t3、图的深度优先遍历n);printf(t4、退出程序n);void print_l_graph(Graph *head) /输出邻接链表的数据 Graph *searchP; searchP=head-next; while(searchP!=NULL) printf(n);void DFS(int vertex) /深度优先遍历 Graph *SearchP; /结点声明 /标记某个结点已遍历过 printf(%d=,vertex); SearchP=headvertex.next; while(SearchP!=NULL) if( ) /判断结点未被遍历过 /递归调用深度优先遍历函数 SearchP=SearchP-next; /下一个邻接点 void main() int source; /图中一条边的起始顶点 int destination; /图中一条边的终止顶点 int i,j; int vermax; /定义图中最大的顶点数 int edgemax; /定义图中最大的边数 int choice; int no; while(1)showmenu();printf( 请输入你的选择：);scanf(%d,&choice);fflush(stdin);/清除键盘缓冲区switch(choice) case 1:printf(请输入图的类别（有向图-1，无向图-0）:); scanf(%d,&no); printf(请输入图中的总顶点数和边数:); scanf(%d%d,&vermax,&edgemax); for(i=1;ivermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i=edgemax;i+)printf(请输入第%d条边的起点：,i);scanf(%d,&source);printf(请输入第%d条边的终点：,i);scanf(%d,&destination);if(source=destination) printf(输入有误！n);/出错：自身循环 else /调用建立邻接链表 Create_l_Graph(source,destination,no); printf(图创建成功，按任意键继续n); getch(); system(cls); break; case 2:printf(图的邻接表如下：n); for(i=1;i=vermax;i+)printf(顶点%d:,i); print_l_graph(&headi);/调用输出邻接链表数据 printf(n); system(pause); system(cls); break; case 3:for(i=1;i=vermax;i+) Visitedi=0; printf(请输入遍历的起点:); scanf(%d,&source); printf(图的深度优先遍历结果为：n); DFS(source); printf(ENDn); system(pause); system(cls); break; case 4:return; default: printf(你的输入有误，请从新输入！n); system(pause); system(cls); (二)提高篇/将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历/程序构思：/用户键盘输入结点与各个边，再将边转成邻接链表。/然后对采用邻接表表示的图进行广度优先遍历。#include#include #define vertexnum 100 /定义最大可输入的结点个数#define QueueMax 100typedef struct node /定义图形的顶点结构 int vertex; /图中的顶点信息为数字 struct node *next;Graph;Graph headvertexnum; /邻接表的表头结点int Visitedvertexnum; /遍历记录int Front=-1;int Rear=-1;int QueueQueueMax;int Enqueue(int Vertex) /元素入队 if (Rear=QueueMax) /队列已满 return -1; else Rear+; /队列尾端指针后移 QueueRear=Vertex; /将值存入队列中 return 1; int Dequeue() /元素出队 if (Front=Rear) /队列已空 return -1; else Front+; /队头指针后移 return QueueFront; void BFS(int Vertex)/广度优先搜索 void Create_l_Graph(int Vertex1,int Vertex2,int no) /以邻接链表建立图形 Graph *searchP; /结点声明 Graph *New; /新结点声明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New-vertex=Vertex2; New-next=NULL; searchP=&(headVertex1); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New-vertex=Vertex1; New-next=NULL; searchP=&(headVertex2); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New; void showmenu() /显示菜单printf( 欢迎使用图的操作演示软件n);printf(t1、创建图的邻接表n);printf(t2、图的输出n);printf(t3、图的广度优先遍历n);printf(t4、退出程序n);void print_l_graph(Graph *head) /输出邻接链表的数据 Graph *searchP; searchP=head-next; while(searchP!=NULL) printf(%d,searchP-vertex); searchP=searchP-next; printf(n);void main() int source; /图中一条边的起始顶点 int destination; /图中一条边的终止顶点 int i,j; int vermax; /定义图中最大的顶点数 int edgemax; /定义图中最大的边数 int choice; int no; while(1)showmenu();printf( 请输入你的选择：);scanf(%d,&choice);fflush(stdin);/清除键盘缓冲区switch(choice) case 1:printf(请输入图的类别（有向图-1，无向图-0）:); scanf(%d,&no); printf(请输入图中的总顶点数和边数:); scanf(%d%d,&vermax,&edgemax); for(i=1;ivermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i=edgemax;i+)printf(请输入第%d条边的起点：,i);scanf(%d,&source);printf(请输入第%d条边的终点：,i);scanf(%d,&destination);if(source=destination) printf(输入有误！n);/出错：自身循环 else /调用建立邻接链表 Create_l_Graph(source,destination,no); printf(图创建成功，按任意键继续n); getch(); system(cls); break; case 2:printf(图的邻接表如下：n); for(i=1;i=vermax;i+)printf(顶点%d:,i); print_l_graph(&headi);/调用输出邻接链表数据 printf(n); system(pause); system(cls); break; case 3:for(i=1;i=vermax;i+) Visitedi=0; printf(请输入遍历的起点:); scanf(%d,&source); pri