數(shù)據(jù)結(jié)構(gòu)迷宮問題實(shí)驗(yàn)報告

竭誠為您提供優(yōu)質(zhì)文檔/雙擊可除數(shù)據(jù)結(jié)構(gòu)迷宮問題實(shí)驗(yàn)報告

篇一：數(shù)據(jù)結(jié)構(gòu)-迷宮-實(shí)驗(yàn)報告與代碼

一．需求分析

本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認(rèn)后程序自動運(yùn)行，當(dāng)迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標(biāo)記所走過的路徑結(jié)束程序；當(dāng)迷宮無路徑時，提示輸入錯誤結(jié)束程序。程序執(zhí)行的命令：1創(chuàng)建迷宮；2求解迷宮；3輸出迷宮求解；

二．算法設(shè)計(jì)

本程序中采用的數(shù)據(jù)模型，用到的抽象數(shù)據(jù)類型的定義，程序的主要算法流程及各模塊之間的層次調(diào)用關(guān)系

程序基本結(jié)構(gòu)：

設(shè)定棧的抽象數(shù)據(jù)類型定義：

ADTstack{

數(shù)據(jù)對象：D={ai|ai∈charset，i=1,2,3,?..,n,n>=0;}

數(shù)據(jù)關(guān)系：R={|ai?1，ai∈D,i=2,?,n}

設(shè)置迷宮的抽象類型

ADTmaze{

數(shù)據(jù)對象：D={ai|ai∈‘’，‘@’，‘#’，‘1’,i=1,2,?,n,n>=0}數(shù)據(jù)關(guān)系：R={r,c}

r={|ai-1,ai∈D,i=1,2,?,n,}

c=|ai-1,ai∈D,i=1,2,?,n,}

結(jié)構(gòu)體定義：

typedefstruct//迷宮中x行y列的位置

{intx;

inty;

}posType;

typedefstruct//棧類型

{intord;//通道塊在路徑上的“序號”

posTypeseat;//通道塊在迷宮中的“坐標(biāo)位置”

intdi;//從此通道塊走向下一通道塊的“方向”

}mazeType;

typedefstruct

{mazeType*base;

mazeType*top;

intstacksize;

}mazestack;

基本函數(shù)：

statusInitstack(mazestack

if(!s.base)

exit(oVeRFLow);

s.top=s.base+s.stacksize;

s.stacksize+=sTAcKIncRemenT;

}

*s.top++=e;

returnoK;

}

2）出棧操作

statuspop(mazestack

e=*--s.top;

returnoK;

}

3）判斷棧是否為空

statusstackempty(mazestack

returneRRoR;

}

4）迷宮路徑求解

statusmazepath(posTypestart,posTypeend)//迷宮路徑求解{

posTypecurpos;

mazestacks;

mazeTypee;

intcurstep;

Initstack(s);

curpos=start;//設(shè)定當(dāng)前位置為入口位置curstep=1;//探索第一步

cout{

if(pass(curpos))//當(dāng)前位置可以通過，即是未曾走到的通道塊{

Footprint(curpos);//留下足跡

e.ord=curstep;

e.seat=curpos;

e.di=1;

push(s,e);//加入路徑

if(curpos.x==end.x

returnTRue;//到達(dá)終點(diǎn)（出口）

}

curpos=nextpos(curpos,e.di);//下一位置是當(dāng)前位置的東鄰

++curstep;//探索下一步

}

else//當(dāng)前位置不能通過

{

if(!stackempty(s))

{

pop(s,e);

while(e.di==4//留下不能通過的標(biāo)記pop(s,e);

cout}

if(e.di{

++e.di;//換下一個方向探索

篇二：數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報告-迷宮問題

實(shí)驗(yàn)報告：迷宮問題

題目：編寫一個求解迷宮通路的程序

一、需求分析：

1)采用二維數(shù)組maze[m][n]來表示迷宮，其中：maze[0][j]和maze[m-1][j](0≤j≤n-1)及maze[i][0]和maze[i][n-1](0≤i≤m-1)為添加在迷宮外圍的一圈障礙。數(shù)據(jù)元素值0表示通路，1表示障礙。限定迷宮的大小m≤8，n≤10.

2)本次實(shí)驗(yàn)直接在主程序中輸入表示迷宮的二維數(shù)組。另外，迷宮的入口和出口位置都將在主程序中直接設(shè)置。

3)實(shí)驗(yàn)中求出的迷宮通路用“-”表示，迷宮的障礙用“#”表示，已走過但未能求出通路的路徑用“@”表示。

4)本程序只求出一條成功的通路。

5)本次實(shí)驗(yàn)將直接輸出構(gòu)建迷宮的二維數(shù)組、初始化的二維數(shù)組和求解后的迷宮數(shù)組。

二、概要設(shè)計(jì)：

數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義。

（1）棧的抽象數(shù)據(jù)類型

ADTstack{

數(shù)據(jù)對象：D={ai|ai∈charset,i=1,2?n,n>=0}

數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2,?n}

基本操作：

Initstack(,#,@,*},0基本操作：

Initmaze(

#defineRAnge20//RAnge為實(shí)際分配的空間行列數(shù)

#definem8//maze數(shù)組的行數(shù)

#definen11//maze數(shù)組的列數(shù)

typedefstruct//表達(dá)迷宮元素位置信息的坐標(biāo)

{

intr,c;

}posType;

typedefstruct//m，n為待處理的迷宮的行列數(shù)，RAnge為實(shí)際分配的空間行列數(shù){

intm,n;

chararr[RAnge][RAnge];

}mazeType;

typedefintdirectiveType;//東西南北方向用1，2，3，4整數(shù)對應(yīng)

typedefstruct//路徑擬用棧來存儲，此處定義棧元素中數(shù)據(jù)域的信息{

intstep;//存儲到達(dá)該點(diǎn)時經(jīng)歷的步數(shù)

posTypeseat;//該點(diǎn)位置

directiveTypedi;//從該點(diǎn)位置走向下一位置的方向

}elemType;

typedefstructnodeType//路徑擬用鏈棧來存儲

{

elemTypedata;

structnodeType*next;

}nodeType,*LinkType;

typedefstruct//對鏈棧的頭指針和元素個數(shù)進(jìn)行封裝

{

LinkTypetop;

intsize;

}stack;

//以上是對存儲結(jié)構(gòu)逐層進(jìn)行定義

voidInitstack(stack

s.size=0;

}

statusmakenode(LinkType

if(!p)

returnFALse;

p->data=e;

p->next=nuLL;

returnTRue;

}

statuspush(stack

if(makenode(p,e))

{

p->next=s.top;

s.top=p;

s.size++;

returnTRue;

}

returnFALse;

}

statusstackempty(stacks)

{//判斷是否為空棧，這里是通過top指針為nuLL來判斷的，本質(zhì)上也可以通過size是否為0來判斷

if(s.top==nuLL)

returnTRue;

returnFALse;

}

statuspop(stack

if(stackempty(s))

returnFALse;

else

{

p=s.top;

s.top=s.top->next;

e=p->data;

s.size--;

free(p);

returnTRue;

}

}

statuspass(mazeTypemaze,posTypecurpos)

{//判斷迷宮maze中，當(dāng)前位置curpos是否是一個可達(dá)位置

intm,n;//注意這里的m，n只是表達(dá)下標(biāo)的臨時變量，與前面出現(xiàn)的m，n是不一樣的

m=curpos.r;

n=curpos.c;

if(maze.arr[m][n]==)

returnTRue;

returnFALse;

}

statussame(posTypecurpos,posTypeend)

{//判斷當(dāng)前位置curpos是否已達(dá)出口

if(curpos.r==end.r

returnFALse;

}

voidFootprint(mazeType

m=curpos.r;

n=curpos.c;

maze.arr[m][n]=-;

}

posTypenextpos(posTypecurpos,intdi)

{//通過di的值，確定下一步的位置，下一步位置實(shí)際是當(dāng)前位置的四個鄰居中的一個

switch(di)

{

case1:

curpos.c++;//向東走

break;

case2:

curpos.r++;//向南走

break;

case3:

curpos.c--;//向西走

break;

篇三：數(shù)據(jù)結(jié)構(gòu)迷宮問題實(shí)驗(yàn)報告

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》

迷宮問題實(shí)驗(yàn)報告

——實(shí)驗(yàn)二

專業(yè)：物聯(lián)網(wǎng)工程

班級：物聯(lián)網(wǎng)1班

學(xué)號：15180118

姓名：劉沛航

一、實(shí)驗(yàn)?zāi)康?/p>

本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認(rèn)后程序自動運(yùn)行，當(dāng)迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標(biāo)記所走過的路徑結(jié)束程序；當(dāng)迷宮無路徑時，提示輸入錯誤結(jié)束程序。

二、實(shí)驗(yàn)內(nèi)容

用一個m*m長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個程序?qū)τ谌我庠O(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。

三、程序設(shè)計(jì)

1、概要設(shè)計(jì)

（1）設(shè)定棧的抽象數(shù)據(jù)類型定義ADTstack{

數(shù)據(jù)對象：D={ai|ai屬于charset，i=1、2…n，n>=0}

數(shù)據(jù)關(guān)系：R={|ai-1,ai屬于D，i=2,3,…n}

基本操作：

Initstack(//迷宮中的行

intcol;//......的列

}posType;//坐標(biāo)

（2）迷宮類型：

typedefstruct{

intm,n;

intarr[RAnge][RAnge];

}mazeType;//迷宮類型

voidInitmaze(mazeType//當(dāng)前位置在路徑上的"序號"

posTypeseat;//當(dāng)前的坐標(biāo)位置

DirectiveTypedi;//往下一個坐標(biāo)位置的方向

}selemType;//棧的元素類型

typedefstruct{

selemType*base;

selemType*top;

intstacksize;

}sqstack;

棧的基本操作設(shè)置如下：

VoidInitstack（sqstack

posTypecurpos=start;

intcurstep=1;//探索第一部

do{

if(pass(maze,curpos)){//如果當(dāng)前位置可以通過,即是未曾走到的通道塊

Footprint(maze,curpos);//留下足跡

e=creat