《数据结构》上机实验报告—有向图的邻接表的建立及遍历.doc
文本预览下载声明
福州大学数计学院
《数据结构》上机实验报告
专业和班级:信息计算科学与应用数学6班
学号 姓名 成绩 实验名称 图的有关操作 实验内容 有向图的邻接表的建立及遍历 实
验
目
的
和
要
求 【实验目的】
1.掌握图的存储思想及其存储实现。
2.掌握图的深度、广度优先遍历算法思想及其程序实现。
3.掌握图的常见应用算法的思想及其程序实现。
问
题
描
述
和
主
要
步
骤
【实验内容】
1. 键盘输入数据,建立一个有向图的邻接表。
2.在有向图的邻接表的基础上计算各顶点的度。
3.采用邻接表存储实现有向图的深度优先遍历。
4.采用邻接表存储实现有向图的广度优先遍历。
【主要程序】
#includestdio.h
#includestdlib.h
#includeconio.h
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define OVERFLOW 0
int visited[MAX_VERTEX_NUM];
typedef struct ArcNode //表结点
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
char *info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode //头结点
{
char data; //顶点信息
ArcNode *firstarc; //第一个表结点的地址,指向第一条依附顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM]; //头结点,头结点的顺序表AdjList[]类型
typedef struct //图结构
{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数与弧数
}ALGraph;
typedef struct QNode //用于BFS遍历的附设链队列结点结构
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct //链队列
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int InitQueue(LinkQueue Q) //初始化链队
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front-next=NULL;
return OK;
}
int EnQueue(LinkQueue Q,int e) //元素e入队
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p-next=NULL;
p-data=e;
Q.rear-next=p;
Q.rear=p;
return OK;
}
int DeQueue(LinkQueue Q,int e)//队首元素出队,由e返回其值
{
QueuePtr p;
if(Q.front==Q.rear) exit(OVERFLOW);
p=Q.front-next;
e=p-data;
Q.front-next=p-next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}
int EmptyQueue(LinkQueue Q) //判断队列Q是否为空
{
if(Q.front==Q.rear)
return 1;
return 0;
}
int LocateVex(ALGraph G,char v) //查找值为v的顶点在顶点向量G.vexs[]中的位置
{
int i;
for(i=0;iG.vexnum;i++)
if(v==G.vertices[i].data)
return i;
return -1;
}
int FirstAdjVex(ALGraph G,char v)//返回v的第一个邻接顶点的序号
{
int i;
ArcNode *p;
i=LocateVex(G,v); //i为顶点v在图G中的序号
if(i==-1)
return -1;
p=G.vertices[i].firstarc;
if(p)
return p-adjvex;
else
return -1;
显示全部