数据结构课程设计-校园导游

实验三：校园导游

1、设计要求

用无向图表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。

要求：

（1）查询任意景点的相关信息

（2）查询图中任意两个景点间的最短路径

（3）查询图中任意两个景点间的所有路径

（4）增加、删除、更新有关景点和道路的信息

实际输入输出情况如下：

（1）有关景点和路线的操作

（2）查看现有导游路线图

（3）对景点信息的增删改与查询

增加景点

删除景点

更改景点信息

查询景点信息

（4）对道路信息的增删改

增加道路

删除道路

更改道路信息

（5）查询两景点间所有路径

（6）查询两景点间最短路径

（7）查询经过多个景点的最短路径

1、数据结构与算法描述

1、校园导游的数据结构 

整个校园导游图以一个无向加权图描述，采用邻接表作为实现图结构的方式。

（1）景点结构

每个景点是一个链表，其结构如下：

#pragma once

#include

#include"GraphNode.h"

using namespace std;

class GraphVertex

{

    friend class DiGraph;

    friend ostream& operator<<(ostream& os,DiGraph& DG);

protected:

    int vertexid;

    string name;

    GraphNode* head;

    string information;

    bool flag;//到达该点的标记

public:

    GraphVertex(){vertexid=0;name="";head=0;flag=false;information="";}

    GraphVertex(int vertexid,string name){this->vertexid=vertexid;this->name=name;head=0;flag=false;};

    ~GraphVertex(){};

    int Length()const;//该顶点的度

    bool Find(int goal,GraphNode*& index)const;//查找该顶点和goal之间是否有路径，如果找到则将该路径指针的引用保存在index

    bool insert(int goal,int length,string roadname);//按照权值递增规则将顶点goal插入该顶点链表

    bool Delete(int goal);//删除该顶点和goal间的路径

};

（2）路线的结构

邻接链表中的每个节点代表了一条路线，其结构如下：

#pragma once

#include

using namespace std;

class GraphNode

{

    friend class GraphVertex;

public:

    int tovertex;

    int length;

    string roadname;

    GraphNode* next;

    GraphNode(int to,int length,string roadname="",GraphNode* next=0){this->length=length;this->tovertex=to;this->roadname=roadname;this->next=next;};

    ~GraphNode(){};

    int operator==(GraphNode y)const{return this->tovertex==y.tovertex;}

};

（3）图结构

整个图的结构是用链表的数组表示，为了使景点的添加删除操作可以充分地利用该数组空间，对该数组使用模拟指针的结构进行描述。

#pragma once

#include"GraphVertex.h"

#include"GraphNode.h"

#include"simNode.h"

class DiGraph

{

    friend ostream& operator<<(ostream& os,DiGraph& DG);

    friend int main();

private:

    int n;

    int e;

    GraphVertex* v;

    Simspace* sp;

    int MaxN;

    void getpath(int from,int to,int** kay,int **l,string& path);

    void getallpath(int from,int to,string& path_temp);

public:

    DiGraph(int MaxN=100){this->MaxN=MaxN;n=0;e=0;v=new GraphVertex[MaxN+1];sp=new Simspace(MaxN);};

    ~DiGraph(){delete[] v;delete sp;};

    int findid(string name);

    DiGraph& addV(string name,string information)

    {

        int i=sp->allc();

        if(!i)return *this;//空间用完

        v[i].name=name;

        v[i].information=information;

        v[i].vertexid=i;

        n++;

        return *this;

    }

    DiGraph& DeleteV(string name);

    DiGraph& addE(string name1,string name2,int length,string roadname);

    DiGraph& DeleteE(string name1,string name2);

    void allpair(int** kay,int** l);

    void Output_path(string from,string to,int** kay,int** l);

    void Output_allpath(string from,string to);

    void getroute(int** l,int* min_route,int* now_route,int n,int s,int e);

    void Output_route(int** l,int** kay,string *route,int n);

    void change_vertex_name(string from,string to);

    void change_road_name(string from_vertex,string to_vertex,string road_name,int length);

    void get_info(string name);

    void change_info(string name,string info);

};

2、对算法中的主要方法的描述：

A.两点间所有路径算法：

要求两点间所有路径，可以采用一个比较直观的递归算法，即从起点开始，对该起点所有邻接点执行以下操作：

如果该顶点已经到达，停止递归过程。

设置该顶点为已到达。

如果该顶点是目标顶点，停止递归过程。

对该顶点执行同样操作。

其关键代码如下：

void DiGraph::getallpath(int start,int end,string& path_temp)//这是获得两点间所有路径的递归方法

{

    v[start].flag=true;

    if(start==end)

    {

     cout<        return;

    }

    GraphNode* p;

    p=v[start].head;

    while(p)//对每个可达的点，进行同样的寻找所有路径操作

    {

        int pos=path_temp.size();//在目标路径中记录完成剩下的递归操作之前的位置

        if(v[p->tovertex].flag){p=p->next;continue;}

        path_temp=path_temp+p->roadname+"\"+v[p->tovertex].name+"\";

     getallpath(p->tovertex,end,path_temp);

        path_temp.erase(pos);//递归该点完毕，抹去递归操作过程中对字符串的改动

     p=p->next;

    }

    v[start].flag=false;

    return;

}

B. 两点间最短路径算法

采用folyd算法，求出该算法所使用的kay[][]和l[][]两个二维数组，继而利用这两个数组进行输出最短路径的操作。关键代码如下：

生成kay和l的操作：

void DiGraph::allpair(int** kay,int** l)//所有点对最短路径

{

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            kay[i][j]=0;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            l[i][j]=-1;

    //初始化kay和l

        int index=1;

    for(int i=1;i<=n;)

    {

        if(v[index].vertexid==0)

        {

            if(index>=MaxN)break;

            index++;

            continue;

        }//若遍历到已经被删除的点则忽略

        GraphNode* gn=v[index].head;

        while(gn)

        {

            l[index][gn->tovertex]=gn->length;

         gn=gn->next;

        }

        if(index==MaxN)break;

        i++;

        index++;

    }

    //以上代码初始化l将边长度信息写入，无边则为-1

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                if(l[i][k]!=-1&&l[k][j]!=-1&&((l[i][j]==-1)||(l[i][k]+l[k][j])                {

                    l[i][j]=l[i][k]+l[k][j];

                    l[j][i]=l[i][k]+l[k][j];

                    kay[i][j]=k;

                    kay[j][i]=k;

                }

}//floyd算法

以下是输出路径的递归算法：

void DiGraph::getpath(int from,int to,int** kay,int **l,string& path)

{

    if(kay[from][to]==0)

    {

        GraphNode* road_temp;

        v[from].Find(to,road_temp);

        path=path+road_temp->roadname+"\";

        return;

    }

    getpath(from,kay[from][to],kay,l,path);

    path=path+v[kay[from][to]].name+"\";

    getpath(kay[from][to],to,kay,l,path);

    return;

}

C.经过多个顶点的最短路径算法

这里我利用folyd算法产生的两个二维数组，生成途径景点的全排列，然后利用l[][]求出排列中路径最短的路，再用与floyd算法相同的输出最短路径的算法进行输出，其关键代码如下：

void DiGraph::getroute(int** l,int* min_route,int* route,int n,int s,int e)//暴力的O(n!)算法 保证得到最短路径

//经过多个顶点的最短路径 利用全排列算法和floyd算法得到

{

    //在perm的输出部分做改动

    if(s==e)

    {

        int length=0,min_length=0;

        for(int i=0;i        {

            if(l[route[i]][route[i+1]]==-1)return;//有两点间没有路径；直接忽略该路径

            length+=l[route[i]][route[i+1]];

            min_length+=l[min_route[i]][min_route[i+1]];

        }

        //若length        

        if(length        {

            for(int i=0;i                min_route[i]=route[i];

        }

        return;

    };

    //做perm处理

    for(int i=s;i    {

        swap(route[s],route[i]);

        getroute(l,min_route,route,n,s+1,e);

        swap(route[s],route[i]);

    }

}

2、分析与探讨

1.测试结果分析

    通过测试结果我们发现，虽然采用的旅行商问题的算法为O(n!)的算法，但因为一般经过的景点数目不多，所以执行速度仍然比较快。其他部分的算法运行

2.算法分析

1、两点间所有路径算法：O(n!)

2、查询任意两点间的最短路径:O(n*3)

3、经过多点的最短路径算法：O(n!)

附录 所有源代码

文件一:GraphNode.h

#pragma once

#include

using namespace std;

class GraphNode

{

    friend class GraphVertex;

public:

    int tovertex;

    int length;

    string roadname;

    GraphNode* next;

    GraphNode(int to,int length,string roadname="",GraphNode* next=0){this->length=length;this->tovertex=to;this->roadname=roadname;this->next=next;};

    ~GraphNode(){};

    int operator==(GraphNode y)const{return this->tovertex==y.tovertex;}

};

文件二：GraphVertex.h

#pragma once

#include

#include"GraphNode.h"

using namespace std;

class GraphVertex

{

    friend class DiGraph;

    friend ostream& operator<<(ostream& os,DiGraph& DG);

protected:

    int vertexid;

    string name;

    GraphNode* head;

    string information;

    bool flag;//到达该点的标记

public:

    GraphVertex(){vertexid=0;name="";head=0;flag=false;information="";}

    GraphVertex(int vertexid,string name){this->vertexid=vertexid;this->name=name;head=0;flag=false;};

    ~GraphVertex(){};

    int Length()const;//该顶点的度

    bool Find(int goal,GraphNode*& index)const;//查找该顶点和goal之间是否有路径，如果找到则将该路径指针的引用保存在index

    bool insert(int goal,int length,string roadname);//按照权值递增规则将顶点goal插入该顶点链表

    bool Delete(int goal);//删除该顶点和goal间的路径

};

文件三 SimNode.h

#pragma once

class Simspace

{

public:

    int Maxsize;

    int *space;

    int first;

    Simspace(int Maxsize=100)

    {

        this->Maxsize=Maxsize;

        space=new int[Maxsize+1];

        for(int i=1;i            space[i]=i+1;

        space[Maxsize]=-1;

        first=1;

    }

    int allc();

    void deallc(int &i);

};

文件四 DiGraph.h

#pragma once

#include"GraphVertex.h"

#include"GraphNode.h"

#include"simNode.h"

class DiGraph

{

    friend ostream& operator<<(ostream& os,DiGraph& DG);

    friend int main();

private:

    int n;

    int e;

    GraphVertex* v;

    Simspace* sp;

    int MaxN;

    void getpath(int from,int to,int** kay,int **l,string& path);

    void getallpath(int from,int to,string& path_temp);

public:

    DiGraph(int MaxN=100){this->MaxN=MaxN;n=0;e=0;v=new GraphVertex[MaxN+1];sp=new Simspace(MaxN);};

    ~DiGraph(){delete[] v;delete sp;};

    int findid(string name);

    DiGraph& addV(string name,string information)

    {

        int i=sp->allc();

        if(!i)return *this;//空间用完

        v[i].name=name;

        v[i].information=information;

        v[i].vertexid=i;

        n++;

        return *this;

    }

    DiGraph& DeleteV(string name);

    DiGraph& addE(string name1,string name2,int length,string roadname);

    DiGraph& DeleteE(string name1,string name2);

    void allpair(int** kay,int** l);

    void Output_path(string from,string to,int** kay,int** l);

    void Output_allpath(string from,string to);

    void getroute(int** l,int* min_route,int* now_route,int n,int s,int e);

    void Output_route(int** l,int** kay,string *route,int n);

    void change_vertex_name(string from,string to);

    void change_road_name(string from_vertex,string to_vertex,string road_name,int length);

    void get_info(string name);

    void change_info(string name,string info);

};

文件五 simNode.cpp

#include "simNode.h"

int Simspace::allc()

{

    if(first==-1)return 0;

    int i=first;

    first=space[first];

    return i;

}

void Simspace::deallc(int& i)

{

    space[i]=first;

    first=i;

    i=-1;

    return;

}

文件六 GraphVertex.cpp

#include "GraphVertex.h"

#include

int GraphVertex::Length()const

{

    int result=0;

    GraphNode* current=head;

    while(current!=0)

    {

     current=current->next;

        result++;

    }

    return result;

}

bool GraphVertex::Find(int goal,GraphNode*& index)const

{

    GraphNode* p=head;

    while(p!=0)

    {

        if(p->tovertex==goal)

        {

            index=p;

            return true;

        }

     p=p->next;

    }

    return false;

}

bool GraphVertex::insert(int goal,int length,string roadname)

{

    GraphNode*p;

    if(Find(goal,p))

        {

         cout<<"已经存在该条道路"<            return false;

        }

    if(head==0)

    {

        head=new GraphNode(goal,length,roadname);

        return true;

    }

    if(lengthlength)

    {

        head=new GraphNode(goal,length,roadname,head);

        return true;

    }

p=head->next;

    GraphNode* pp=head;

    while(p!=0)

    {

        if(length>pp->length&&lengthlength)

        {

         pp->next=new GraphNode(goal,length,roadname,p);

            return true;

        }

        pp=p;

     p=p->next;

    }

pp->next=new GraphNode(goal,length,roadname);

    return true;

}

bool GraphVertex::Delete(int goal)

{

    GraphNode* p;

    if(!Find(goal,p))return false;

    if(p==head)

    {

     head=head->next;

        delete p;

        return true;

    }

    GraphNode* pp=head;

    while(pp->next!=p)

     pp=pp->next;

pp->next=p->next;

    delete p;

    return true;

}

文件七 DiGraph.cpp

#include "DiGraph.h"

#include

#include

#include

using namespace std;

using std::cout;

int DiGraph::findid(string name)//临时的O(n)的寻找顶点id的算法

{

    int index=1;

    for(int i=1;i<=n;)

    {

        if(v[index].vertexid==0)

        {

            if(index>=MaxN)break;

            index++;

            continue;

        }//若遍历到已经被删除的点则忽略

        if(v[index].name==name)

            return index;

        if(index==MaxN)break;

        i++;

        index++;

    }

    return 0;

}

void DiGraph::change_vertex_name(string from,string to)

{

    int id=findid(from);

    v[id].name=to;

}

void DiGraph::change_road_name(string from,string to,string road_name,int length)

{

    int from_int=findid(from);

    int to_int=findid(to);

    GraphNode* target;

    v[from_int].Find(to_int,target);

target->roadname=road_name;

target->length=length;

    v[to_int].Find(from_int,target);

target->roadname=road_name;

target->length=length;

}

void DiGraph::get_info(string name)

{

    int id=findid(name);

cout<}

void DiGraph::change_info(string name,string info)

{

    int id=findid(name);

    v[id].information=info;

}

DiGraph& DiGraph::addE(string name1,string name2,int length,string roadname)

{

    int id1=findid(name1);

    int id2=findid(name2);

    if(v[id1].insert(id2,length,roadname)&&v[id2].insert(id1,length,roadname))

    e++;

    return *this;

}

DiGraph& DiGraph::DeleteV(string name)

{

    int id=findid(name);

    if(id==0)

    {

     std::cout<<"不存在該景點。"<        return *this;

    }

    int head;

    while(v[id].head!=0)

    {

     head=v[id].head->tovertex;

        v[id].Delete(head);

        v[head].Delete(id);

        e--;

    }

    v[id].vertexid=0;

sp->deallc(id);

    n--;

    return *this;

}

DiGraph& DiGraph::DeleteE(string name1,string name2)

{

    int id1=findid(name1);

    int id2=findid(name2);

    if(v[id1].Delete(id2)&&v[id2].Delete(id1))

        e--;

    return *this;

}

ostream& operator<<(ostream& os,DiGraph& DG)

{

    os<<"景点个数:"<    GraphVertex GV;

    int index=1;

    for(int i=1;i<=DG.n;)

    {

        GV=DG.v[index];

        if(GV.vertexid==0)

        {

            if(index>=DG.MaxN)break;

            index++;

            continue;

        }//不遍历已经删除的顶点

        os<        for(GraphNode* p=GV.head;p!=0;p=p->next)

            {

                os<roadname<<" to "<tovertex].name<<<<"length="<length<<";";

            }

    os<    if(index>=DG.MaxN)break;

    index++;

    i++;

    }

    return os;

}

void DiGraph::getpath(int from,int to,int** kay,int **l,string& path)

{

    if(kay[from][to]==0)

    {

        GraphNode* road_temp;

        v[from].Find(to,road_temp);

        path=path+road_temp->roadname+"\";

        return;

    }

    getpath(from,kay[from][to],kay,l,path);

    path=path+v[kay[from][to]].name+"\";

    getpath(kay[from][to],to,kay,l,path);

    return;

}

void DiGraph::allpair(int** kay,int** l)//所有点对最短路径

{

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            kay[i][j]=0;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            l[i][j]=-1;

    //初始化kay和l

        int index=1;

    for(int i=1;i<=n;)

    {

        if(v[index].vertexid==0)

        {

            if(index>=MaxN)break;

            index++;

            continue;

        }//若遍历到已经被删除的点则忽略

        GraphNode* gn=v[index].head;

        while(gn)

        {

            l[index][gn->tovertex]=gn->length;

         gn=gn->next;

        }

        if(index==MaxN)break;

        i++;

        index++;

    }

    //以上代码初始化l将边长度信息写入，无边则为-1

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                if(l[i][k]!=-1&&l[k][j]!=-1&&((l[i][j]==-1)||(l[i][k]+l[k][j])                {

                    l[i][j]=l[i][k]+l[k][j];

                    l[j][i]=l[i][k]+l[k][j];

                    kay[i][j]=k;

                    kay[j][i]=k;

                }

    /*for(int i=1;i<=n;i++)

    {

     for(int j=1;j<=n;j++)

         cout<     cout<    }

for(int i=1;i<=n;i++)

    {

     for(int j=1;j<=n;j++)

         cout<     cout<    }*/

}//floyd算法

void DiGraph::Output_path(string from,string to,int** kay,int** l)//输出任意两点最短路径，使用已经准备好的kay和l

{

    string path_passed;

    int start=findid(from);

    int end=findid(to);

cout<    getpath(start,end,kay,l,path_passed);

cout< cout<}

void DiGraph::getallpath(int start,int end,string& path_temp)//这是获得两点间所有路径的递归方法

{

    v[start].flag=true;

    if(start==end)

    {

     cout<        return;

    }

    GraphNode* p;

    p=v[start].head;

    while(p)//对每个可达的点，进行同样的寻找所有路径操作

    {

        int pos=path_temp.size();

        if(v[p->tovertex].flag){p=p->next;continue;}

        path_temp=path_temp+p->roadname+"\"+v[p->tovertex].name+"\";

     getallpath(p->tovertex,end,path_temp);

        path_temp.erase(pos);

     p=p->next;

    }

    //if(f    v[start].flag=false;

    return;

}

void DiGraph::Output_allpath(string from,string to)

{

    int start=findid(from);

    int end=findid(to);

    string path_temp=from+"\";

    getallpath(start,end,path_temp);

}

inline void swap(int &a,int& b)//内联函数负责交换两个变量的值

{

    int c=a;a=b;b=c;

}

void DiGraph::getroute(int** l,int* min_route,int* route,int n,int s,int e)//暴力的O(n!)算法 保证得到最短路径

//经过多个顶点的最短路径 利用全排列算法和floyd算法得到

{

    //在perm的输出部分做改动

    if(s==e)

    {

        int length=0,min_length=0;

        for(int i=0;i        {

            if(l[route[i]][route[i+1]]==-1)return;//有两点间没有路径；直接忽略该路径

            length+=l[route[i]][route[i+1]];

            min_length+=l[min_route[i]][min_route[i+1]];

        }

        //若length        /*for(int i=0;i        {

         cout<        }*/

        /*cout<     cout<        if(length        {

            for(int i=0;i                min_route[i]=route[i];

        }

        return;

    };

    //做perm处理

    for(int i=s;i    {

        swap(route[s],route[i]);

        getroute(l,min_route,route,n,s+1,e);

        swap(route[s],route[i]);

    }

}

void DiGraph::Output_route(int** l,int** kay,string * route_name,int n)//这里输出经过多个顶点的最短路径，利用getroute方法

//并且使用了前面定义的输出最短路径的getpath方法

{

    int* route=new int[n];

    int* min_route=new int[n];

    string path_pass="";

    for(int i=0;i        route[i]=min_route[i]=findid(route_name[i]);

    getroute(l,min_route,route,n,0,n-1);

    for(int i=0;i    {

        //cout<     cout<        getpath(min_route[i],min_route[i+1],kay,l,path_pass);

     cout<        path_pass="";

    }

cout<}

int main()

{

    string input;

    DiGraph dg;

    dg.addV("校门","学校的大门");

    dg.addV("食堂","学生吃饭的地方");

    dg.addV("教学楼","学生上课的地点");

    dg.addV("实验楼","学生做实验的地方");

    dg.addV("宿舍","学生们日常生活的地方");

    dg.addV("操场","给学生提供运动的场所");

    dg.addV("澡堂","学生洗澡的地方");

    dg.addE("校门","食堂",4,"A路");

    dg.addE("校门","教学楼",9,"B路");

    dg.addE("教学楼","食堂",3,"C路");

    dg.addE("校门","实验楼",2,"D路");

    dg.addE("校门","宿舍",8,"E路");

    dg.addE("宿舍","澡堂",5,"F路");

    dg.addE("宿舍","食堂",2,"G路");

    dg.addE("实验楼","教学楼",3,"H路");

    dg.addE("实验楼","食堂",10,"I路");

    dg.addE("操场","食堂",6,"J路");

    while(true)

    {

     cout<<"歡迎來到校園導遊系統"<     cout<<"---------------------------------------------"<     cout<<"請輸入指令："<     cout<<"1:景點和路線操作"<     cout<<"2：尋找最短路徑"<     cout<<"0：退出系統"<     cout<<"---------------------------------------------"<     cout<<"請選擇。"<     cin>>input;

        if(input=="0")break;

        else if(input=="1")

        {

            while(true)

            {

             cout<<"---------------------------------------------"<             cout<<"請輸入指令"<             cout<<"1:增加景點"<             cout<<"2:刪除景點"<             cout<<"3:增加路線"<             cout<<"4:刪除路線"<             cout<<"5:更改景点名"<             cout<<"6:更改路线名"<             cout<<"7:查询景点信息"<             cout<<"8:更改景点信息"<             cout<<"9:查看導遊圖信息"<             cout<<"0:返回上級菜單"<             cout<<"---------------------------------------------"<             cin>>input;

                if(input=="1")

                {

                    string info;

                 cout<<"請輸入景點名稱和景点简介"<                 cin>>input;

                 cin>>info;

                    dg.addV(input,info);

                 cout<<"添加成功"<                }

                else if(input=="2")

                {

                 cout<<"請輸入景點名稱"<                 cin>>input;

                    dg.DeleteV(input);

                 cout<<"刪除成功"<                }

                else if(input=="3")

                {

                 cout<<"輸入兩個景點的名稱，再輸入道路名稱，再輸入長度，中間以空格分開"<                    string v1="";

                    string v2="";

                    int road_length;

                 cin>>v1;

                 cin>>v2;

                 cin>>input;

                 cin>>road_length;

                    dg.addE(v1,v2,road_length,input);

                 cout<<"添加成功"<                }

                else if(input=="4")

                {

                 cout<<"輸入兩個景點的名稱"<                    string v1="";

                    string v2="";

                 cin>>v1;

                 cin>>v2;

                    dg.DeleteE(v1,v2);

                 cout<<"刪除成功"<                }

                else if(input=="5")

                {

                 cout<<"请输入原景点名和更改后的景点名字，用空格分开"<                    string v1="";

                    string v2="";

                 cin>>v1;

                 cin>>v2;

                    dg.change_vertex_name(v1,v2);

                }

                else if(input=="6")

                {

                 cout<<"请输入两个景点的名字和更改后的道路名和道路长度，用空格分开"<                    string v1="";

                    string v2="";

                    int length=0;

                 cin>>v1;

                 cin>>v2;

                 cin>>input;

                 cin>>length;

                    dg.change_road_name(v1,v2,input,length);

                }

                else if(input=="7")

                {

                 cout<<"请输入景点的名字"<                 cin>>input;

                    dg.get_info(input);

                }

                else if(input=="8")

                {

                 cout<<"请输入景点名字和景点信息"<                    string info;

                 cin>>input;

                 cin>>info;

                    dg.change_info(input,info);

                 cout<<"更改成功"<                }

                else if(input=="9")

                {

                 cout<                }

                else if(input=="0")break;

                else {cout<<"輸入非法，請檢查輸入。"<            }

        }

        else if(input=="2")

        {

            int** l;

            int** kay;

            int n=dg.n;

            kay=new int*[n+1];

            l=new int*[n+1];

            for(int i=1;i<=n;i++)

            {

                l[i]=new int[n+1];

                kay[i]=new int[n+1];

            }

            dg.allpair(kay,l);

            //以上初始化一些東西

            while(true)

            {

             cout<<"---------------------------------------------"<             cout<<"請輸入指令"<             cout<<"1:兩景點間所有路徑"<             cout<<"2:兩景點間最短路徑"<             cout<<"3:多個景點間最短路徑"<             cout<<"0:返回上級菜單"<             cout<<"---------------------------------------------"<             cin>>input;

                if(input=="0")break;

                else if(input=="1")

                {

                    string v1="";

                    string v2="";

                 cout<<"請輸入兩點的名稱，中間以空格分開"<                 cin>>v1;

                 cin>>v2;

                    dg.Output_allpath(v1,v2);

                }

                else if(input=="2")

                {

                    string v1="";

                    string v2="";

                 cout<<"請輸入兩點的名稱，中間以空格分開"<                 cin>>v1;

                 cin>>v2;

                    dg.Output_path(v1,v2,kay,l);

                }

                else if(input=="3")

                {

                 cout<<"請輸入途徑景點的名稱，以空格分開，輸入回車結束"<                    cin.ignore(numeric_limits ::max(),'\\n');

                    getline(cin,input);

                    stringstream ss;

                    ss.clear();

                    ss.str(input);

                    int count=0;

                    string string_temp[100];

                    for(int i=0;i<100;i++)

                    {

                     ss>>string_temp[i];

                        count++;

                        if(ss.eof())break;

                    }

                    string* string_target=new string[count];

                    for(int i=0;i                    {

                        string_target[i]=string_temp[i];

                    }

                    /*for(int i=0;i                    {

                     cout<                    }

                 cout<                    dg.Output_route(l,kay,string_target,count);

                }

                else{cout<<"輸入非法，請檢查輸入"<            }

        }

        else{cout<<"輸入非法，請檢查輸入。"<        

    }

}//main方法负责所有与用户交互的处理