南邮数据结构实验三
实 验 报 告
（2015 / 2016 学年 第 一 学期）
课程名称 实验名称
数据结构
图的基本运算及飞机换乘次数最少问题
实验时间 指导单位 指导教师
2015 年 12 月 4 日
计算机科学与技术系
黄海平
学生姓名 学院(系)
陈明阳 贝尔英才
班级学号 Q14010119
专 业 信息科技强化班
实 验 报 告
1
#include #include using namespace std; const int INF = 2147483647;
enum ResultCode { Underflow , Duplicate , Failure , Success , NotPresent , OutOfBounds }; template class 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; protected :
int n, e; };
template
class MGraph :public Graph //邻接矩阵类 {
public :
MGraph(int mSize, const T noedg); ~MGraph();
ResultCode Insert(int u, int v, T w); ResultCode Remove(int u, int v); bool Exist(int u, int v)const ; int Choose(int *d, bool *s);
void Dijkstra(int v, T *d, int *path);
protected : T **a; T noEdge;
};
template
MGraph ::MGraph(int mSize , const T noedg ) {
n = mSize ; e = 0;
noEdge = noedg ; a = new T *[n];
for (int i = 0; i
{
a[i] = new T [n];
for (int j = 0; j
a[i][j] = noEdge; a[i][i] = 0;
}
2
}
template MGraph ::~MGraph() {
for (int i = 0; i
delete []a[i]; delete[]a;
template
ResultCode MGraph ::Insert(int u , int v , T w ) {
if (u n - 1 || v >n - 1 || u == v )
return Failure ; return Duplicate ; if (a[u ][v ] != noEdge) a[u ][v ] = w ; a[v ][u ] = w ; e++; }
return Success ; template
ResultCode MGraph ::Remove(int u , int v ) {
if (u n - 1 || v >n - 1 || u == v )
return Failure ; if (a[u ][v ] == noEdge) return NotPresent ; a[u ][v ] = noEdge;
a[v ][u ] = noEdge; e--;
return Success ; }
template
bool MGraph ::Exist(int u , int v ) const {
if (u n - 1 || v >n - 1 || u == v || a[u ][v ] == noEdge) }
return false ; return true ;
template
int MGraph ::Choose(int *d , bool *s ) //求最小d[i] {
int i, minpos; T min;
3
min = INF; minpos = -1; }
if (d [i]
min = d [i]; minpos = i; }
for (i = 0; i
return minpos;
template
void MGraph ::Dijkstra(int v , T *d , int *path ) //迪杰斯特拉算法 {
int i, k, w; if (v n - 1) throw OutOfBounds ; bool *s = new bool [n]; for (i = 0; i
{
s[i] = false ; d [i] = a[v ][i]; if (i != v &&d [i]
path [i] = -1; }
s[v ] = true ; d [v ] = 0;
for (i = 1; i
{
k = Choose(d , s); s[k] = true ;
for (w = 0; w
if (!s[w] && (d [k] + a[k][w])
d [w] = d [k] + a[k][w]; path [w] = k; }
}
源.cpp
#include #include
4
#include"Graph.h" using namespace std; int main() {
int n, m;
cout > n;
cout > m;
MGraph A(n, INF); int c, f;
cout
{
cout > c >> f; A.Insert(c, f, 1); }
char s; do {
int v, w;
cout > v >> w;
while (vn - 1 || v>n - 1)
{
cin >> v >> w; }
cout
int *b = new int [n]; int *d = new int [n]; int *path = new int [n]; A.Dijkstra(v, d, path); int e = n - 1;
int j, i,k = 0; b[j] = -2; {
j = w;
while (path[j] != -1)
{
b[e] = path[j]; e--;
j = path[j];
for (j = 0; j
5
}
cout
cout
{
if (b[k] != -2)
cout
if (e == n - 1 || d[j] == INF) else
cout
}
cout
if (w == v) delete[]b; delete[]d; delete[]path;
cout > s;
while (s != 'Y' &&s != 'y' &&s != 'n' &&s != 'N' ) {
return 0; }
cout > s; }
} while (s == 'Y' || s == 'y' );
运行截图：
6
实 验 报 告
7
8