数据结构试验报告-图的基本操作.doc

中原工学院数据结构实验报告学 院： 计算机学院 专 业：计算机科学与技术 班 级： 计科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.verticesi.info;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.verticesi.info,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.verticesv.infoadjvex)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.verticesv.infonext-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 _tmain(int argc, _TCHAR* argv)ALGraph G;CreatGraph(G);cout深度优先搜索图:endl;DFSTraverse(G);coutendl;cout广度优先搜索图:endl;BFSTraverse(G);coutendl;system(pause);return 0;