校园导游

南通大学计算机科学与技术学院

《数据结构实验报告书》

之

校园导游

班级： 网工121

学号：

设计者：

指导老师： 丁卫平

完成日期： 2014.1.14

附件

1.程序代码：

#include #include #include #include #include #include using namespace std;

#define MGRAPH

#define MAX_VERTEX_NUM 20 //最大顶点数

void AddPoint(); void Select(); void Welcome(); void Goodbye(); void Password(); void Short_Floyd(); void StartGuide();

void SearchInformation(); const int infinity = INT_MAX;

struct ArcCell{ int adj; //对无权图有1，0表示是否相邻，对带权图，则为权值类型 char *info; //该弧的相关信息 };

template struct _MGraph{

T vexs[MAX_VERTEX_NUM]; ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum; int arcnum; int kind; };

typedef int PathMatrix_1[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 路径矩阵，二维数组

typedef int ShortPathTable[MAX_VERTEX_NUM]; // 最短距离表，一维数组

typedef int PathMatrix_2[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 3维数组

typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 2维数组

template class MGraph{ public: _MGraph mgraph;

bool visited[MAX_VERTEX_NUM];

void CreateGraph(); //v是图的顶点集 vr是图的边集 //构造函数

// void DestroyGraph(); //析构函数销毁图 int LocateVex (T u); //图存在，图中存在顶点u 则返回该顶点在图中的位置 bool CreateUDN(); //构造无向网 bool (*VisitFunc)(T v); //访问顶点v的方式 void ShortestPath_DIJ(int v0,PathMatrix_1 &P,ShortPathTable &D); void ShortestPath_FLOYD(PathMatrix_2 &P,DistancMatrix &D); };

template

void MGraph::CreateGraph()//ok { CreateUDN(); }

template

bool MGraph::CreateUDN()//ok //构造无向网 { int i , j ,w; T v1, v2;

cout<<\"请输入景点的个数，路径边的个数: \"; cin>>mgraph.vexnum>>mgraph.arcnum ; cout<<\"请输入各个景点 \"; for(i = 0;i>mgraph.vexs[i]; } for(i = 0;i>v1>>v2>>w; int m = LocateVex(v1); int n = LocateVex(v2); mgraph.arcs[m][n].adj = w;// mgraph.arcs[n][m].adj = w;// } mgraph.kind = 1; return true; }

template

int MGraph::LocateVex(T u)//ok { for(int i = 0 ;i} return -1; }

//#endif

template

void MGraph::ShortestPath_FLOYD(PathMatrix_2 &P,DistancMatrix &D)

// 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w] // 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。 { int u,v,w,i; for(v = 0;v和从u到w的所有路径 } } } } } }

MGraph g;

void Welcome()//欢迎函数 { cout<<\"﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏﹏\"<void Goodbye() { cout<<\"感谢您的使用,再见!\"<void Map()//校园平面图函数 { cout<<\"这是南通大学的校园平面图!\"<║\"<║\"<void StartGuide()//开始导航函数 { char choice; cout<<\"-------------------------\"<>choice; system(\"cls\"); switch(choice) { case 'A':Map();break; case 'B':Short_Floyd(); break; case 'C': { system(\"cls\"); SearchInformation(); }break;

case 'D':Goodbye();break; default:cout<<\"你的输入有误\"<}

void Administer() { char choice; cout<<\"-------------------------\"<>choice; system(\"cls\"); switch(choice) { case 'A': AddPoint();break; case 'B': Select();break; default:{ cout<<\"-------------------------\"<void InputPassword() { int m=0; string password; string c;

system(\"CLS\"); ifstream infile(\"password.txt\"); infile>>c; while(m<3) { cout<<\"请输入登录密码：\"; cin>>password; if(c==password) { cout<<\"----------------------------\"<\"<void AddPoint() { cout<<\"请创建校园导游图.\"<int opekind; void opeshow() { cout<<\"* 菜 单 *\"<void Short_Floyd()

{ MGraph g; PathMatrix_2 p; // 3维数组 DistancMatrix d; // 2维数组 int i,j,k;

opeshow(); cin>>opekind; while(opekind>0 && opekind<4) { if (opekind==1) { cout<<\"请选择有向网\"<cout<>opekind; }//while Goodbye(); }

void SearchInformation() { cout<<\"选择你想查询的景点名称.\"<>choice; cout<<\"正在查询请稍后...\"<}break; case'C': { cout<<\"超市,同学们一般的生活用品都可以买到，不过比较贵.\"<default: {

cout<<\"-------------------------\"<cout<<\"-------------------------\"<StartGuide(); }

void Select() { char choice;

cout<<\"╔═══════════╗\"<>choice; system(\"cls\"); switch(choice) { case 'A':StartGuide(); break; case 'B':InputPassword(); break; case 'C': Goodbye(); break; default:{ cout<<\"﹏﹏﹏﹏﹏﹏\"<void main() { Welcome(); Select(); }

2.程序运行结果：