实验5 图的操作
一、实验目的
1. 熟悉图的存储结构;
2.熟悉图的创建操作;
3.熟悉图的遍历操作。
三、实验要求
1..每个同学必须独立完成;
2.程序中的开头部分必须对本程序的总体功能进行注释;程序中每个函数段必须要有注释说明该函数的功能或作用;
3.上机进行调试和修改并填写实验报告;
4.实验报告中的源程序必须调试通过。
5.在体会中描述如下内容:
(1)对算法与程序的区别上的体会。
(2)本次实验过程的体会,是否自己独立完成?最大的困难是什么?自己准备如何解决这个困难?
6.提交实验报告(报告中包含关键源代码)
实验内容
1、用邻接表结构实现如图所示无向图的存储;
2、在第1步骤基础上实现该无向图的深度优先遍历;输出遍历序列;
3、在第1步骤基础上实现该无向图的广度优先遍历;输出遍历序列;
参考代码:
#include "stdio.h"
#include "conio.h"
#define MaxVertexNum 100
#define MAXSIZE 100
typedef struct
{
int data[MAXSIZE];
int front;
int rear;
}SeqQueue;
typedef char VertexType;
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxVertexNum];
typedef char elemtype;
/*边结点*/
typedef struct node
{
int adjvex;/*邻接点域*/
struct node *nextedge;/*链域*/
}EdgeNode;
/*顶点表结点*/
typedef struct vnode
{
VertexType vertex; /*顶点域*/
EdgeNode *firstedge; /*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*/
/*
对于简单的应用,无须定义此类型,可直接使用AdjList类型
*/
typedef struct
{
AdjList adjlist;/*邻接表*/
int n,e; /*当前结点数和边数*/
int kind; /*图的种类标志*/
}ALGraph;
/*建立无向图的邻接表*/
void CreateALGraPh(ALGraph *G1)
{
int i,j,k;
EdgeNode *s;
/*读入顶点数和边数*/
printf("please input vertices: ");
scanf("%d",&G1->n);getchar();
printf("please input Vertex edge number: ");
scanf("%d",&G1->e);getchar();
/*建立顶点表*/
for(i=0;i<G1->n;i++)
{
printf("please input the %dth Vertex\n",i+1);
scanf("%c",&G1->adjlist[i].vertex);getchar(); /*读入顶点信息*/
G1->adjlist[i].firstedge=NULL; /*边表置为空表*/
}
printf("Please enter no to chart the relationship between vertices.the style is vi,vj\n\n ");
/*建立边表*/
for(k=0;k<G1->e;k++)
{
printf("the %dth is: ",k+1);
scanf("%d,%d",&i,&j); /*读入边(vi,vj)的顶点对序号*/
s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/
s->adjvex=j;/*邻接点序号为j*/
s->nextedge=G1->adjlist[i].firstedge;
G1->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i;/*邻接点序号为i*/
s->nextedge=G1->adjlist[j].firstedge;
G1->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/
}
}
/*邻接表表示的深度优先遍历*/
void DFS(ALGraph *G1,int i)
{
EdgeNode *p;
printf("%c ",G1->adjlist[i].vertex);/*访问顶点vi*/
visited[i]=TRUE;/*标记vi已访问*/
p=G1->adjlist[i].firstedge; /*取vi边表的头指针*/
while(p)
{
if(!visited[p->adjvex]) /*若vi尚未被访问,则以vj为出发点向纵深搜索*/
{
DFS(G1,p->adjvex);
}
p=p->nextedge;/*找vi的下一邻接点*/
}
}
/*邻接表表示的广度优先遍历*/
void BFS(ALGraph *G,int k)
{
int i;
SeqQueue *Q;
EdgeNode *p;
/*初始队列*/
Q=(SeqQueue *)malloc(sizeof(SeqQueue));
Q->front=Q->rear=0;
printf("%c ",G->adjlist[k].vertex);
visited[k]=TRUE;
/*入队*/
Q->data[Q->rear]=k;
Q->rear=(Q->rear+1)%MAXSIZE;
Q->rear++;
while(Q->rear)
{
i=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
Q->rear--;
p=G->adjlist[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
printf("%c ",G->adjlist[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
Q->data[Q->rear]=p->adjvex;
Q->rear=(Q->rear+1)%MAXSIZE;
Q->rear++;
}
p=p->nextedge;
}
}
}
executeBFS(ALGraph *G)
{
int i;
for(i=0;i<G->n;i++)/*将图G的所有顶点设置未访问过标记 */
visited[i]=FALSE;
for(i=0;i<G->n;i++)/*对图G调用bfs函数进行广度优先搜索*/
if(!visited[i])
BFS(G,i);
}
main()
{
ALGraph *G1;
int i;
CreateALGraPh(&G1);
printf("DFS\n");
DFS(&G1,0);
printf("\nBFS\n");
executeBFS(&G1);
getch();
}
分享到:
相关推荐
实验5的主要目标是实现银行家算法,以便在多进程环境中确保系统的安全性。安全性意味着系统能够保证每个进程在有限的时间内完成,即使所有进程同时请求资源。以下是实现银行家算法的关键步骤: 1. **初始化**: 首先...
5. 实验结果分析:对实验数据进行分析,解释观察到的现象,并讨论可能出现的问题和解决方案。这有助于深化对操作系统原理的理解。 6. 实验总结:回顾实验过程,总结所学知识,提出改进或扩展实验的建议。这是提升...
在这个实验报告中,我们关注的是如何利用PV操作来解决经典的生产者-消费者问题,以及如何通过Java代码实现这一过程。 实验的目的不仅在于理解进程与程序的区别,深入认识并发执行的本质,还在于通过实际编程验证...
【HIT操作系统实验5】是针对哈尔滨工业大学计算机科学与技术专业操作系统课程的一项实践任务,旨在深化学生对操作系统基本原理的理解,提升其动手能力和问题解决能力。在这个实验中,学生将有机会接触并操作真实或者...
山东大学的操作系统实验旨在让学生深入理解操作系统的基本概念和原理,通过实践来提升理论知识的应用能力。实验内容包括进程控制、线程与管道通信、Shell编程以及进程同步和互斥等关键领域。 实验一:进程控制 在这...
实验5简单shell编程引入了bash shell,它是Linux默认的命令解释器。编写shell脚本可以自动化日常任务,提高工作效率。学习条件语句(if-else)、循环(for、while)、函数和变量的使用,是shell编程的核心。 实验7...
5. **实验五:设备管理** - 目标:理解设备管理的重要性及其实现方式。 - 内容: - 学习I/O控制方式、缓冲技术等。 - 设计简单的设备管理程序。 6. **实验六:WINDOWS 2000的文件管理** - 目标:掌握Windows ...
在"操作系统所有实验,希冀平台7个实验"中,我们可以深入理解操作系统的原理和功能,通过实践来掌握相关知识。以下是这7个实验可能涉及的一些关键知识点: 1. **进程管理**:在操作系统中,进程是程序的执行实例。...
《操作系统》实验5域排序与记录连接 《操作系统》实验6记录连接与剪切 《操作系统》实验7记录粘贴与分割 《操作系统》实验8目录属性操作 《操作系统》实验9批处理操作接口1:赋值与取值 《操作系统》实验10批处理...
操作系统位示图实验报告主要探讨了如何有效地管理磁盘存储空间,这是操作系统设计中的关键问题。位示图是一种常见的磁盘空间管理技术,它通过一个位数组来表示磁盘上的所有块,其中位的值“1”表示块已被占用,“0”...
这篇实验报告将深入探讨2012年中央广播电大的操作系统课程所涉及的关键概念和实验实践。 首先,我们要理解操作系统的五大基本功能:进程管理、内存管理、文件管理、输入/输出(I/O)管理和设备管理。在2012年的实验...
在哈工大的操作系统课程中,实验五主要关注的是“地址映射与共享”这一核心概念。这个实验旨在帮助学生深入理解操作系统如何管理内存,特别是如何实现进程间的资源共享,以及地址空间是如何映射到物理内存的。以下是...
华北电力大学操作系统实验报告 本实验报告的主要内容是关于计算机操作系统的实验报告,涵盖了操作系统集成实验环境OS Lab的基本使用方法、编译、调试EOS操作系统内核以及EOS应用程序等知识点。 本实验报告的主要...
实验5HFISO14443A操作主要涵盖了高频RFID技术的基础知识,特别是ISO14443A协议的应用。这个实验旨在让学生理解和实践ISO14443A卡的操作,包括读写器参数设置、数据块操作、密钥管理以及halt操作。 1. **读写器参数...
中北大学的操作系统实验报告旨在让学生深入理解操作系统的工作原理,并通过实践操作提升其编程和分析能力。以下是根据实验报告可能涉及的一些关键知识点的详细说明: 1. **进程管理**:操作系统中,进程是程序的...
在本实验中,我们将深入探讨上海交通大学头歌实践教学平台上的Chcore操作系统,这是一个专为教育设计的操作系统模拟环境,让学生能够亲手实践操作系统的核心概念。实验分为两部分:内存管理和系统调用与缺页异常。 ...
5. **文件的创建与打开**:操作系统提供API(应用程序接口)供程序创建新文件,通过指定文件名、路径和打开模式(只读、只写、读写等)。打开文件后,就可以进行读写操作。 6. **文件的读写操作**:通过读写函数,...
这份"操作系统的实验报告及程序5个"的压缩包文件包含了五个关键领域的实践学习内容,分别是存储管理、进程调度、文件管理、主存空间分配与回收以及作业调度。接下来,我们将深入探讨这些知识点。 1. 存储管理: ...
一、实验目的 1、掌握图的存储方式 2、 掌握图的相关操作 二、实验内容 1、实现拓扑排序算法。
【实验名称】Linux操作系统实验一:Linux操作、使用与编程 【实验目标】 1. 熟悉Linux系统的安装,如Red Hat发行版。 2. 学习Linux的启动流程,理解其初始化阶段。 3. 了解Linux文件系统的层次结构,理解其组织方式...