2025年数据结构与算法可视化解析及旅游景观优化策略

学生学号试验课成绩

或修理）上等

学生实验报告书

试验课程名称数据构造与算法综合试验

开课学院计算机科学与技术学院

指导教师姓名

学生姓名

学生专业班级

年第2学期

试验课程名称：数据构造与算法综合试验

试脸项目名称图与景区信息管理系统实践汇报成绩

试验者专业班级组别

同组者完毕日期5月23日

第一部分：试验分析与设计(可力口页)

一、试验目的和规定

1.FI的

•掌握图的定义和图的存储构造。

•掌握图的创立措施和图的应用

•使用C++语言，定义图的数据构造，结合迭代开发思绪实现“景区信息管理系统”。

•掌握图的两种遍历措施和应用。

•使用C++语言和深度优先算法实现“旅游景点导航”功能开发。

•掌握迪杰斯特拉算法和应用。

•使用C++语言和迪杰斯特拉算法实现“搜索最短途径”功能开发。

•理解最小生成树的概念，掌握普里姆算法和应用。

•使用C++语言和最小生成树算法实现“铺设电路规划”功能开发。

2.规定

•开发景区信息管理系统，对景区的信息进行管理。

•使用图的数据构造来保留景区景点信息，为顾客提供创立图、查询景点信息、旅

游景点导航、搜索最短途径、铺设电路规划等功能。

二、分析与设计

(1)创立工程读取文献信息，创立图，输出周围景点信息读取景区信息文献，采用图的存储

构造，创立景区景点图，查询景点信息。

(2)迭代开发，进行深度优先搜索，实现旅游景点导航。

⑶继续迭代，采用迪杰斯特拉算法、普里姆算法，实现搜索最短途径和电路铺

设，开发景区信息管理系统。

1.数据构造的设计

•讥录顶点信息的构造佃

structVex

(

ininum;〃景点编号

charname[20];〃景点名字

chardesc[1024];〃景点简介

)；

・记录边的信息的构造体

structEdge

(

intvexl;〃边的第一种顶点

intvex2;//边的第二个顶点

int哪eight;//权值

)；

•用来保留途径的链表的构造体

typedefstructPath

(

intvexs[20];//保留一条途径

PuLh;

)*PathLisl;

•CGraph类用来实现对应功能的措施

classCGraph

(

private:

intm,aAdjMatrix[2O][20];//邻接矩阵

Vexm_aVexs[20];//顶点信息数组

intm_nVexNum;//目前图的顶点个数

public:

voidInit(void):

boolInscrtVcx(VexsVex);

boolInsertEdge(EdgesEdge)：

VexGetVex(intnVex);

intGetVexnum(void);

intFindEdge(intnVex,EdgeaEdge[]);

voidDFS(intnVex,boolaVisited[],int&nlndex,PathListfepList);

voidDFSTraverse(intnVex,PathList&pLisi);

intFindShortPath(intnVcxStart,intnVcxEnd,EdgeaPath[]);

voidFindMinTree(EdgeaPath[]):

)；

2.关键算法设计

（1）输出周围景点信息

Input:操作表号与景点编号

Output:输入景点的周围景点信息

for(inti=0:i<mnVexNum：i++)

(

〃既没有遍历过，又与目前顶点相连的顶点

if(!aVisited[i]&&(m_aAdjMalrix[nVex][i]>0))

(

//以该顶点为起点遍历剩余的顶点

DFS(i,aVisited,nlndex,pList);

aVisited[i]=false;〃访问状态置空

nIndex—;〃l可溯

}

)

)

voidCGraph::DFSTraverse(intnVex,PathList&pl.ist)

(

intnIndcx=0：

boolaVisitedtMAXVERTEX_NUM]={false)：

DFS(nVex,aVisited,nlndex,pList);

)

(3)Dijkstra算法搜索最短途径

Input:操作表号与起始景点编号

Output:从起始顶点到终点的最短途径

Process:

intCGraph::FindShortPath(intnVexStart,intnVexEnd,EdgeaPath[])

(

intnShortPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃保留破用途径

intnShortDistance[MAX_VERTEX_NUM]"/保留最短距离

boolaVisitcd[MAX_YERTEX一NUN];//判断某顶点与否已经加入到最短途径

〃初始化

intv;

for(v=0：v<m_r)VexNum;v++)

{

aVisited[v]=false;

if(m_aAdjMatrix[nVexStart][v]!=0)

〃初始化该顶点到其他顶点的最短距离，默认为两点间的距离

nShortDistance[v]=m_aAdjMatrix[nVexStart][v]：

else

〃假如顶点i和nVexStart不相连，则最短距离设为最大值

nShortDistance[v]=0x7FFFFFFF;

nShortPath[v][0]=nVexStart;〃起始点为nVexStarl

for(intj=l;j<m_nVexNum;j++)

nShortPath[Y][j]=T;//初始化最短途件

)

}

〃初始化，nVexSiart顶点加入到集合中

aVisited[nVexStart]=true;

intmin;

for(inti=l;i<m_nVexNum;i++)

(

min=0x7FFFFFFF;

boolbAdd=fa1se;//判断与否尚有顶点可以加入到集合中

for(intj-0;j<mnVexNum;j++)

{

if(aVisited[j]=false)

(

if(nShortDistance[j]<min)

(

v=j;〃j顶点离nVexStart顶点近来

min=nShortl)istancc[j];//j到nVoxStart的最短距离为min

bAdd=true;

}

}

}〃假如没有顶点可以加入到集合，则跳出循环

if(bAdd==false)

{

break;

}

aVisited[v]=true;}/将顶点j加入到集合

nShortPath[v][i]=v;〃将顶点j保留到nVexStart到j的最短途径里

for(intw=0;w<m_nVexNum;w++)

{

〃将w作为过庾顶点计算nVexStart®过w到每个顶点的距离

if(aVisited[w]==false&&(min+tn_aAdjMatrix[v][w]<nShortDistance[w])&&m_aAdjMatrix[v][w]!=0)

(

〃更新目前最短途径及距离

nShortDislance[w]=min+m_aAdjMatrix[v][w];

for(inti=0;i<m_nVexNum：i++)

(

〃假如通过w抵达顶点i的距高比较短，则将w的最短途径发制给i

nShortPath[w][i]=nShortPath[v][i];

}

}

)

)

intnIndex=0;

intnVcxl=nVcxStart;

//招最短途径保留为边的构造体数组

for(inti=l;i<mnVexNum;i++)

if(nShortPath[nVe>:End][i]!=-l)

(

aPath[nIndex].vexl=nVexl;

aPathCnlndex].vex2=nShortPath[nVexEnd][i];

aPath[nIndex].weight=m_aAdjMatrix[aPath[nlndex].vexl][aPathtnlndex].vex2];

nVexl=nShortPath[nVexEnd][i];

nlndex++;

}

)

returnnlndex;

)

(4)普里姆算法构建最小生成树

Input:输入操作编号

Output:得到最小生成树的途径

Process:

voidCGraph::FindMinTree(EdgeaPath口)

(

boolaVisited[MAX_VERTEX_NUM]://判断某顶点与杳在最小生成树顶点集合里

for(inti=0;i<MAX_VERTEX_NUM:i++)

{

aVisited[i]=falsc;

1

aYisiled[O]=true;〃。顶点加入到集合中

intmin;

intnVexl,nVex2:

for(intk=0;k<m_nVexNuin-1;k++)

min=0x7FFFFFFF;

for(inti=0：i<m_nVexNum;i++)

(

if(aVisited[iD〃从集合中取一种顶点

{

for(intj=0;j<m_nVexNum;j++)

{

if(ieVisitcd[j])『7从不在集合的顶点中取出一种顶点

(

if((maAdjMatrix[i][j]<min)&&(maAdjMatrix[i][j]!=0))

(

nVexl=i;

nVex2=j;

min=m_aAdjMatrix[i][j];〃找出一短的边

)

|

)

)

〃保留最短边的两个顶点

aPath[k].vexl=nVe>:l;

aPalh[k].vex2=nVe>.2;

aPath[k].weight=m_aAdjMatrix[nVexl][nVex2];

〃将两个顶点加入到集合

aVisited[nVexlJ=true;

aVisited[nVex2]=true:

3.测试用例设计

•使用试验所规定的图创立两个文本文献，对文献进行读取，观测其有关功能的实现。

三、重要仪器设备及耗材

1.安装了Windows10或其他版本的Windows操作系统的PC机1台

2.PC机系统上安装了MicrosoftVisualStudio开发环境

第二部分：试验过程和成果(可加页)

一、实现阐明

使用MircosoftVisualStudio开发工具，创立一种空的控制台工程。运用图的存储

构造来保留景区景点图，使用C++语言开发景区信息管理系统，工程名为GraphCPro。

(1)添加Graph」文献，用来定义图的数据构造，实现图的有关操作。

(2)添加Tourism,h文献，用来实现景区信息管理系统的有关功能。Tourism,h寄存

与Tourism,cpp有关函数的数据类型的定义，函数原型的申明等。

(3)添加Main,cpp文献,在文献中创立程序入匚函数intmain(void)。调用Tourism,h

中的有关函数实现对应功能。

调试阐明(调试手段、过程及成果分析)

调试的重要内容为编写程序的语法对的性与否，程序逻辑的对的性与否。调试手

段重要采用了MircosoftVisualStudio集成开发环境中的“开始执行（Ctrl+F5）”

运行并测试，和F11“逐语句调试”、E12“逐过程调试”、F9“切换断点”、ctrl+B

“新建断点”等。

三、软件测试（测试效果.界面、综合分析和结论）

L测试效果界面

一顶点------------一区

B区0A

一

c区

一

-D区

E区

一

F区

一

TG区

-Ni-

0>2X7^o

V二VI

/o

V0>V5\6o

/!

0>4\1oo

V二Vo

/!o

1>6\1oo

VV7o

V1二>V2\1oO

/!o

V2>V3\4o

/»o

V3二>V4\3oo

/!

V3>V64o

!\o

二/

V4>V5\6oo

/!

V5>V6\5oo

—/

济输入选项（0、5）:2

查询景点信息

3—A区

1—BIX

2—C区

3—D区

一E区

5—F区

5—G区

请输入想要查询的景点编号：3

）区

风景优美，景色宜人

----------周边景区---------

）IX->C区400m

）区-元区300m

2>G区400m

:旅游景点导航

0-A区

1-B区

2-C区

3-D区

4-E区

5-呕

6~G区

7・H区

请输入要查询的起点编号：

4

导游路线为：

路线1:E区->A区->区-AG区->9区-><7区,->D区-汨区

路线2:E区-油区->F区->G区-汨区-刈区->C区-与区

路线3:E区-〉D区-〉H区->6区->8区->C区->A区->F区

路线4:E区->D区-汨区-〉G区-万区-油区