2023年數據結構實驗報告圖與景區(qū)

學生學號實驗課成績

忒隆理7大考

學生實驗報告書

實驗課程名稱數據結構與算法綜合實驗

開課學院計算機科學與技術學院

指導教師姓名

學生姓名

學生專業(yè)班級

2022

2023

3學年第學期

實驗課程名稱：數據結構與算法綜合實驗

實驗項目名稱圖與景區(qū)信息管理系統(tǒng)實踐報告成績

實驗者專業(yè)班級組別

同組者完畢日期2023年5月23日

第一部分:實驗分析與設計（可加頁）

一、實驗目的和規(guī)定

1.目的

?掌握圖的定義和圖的存儲結構。

?掌握圖的創(chuàng)建方法和圖的應用

?使用C++語言，定義圖的數據結構,結合迭代開發(fā)思緒實現“景區(qū)信息管理系統(tǒng)”。

=掌握圖的兩種遍歷方法和應用。

=使用C++語言和深度優(yōu)先算法實現“旅游景點導航”功能開發(fā)。

?掌握迪杰斯特拉算法和應用。

?使用C++語言和迪杰斯特拉算法實現“搜索最短途徑”功能開發(fā)。

?理解最小生成樹的概念，掌握普里姆算法和應用。

=使用C++語言和最小生成樹算法實現“鋪設電路規(guī)劃”功能開發(fā)。

2.規(guī)定

=開發(fā)景區(qū)信息管理系統(tǒng),對景區(qū)的信息進行管理。

?使用圖的數據結構來保存景區(qū)景點信息，為用戶提供創(chuàng)建圖、查詢景點信息、旅

游景點導航、搜索最短途徑、鋪設電路規(guī)劃等功能。

二、分析與設計

（1）創(chuàng)建工程讀取文獻信息，創(chuàng)建圖，輸出周邊景點信息讀取景區(qū)信息文獻，采用

圖的存儲結構，創(chuàng)建景區(qū)景點圖，查詢景點信息。

（2）迭代開發(fā)，進行深度優(yōu)先搜索，實現旅游景點導航。

⑶繼續(xù)迭代，采用迪杰斯特拉算法、普里姆算法，實現搜索最短途徑和電路鋪

設，開發(fā)景區(qū)信息管理系統(tǒng)。

1.數據結構的設計

?記錄頂點信息的結構體

structVex

{

。intnum;〃景點編號

。charname[20];〃景點名字

。chardesc[1024];//景點介紹

}；

=記錄邊的信息的結構體

structEdge

(

intvexl；〃邊的第一個頂點

。intvex2；〃邊的第二個頂點

intweight；//權值

};

=用來保存途徑的鏈表的結構體

typedefstructPath

{

intvexs[20];〃保存一條途徑

。Path*next;

}*PathList;

?CGraph類用來實現相應功能的方法

classCGraph

(

private：

。intm_aAdjMatrix[20][20]；//鄰接矩陣

。Vexm_aVexs[20];〃頂點信息數組

。intmnVexNum;〃當前圖的頂點個數

public:

voidTnit(void);

。boolInsertVex(VexsVex);

boolInsertEdge(EdgesEdge)；

VexGetVex(intnVex);

。intGetVexnum(void);

。intFindEdge(intnVex,EdgeaEdge[])；

voidDFS(intnVex,boo1aVisited[],int&nIndex,PathList&pList);

。voidDFSTraverse(intnVex,PathList&pList);

intFindShortPath(intnVexStart,intnVexEnd,EdgeaPath[]);

voidFindMinTree(EdgeaPath口);

)；

2.核心算法設計

(1)輸出周邊景點信息

Input:操作表號與景點編號

Output:輸入景點的周邊景點信息

Process:

intCGraph::FindEdge(int.nVex,EdgeaEdge[])

(

0

。intk=0;

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

(

if(m_aAdjMatrix[nVex][i]!=0)

0{

。aEdge[k].vexl=nVex；

t>。aEdge[k].vex2=i;

。aEdge[k].weight=m_aAdjMatrix[nVex][i];

。k++;

°}

)

。returnk;〃返回邊的條數

)

(2)深度優(yōu)先搜索算法實現旅游景點導航

Input:操作表號與景點編號

Output：從輸入景點出發(fā)走遍整個景區(qū)的各種路線方案

Process:

voidCGraph::DFS(intnVex,boo1aVisited口，int&nTndex,PathList&pList)

(

oaVisited[nVex]=true;〃改為已訪問

。pList->vexs[nlndex++]=nVex;//訪問頂點

?！ㄅ袛嗍欠袼泄?jié)點都已訪問過

intnVexNum=0;

ofor(inti=0;i<mnVexNum;i++)

(

oif(aVisited[i])nVexNum++；

6)

。?！ㄋ许旤c都被訪問過

。if(nVexNum==m_nVexNum)

(

〃新增鏈表節(jié)點,保存本次遍歷的途徑

。pList->next=(PathList)malloc(sizeof(Path))；

ofor(inti=0;i<m_nVexNum；i++)

00{

pList->next->vexs[i]=pList->vexs[i]；

。}

。pList=pList—>next;

。opList->next=NULL;

。)

e1se

6{

。//按頂點的存儲順序，查找當前頂點相連的的頂點

for(inti=0;i<mnVexNum；i++)

(

?！葲]有遍歷過,又與當前頂點相連的頂點

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

。(

。。?！ㄒ栽擁旤c為起點遍歷剩下的頂點

。DFS(i,aVisited,nlndex,pList)；

。。。。aVisited[i]:false;〃訪問狀態(tài)置空

。o。nIndex—;〃回溯

00)

voidCGraph：:DFSTraverse(intnVex,PathList&pList)

{

。intn!ndex=0；

boo1aVisited[MAX_VERTEX_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?VERTEXNUM]；//保存最短距離

boo1aVisited[MAX_VERTEX_NUM];//判斷某頂點是否已經加入到最短途徑

。//初始化

。intv;

。for(v=0;v<mnVexNum;v++)

。(

。。aVisited[v]=false;

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

//初始化該頂點到其他頂點的最短距離,默認為兩點間的距離

。nShortDistance[v]=m_aAdjMatrix[nVexStart][v]；

。e1se

?！偃珥旤ci和nVexStart不相連,則最短距離設為最大值

nShortDistanee[v]=0x7FFFFFFF;

。nShortPath[v][0]=nVexStart;//起始點為nVexStart

for(int1;j<m_nVexNum；j++)

nShortPath[v][j]=-1；〃初始化最短途徑

)

//初始化,nVexStart頂點加入到集合中

aVisited[nVexStart]=true；

。intmin;

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

0{

。。min=0x7FFFFFFF;

。boo1bAdd二false;〃判斷是否尚有頂點可以加入到集合中

ofor(intj=0;j<mnVexNum;j++)

。(

t>ooif(aVisited[j]—false)

00(

。oif(nShortDistance[j]<min)

°{

。。。。v二j;〃j頂點離nVexSlarl頂點最近

。。。min=nShortDistance[j];〃)到門丫exStart的最短距離為min

。。bAdd=true;

000)

6001

。}//假如沒有頂點可以加入到集合，則跳出循環(huán)

oif(bAdd==fa1se)

00{

?break;

)

。aVisited[v>true；//將頂點j加入到集合

nShortPath[v][i]=v；//將頂點j保存到nVexStart到j的最短途徑里

t>for(intw=0;w<mnVexNum;w++)

(

//將w作為過度頂點計算rWexStart通過w到每個頂點的距離

。if(aVisited[w]==false&&(min+m_aAdjMatrix[v][w]<nShortDistance_a

AdjMatrix[v][w]!=0)

000(

。〃更新當前最短途徑及距離

。。。nShortDistance[w]=min+m_aAdjMatrix[v][w];

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

0oo(

。。。?！偃缤ㄟ^W到達頂點i的距離比較短，則將W的最短途徑復制給i

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

0Of

00)

。)

)

intnlndex=0；

。intnVexl=nVexStart;

//將最短途徑保存為邊的結構體數組

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

oif(nShortPath[nVexEnd][i]!=-l)

。(

aPath[nIndex].vex1=nVex1;

aPath[nIndex].vex2=nShortPath[nVexEnd][i]；

oaPath[nlndex].weight=m_aAdjMatrix[aPath[nlndex].vexl][aPath[nlnd

ex].vex2];

。。nVexl=nShortPath[nVexEnd][i];

。nlndex++;

。)

。)

t>returnnIndex;

)

(4)普里姆算法構建最小生成樹

Input:輸入操作編號

Output：得到最小生成樹的途徑

Process:

voidCGraph::FindMinTree(EdgeaPath[])

(

boolaVisited[MAX_VERTEX_NUM];〃判斷某頂點是否在最小生成樹頂點集合里

。for(inti=0；i<MAX_VERTEX_NUM;i++)

{

。aVisited[i]=false;

b}

。aVisited[0]=true；〃。頂點加入到集合中

。intmin;

。intnVexl,nVex2；

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

(

。min=0x7FFFFFFF;

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

00{

if(aVisited[i])〃從集合中取一個頂點

。(

。for(intj=0;j<m_nVexNum;j+4-)

d0{

。。if(!aVisited[j])〃從不在集合的頂點中取出一個頂點

00{

。3if((m_aAdjMatrix[i][j]<min)&&(m_aAdjMatrix[i][j]!=0))

0a(

o。。nVexl=i;

。ooonVex2=j;

。o。。。min=m_aAdjMatrix[i][j];〃找出最短的邊

6bO}

6)

00}

0}o

//保存最短邊的兩個頂點

aPath[k].vexl=nVexl;

aPath[k].vex2=nVex2；

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

〃將兩個頂點加入到集合

。aVisited[nVexl]=true;

aVisited[nVex2]=true;

3.測試用例設計

?使用實驗所規(guī)定的圖創(chuàng)建兩個文本文獻，對文獻進行讀取，觀測其相關功能的實

現。

三、重要儀器設備及耗材

1.安裝了Windows10或其它版本的Windows操作系統(tǒng)的PC機1臺

2.PC機系統(tǒng)上安裝了MicrosoftVisualStudio2023開發(fā)環(huán)境

第二部分:實驗過程和結果(可加頁)

一、實現說明

使用MircosoftVisua1Studio2023開發(fā)工具，創(chuàng)建一個空的控制

臺工程。運用圖的存儲結構來保存景區(qū)景點圖，使用C++語言開發(fā)景區(qū)信息管理系

統(tǒng)，工程名為GraphCPro。

(1)添加Graph,h文獻，用來定義圖的數據結構,實現圖的相關操作。

(2)添加Tourism.h文獻,用來實現景區(qū)信息管理系統(tǒng)的相關功能。Touri

sm.h存放與Tourism.cpp相關函數的數據類型的定義，函數原型的聲明等。

(3)添加Main.cpp文獻,在文獻中創(chuàng)建程序入口函數intmain(void)o

調用Tourism.h中的相關函數實現相應功能。

二、調試說明（調試手段、過程及結果分析）

調試的重要內容為編寫程序的語法對的性與否，程序邏輯的對的性與否。

調試手段重要采用了MircosoftVisualStudio2023集成開發(fā)環(huán)境中

的“開始執(zhí)行（Ctrl+F5）”運營并測試,和Fl1“逐語句調試”、F12“逐過程

調試”、F9“切換斷點”、ctrl+B“新建斷點”等。

三、軟件測試（測試效果.界面、綜合分析和結論）

1.測試效果界面

-A

區(qū)O-

-BI區(qū)

-CI區(qū)

區(qū)

-D田I

區(qū)

田

區(qū)

Nh

-G_I-

>V27^^

V0->56oo

Voo

V0->V41o

>61oo

V0-Vooo

V1->V21ooO

V1->V34oo

V2->V43oo

V3->V64oo

V3->V56oo

V4->V65oo

V5-

語輸入選項（0~5）:2

否而景點信息

）—A區(qū)

1—B區(qū)

2—C區(qū)

3—D區(qū)

工一E區(qū)

5—F區(qū)

5―G區(qū)

清輸入想要杏詢的景點編號：3

）區(qū)

風景優(yōu)美，景色宜人

---------周邊景區(qū)--------

）區(qū)->（:區(qū)400m

）l1->Elg300m

）區(qū)一二區(qū)400m

===============旅游景點導航==============

0-A區(qū)

1-B區(qū)

2-C區(qū)

3-D區(qū)

4-E區(qū)

5-F