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

《【学生版】实验六图基本操作的编程实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验六图基本操作的编程实现【实验目的】图基本操作的编程实现要求：图基本操作的编程实现（2学时，验证型），常握图的建立、遍历、插入、删除等基本操作的编程实现,存储结构可以在顺序结构、链接结构、联合使用多种结构等屮任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】编程对图进行存储（邻接矩阵或邻接表都可以，由学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。设计一个将图形转成邻接链表的程序。设计一个深度优先搜索法来查找图形的程序。设计一个广度优先搜索法来查找-个图形的程序。鼓励开发出难

2、度更高的程序。【思考问题】1.图的定义和特性？2.图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？3.图的主要遍历思路是哪些？4.举出图的应用范例？【参考代码】（一）基础篇//将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历〃程序构思：//用户键盘输入结点与各条边，再将边转成邻接链表。//然后对采用邻接表表示的图进行深度优先遍历。#include〈stdio.h>^include^definevertexnum100typcdefstructnode{intvertex;structnode*next;}Graph;Gr

3、aphhcad[vertoxnum];intVisited[vertexnum];//定义最大可输入的结点个数//定义图形的顶点结构〃图中的顶点信息为数字//邻接表的表头结点//遍历记录voidCreate_l_Graph(intVertexl,intVertex2,intno){//以邻接链表建立图形Graph^search?;〃结点声明Graph*New;//新结点声明New=(Graph*)malloc(sizeof(structnode));if(New!=NULL){New->vertex=Vertex2;New->ncxt=NULL;searchP

4、=&(head[Vertexl]);while(searchP-〉next!=NULL)searchP二searchP->next;searchP->next二New;if(no=0){New=(Graph*)malloc(sizeof(structnode));New->vertex=Vertexl;New->next二NULL;searchP=&(head[Vertex2]);while(searchP~>next!=NULL)searchP二searchP->next;searchP-〉next=New;}}}voidshowmenu（）printf("

5、printf("t1、printf(〃t2、printf(〃t3、printf("t4、}〃显示菜单欢迎使用图的操作演示软件〃）;创建图的邻接表〃）；图的输出『）；图的深度优先遍历『）；退出程序〃）；voidprint1graph(Graph*head){//输出邻接链表的数据Graph*searchP;searchP=hcad->next;while(searchP!=NULL)voidDES(intvertex)//深度优先遍历Graph*SearchP;//结点声明〃标记某个结点己遍历过printf(//[%d]==>//,ver

6、tex);SearchP二head[vertex]・next;while(SearchP!二NULL){//判断结点未被遍历过//递归调用深度优先遍历函数//下一个邻接点if()SearchP=SearchP->next;}}voidmain(){〃图中一条边的起始顶点〃图中一条边的终止顶点//定义图中最大的顶点数//定义图中最大的边数intsource;intdestination;inti,j;intvermax;intedgemax;intchoice;intno;wh订e⑴{shomnenu();printf(/z请输入你的选择：")；scanf&ch

7、oice);fflush(stdin);//清除键盘缓冲区switch(choice){casel:printf(z/请输入图的类别(有向图T,无向图-0);scanf("%d",&no);printfC请输入图中的总顶点数和边数:〃)；scanf("%d%cT,&vennax,&edgemax);for(i=l;i

8、7条边的终点:〃，i);seanf("