图的邻接矩阵存储结构建立顾云康E01114300文档格式.docx
- 文档编号:7238364
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:19
- 大小:90.12KB
图的邻接矩阵存储结构建立顾云康E01114300文档格式.docx
《图的邻接矩阵存储结构建立顾云康E01114300文档格式.docx》由会员分享,可在线阅读,更多相关《图的邻接矩阵存储结构建立顾云康E01114300文档格式.docx(19页珍藏版)》请在冰点文库上搜索。
2需求分析
(1)设置图的邻接矩阵存储结果
(2)编写图的基本操作函数,包括图的建立,邻接矩阵的输出
(3)编写深度遍历、广度遍历的递归与非递归算法
(4)编写主函数,控制程序运行
3课程设计报告内容
3.1概要设计
(1)图的邻接矩阵存储结构:
typedefenum
{
DG,DN,UDG,UDN}GraphKind;
//有向图,有向网,无向图,无向网
typedefstructArcCell
{//邻接矩阵表示法的各个数据结构
VrTypeadj;
//顶点关系类型。
对无权图,用或表示相邻否;
对带权图,则为权值类型。
InfoType*info;
//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
VertexTypevertex[MAX_VERTEX_NUM];
//顶点向量
AdjMatrixarcs;
//邻接矩阵
intvexnum,arcnum;
//图的当前顶点数和弧(边)数
GraphKindkind;
//图的种类标志
}MGraph;
(2)主函数流程:
首先选择输入图的种类,再输入图的顶点、边的信息,最后给出四种算法的遍历结果。
3.2详细设计
(1)主函数:
voidmain()
{
inti;
MGraphG;
printf("
请输入要构造的图的类型(无向图:
1,无向网:
2):
\n"
);
scanf("
%d"
&
G.kind);
switch(G.kind)
case1:
CreateUDG(G);
break;
case2:
CreateUDN(G);
default:
break;
}
DepthFirstSearch1(G);
BreadthFirstSearch1(G);
DFS(G);
BFS(G);
Display(G);
scanf("
i);
}
(2)构造图的邻接矩阵函数:
voidCreateUDG(MGraph&
G)
{//采用数组(邻接矩阵)表示法,构造无向图
inti,j,k,IncInfo;
//i,j,k为计数器,IncInfo为标志符
charch;
//用于吃掉多余的字符
VertexTypev1,v2;
//用于放置输入的弧的两个顶点
请输入无向图G的顶点数,边数,弧是否含相关信息(是1,否0):
\n"
%d,%d,%d"
G.vexnum,&
G.arcnum,&
IncInfo);
ch=getchar();
//用于吃掉回车
请输入%d个顶点的值(1个字符,空格隔开):
G.vexnum);
for(i=0;
i<
G.vexnum;
++i)//构造顶点向量
scanf("
%c"
G.vertex[i]);
ch=getchar();
请输入%d条边的顶点顶点(以空格作为间隔):
G.arcnum);
++i)//初始化邻接矩阵
for(j=0;
j<
++j)
{
G.arcs[i][j].adj=0;
G.arcs[i][j].info=NULL;
for(k=0;
k<
G.arcnum;
++k)
%c%c"
v1,&
v2);
//ch吃掉回车符
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
if(IncInfo)scanf("
G.arcs[i][j].info);
G.arcs[i][j].adj=G.arcs[j][i].adj=1;
//置<
v1,v2>
的对称弧<
v2,v1>
(3)递归深度遍历函数:
voidDFSTraverse(MGraph&
G,inti)
%c"
G.vertex[i]);
Visit[i]=true;
for(intj=0;
j++)
if(G.arcs[i][j].adj==1&
&
!
Visit[j])
{
DFSTraverse(G,j);
}
voidDFS(MGraph&
递归深度优先遍历开始:
i++)Visit[i]=false;
i++)
if(!
Visit[i])
DFSTraverse(G,i);
(4)非递归深度遍历函数、非递归广度遍历函数、递归广度遍历函数详见源程序。
3.3调试分析
4总结
在完成本次课程设计中,我发现很多理论性知识在实际使用时与单纯的理论还是有所差别的,比如图的邻接矩阵存储、广度优先遍历、深度优先遍历等。
我认识到了图的模型在解决实际问题中的作用,使我对数据结构的学习有了更进一步的理解。
今后我会更加注重培养自己的实践动手能力。
5程序清单
见附录
6参考文献
[1]严蔚敏,吴伟民编著.数据结构(C语言版)--北京:
清华大学出版社,2007.
[2]严蔚敏,吴伟民米宁编著.数据结构题集(C语言版)--北京:
7程序运行结果
附录
程序清单:
#include"
stdafx.h"
#include<
stdio.h>
malloc.h>
conio.h>
stdlib.h>
string.h>
#defineERROR0
#defineOK1
#defineMAX_VERTEX_NUM20//定义最大值
#defineINFINITY32768//定义极大值
#defineMAX_INFO20
boolVisit[MAX_INFO];
typedefintVrType;
//定义新的类型
typedefintInfoType;
typedefcharVertexType;
{DG,DN,UDG,UDN}GraphKind;
typedefstruct
{//设置栈
intelem1[MAX_VERTEX_NUM];
inttop;
}SeqStack;
intLocateVertex(MGraphG,VertexTypev);
G);
voidCreateUDN(MGraph&
voidDepthFirstSearch1(MGraphG);
voidBreadthFirstSearch1(MGraphG);
intCreateGraph(MGraph&
voidDisplay(MGraphG);
intLocateVertex(MGraphG,VertexTypev)
{//用于返回输弧端点所表示的数值
intj=0,k;
for(k=0;
if(G.vertex[k]==v)
{j=k;
return(j);
}//CreateUDG
{//采用数组(邻接矩阵)表示法,构造无向网
inti,j,k,w,IncInfo;
//i,j,k为计数器,w用于放置权值,IncInfo为标志符
请输入无向图G的顶点数,边数,弧是否含相关信息(是:
,否:
):
\n"
//{adj,info}
请输入该边的权值:
"
w);
G.arcs[i][j].adj=w;
G.arcs[i][j]=G.arcs[j][i];
}//CreateUDN
voidDepthFirstSearch1(MGraphG)
{//无向图、无向网深度优先遍历
inti,j,k,visited[20],t=1,a=1;
//i,j,k为计数器,visited[20]为标志符用于表示是否已经访问过
SeqStackp;
++i)//初始化标志符
visited[i]=0;
visited[0]=1;
//规定以第一个字符开始遍历
非递归深度优先遍历开始:
k=0;
i=0;
G.vertex[0]);
while(i<
G.vexnum)
{//不断以行循环在遇到符合条件时打印,每打印出一个就让t加,把合适的值用栈来表示,把指针指向新的项
if(G.arcs[i][j].adj!
=0&
G.arcs[i][j].adj!
=INFINITY&
visited[j]==0)
{
printf("
G.vertex[j]);
visited[j]=1;
p.elem1[k]=i;
p.top=k;
k++;
i++;
a++;
t++;
if(j==G.vexnum)
{//当在某一行无法找到合适值时,输出栈内的值,返回上一行重新开始循环
i=p.elem1[p.top];
p.top--;
k--;
if(t==G.vexnum)break;
//当全部的定点都打印出来了就退出循环
voidBreadthFirstSearch1(MGraphG)
{//无向图、无向网广度优先遍历
inti,j,k,visited[20],t=1;
//i,j为计数器,visited[20]为标志符用于表示是否已经访问过
非递归广度优先遍历开始:
for(j=0;
++j)//不断以行循环在遇到符合条件时打印,每打印出一个就让t加,把指针指向新的项
if(G.arcs[i][j].adj!
t++;
i++;
//换行,重新开始循环
voidBFS(MGraphG)//递归广度优先遍历
\n递归广度优先遍历开始:
//递归深度遍历
voidDisplay(MGraphG)
{//输出图的邻接矩阵
inti,j;
\n该图的邻接矩阵为:
++i)
{for(j=0;
printf("
%d"
G.arcs[i][j].adj);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图的邻接矩阵存储结构建立 顾云康E01114300 邻接矩阵 存储 结构 建立 顾云康 E01114300