《数据结构实验报告实验3》由会员分享，可在线阅读，更多相关《数据结构实验报告实验3（11页珍藏版）》请在金锄头文库上搜索。
1、本科实验报告课程名称： 数据结构 实验项目： 图结构 实验地点： 迎西校区逸夫楼302 专业班级：软件1109 学号： 2011004872 学生姓名： 栗永春 指导教师： 牛之贤 年 月 日图结构一、实验目的和要求目的与要求二、实验内容和原理三、主要仪器设备四、操作方法与实验步骤列出调试通过的源程序。习题2：/* 采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。 *xiaojinglingfen*/#include #include #include int n;/定义全局变量，表示所构造的图中的总的顶点个数/用于构造结点之间联系关系的弧结点typedef struct arcNo
2、deint position;/用来存放节点的标号struct arcNode *next;/用来存放结点的下一个弧的信息ArcNode, *ArcNode_;/定义用来构造元素的结点typedef struct vNodeint mark;/在程序中用来标识是否被访问过ArcNode *first;/存储连接到该结点的第一个弧信息的地址VNode, *VNode_;/函数声明部分VNode_ Structure();/构造一个图void DFS(VNode_ Chart, int t);/递归方法实现链表深度探索void Initialize(VNode_ Chart);/初始化所构造的顶点
3、信息void End(VNode_ Chart);/收尾工作，释放由malloc申请的空间void main()int i=0;int count=0;VNode_ Chart = Structure();/创建图while(Charti.mark = 0)DFS(Chart, i);+count;i = 0;while(Charti.mark != 0)&i5)+i;printf(该图的连通分量的个数是%d., count);End(Chart);/构造一个图的过程VNode_ Structure()VNode_ Chart;int i, j, k;ArcNode_ p, q;printf(
4、下面进行构造图的过程，请按照提示输入信息完成构造图的过程！n);printf(n请输入要构造的图的顶点总数.n);scanf(%d, &n);/将用户输入的总的顶点数保存/对输入数据进行判断while(n1)printf(录入的数据有误！请重新输入。n);scanf(%d, &n);Chart = (VNode_)malloc(n*sizeof(VNode);Initialize(Chart);/初始化申请出来的空间printf(请按照下面的提示构造图。nn);for(i=0; iposition = k-1;(Chart+i)-first = q;p = q;scanf(%d, &k);wh
5、ile(k != 0)q = (ArcNode_)malloc(sizeof(ArcNode);q-position = k-1;p-next = q;p = q;scanf(%d, &k);p-next = NULL;elseCharti.first = NULL;return Chart;/递归方法实现链表深度探索void DFS(VNode_ Chart, int t)ArcNode_ q;if(Chartt.mark = 0)Chartt.mark = 1;for(q=Chartt.first; q != NULL; q=q-next)DFS(Chart, q-position);/初
6、始化所构造的顶点信息void Initialize(VNode_ Chart)int i;for(i=0; i mark = 0;/收尾工作，释放由malloc申请的空间void End(VNode_ Chart)int i;ArcNode_ p, q;for(i=0;inext;free(q);free(Chart);习题2/* 试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向 * 图中是否存在有顶点Vi到Vj顶点的路径(ij)。 */#include #include #include int n;/定义全局变量，表示所构造的图中的总的顶点个数/用于构造结点之间联系关系的弧
7、结点typedef struct arcNodeint position;/用来存放节点的标号struct arcNode *next;/用来存放结点的下一个弧的信息ArcNode, *ArcNode_;/定义用来构造元素的结点typedef struct vNodeint mark;/在程序中用来标识是否被访问过ArcNode *first;/存储连接到该结点的第一个弧信息的地址VNode, *VNode_;/函数声明部分VNode_ Structure();/构造一个图void DFS(VNode_ Chart, int t);/递归方法实现链表深度探索void Initialize(VN
8、ode_ Chart);/初始化所构造的顶点信息void End(VNode_ Chart);/收尾工作，释放由malloc申请的空间void main()int i=0;int count=0;int w, v;VNode_ Chart = Structure();/创建图printf(请输入要查询的顶点w,vn);scanf(%d,%d, &w, &v);DFS(Chart, w-1);if(Chartv-1.mark)printf(顶点V%d，与顶点V%d之间连通。, w, v);elseprintf(顶点顶点V%d，与顶点V%d之间不连通。, w, v);printf(nn);End(
9、Chart);/构造一个图的过程VNode_ Structure()VNode_ Chart;int i, j, k;ArcNode_ p, q;printf(下面进行构造图的过程，请按照提示输入信息完成构造图的过程！n);printf(n请输入要构造的图的顶点总数.n);scanf(%d, &n);/将用户输入的总的顶点数保存/对输入数据进行判断while(n1)printf(录入的数据有误！请重新输入。n);scanf(%d, &n);Chart = (VNode_)malloc(n*sizeof(VNode);Initialize(Chart);/初始化申请出来的空间printf(请按照
10、下面的提示构造图。nn);for(i=0; iposition = k-1;(Chart+i)-first = q;p = q;scanf(%d, &k);while(k != 0)q = (ArcNode_)malloc(sizeof(ArcNode);q-position = k-1;p-next = q;p = q;scanf(%d, &k);p-next = NULL;elseCharti.first = NULL;return Chart;/递归方法实现链表深度探索void DFS(VNode_ Chart, int t)ArcNode_ q;if(Chartt.mark = 0)Chartt.mark = 1;for(q=Chartt.first; q != NULL; q=q-next)
