邻接矩阵、邻接表等存储结构的相关算法.doc

内蒙古科技大学信息工程学院计算机系
《数据结构与算法》实验报告
姓名

学号
1367159107

班级

实验日期
第 14 周（星期二）12 月2 日第 7、8节
项目号、实验名称
5、图的存储结构算法
实
验
要
求
（任课
教
师
提
供）
1、 该实验要求掌握邻接矩阵、邻接表等存储结构的相关算法；
2、验证性实验要求在实验前认真研读相关教材，作好充分的预习准备工作，写出实验预习报告；
3、学生必须在规定时间内独立完成，对实验过程中出现的问题，要求尽量做到独立思考，独立解决；
4、每次实验的结果必须经过教师认可后，实验方可结束；
5、要求学生必须认真对待每一个实验，不得缺席、迟到、早退；
6、要求实验中认真做好实验记录，实验后认真完成实验报告；

实
验
内
容
（由学
生
填
写）

邻接矩阵的存储法主程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

#define MAXQSIZE 10 //最大队列长度
#define FALSE 0
#define TRUE 1

typedef int VRType;
typedef int InfoType;
typedef char VertexType;
typedef int Status;
typedef int QElemType;

typedef struct
{
QElemType *base;
int front;
int rear;
} SqQueue;

typedef struct ArcCell
{
VRType adj;
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
}MGraph;

bool visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(int v);
int w;

void CreateGraph(MGraph &G); //邻接矩阵创建图

void BFSTraverse(MGraph G, Status (*Visit)(int v));//邻接矩阵的广度遍历
void DFSTraverse(MGraph G, Status (*Visit)(int v));//邻接矩阵的深度遍历
void DFS(MGraph G, int v);
Status printGraph(int v);
int FirstAdjVex(MGraph G, int v);//返回图G中顶点v的第一个邻接点。若不存在邻接点，则返回0。
int NextAdjVex(MGraph G, int v, int w);//返回图G中顶点v的邻接点中处于w之后的那个邻接点，若不存在这样的邻接点，则返回0。

Status InitQueue(SqQueue &);
Status EnQueue(SqQueue &, QElemType);
Status DeQueue(SqQueue &, QElemType &);
Status QueueEmpty(SqQueue);

void main( void )
{
int i, j;
MGraph G;
{//创建图的邻接矩阵
cout<<"开始创建图的邻接矩阵......"<<endl;
CreateGraph(G);
}

{//邻接矩阵的广度遍历代码块
cout<<"邻接矩阵的广度遍历......"<<endl;
for(i = 0; i < G.vexnum; i++)
{
for(j = 0; j < G.vexnum; j++)
{
cout<<G.arcs[i][j].adj;
cout<<"\t";
}
cout<<endl;
}
cout<<"\n遍历结果为:"<<endl;
BFSTraverse(G, printGraph);

}

cout<<endl;
{//邻接矩阵的深度遍历 代码块
cout<<"邻接矩阵的深度遍历......"<<endl;
for(i = 0; i < G.vexnum; i++)
{
for(j = 0; j < G.vexnum; j++)
{
cout<<G.arcs[i][j].adj;
cout<<"\t";
}
cout<<"\n";
}
cout<<"\n遍历结果为:"<<endl;
DFSTraverse(G, printGraph);
}
}
void CreateGraph(MGraph &G)
{
int weigh;
int i, j = 0, k = 0;
char hand, tide;

cout<<"input the number for vexnum and arcnum:";
cin>>G.vexnum>>G.arcnum;

for(i = 0; i < G.vexnum; i++)
{
for(j = 0; j < G.vexnum; j++)
G.arcs[i][j].adj = 88;
}

cout<<endl;
cout<<"input "<<G.vexnum<<" char for vexs(use -enter- to change):";
for(i=0; i < G.vexnum; i++)
cin>>G.vexs[i];
cout<<endl;
cout<<"input "<<G.arcnum<<" arc(char -enter- char -enter- weigh):"<<endl;
j = 0;
k = 0;
for(i=0; i < G.arcnum; i++)
{
cout<<i<<":";
cin>>hand;
cin>>tide;
cin>>weigh;
while (hand != G.vexs[j])
j++;
while (tide != G.vexs[k])
k++;
G.arcs[j][k].adj = weigh;
G.arcs[k][j].adj = weigh;
j = 0;
k = 0;
cout<<endl;
}
}

void BFSTraverse(MGraph G, Status (*Visit)(int v))
{

SqQueue Q;
QElemType u;

InitQueue(Q);

for(int v=0; v < G.vexnum;++v)
visited[v]=FALSE;
for(v=0; v<G.vexnum;++v)
if(!visited[v])
{
visited[v]=TRUE;
Visit(v);
EnQueue(Q, v);
while(QueueEmpty(Q))
{
DeQueue(Q, u);
for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
if(! visited[w])
{
visited[w]=TRUE;
Visit(w);
EnQueue(Q, w);
}
}
}
}

void DFSTraverse(MGraph G, Status (*Visit)(int v))
{
int j;
VisitFunc = Visit;
for( j=0; j<G.vexnum; j++)
visited[j] = 0;
for(j=0; j<G.vexnum; j++)
if(!visited[j])
DFS(G, j);
}

void DFS(MGraph G, int v)
{

visited[v]=1;
VisitFunc(v);
for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))
if(!visited[w])
DFS(G, w);
}

int FirstAdjVex(MGraph G, int v)
{
int j;
for(j = 0; j < G.vexnum; j++)
{
if(G.arcs[v][j].adj != 88 && visited[j] != 1)
return j;
}
return 0;
}

int NextAdjVex(MGraph G, int v, int w)
{
int j;
for(j = 0; j < G.vexnum; j++)
{
if(G.arcs[v][j].adj != 88 && j != w && visited[j] != 1)
return j;
}
return 0;
}

Status printGraph(int v)
{
printf("%c\t", v + 'a');
return 1;
}

Status InitQueue(SqQueue & queue)
{
queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType));

if (!queue.base)
return FALSE;
queue.front = queue.rear = 0;

return TRUE;
}

///////////////////////////////////////////////////////////////////////
//
// 函数名 : EnQueue
// 功能描述 : 插入元素到队列
// 参数 : SqQueue &queue
// 参数 : QElemType element
// 返回值 : Status
//
///////////////////////////////////////////////////////////////////////
Status EnQueue(SqQueue &queue, QElemType element)
{
//先判断是不是没满的队列
if ((queue.rear + 1) % MAXQSIZE == queue.front)
return FALSE;
queue.base[queue.rear] = element;

queue.rear = (queue.rear + 1) % MAXQSIZE;

return TRUE;
}

///////////////////////////////////////////////////////////////////////
//
// 函数名 : DeQueue
// 功能描述 : 删除队列的头结点
// 参数 : SqQueue &queue
// 参数 : QElemType &element
// 返回值 : Status
//
///////////////////////////////////////////////////////////////////////
Status DeQueue(SqQueue &queue, QElemType &element)
{
//判断队列是不是空的
if (queue.front == queue.rear)
return FALSE;
element = queue.base[queue.front];
queue.front = (queue.front + 1) % MAXQSIZE;

return TRUE;
}

Status QueueEmpty(SqQueue queue)
{
if (queue.front == queue.rear)
return FALSE;
else
return TRUE;

}

运行结果如下:

评
语
（由教
师
填
写）

说明：
1、每个实验项目填写一份实验报告，电子版命名方式为：学号姓名项目号.doc。例如：1167111182张三3.doc表示张三做的第3个项目的实验报告。
2、实验报告电子版应该在实验后一周内由学习委员收齐后存放在一个文件夹下，文件夹命名方式为：软件12-1班3，表示软件12-1班第3个项目的实验报告，压缩。第一时间发送给任课教师。必须以班级为单位上交。
3、任课教师要求在收到实验报告的一周内进行批阅，并给出成绩及评语。
4、实验报告电子版由任课教师保存。
5、表格宽度可以根据实际情况伸缩。
13