厦门理工学院数据结构实验7图的定义和操作.doc

《数据结构》实验报告

实验序号：7实验项目名称：图的定义和操作

学号

姓名

专业、班

实验地点

指导教师

实验时间

一、实验目的及要求

掌握图的基本存储方法；

掌握图的两种有哪些信誉好的足球投注网站路径的遍历算法；

掌握拓扑排序算法；(选做)

二、实验设备（环境）及要求

微型计算机；

windows操作系统；

MicrosoftVisualStudio6.0集成开发环境。

三、实验内容与步骤

编程实现图的遍历图算法（按图的深度优先有哪些信誉好的足球投注网站算法或广度优先有哪些信誉好的足球投注网站算法遍历）；

应用拓朴排序算法编制程序解决问题。（附加题）

四、分析与讨论

对上机实践结果进行分析，上机的心得体会。

五、教师评语

签名：

日期：

成绩

附源程序清单：

#includestdio.h

#includestdlib.h

#includeconio.h

#defineMAX_VEXTEX_NUM9/*图中顶点数*/

#defineARC_NUM12/*图中弧数*/

#defineMAX_QUEUEMEM(MAX_VEXTEX_NUM+1)

/*定义描述图的顶点之间连接信息的数组*/

intGraphEdge[ARC_NUM*2][2]={{0,1},{1,0},{1,2},{2,1},{2,3},{3,2},{3,4},{4,3},{4,5},{5,4},{5,0},{0,5},{0,6},{6,0},{6,8},{8,6},{6,7},{7,6},{7,8},{8,7},{7,3},{3,7},{8,4},{4,8}};

/*定义数组visited用来标示一个顶点是否被访问过*/

intvisited[MAX_VEXTEX_NUM]={0,0,0,0,0,0,0,0,0};

/*定义表结点，即每条弧对应的结点*/

typedefstructArcNode{

intadjvex;/*该弧所指向的顶点的位置*/

structArcNode*nextarc;/*指向下一条弧的指针*/

}ArcNode;

/*定义头结点*/

typedefstructVNode{

intdata;/*顶点信息*/

structArcNode*firstarc;/*指向第一条依附该顶点的弧的指针*/

}VNode,AdjList[MAX_VEXTEX_NUM];

/*定义图的结构*/

typedefstruct{

VNodevertices[MAX_VEXTEX_NUM];/*定义表头数组*/

intvexnum;/*定义图中顶点数*/

intarcnum;/*定义图中弧数*/

}ALGraph;

voidCreateGraph(ALGraph*alGraph)

{

inti,j;

ArcNode*newnode;

ArcNode*vexNode;

alGraph-vexnum=MAX_VEXTEX_NUM;

alGraph-arcnum=ARC_NUM;

/*初始化表头*/

for(i=0;iMAX_VEXTEX_NUM;i++)

{

alGraph-vertices[i].data=i;

alGraph-vertices[i].firstarc=NULL;

}

for(j=0;j2*ARC_NUM;j++)

{

i=GraphEdge[j][0];

if(alGraph-vertices[i].firstarc==NULL)

{

newnode=(ArcNode*)malloc(sizeof(ArcNode));

newnode-adjvex=GraphEdge[j][1];

newnode-nextarc=NULL;

alGraph-vertices[i].firstarc=newnode;

}

else

{

vexNode=alGraph-vertices[i].firstarc;

while(vexNode-nextarc!=NULL)

{

vexNode=vexNode-nextarc;

}

newnode=(ArcNode*)malloc(sizeof(ArcNode));

newnode-adjvex=GraphEdge[j][1];

newnode-nextarc=NULL;

vexNode-nextarc=newnode;

}

}

}

voidOutputGraph(