数据结构课程设计实践报告.docx

数据结构实验报告
实验名称:
提交文档学生姓名：
提交文档学生学号：
同组成员名单：
指导教师姓名：
结构图
一、实验目的和要求
1、设计目的
掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通alloc(sizeof( ALGraph)); pnntf("图G的邻接矩阵转换成邻接表：5”); MatToList l();
Disp Adj 1(G);
pnntf("图G的邻接表转换成邻接矩阵：5”);
ListToMat 1 (Qg 1);
DispMat l(gl);
return 0;
〃不带权图的算法
void MatToList(MGraph g. ALGraph *&G)
{
int i,j；
AicNode *p;
G = (ALGraph*)malloc(sizeof( ALGraph));
for(i=0; i<; i++)
for(j = J；j>=O;j—)
if([i][j]!=O)
{
p = (AicNode*)malloc(sizeof(ArcNode)); p->adjvex = j;
p->nextarc = G->adjlist[i] .fiistarc;
G->adjlist[i] .firstarc = p;
}
G->n = ;
G->e = ;
}
void ListToMat(ALGiaph *G;MGraph &g)
{
intij;
AicNode *p;
for(i=0; i<G->n; i++)
for(j=0;j<G->n;j++)
[i][j] = 0;
for(i=0; i<G->n; i++)
{
p = G->adj list[i]. firstarc;
wlule(p!=NULL)
{
[i][p ->adjvex] = 1;
p = p->nextarc;
}
}
= G->n;
= G->e;
} void DispMat(MGraph g)
mt i,j;
void DispAdj l(ALGiaph *G)
mt i;
AicNode *p;
foi(i=0; i<G->n; i++)
{
p = G->adj list [i]. fiistarc;
while(p!=NULL)
{
printf(n%3d(%d)'\p->adjvex,p->mfb); p = p->nextarc;
}
}
}
二、编译并链接程序;
三、运£程序選如下图:
0
5
OO
7
oo
oo
co
0
4
co
co
co
8
OD
0
8
8
9
co
CO
5
0
CO
6
co
CO
co
5
0
co
3
CO
oo
oo
1
0
图G的邻接矩阵转换咸邻接表;
0:
1<5>
3<7>
1:
2C4>
2：
0C8>
5<9>
3：
215〉
5<6>
4：
30
5：
0<3>
4<1>
图G的邻接表转换成邻接矩阵,
0
5
co
7
co
CO
OD
8
4
8
8
8
8
CO
0
CO
CO
9
CO
co
5
0
CO
6
co
co
oo
5
0
OO
CO
co
co
1
实验©
源程序
一、输入如下所示程序;
extern void MatToList 1 (MGraph. ALGraph *&);
extern void DispAdj 1 (ALGraph *G);
extern void DFS(ALGraph *Gjnt v);
extern void DFS1 (ALGraph *Giiit v);
extern void DFS2(ALGraph *Giiit v);
extern void BFS(ALGraph *G；int v);
mt niainQ
mt 1J;
MGraph g;
ALGraph *G;
mtA[MAXV][6] = {{0,5JNF；7JNEINF}，{INFO4JNF,INhINF},
{& INE0,INEINE9},{INEINE5,0,INF,6}, {INEINRINF； 5 QINF }, { 3 ,INF,IN