数据结构实验报告实验3.doc

文档介绍：本科实验报告
课程名称: 数据结构
实验项目: 图结构
实验地点: 迎西校区逸夫楼302
专业班级:软件1109 学号: 2011004872
学生姓名: 栗永春
指导教师: 牛之贤

年月日
图结构
一、实验目的和要求
目的与要求
二、实验内容和原理
三、主要仪器设备
四、操作方法与实验步骤
列出调试通过的源程序。<br****题2:
/****************************************************************
* 采用邻接表存储结构,编写一个求无向图的连通分量个数的算法。*
* xiaojinglingfen *
****************************************************************/
#include &lt;&gt;
#include &lt;&gt;
#include &lt;&gt;
int n; //定义全局变量,表示所构造的图中的总的顶点个数
//用于构造结点之间联系关系的弧结点
typedef struct ode
{
int position; //用来存放节点的标号
struct ode *next; //用来存放结点的下一个弧的信息
}ode, *ode_;
//定义用来构造元素的结点
typedef struct vNode
{
int mark; //在程序中用来标识是否被访问过
ode *first;//存储连接到该结点的第一个弧信息的地址
}VNode, *VNode_;
//函数声明部分
VNode_ Structure();//构造一个图
void DFS(VNode_ Chart, int t);//递归方法实现链表深度探索
void Initialize(VNode_ Chart);//初始化所构造的顶点信息
void End(VNode_ Chart);//收尾工作,释放由malloc申请的空间
void main()
{
int i=0;
int count=0;
VNode_ Chart = Structure();//创建图
while(Chart[i].mark == 0)
{
DFS(Chart, i);
++count;
i = 0;
while((Chart[i].mark != 0)&amp;&amp;i&lt;5)
{
++i;
}
}
printf(&quot;该图的连通分量的个数是%d.&quot;, count);
End(Chart);
}
//构造一个图的过程
VNode_ Structure()
{
VNode_ Chart;
int i, j, k;
ode_ p, q;
printf(&quot;下面进行构造图的过程,请按照提示输入信息完成构造图的过程!\n&quot;);
printf(&quot;\n请输入要构造的图的顶点总数.\n&quot;);

scanf(&quot;%d&quot;, &amp;n);//将用户输入的总的顶点数保存
//对输入数据进行判断
while(n&lt;1)
{
printf(&quot;录入的数据有误!请重新输入。\n&quot;);
scanf(&quot;%d&quot;, &amp;n);
}
Chart = (VNode_)malloc(n*sizeof(VNode));
Initialize(Chart);//初始化申请出来的空间
printf(&quot;请按照下面的提示构造图。\n\n&quot;);
for(i=0; i&lt;n; ++i)
{
printf(&quot;请输入指向‘V%d’顶点的所有顶点,结束请输入 0 \n&quot;, i+1);
scanf(&quot;%d&quot;, &amp;k);
if(k != 0)
{
q = (ode_)malloc(sizeof(ode));
q-&gt;position = k-1;
(Chart+i)-&gt;first = q;
p = q;
scanf(&quot;%d&quot;, &amp;k);
while(k != 0)
{
q = (ode_)malloc(sizeof(ode));
q-&gt;position = k-1;
p-&gt;next = q;
p = q;
scanf(&quot;%d&quot;, &amp;k);
}
p-&gt;next = NULL;
}
else
{
Chart[i].first = NULL;
}

}
return Chart;
}
//递归方法实现链表深度探索
void DFS(VNode_ Chart, int t)
{
od