已阅读5页,还剩4页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中原工学院数据结构实验报告学 院: 计算机学院 专 业:计算机科学与技术 班 级: 计科112 姓 名: 康岩岩 学 号: 201100814220 指导老师: 高艳霞 2012-11-22实验五 图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容问题描述对给定图,实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果,对程序进行分析。【设计思路】【代码整理】#include stdafx.h#include #include using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enumDG,DN,UDG,UDNKind;typedef struct ArcNodeint adjvex; /顶点位置struct ArcNode *nextarc; /下一条弧int *info; /弧信息;typedef structchar info10; /顶点信息ArcNode *fistarc; /指向第一条弧VNode,AdjListMAX_SIZE;typedef structAdjList vertices;int vexnum,arcnum; /顶点数,弧数int kind; /图的种类,此为无向图ALGraph; /这是队列的节点,仅用于广度优先搜索typedef struct Nodeint num;struct Node* next;/队列的头和尾typedef structNode * front;Node *rear;PreBit;int LocateVex(ALGraph G,char info);/定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); /图中加入弧Status CreatGraph(ALGraph&G);/创建图的邻接表Status DFSTraverse(ALGraph G);/深度优先搜索Status BFSTraverse(ALGraph G);/广度优先搜索Status DFS(ALGraph G,int v);/深度优先搜索中的数据读取函数,用于递归bool visitedMAX_SIZE; / 访问标志数组/初始化队列Status init_q(PreBit&P_B)P_B.front=P_B.rear=(Node*)malloc(sizeof(Node);if(!P_B.front)exit(OVERFLOW);P_B.front-next=NULL;/将数据入队Status en_q(PreBit & P_B,int num)Node *p=(Node*)malloc(sizeof(Node);if(!p)exit(OVERFLOW);p-num=num;p-next=NULL;P_B.rear-next=p;P_B.rear=p;return OK;/出队Status de_q(PreBit & P_B)if(P_B.front=P_B.rear)return ERROR;Node* p=P_B.front-next;P_B.front-next=p-next;if(P_B.rear=p)P_B.rear=P_B.front;free(p);return OK;Status CreatGraph(ALGraph&G)cout请输入顶点数目和弧数目G.vexnumG.arcnum;/依次输入顶点信息for(int i=0;iG.vexnum;i+)cout请输入顶点名称G.;G.verticesi.fistarc=NULL;/依次输入弧信息for(int k=1;k=G.arcnum;k+)char v110,v210; /用于表示顶点名称的字符数组int i,j; /表示两个顶点的位置BACK: /返回点cout请输入第k条弧的两个顶点v1v2;i=LocateVex(G,v1); /得到顶点v1的位置j=LocateVex(G,v2); /得到顶点v2的位置if(i=-1|j=-1) /头信息不存在则返回重输cout不存在该节点!adjvex=adjvex; p-nextarc=G.verticesadjvex.fistarc;/指向头结点的第一条弧G.verticesadjvex.fistarc=p; /头结点的第一条弧指向p,即将p作为头结点的第一条弧return OK;/定位顶点的位置int LocateVex(ALGraph G,char info)for(int i=0;iG.vexnum;i+)if(strcmp(G.,info)=0) /头结点名称与传入的信息相等,证明该头节点存在return i; /此时返回位置return -1;/深度优先搜索Status DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;v+)visitedv=false;char v110;int i;BACK:cout请输入首先访问的顶点v1;i=LocateVex(G,v1);if(i=-1)cout不存在该节点!endl;goto BACK;DFS(G,i);return OK;/深度优先搜索递归访问图Status DFS(ALGraph G,int v)visitedv=true;coutG.adjvex)DFS(G,p-adjvex); /递归读取p=p-nextarc;return OK;/广度优先搜索Status BFSTraverse(ALGraph G)for(int v=0;vG.vexnum;v+)visitedv=false;char v110;int v;BACK:cout请输入首先访问的顶点v1;v=LocateVex(G,v1);if(v=-1)cout不存在该节点!endl;goto BACK;PreBit P_B;init_q(P_B);ArcNode *p;visitedv=true;coutG.next-num;/读出顶点位置de_q(P_B);/顶点已经访问过,将其出队列p=G.verticesw.fistarc;/得到与顶点相关的第一条弧 while(p) if(!visitedp-adjvex)en_q(P_B,p-adjvex);/将弧入队,但不读取,只是将其放在队尾p=p-nextarc;return OK;int _
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 期末专题 利用三角形全等测距离 教案 -2024-2025学年人教版数学八年级上册
- 浙教版四年级上册信息技术第7课数据计算(教案)
- 设置单元格格式 教案-甘教版七下信息技术(pdf版)
- 青岛版科学六三制三年级下册第三单元生活中的材料《10天然材料和人造材料》教学设计
- 冀教版六上第四单元第6课时 圆环的面积 教案
- 蒙牛“敲铃人”村小校长赋能计划执行方案
- 第二十三章旋转(知识归纳题型突破)(八大题型134题)-九年级数学上册单元速记巧练(人教版)
- 班级篮球赛活动策划(3篇)
- 2024年标准夫妻离婚协议书(34篇)
- 餐厅活动策划方案模板7篇
- 2024年边缘计算定义业务新引擎-边缘典型场景数据价值洞察报告
- 2024-2030年足球行业市场发展分析及发展趋势与规划建议研究报告
- 《电子元器件检测与识别》(人民邮电出版社)同步教学(教案)
- 2024年生物航煤行业研究报告:市场规模、供需态势、发展前景预测
- 文化传媒产业数字营销推广与服务模式创新报告
- 2024年湖北武汉科技馆工作人员招考高频考题难、易错点模拟试题(共500题)附带答案详解
- 2024年6月高等学校英语应用能力考试B级真题2
- 2024年单招语文模拟试题及参考答案
- 人教版(2024新版)九年级上册化学:第五单元 课题2《化学方程式》教案教学设计
- 《初中语文教材古诗词教学策略研究》中期报告
- 临床老年人误吸预防
评论
0/150
提交评论