南邮数据结构实验三图的基本运算及飞机换乘次数最少问题.doc

《南邮数据结构实验三图的基本运算及飞机换乘次数最少问题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告（2015/2016学年第2学期）课程名称数据结构A实验名称图的基本运算及飞行换乘次数最少问题实验时间年月日指导单位计算机科学与技术系指导教师学生姓名班级学号学院(系)专业 试验一图的基本运算一、问题描述（1）验证教材中关于在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法（见程序9.1~程序9.8）；（2）在邻接矩阵存储结构上实现图的深度和广度优先遍历算法；（3）设计主函数，测试上述运算；（4）提示：扩充MGraph类，在扩充类上增加DFS和BFS函数；二、概要设计图如下所示，显示了名为operation_of_map的（默认文件名）工程，实现了Graph,SeqQueue,

2、结点类ENode,邻接矩阵类MGraph,邻接表LGraph类，包括几种为不同传入类型准备的构造函数。声明所要求的函数，并在后续过程中实现函数功能，最后通过一个main函数求解。三、详细设计1.类与类的层次结构Graph类public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;protected:intn,e;SeqQueue类MGraph类public:SeqQueue(intmSize);~SeqQueue(

3、){delete[]q;}boolIsEmpty()const{returnfront==rear;}boolIsFull()const{return(rear+1)%maxSize==front;}boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;public:MGraph(intmSize,constT&noedg);~MGraph();ResultCodeInsert(intu,intv,T&w);ResultCo

4、deRemove(intu,intv);boolExist(intu,intv)const;voidDFS();voidBFS();protected:T**a;TnoEdge;voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);ENode类LGraph类public:ENode(){nextArc=NULL;}ENode(intvertex,Tweight,ENode*next){adjVex=vertex;w=weight;nextArc=next;}intadjVex;Tw;ENode*nextArc;public:LGraph(i

5、ntmSize);~LGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;protected:ENode**a;四、程序代码#include"stdafx.h"#includeusingnamespacestd;constintINFTY=2147483640;enumResultCode{Underflow,Duplicate,Failure,Success,NotPresent};templateclassGrap

6、h{public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;protected:intn,e;};templateclassSeqQueue{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}boolIsEmpty()const{returnfront==rear;}boolIsFull()const{return(rear+1)%maxSize==

7、front;}boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;};templateSeqQueue::SeqQueue(intmSize){maxSize=mSize;q=newT[maxSize];