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

.

实 验 报 告

（ 2015 / 2016 学年 第 2学期）

课程名称 实验名称

数据结构A

图的基本运算及飞行换乘次数最少问题

实验时间 指导单位 指导教师

年 月 日

计算机科学与技术系

.

.

学生姓名 学院(系)

班级学号 专 业

.

.

试验一 图的基本运算

一、问题描述

（1）验证教材中关于在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法（见程序9.1~程序9.8）；

（2）在邻接矩阵存储结构上实现图的深度和广度优先遍历算法； （3）设计主函数，测试上述运算；

（4）提示：扩充MGraph类，在扩充类上增加DFS和BFS函数； 二、概要设计

图如下所示，显示了名为operation_of_map的（默认文件名）工程，实现了Graph,SeqQueue,结点类ENode,邻接矩阵类MGraph,邻接表LGraph类，包括几种为不同传入类型准备的构造函数。声明所要求的函数，并在后续过程中实现函数功能，最后通过一个main函数求解。

三、详细设计

.

.

1.类与类的层次结构 Graph类 public: virtual ResultCode Insert(int u, int v, T&w) = 0; virtual ResultCode Remove(int u, int v) = 0; virtual bool Exist(int u, int v)const = 0; int n, e; protected:

SeqQueue类 public: SeqQueue(int mSize); ~SeqQueue() { delete[]q; } MGraph类 public: MGraph(int mSize, const T& noedg); ~MGraph(); ResultCode Insert(int u, int v, ResultCode Remove(int u, int v); bool Exist(int u, int v)const; void DFS(); void BFS(); T**a; T noEdge; void DFS(int v, bool*visited); void BFS(int v, bool*visited); bool IsEmpty() const { return front bool IsFull() const { return (rear bool Front(T &x)const; bool EnQueue(T x); bool DeQueue(); == rear; } + 1) % maxSize == front; } T&w); protected: void Clear() { front = rear = 0; } int front, rear; int maxSize; T*q; private: ENode类 public: .

LGraph类 public: LGraph(int mSize); ~LGraph(); ResultCode Insert(int u, int v, ResultCode Remove(int u, int v); bool Exist(int u, int v)const; ENode**a; ENode() { nextArc = NULL; } ENode(int vertex, T weight, ENode { } int adjVex; adjVex = vertex; w = weight; nextArc = next; *next) T&w); protected: .

T w; ENode *nextArc;

四、程序代码

#include \ #include using namespace std;

const int INFTY = 2147483640;

enum ResultCode { Underflow, Duplicate, Failure, Success, NotPresent }; template class Graph { public: };

template class SeqQueue { public: };

template

.

virtual ResultCode Insert(int u, int v, T&w) = 0; virtual ResultCode Remove(int u, int v) = 0; virtual bool Exist(int u, int v)const = 0; int n, e;

protected:

SeqQueue(int mSize); ~SeqQueue() { delete[]q; }

bool IsEmpty() const { return front == rear; }

bool IsFull() const { return (rear + 1) % maxSize == front; } bool Front(T &x)const; bool EnQueue(T x); bool DeQueue();

void Clear() { front = rear = 0; } int front, rear; int maxSize; T*q;

private: