|
二．设计思路 校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用狄克斯特拉（Dijkastra）算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径。 内容来自论文无忧网 www.paper51.com
三．详细设计过程 3.1 景点基本信息的设计 http://www.paper51.com 为了方便操作，每一个景点名称用一个代码表示，因此景点基本信息设计成结构体类型，此类型包含两个成员变量：景点名称及其代码。在此我设计了10个景点，具体如下： 内容来自论文无忧网 www.paper51.com struct Sight 内容来自论文无忧网 www.paper51.com
{ 内容来自论文无忧网 www.paper51.com charName[40]; http://www.paper51.com int Num; 内容来自论文无忧网 www.paper51.com }W[10] = {{"柳池", 1},{"北山体育场", 2},{"龙山体育场", 3},{"老区图书馆", 4}, http://www.paper51.com {"西科花园", 5},{"科技中心", 6}, {"行政楼", 7},{"九洲湖",8}, copyright paper51.com {"逸夫图书信息中心",9},{"新区运动场",10}}; 内容来自论文无忧网 www.paper51.com
3.2 顺序表的设计 paper51.com 一个景点存在自己的名字和代码等信息，两个景点之间有一个距离，由于系统模拟中要用到这些参数，因此可用顺序表来存储这些参数。 http://www.paper51.com 在顺序表中频繁存取数据，必然少不了存取操作，因此顺序表中需要设计一个插入函数void Insert(DataType &item,int pos)const和一个删除函数DataType Delete(const intpos) 。当在顺序表的pos存入一个数据item时,pos后的每一个元素依次后移；当删除pos处的数据元素时，pos后的元素依次前移。当求最短路径时需要取某个景点或某条路径的值，所以还需设计取值函数DataType GetData( int pos)const。另外顺序表中的一些基本函数也是必须设计的，如：取表中元素个数的函数int ListSize(void) const ；判断表空否的函数int ListEmpty(void) const 等。 paper51.com 3.3 图类的设计 paper51.com 图类的私有部分有结点信息的顺序表SeqList Vertices ，边的条数int numOfEdges ，景点间的距离取决于两景点，所以用一个二位数组int Edge[MaxVertices][MaxVertices]存储。 内容来自论文无忧网 www.paper51.com 有了这些条件后，需要将校园的景点、景点间距离等作为图的结点值、边的权值等构造一个图，所以图类中成员函数必须有取结点值的函数VerT GetValue(const int i) 、取边权值的函数int GetWeight(const int v1, const int v2)const 、插入结点的函数void InsertVertex(const VerT&vertex) 和插入边的函数voidInsertEdge(const int v1, const int v2, int weight) 。这几个函数的设计如下： paper51.com VerT AdjMWGraph::GetValue(const int i) //取结点i的值 内容来自www.paper51.com { http://www.paper51.com if(i< 0 || i > Vertices.ListSize()) http://www.paper51.com { paper51.com
cout<<"The 'i' is over the data!" <<endl; copyright paper51.com exit(0); 内容来自www.paper51.com } paper51.com returnVertices.GetData(i); copyright paper51.com } copyright paper51.com int AdjMWGraph::GetWeight(const int v1, const int v2) //取边<v1,v2>的权值 内容来自论文无忧网 www.paper51.com { 内容来自www.paper51.com if(v1< 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 >Vertices.ListSize()) copyright paper51.com { 内容来自论文无忧网 www.paper51.com cout<<"The 'v1' and 'v2' are over data!" <<endl; http://www.paper51.com exit(0); copyright paper51.com } 内容来自www.paper51.com
returnEdge[v1][v2]; paper51.com } 内容来自论文无忧网 www.paper51.com
void AdjMWGraph::InsertVertex(const VerT &vertex) //插入结点vertex 内容来自www.paper51.com
{ copyright paper51.com Vertices.Insert(vertex,Vertices.ListSize()); http://www.paper51.com
} copyright paper51.com //插入边<v1,v2>,权值为weight copyright paper51.com void AdjMWGraph::InsertEdge(const int v1, const int v2, int weight) http://www.paper51.com
{ copyright paper51.com if(v1< 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 >Vertices.ListSize()) copyright paper51.com
{ 内容来自论文无忧网 www.paper51.com cout<<"The 'v1' and 'v2' are over data!" <<endl; 内容来自论文无忧网 www.paper51.com exit(0); copyright paper51.com
} http://www.paper51.com copyright paper51.com Edge[v1][v2]= weight; 内容来自www.paper51.com numOfEdges++; 内容来自论文无忧网 www.paper51.com
} paper51.com |