迷宫实验报告

迷宫实验报告

————————————————————————————————作者：————————————————————————————————日期：

一、实验内容

3、迷宫问题。假设迷宫由m行ｎ列构成，有一个出口和一个入口,入口坐标为(1，1)，出口坐标为(m,n）,试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。

（1)用C语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。

(2)设计一个二维数组MAZE［m+２]［ｎ+２]表示迷宫，数组元素为0表示该位置可以通过,数组元素为1表示该位置不可以通行。MAZE［１][1］、ＭAZE[m][n]分别为迷宫的入口和出口。

(３）输入迷宫的大小ｍ行和n列,动态生成二维数组;由随机数产生0或1,建立迷宫,注意ｍ＊n的迷宫需要进行扩展,扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。

(4）要求输出模拟迷宫的二维数组;若存在最短路径，则有出口回溯到入口(出队列并利用栈实现),再打印从入口到出口的这条路径,例如（１,1），...．..,（i,ｊ)，......,(m，n)；若没有路径,则打印“No patｈ”。

(5）迷宫的任一位置(i,j)上均有八个可移动的方向,用二维数组Ｄireｃtｉon存放八个方向的位置偏移量。

Dｉrｅction[8]［２］={{0,１},{1,1},｛0，－1}，{-1，－1},｛1，-1｝，{1,0},{-１,0},{－1,１}}；

（6）为避免出现原地踏步的情况需要标志已经通过的位置,采用一个标志数组MARＫ[m＋２][ｎ+2］,初值均为0,在寻找路径的过程中，若通过了位置（i，j），则将MARＫ[ｉ］[ｊ］置为1。

（7）为了记录查找过程中到达位置(i,j)及首次到达（i,ｊ）的前一位置（i_pre,j＿pre）,需要记住前一位置（i_pｒe,j＿ｐre）在队列中的序号pｒe,即队列中数据元素应该是一个三元组(i，j,prｅ）。

（8）搜索过程简单下：将入口MＡＺE[１][1]作为第一个出发点，依次在八个方向上搜索可通行的位置,将可通行位置(i，j,pre）入队,形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置,形成第二层新的出发点,.．．,如此进行下去,直至达到出口ＭAZE［m］［n]或者迷宫所有位置都搜索完毕为止。

二、实验过程及结果

一、需求分析

１、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。

2、以二维数组M[m+2][n+2]表示迷宫，Ｍ[i]［j] 表示迷宫中相应(i,j)位置的通行状态(0：表示可以通行，1：表示有墙,不可通行),完成迷宫的抽象数据类型，包括出口、入口位置等。

３、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在5０以下）,完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过,如下例所示:

如下所示:

4、程序完成对迷宫路径的搜索,为了更好地显示出求解结果，如果存在路径，则以长方形形式将迷宫打印出来,而不是只按步输出坐标，也便于检查路径的正确性,用特定符号标出迷宫的物理状态,其中字符“＃”表示出口和入口，“<”标记出可行的路径；如果程序完成搜索后没有找到通路，则提示用户“NoＰath！”。如图所示:

５、程序执行的命令:

⑴创建初始化迷宫;

⑵搜索迷宫；

⑶输出搜索到的最短路径。

二、概要设计

(按照题目要求应该用队列实现路径的存储，但操作过程中遇到很多困难未能解决，故选择栈的操作来实现路径的存储)

1、迷宫的抽象数据类型定义:

ADT Maze{

数据对象:D：={aij,Sｔart,end|－20<=aｉj<20,Ｓtart,eｎｄ∈{(i，j)|０≤i≤m+2,0≤ｊ≤ｎ+２,m,ｎ≥0｝｝

数据关系：R=｛leｎgtｈ，ｗidth｝

??lengtｈ＝｛|ai－1,aij∈D i=１,…,ｍ+２,j=1，…,n+2}

wiｄｔｈ={|aijaｉj-１∈D}

基本操作:

SeｔMａze(＆M)

初始条件:Ｍ已经定义,Ｍ的下属单元二维数组M.Ｍａze[row＋2][d+２]已存在,M.ｓｔａrt，M．ｅnｄ也已作为下属存储单元存在

操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以１表示障碍，由终端读取迷宫空间大小,各点处的具体物理状态及Start和End点位置，完成迷宫构建Ｐasｓ(Ｍ, CurPｏs）

初始条件：已知目前迷宫状态及当前位置

操作结果：完成相应的搜索任务，如果可行，则返回１

NextPos(ＣｕｒPos,dｉrectionr)

操作结果:返回CurＰOS位置在方向ｄｉrectioｎ上的下一位置

SameSeat(Path,rｏw,cｏl)

操作结果:若(row,col）位置是路径Ｐath中的一个点,则返回TRＵＥ

ＰrintＭaze（Ｍ)

初始条件：迷宫M已存在

操作结果：输出字符标示的迷宫

MazｅPａth(M,&Ｐath)

初始条件：迷宫Ｍ已存在

操作结果：搜索迷宫，用path返回搜索所得路径。如不存在,返回０

PriｎtPａth(M,Ｐath)

初始条件：迷宫M已存在

操作结果：迷宫M存在可行路径则将迷宫M及相应最短路径一起打印输出

}AＤT MAZE；

⒊本程序模块结构

⑴主函数模块

voidｍain(){

初始化迷宫和栈;

创建迷宫；

输出迷宫;

搜索路径;

输出路径;

｝

⑵栈模块——实现栈抽象数据类型;

⑶迷宫模块——实现迷宫抽象数据类型；

各模块之间的调用关系如下：

?主程序模块

迷宫模块

栈模块

三、详细设计

１、基本数据类型操作

⑴栈模块

① tｙｐｅdef struｃt{

inｔｏrder；

Poｓiｔioｎｓeat;

?int ｄirection；

}SＥleｍType;//步数、方向及位置

//栈定义

②ｔyｐedeｆsｔｒuct ｌnode{

?SEｌemＴype *basｅ；

?SEｌemType*toｐ;/／设两指针便于判断栈是否为空

?iｎｔstａcksizｅ；//栈当前可使用的最大容量

}SqStack；

③参数设置：

#deｆine SＴACK_INIＴ_SIZE 100

＃defｉｎe STＡCKIＮCRENＴ1０

/／----－－--－-基本操作的算法描述-－--－－-－----－-－-－－-－

Stａtus InitStacｋ(SqＳtack &s){ //构造一个空栈

S.ｂase=(SelemType )malｌoc(STＡＣK_INIT_SIＺＥ*SｉzeOｆ(SelemTｙpｅ）);

if(!S.base)exiｔ(OVERLOW）; /／存储分配失败

S．top=Ｓ.base;

S.stackｓiｚe=ＳTACK_ＩNIT_SIZE；

rｅtuｒn ok;

}

SｔａtuｓStackＥmｐty(Ｓｑstacｋ&S)｛／/ 若S为空返回ＴRUＥ，否则返

回ＦＡLＳE

reｔuｒｎS.base=＝S.top;

}

StatuｓGeｔTop(SqＳtaｃk ＆S,Ｓelemtｙpe ＆e){

/／栈不空,用e返回s的栈顶元素及OK，否则返回ERＲOＲ

if(Ｓ.tｏp=＝S．bａsｅ）returｎEＲＲOR；

e＝*（Ｓ.ｔop-１);

ｒｅturｎok;

}

StatuｓPuｓh(Ｓqsｔａｃk &S,SeleｍTyｐe &e){ ／／插入元素ｅ为新的栈顶元素

ｉf(S.toｐ-S．bａse>=S.ｓtacksiｚｅ)｛／／栈满追加存储空间

Ｓ.ｂaｓe=(SelemＴype)ｒｅalloc(S．ｂａse,(S.stacksize+STＡCＫＩＣＲEMＥNT）Sizeof(Ｓeｌeｍtｙpe)）;

iｆ（!S.base) eｘit(OVERFLOW）／/ 存储分配失败

S.top=S．basｅ+S.sｔacksize; ／/确定新的栈顶指针

S.stacksｉze＋=ＳTACKINCRＥＭEＮT;// 已分配空间增加｝

*S.top++＝*e;

return ｏｋ;

}

Statｕs Ｐoｐ(Sｑｓｔack &s,SｅlemTｙｐe&e){

/／若栈不变,则删除栈顶元素,用e返回其值及ok,否则falｓｅ

if(S.toｐ=o=S.baｓｅ)

ｒetｕｒｎＥRROR;

*e=*－-S.top; // 顶指针减小,用e返回其数据

returｎｏk；

}

⑵迷宫模块：

①迷宫的数据类型

#ｄefｉneＭAＸLENＧＴH ５0 /／迷宫的最大长度

#definｅＭAＸWIDTＨ５0 /／屏幕宽度，迷宫的最大宽度

//元素类型

ｔyｐedeｆｉnｔＳｔatus;

typedef strｕct{

?ｉｎｔroｗ;

int ｃol;

}Ｐosiｔiｏｎ; //位置坐标

//迷宫定义

typｅdef iｎt ＥlemTｙpｅ;

typedef struct MAZＥ{

ElemType Ｍaze[MＡXＬENＧTH][MAＸＷＩDTH］; // 迷宫的物理状态描述

?iｎｔleｎｇth,wiｄtｈ;?／/迷宫的大小

?Poｓｉtｉｏn start,ｅnd；?//开始与结束位置与栈的单元类型相同

}MAZE;?／/“迷宫”型数据

②迷宫模块中的基本操作

Statｕs semaｚe(MＡＺE &Ｍ)｛

Printｆ（“Pleaｓe inｐut ｔhe leｎgｔh aｎｄwｉdtｈof the MAZＥ”);

sａｎf(“rlength,ｗiｄth”);

for（k=0;k＜ｗidth＋2；ｋ++)?

?Ｍ－>Maze[0][k］=1;

?fｏr（j＝0；j<ｌength＋２;ｊ＋+)

??M-＞Maze[j］[0]=1;

?foｒ(j=0;j＜ｌenｇth+2;j++)

??M->Maｚe[j][widｔh+1]=1;

fｏr(k＝0;k

??M－＞Maze[length+１][k]=1; //设置迷宫围墙

for(ｊ＝1;j<＝lｅnｇtｈ；ｊ++)

{

?ｆor(ｋ=1；k<=ｗｉｄth;k++）

M->Maｚｅ[j][k]=raｎd(）%2;?／／随机生成迷宫

?}

Ｍ->lｅnｇｔh＝length;

?M->ｗidth＝wiｄth;

M->starｔ．row=1;

M－＞start．coｌ=1;

M->end.ｒｏｗ=M－>ｌengtｈ;

Ｍ->end.col=Ｍ->ｗｉdth;?

?M->Maze[M->starｔ．row][Ｍ－>stａｒt.ｃoｌ］＝M－>Mａze[Ｍ-＞eｎｄ.row][M->ｅnd.col]=0;//入口和出口设置*/

｝

void ＰriｎtMaze(MＡZE M)｛／/ 打印出迷宫,包括边界

printf（"迷宫入口:［1，1]--用#表示\n")；

?prｉntf(＂迷宫出口:[％d,%d］-－用＃表示＼n",Ｍ.lenｇth，M.ｗidｔh);

?for(rｏw＝0;row＜M.length＋２;row＋+){

??for(col=0;coｌ

???iｆ((row==1&&col＝＝１)||(ｒoｗ＝=M．length&&cｏl=＝M.width)）

printf（＂＃＂); //入口和出口用＃表示

ｅlｓｅ

?prinｔf（＂%c"，M.Maze[row]［cｏl]);

}

?ｐrｉntｆ("\ｎ＂);

}// 用字符型打印输出（i,j）状态

}

Status Paｓs（MＡZE Ｍ，ＰoｓitioｎＣurＰｏs)｛

/／判断迷宫中当前位置CuｒPｏs上能否通过

// 如果通过返回1

if(Ｍ.Mａzｅ［CurPos.rｏw][CurPｏs．ｃol]==0)

reｔurn１；// 如果当前位置是可以通过，返回1

elｓe rｅturn 0; // 其它情况返回０

}

Posｉｔion NextPｏｓ(Ｐosiｔｉon CuｒＰoｓ, int ｄiｒectioｎ）{

//返回当前位置在ｄireｃtion方向上的下一位置

?RetuｒｎPos.rｏw=ＣurPｏs.row+Diｒection［direｃtiｏn-1][0］;

ReturnPｏｓ.coｌ＝CurPos.ｃoｌ＋Direcｔioｎ［dｉｒecｔion-1][１];

return RｅtuｒｎPｏｓ;

}

Ｓtａｔｕs SameSeaｔ(SqSｔaｃk Path,int roｗ,int col)｛

//位置（ｒｏｗ，col)在路径中时返回TRUＥ

?whｉle（p

??ｉf(Path.basｅ[num].ｓｅat.row＝=row＆&Path.baｓｅ[ｎum]．seat.col==ｃol)//路径某一步所在的位置

?ｒetｕrn ＴＲUE；

num++;

?p++；

?}

reｔurn FALＳE;

}

Staｔｕs ＭazePath（ＭAＺE M,SqSｔaｃk *S){

// 若迷宫ｍaze中从入口ｓtart到出口eｎd的通道,则求得一条存放在栈中// （从栈底到栈顶），并返回ＳUCCEＳS；否则返回ＦAIL

curpos=M.start; ／/ 设定"当前位置"为"入口位置"

curstep=1; /／探索第一步

//第一次查找路径,设置5个方向（不远离!终点的五个方向)，若找到则返回SUC ＣESS

?do｛

if(Pass(M,ｃｕrpos))｛// 当前位置可通过，即是未曾走到过的通道块

??M.Ｍaｚe[cuｒpos.rｏｗ][curpos．col]=＇'; // 留下足迹

?e．ｄirectiｏn=1;

?e．oｒder=cuｒstep；

?? e.seａt=cｕrpos;

Ｐuｓｈ(S,&e）；// 加入路径

if(ｃuｒpos.rｏw=＝M.ｅnd．row&&ｃｕｒpos．ｃol==Ｍ.end.col）{ ??/／到达终点(出口)

?return SUCＣEＳS；

?}

?curｐos=NeｘtPos（cｕrpoｓ，１);/／下一位置在当前位置的右下方

?ｃursteｐ++; ／／探索下一步}

?ｅｌsｅ{// 当前位置不能通过

?iｆ(!StackEmpty(S）){

??Pop(S，&e）;

??while(e.ｄirecｔiｏn=＝5&&!ＳｔaｃkEｍpty(Ｓ)）{

??M.Maze[ｃｕrｐos.row][ｃuｒpos.col]='＇; //标记不能通过

Pｏp(Ｓ,&e）; ／／留下不能通过的标记，并退回一步

?｝// whiｌe

?iｆ(e.dirｅcｔion<5){

? e.ｄirection++;

??ＧetTｏp（S,&tｅ);

?if(ｅ.diｒectiｏｎ＝＝5&&ｔe．ｄｉrection==2）{

??Pｏp(S，&e);

?? e.dｉreｃtｉｏｎ+＋;

?}

????Push(S，＆e）; ／/换下一个方向探索

??curpｏs=NexｔPｏs(e．seaｔ，e.diｒeｃtiｏn); /／当前位置设为新方向的相邻块

???} ／／if

?} //if

?｝／/ｅlse

}ｗhiｌｅ(！SｔaｃkEmpty(S));

?cｕｒpos=M.ｓtａrt; // 设定＂当前位置＂为＂入口位置"

curｓtｅp=１; ／/ 探索第一步

?/／如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况

?ｄo{

?if(Pass（M,ｃｕrpos)){ // 当前位置可通过，即是未曾走到过的通道块

??M．Ｍaze[cｕrpos.row][ｃｕrpｏｓ.cｏｌ]='';／/留下足迹?ｅ．direｃｔｉoｎ=１;

? e.oｒder=cursｔep；

?? e.sｅａt＝curｐos；

?Puｓh(Ｓ,&e);//加入路径

if(ｃurpos.rｏw＝=M．ｅnd.rｏw＆＆curｐoｓ.coｌ=＝Ｍ.ｅnd.coｌ)｛

?／/ 到达终点(出口）

??//PriｎｔＰａth(mａze,S); //输出路径

??rｅtuｒn ＳUCCESＳ;

｝

??curpｏs=ＮeｘｔＰos(cｕrｐｏs,1); ／／下一位置是当前位置的东邻

?cｕrstep++；／/ 探索下一步

}

?elsｅ{ //当前位置不能通过

??if(!SｔackEｍpty（Ｓ)）{

Pｏｐ（S，&ｅ）;

?ｗｈile(e.ｄirｅcｔion==8&&!StackEmpty(S）){

??M.Mａze[curpos.rｏw][ｃurｐos．coｌ]=＇'；?/／标记不能通过

??Pop(Ｓ,＆e);// 留下不能通过的标记,并退回一步

?} // while

?if(e.ｄirｅctｉon<８){

?? e.direｃtion＋＋;

?GetTop(S,&ｔe)；

???iｆ(ｅ.ｄｉrectｉon＝=４&&ｔe．dｉrectｉｏｎ＝=2)｛

????Pop（S,&e)；

?? e.direｃtｉｏｎ＋+;

?｝

????Push(S，&e); /／换下一个方向探索

?ｃｕrpos＝NｅｘtＰoｓ（e.seａt,e.ｄｉrｅｃtion)；// 当前位置设为新方向的相邻块

??｝／/if

｝／／if

} // eｌｓe

}ｗhile(!StａcｋEmpｔy（S));

?ｒetuｒn FAIL；

｝/／MazeＰath

voｉd PrinｔPａｔh（MAZＥM，SqＳtacｋPath){// 将迷宫及路径一起打印ｉf(StａcｋＥmpty(&Paｔh）){

??pｒiｎtf（"NｏＰath！＼n"）;／／路径栈为空，则提示无路径

?exit(ＯVERFLＯW);

}

?printf("＼ｎＴｈe Path:\n")；

for(ｒow=０；roｗ＜M.lｅngth＋2；rｏw++){

ｆor（col＝0；coｌ

?iｆ(SamｅＳeａt(Pａｔh,ｒｏw,ｃoｌ)){

??if((row＝=1＆&coｌ=＝1）||（rｏｗ==M.ｌength&&coｌ=＝Ｍ．wiｄtｈ)) ????prｉntf("# ");

??ｅlｓｅ

???pｒintf(＂>")；

??num++；

?p++;

???｝

??else

??printｆ("%c ",M.Maｚe[roｗ][col]);

?}

??ｐrintf("\n"）;

?}

}

⑶ 主函数算法:

void m ａｉｎ()｛

?MA ＺＥ Ｍ;

Sq Ｓtack path ；

?Init Ｓta ｃk(&p ａth);

SetMaz ｅ（＆M)；

?Pr ｉｎtMaze （M);

Maze Ｐath(Ｍ,&path);

Prin ｔＰat ｈ(Ｍ，p ａth);

}

⒉ 函数的调用关系反映了本演示程序的层次结构 ma ｉｎ

Init Ｓｔac ｋ Ｍaz ｅＰa ｔh P ｒintP ａth Ｐri ｎtMaze Pass ＳｅtMaze Sa ｍeSe ａｔ N ｅx ｔP ｏs

?

……

Push G ｅtTop P ｏp StackEmp ｔｙ

四、调试分析

1、开始没有将Ｍ[n ］[m].ｓta ｒt.end 设置为MAZ Ｅ 型数据的下属单元,使得各个迷宫

操作的函数参数十分散杂,调试时各参数关系不易把握。

２、另行设置P ｒi ｎt Ｐａt ｈ函数,使得终端输出更加友好，并巧妙地将迷宫以特殊、明

朗的字符输出，效果更好。

3、开始出栈入栈的条件没有控制好,导致输出时不是完整路径,甚至出错。

4、选择方向时有一定策略,开始选择时按照顺时针依次读取方向,发现太耗时且效果不

好，容易出现不必要的弯折走法，后来通过控制方向顺序,即第一方向为东南方，然后

再东方、南方...，选取越靠近出口的方向为优先方向，因为这样的话搜索路径时自然会

本着路径最短的原则向出口处行进,那么找到的路径自然是最短路径(之一)。

５、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况,比如

先往东再往西南,其实是可以直接往南的，因此为了避免这种情况,在入栈时还要先进行

这种情况的判断，如是这种情况则出栈将前一位置方向改变再入栈。

迷宫处

工作栈

6、为了便于找到最短路径，起初只使用了靠近出口处的五个方向，但是发现有特殊情

况存在时由于不能想远离出口的方向行进而找不到路径,因此在搜索路径时进行了两次搜索，第一次使用五个靠进出口的方向搜索，找到路径时则返回SUCCＥSS,若未搜索到则再进行一次八个方向的搜索,即为了防止漏掉特殊情况,找到时则返回SUCCESS,由于第一搜索无结果若第二次搜索到路径也只能是特殊情况，故也应该是最短路径(之一）。

7、最大的问题是并没有按照题目要求来做，因为题目中要求用队列来存储路径，经过

实验发现有很多问题难以解决，故选择了只用栈的方法来实现。

五、用户说明

⒈本程序的运行环境为ｗindows ７（６4位）操作系统,执行文件为数据结构迷宫．ｅ

xｅ;

⒉进入演示程序后,即显示对话形式的提示操作过程，

1、提出输入迷宫的大小

2、按ｅｎter键输出随机生成的迷宫

3、按ｅntｅr键开始搜索路径

搜索结果：

The Ｐaｔh:输出迷宫及路径或者输出Ｎo Path!

⒊提示输入迷宫大小后,用户输入所要处理迷宫的长roｗ,宽ｃoｌ；

⒋提示输入迷宫后,用户将迷宫输入,０代表可行，1代表障碍；

⒌按任意键开始后,程序自动进行对所建迷宫的搜索,并将搜索结果；

⒍按任意键退出程序。

六、测试结果

1、无路径:

2、找到最短路径：

七、附录（源代码及注释）

#incｌuｄe＂ｔime.h"

#inｃlude ＂ｓtdｉo.h"

＃ｉnｃlｕdｅ"sｔdlib．ｈ＂

#ｉnclude "cｏnio．h"

#ｄefｉne ＮＵLL 0

#defｉne TRUE 1

#define FＡLSE 0

#definｅSUCCESS 1

#deｆine ＦＡIＬ０

#deｆineＯK１

#definｅERROR0

#dｅfｉnｅOVERFLOW -1

#define ＩＮＦEASIＢＬＥ-２

#dｅfine MAＸＬEＮＧTH５0

#dｅfｉne MＡXＷIDTH ５０

＃define STACK_INIT_SIZE100

＃ｄeｆｉｎｅSＴACKINＣRENT １０

/／元素类型

typedef inｔＳtatｕs;

tｙpedｅf stｒｕct｛

ｉnｔｒoｗ;

?int cｏｌ;

｝Poｓitｉｏn;?//位置坐标

typｅdeｆstruct｛

int ｏrder;

?Ｐｏsiｔiｏn seat;

?ｉnt direction;

}SＥlemType;//步数、方向及位置

／/栈定义

typedefｓtruｃtｌnｏｄｅ{

SＥlｅmＴype*basｅ;

SElｅmＴｙpｅ*top;//设两指针便于判断栈是否为空?int stacｋsize;//栈当前可使用的最大容量

}SqStａcｋ;

／/迷宫定义

ｔｙpedef inｔEｌemType;

ｔypeｄef ｓtrucｔMAZE{

?EｌeｍTｙpｅMazｅ[MAXLＥNGTH][ＭＡXWIDＴH］;

?int lｅngｔh,width;

?Pｏsitioｎｓtaｒt,end;

｝MAZE；／/迷宫大小及出入口位置

/／栈操作函数声明

Ｓtatus ＩniｔStaｃk(SqStaｃｋ＊Ｓ);//初始化

StatｕｓＳtacｋＥｍｐty（SｑＳtack *S）;//判空

SｔａtuｓGｅtTop(ＳqＳtack *s，SElｅmTypｅ*e);//取栈顶元素

Staｔus Puｓh（SqＳtaｃk *S,SElemTyｐｅ*e);/／入栈

StatｕｓPｏp(SｑSｔaｃｋ*s,SEleｍTyｐe *e)；//出栈

/／迷宫操作函数说明

ｖｏｉd SetMazｅ(MAＺE *Ｍ); /*设置迷宫，随机生成*/

void PｒintＭazｅ（ＭＡZE Ｍ)；/*输出迷宫*／

Staｔus Pass(MＡZE M, Pｏsition CurPｏｓ);//判断当前位置是否可通

Posｉtion NextPoｓ(Pｏsitｉon CurPos, ｉnt directｉoｎr）;/／下一位置

ＳtatuｓSａmeSｅaｔ(ＳqStack Pａth,iｎt roｗ，int col);//找到迷宫中可行路径的各个位置Ｓｔａtus MaｚePath(MAZE M,SｑＳtａcｋ*Patｈ);//搜索迷宫路径

void PrｉntPath(MAＺE M,SqＳtacｋPａth)；/／若迷宫Ｍ存在可行路径则将该路径在迷宫中输出

/／主函数

void maｉn(){

MAZE M;

?SｑＳtａｃk ｐａtｈ;

InitSｔack(&path);

ＳetMaze（&Ｍ);

?PriｎtMａｚe（M);

ＭazePath(M,&path)；

?PrｉntPath（M,path）;

}

//迷宫操作

void ＳetMａze（MAＺE *M){

inｔleｎgth,ｗidth,j，ｋ;

prinｔf("Please input tｈe lengｔｈaｎd widｔｈoｆthe MAZＥ:\nｌength (０<ｌｅｎgｔｈ<=50):"）;

?scanf("％d",&leｎｇtｈ）;

?priｎｔf("widtｈ(0＜wiｄtｈ＜＝5０):＂);

?scaｎf("%ｄ",&width);

ｓrand(（ｕnsiｇnｅd)time(NULL））;

?for（k＝0;k

?M->Mazｅ[0][k]=1;

?fｏr(j=0;j

??Ｍ－>Ｍaze［j]［０］＝1;

?fｏr(j＝0;j

?M->Mａze[j][ｗidth+1]=1;

?foｒ(k=０;ｋ

??M－>Ｍaze［lｅnｇtｈ＋１][k]＝1; /／设置迷宫围墙

fｏr(j＝１;j<=length；j+＋)

?{

?foｒ（ｋ＝１;ｋ＜＝ｗidth;k＋＋)

?M->Ｍaze［j][k]=raｎｄ（)%2; /／随机生成迷宫

｝

?Ｍ->ｌenｇth=lｅngth;

?M->width＝ｗidｔh;

Ｍ->ｓtａrt.ｒoｗ=1;

Ｍ－>stａｒｔ.col＝1;

?M->eｎd.row=M-＞length;

M－>eｎd.col=M->widｔｈ;

?M－>Ｍaｚｅ［Ｍ－>sｔarｔ.ｒoｗ][M->ｓtart.col]＝Ｍ->Maze[M->end.rｏw］[Ｍ->ｅｎd．co ｌ]＝0;//入口和出口设置＊/

}

void PrintMａze(MＡＺE M){

?int row,col;

printf("迷宫入口:[1,1]-－用＃表示\ｎ");

?priｎｔf("迷宫出口：[％d，％d]-－用#表示\n",Ｍ.lengtｈ,Ｍ．width）;

foｒ(rｏw=０；roｗ<Ｍ.lｅngth+2;ｒow++){

?fｏr(col=0;cｏl

?if((rｏw==1＆&col==１)｜|(row=＝Ｍ.leｎgth＆＆cｏl＝＝Ｍ.width)）

??ｐrintf（"＃"); ／/入口和出口用#表示

??ｅlse

??prｉｎtf（"%c ＂,M.Mａze[row][coｌ]）;

??}

pｒintf("\n");

?｝

}

Stａｔus Pａsｓ（ＭAZE M,Poｓiｔion CuｒPos) {

ｉf (M.Mａze[CurPos．row］［ＣｕｒPoｓ.cｏl]==0)

rｅturn 1；// 如果当前位置是可以通过,返回1

else rｅtｕｒn ０; // 其它情况返回0

}

Positｉon NｅxtPos(Pｏsiｔiｏn CｕｒＰos，int direｃtｉｏn）{

PositｉoｎRetuｒnPoｓ;

?iｎｔDireｃtion[８］[2]={{１,１}，{0,1},｛１,０},｛－1,1},{1,-1｝，{０,-１},{-1,０},{-1,-1}}；/／按一定次序依次设置八个方向

ＲeｔurnPos.ｒow=CｕrPos.roｗ+Dｉrｅcｔion［dirｅctiｏn-１][0];

?RｅｔuｒnPｏs.cｏl=ＣurPｏs．ｃol+Ｄirｅctioｎ[directiｏn-1]［１];

retｕrn ReturnPos；

｝

Statｕs SaｍeSeaｔ(SqＳtａck Ｐａth,iｎｔroｗ,int ｃoｌ){

SEｌemＴype *ｐ=Path.base;

?int num=0;

?while(p

if（Ｐａtｈ．bａｓe［nｕm］.seat.ｒow=＝row&&Ｐａｔh.basｅ[nｕm］.sｅat.ｃo ｌ==coｌ)／/路径某一步所在的位置

?return TRUE;

?num++;

?p＋+;

?｝

?ｒeｔurn FAＬSE;

}

Ｓｔatｕs MazｅPａth（MAZE M，SｑSｔacｋ＊Path){

／／若迷宫maze中从入口ｓtart到出口eｎｄ的通道，则求得一条存放在栈中

?// (从栈底到栈顶），并返回SUCCESS;否则返回ＦＡIL

?Ｐosition cｕrpoｓ;

int curstep;

?SEｌeｍＴｙｐe e,te;

curpos＝Ｍ.start；// 设定"当前位置"为"入口位置＂

?curｓtｅp=1; ／／探索第一步

／/第一次查找路径，设置５个方向（不远离！终点的五个方向)，若找到则返回ＳUCC ＥSS

ｄo｛

?if(Paｓｓ(M,cｕｒpoｓ)){ /／当前位置可通过，即是未曾走到过的通道块

??M.Mａｚe［curpoｓ.row][cuｒpｏｓ.coｌ]＝＇＇; /／留下足迹

?? e.dirｅction=1;

? e.ｏrｄer=curstep;

? e.seat=curpｏs；

??Ｐush(Ｓ，&ｅ）; // 加入路径

?ｉf（ｃｕrｐos．rｏw＝=M.end.rｏw＆&ｃurpos.ｃol==Ｍ．enｄ.col)｛

／／到达终点（出口)

??return SUCCESS;

??}

??cuｒpｏs＝NｅxtPos（cｕrpoｓ，1);// 下一位置在当前位置的右下方?ｃursｔep++;//探索下一步

}

else{ /／当前位置不能通过

??if(!SｔａcｋEmｐｔy(Ｓ）){

??Pop(S，&e);

??while(ｅ.ｄiｒection=＝5&&！SｔaｃｋEmpｔy(S)){

???M.Maｚe[curpｏs.ｒｏw］［ｃｕrpos.col]=' ＇;?／／标记不能通过

?Pop（S，&ｅ);// 留下不能通过的标记，并退回一步

?} ／／ｗhiｌe

?iｆ(e．dｉrｅctｉon<5){

????ｅ.direｃtiｏn＋+;

ＧetTop(S,&te);

???if(ｅ.dｉrection=＝5&&ｔｅ.ｄirecｔioｎ＝=2)｛

???Ｐｏp（Ｓ,&e);

?? e.ｄｉrectｉoｎ++；

?}

?Push(Ｓ，&e); ／/换下一个方向探索

???cuｒpos=ＮextＰｏs（e．sｅａt,e.dｉrection)；/／当前位置设为新方向的相邻块?}//if

?｝/／if

?}/／eｌse

｝whiｌe(!StackEｍpｔｙ(S));

?curpｏｓ＝M．stａrt;／/ 设定＂当前位置"为"入口位置"

?curstep=１;// 探索第一步

/／如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况

do｛

if(Pａss（Ｍ，curｐｏs）){ /／当前位置可通过，即是未曾走到过的通道块

?M．Ｍazｅ[cｕrｐｏs.roｗ][ｃurpos.cｏl]=' '; /／留下足迹

e.directｉｏn=1;

?? e.oｒder＝ｃurstep;

?ｅ.seat=cuｒpos;

?Pusｈ（S，&e); ／/加入路径

??if(cuｒpos.row==Ｍ.end.ｒow＆&ｃurｐｏs．coｌ＝=M.eｎd．cｏl）{ ??// 到达终点（出口)

?//PrintPatｈ（maze,S)；?//输出路径

??ｒｅturn SUCＣESＳ;

?｝

?cｕrpos＝NextPoｓ(curpoｓ,1)；／/ 下一位置是当前位置的东邻?ｃurstep++; ／/ 探索下一步

}

else{ //当前位置不能通过

??if(!SｔａｃｋＥmpty(S)){

??Pop(S,&ｅ)；

?wｈile(e.ｄirection＝=８&&!StacｋEmptｙ(S)){

?M.Mazｅ[ｃurpｏｓ.roｗ][curpos.col]=' '; ／/标记不能通过

?Ｐop(S,&e）；／/ 留下不能通过的标记,并退回一步

｝// while

???iｆ(e．direｃtioｎ<８)｛

??? e.directiｏｎ++;

???GetTｏp（S,＆te）;

???iｆ(ｅ．diｒection＝＝4&＆te.ｄirectioｎ==2){

数据结构迷宫问题实验报告

《数据结构与算法设计》迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航

一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元

StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作： InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障 碍，值1表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上 的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 } PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 } }ADTmaze （3）本程序包括三个模块 a、主程序模块

网络互连的实验报告

实验一IP子网间的通信 1. 实验的目的： 1.1 掌握用路由器、交换机进行局域网互联配置； 1.2 理解交换机、路由器的工作原理。 2.实验的内容： 2.1 利用二层交换机构成一局域网或者说是广播网； 2.2 创建两个IP子网，每台交换机分属一个子网； 2.3 利用路由器连接局域网，并且为连接端口配置两个IP地址作为两个IP子网的网关， 实现子网1和子网2的互联通信。 3.实验的原理： 3.1 通过路由器实现子网间的通信，其原理如下： 路由器工作在OSI模式中的第三层，即网络层。路由器利用网络层定义的“逻辑”上的网络地址（即IP地址）来区别不同的网络，实现网络的互联和隔离，保持各个网络的独立。路由器不转发广播消息，而是把广播消息限制在各自的网络内部。发送到其他网络的数据先是被送到路由器，在由路由器转发出去。同一个子网内的主机可以自由通信，不同的子网间的主机不能直接通信，要借助路由器。 3.2 通过交换机可以实现子网内部的通信，它原理如下： 交换机工作在OSI模式中的第二层，即数据链路层。交换机内部维护着一张连接的启动计算机的网卡地址和端口对应表。它接收到的所有的帧进行检查，读取帧中源MAC地址，基于数据中携带的目标MAC地址转发到对应的端口，实行过滤转发而不是广播方式传送。交换机工作的时候，只有请求端口iuhe目的的端口间相互响应而不会影响到其他端口，因此能有效的隔离冲突和压抑广播风暴的产生。 4. 实验的环境： 华为路由器一台、华为二层交换机一台、Console口线一根、主机四台，标准网线若干 5.实验的步骤： 5.1 连接各个设备，如图所示：

5.2 配置路由器的E0端口的IP地址和它的子网掩码，作为192.168.2.0的子网网关： [Router] interface e0 [Router-Ethernet0] ip address 192.168.2.254 255.255.255.0 5.3 在E0端口增加第二条IP地址和它的子网掩码，作为192.168.3.0的子网网关： [Router] interface e0 [Router-Ethernet0] ip address 192.168.3.254 255.255.255.0 sub 5.3 配置路由器的rip协议，实现两个子网间的通信： [Router] rip [Router-rip] network 192.168.2.0 [Router-rip] network 192.168.3.0 5.4 配置各个PC主机的IP地址、子网掩码和默认网关，实现两个子网间的PC主机能 相互ping通。 PCA主机上的配置如下： IP 地址：192.168.2.1 子网掩码：255.255.255.0 默认网关：192.168.2.254 如图所示：

13种典型网页版式设计介绍

13种典型网页版式设计介绍 一、骨骼型 骨骼型是一种规范的理性的分割方法。常见的骨骼有竖向通栏、双栏、三栏、四栏和横向通栏、双栏、三栏和四栏等。一般以竖向分栏为多。在图片和文字的编排上则严格按照骨骼比例进行编排配置，给人以严谨、和谐、理性的美。骨骼经过相互混合后的版式，既理性、条理，又活泼而具弹性。二、满版型 版面以图象充满整版，主要以图象为诉求，视觉传达直观而强烈。文字的配置压置在上下、左右或中部的图象上。满版型给人以大方、舒展的感觉，是商品广告常用的形式。 三、上下分割型 把整个版面分为上下两个部分，在上半部或下半部配置图片，另一部分则配置文案。配置有图片的部分感性而有活力，而文案部分则理性而静止。上下部分配置的图片可以是一幅或多幅。 四、左右分割型 把整个版面分割为左右两个部分，分别在左或右配置文案。当左右两部分形成强弱对比时，则造成视觉心理的不平衡。这仅仅是视觉习惯上的问题，也自然不如上下分割的视觉流程自然。不过，倘若将分割线虚化处理，或用文字进行

左右重复或穿插。 左右图文则变得自然和谐。 五、中轴型 将图形做水平或垂直方向的排列，文案以上下或左右配置。水平排列的版面给人稳定、安静、和平与含蓄之感。垂直排列的版面给人强烈的动感。 六、曲线型 图片或文字在版面结构上作曲线的编排构成，产生节奏和韵律。 七、倾斜型 版面主体形象或多幅图版做倾斜编排，造成版面强烈的动感和不稳定因素，引人注目。 八、对称型 对称的版式给人稳定、庄重理性的感觉。对称有绝对对称和相对对称。一般多采用相对对称。以避免过于严谨。对称一般以左右对称居多。 九、中心型 重心有三种楷念。1、直接以独立而轮廓分明的形象占据版 面中心。2、向心：视觉元素向版面中心聚拢的运动。3、离心：犹如将石子投入水中，产生一圈圈向外扩散的弧线运动。重心型版式产生视觉焦点，使强烈而突出。

迷宫问题c++实验报告

数据结构实验报告 班级： 姓名： 学号： 组员： 问题描述： 迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的

门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计功能要求： 迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 算法输入：代表迷宫入口的坐标 算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路 任务分派 为了达到锻炼大家独立设计算法的能力，大家一致决定，先自己独立设计算法，不论算法的好坏、难易，完完全全出自于自己的手中。 在大家独立完成算法后，进行小组集中讨论，将自己的算法思想与大家交流，特别是自己最自豪的部分或是自己觉得可以改进的地方，之后得出最优结果。 独立设计 求解思想： 利用递归的方式进行求解。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 如果现在位置(i,j)处于迷宫的边界位置，则有2种或3种可能的走法，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1，这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 struct Pos { int x,y; int di; }; 其中x、y分别表示横纵坐标值、di表示前进的方向。 在已经某一位置（i, j, d）的情况下，其下一个位置横、纵坐标的取值如表4-2所示。 而走到一个新位置时，其方向值初始置为1。 代码 #include "iostream" #include "iomanip" using namespace std; struct Pos { int x,y; int di; };

迷宫实验报告

一、实验内容 3、迷宫问题。假设迷宫由m行n列构成，有一个出口和一个入口，入口坐标为（1,1），出口坐标为（m,n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。 （1）用C语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。 （2）设计一个二维数组MAZE[m+2][n+2]表示迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE[1][1]、MAZE[m][n]分别为迷宫的入口和出口。 （3）输入迷宫的大小m行和n列，动态生成二维数组；由随机数产生0或1，建立迷宫，注意m*n的迷宫需要进行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。 （4）要求输出模拟迷宫的二维数组；若存在最短路径，则有出口回溯到入口（出队列并利用栈实现），再打印从入口到出口的这条路径，例如（1,1），......，（i,j），......，（m,n）；若没有路径，则打印“No path”。 （5）迷宫的任一位置（i,j）上均有八个可移动的方向，用二维数组Direction存放八个方向的位置偏移量。 Direction[8][2]={{0,1}，{1,1}，{0，-1}，{-1，-1}，{1,-1}，{1,0}，{-1,0}，{-1,1}}； （6）为避免出现原地踏步的情况需要标志已经通过的位置，采用一个标志数组MARK[m+2][n+2]，初值均为0，在寻找路径的过程中，若通过了位置（i，j），则将MARK[i][j]置为1。 （7）为了记录查找过程中到达位置（i，j）及首次到达（i,j）的前一位置（i_pre,j_pre），需要记住前一位置（i_pre,j_pre）在队列中的序号pre，即队列中数据元素应该是一个三元组（i,j,pre）。 （8）搜索过程简单下：将入口MAZE[1][1]作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置（i,j,pre）入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，...，如此进行下去，直至达到出口MAZE[m][n]或者迷宫所有位置都搜索完毕为止。 二、实验过程及结果 一、需求分析 1、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。 2、以二维数组M[m+2][n+2]表示迷宫，M[i][j] 表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行），完成迷宫的抽象数据类型，包括出口、入口位置等。 3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在50以下)，完成对应迷宫的初始化。根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示： 如下所示：

数据结构-迷宫实验报告

云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 实验难度 A □ B □ C □ 承担任务 （难度为C时填写） 指导教师评分（签名） 【实验题目】 实验4.数组的表示极其应用 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如；对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，…。?

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识） 本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。 可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。? 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1. 设定迷宫的抽象数据类型定义： ADT Maze { 数据对象：D = { a i, j | a i, j ∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、 ‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row, col≤18 } 数据关系：R = { ROW, COL } ROW = { < a i-1, j , a i, j > | a i-1, j , a i, j ∈D, i=1, … , row+1, j=0, … , col+1} COL = { < a i, j-1, a i, j > | a i, j-1 , a i, j ∈D, i=0, … , row+1, j=1, … , col+1} 基本操作： Init_hand_Maze( Maze, row, col) 初始条件：二维数组Maze[][]已存在。

栈和队列综合实验报告

栈和队列综合实验报告 一、实验目的 （1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用 （3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 能任意设定的迷宫 （选作）如果有通路，列出所有通路 提示： 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11

01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。 其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。 五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++;

k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断 六、程序调试问题分析 最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。 第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。

最简单的c语言迷宫游戏实验报告

一、内容： 1、本游戏主要实现了人控制键盘方向键使小人（*）走出迷宫。 2、具有的功能： 1）、在游戏菜单里人可以选择不同难度的游戏进行游戏； 2）、在游戏过程中，可以通过键盘方向键使小人移动，走出迷宫； 3）、在游戏过程中，当人碰到墙壁（#）的时候小人过不去； 4）、当人顺利完成游戏之后，输出“========you are win!======”字样，30秒钟后自动返回到游戏菜单； 5）、在游戏过程中，人可以通过按Esc键返回游戏菜单；也可以可以按0直接退出游戏； 6）、在游戏菜单里，按0键可以退出游戏。 3、具体应用： 1）、人主要同过键盘的1,2,3数字键来选择游戏难度； 2）、在游戏中通过Esc键来返回菜单； 3）、同过0键退出游戏。 二、上机环境 操作系统：windows7 开发工具:VC6.0 三、函数调用关系图

四、各函数功能说明 main() 主函数； menu() 游戏菜单； roadcake() 消去小人路径； introduce() 游戏介绍； system(“cls”) 消屏函数； exit(0) 退出游戏； drawmg1() 画初级难度迷宫； drawmg2() 画中级难度迷宫； drawmg3() 画高级难度迷宫； control1() 控制初级难度游戏； control2() 控制中级难度游戏； control3() 控制高级难度游戏； 五、算法流程图 首先定义三个全局数组mg1[20][20]、mg2[30][30]、mg3[30][30]用于画出迷宫的地图；1表示墙（#），0表示空地（）； Introduce( )函数里如果按Enter键，则调用menu( )函数，从键盘中输入相应的提示数字，进入难度不同的游戏；游戏的执行在此只初级难度进行描述，其余的难 度与其类似； 选了1后调用system（”cls”）进行清屏；drawmg1()函数进行迷宫的地图的绘

《数据结构课程设计》走迷宫游戏

信息工程学院 课程设计报告 课程名称《数据结构》 课题名称走迷宫游戏 专业 班级 学号 姓名 联系方式 指导教师 2015 年 12 月 27 日

目录 1、数据结构课程设计任务书............................................................... １ 1.1、题目........................................................................... １ 1.2、要求........................................................................... １ 2、总体设计............................................................................. １ 2.1、设计思路及总体组成框架......................................................... １ 2.2、操作流程图..................................................................... ２ 3、详细设计............................................................................. ５ 3.1、程序中所采用的数据结构及存储结构的说明......................................... ５ 3.2、函数功能模块说明............................................................... ５ 3.3、各函数的调用关系 ............................................................................................................................... ７ 4、调试与测试：......................................................................... ７ 4.1、调试方法与步骤：............................................................... ７ 4.2、测试结果的分析与讨论：......................................................... ８ 4.3、测试过程中遇到的主要问题及采取的解决措施：................................... １０ 6、源程序清单......................................................................... １０ 7、数据结构课程设计总结............................................................... １４ 8、参考文献........................................................................... １４

迷宫实验实验报告

迷宫实验 一．摘要 迷宫实验主要是要探讨研究一个人只靠自己的动觉，触觉和记忆获得信息的情况下，如何学会在空间中定向。本实验的被试是华东师范大学应用心理学系大二的一名女同学，本实验以学习遍数为自变量，以所用时间和错误次数为因变量，让被试在排除视觉条件下，用小棒从迷宫起点凹槽移动到达终点，其间小棒每次进入盲巷并与盲巷末端金属片接触算一次错误，学会的定义为连续三遍不出错。而且主试也不能给予被试任何提示或暗示。被试要运用动觉，思维，记忆等自己认为有效的方法独立完成。测试中为了控制疲劳带来的误差，若被试感到疲劳，可稍事休息再进行实验。分析实验数据可知，被试走完迷宫所用时间成减少趋势，错误次数也成减少趋势。在最初几次走迷宫时，错误次数会出现反复的时多时少的情况，所用时间也在反复，时多时少，这表明被试在摸索迷宫路线，处于对整个迷宫的整体定位中。随着学习遍数的增加，错误次数与走完一次迷宫所用的时间开始减少，这表明被试对于迷宫的整体情况有了比较清楚的了解。 关键词迷宫学习次数学习时间错误次数 二．引言 人类从十九世纪末就开始研究迷宫学习了。1899 年,斯莫尔(W. S. Small ) 让白鼠学习一条相当复杂的迷津通路。通过研究他认为,白鼠迷宫学习所依靠的主要是触觉和动觉记忆。1912 年希克思(V. C. Hicks) 和卡尔把迷宫用于研究人类学习。泊金斯（Perkins，1927）最早使用这种在手指迷宫的基础上发展起来的最简便、最常用的触棒迷宫（pencil maze）。近年来，学者们则利用迷宫进行逆反学习能力的研究。而在特殊教育领域，也利用迷宫队正常人和盲人进行了触棒迷宫的对比试验，并得出了盲人心理的巨大补偿作用和学习潜能的结论。 迷宫是研究一个人只靠自己的动觉、触觉和记忆获得信息的情况下，如何学会在空间中定向。迷宫的种类很多，结构方式也不一样，但是有一个特征，这就是有一条从起点到终点的正确途径与从此分出的若干条盲巷。被试的任务是寻找与巩固掌握这条正确途径。迷宫的学习一般可分为四个阶段：1.一般方位辨认。2.掌握迷宫的首段、尾段和中间的一、二部分。3.扩大可掌握的部分，直至全部掌握空间图形。4.形成集体对空间图形的自动化操作。迷宫学习与被试的智商有关，它涉及被试的空间定向能力、思维、记忆诸多方面。 在此迷宫实验中，被试排除视觉条件，用小棒从迷宫起点沿凹槽移动到达终点。在此过程中，被试要运用动觉，思维，记忆等自己认为有效

c++迷宫游戏实验报告材料

1、问题描述 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向健操纵老鼠在规定的时间内走到粮仓处。 基本要求： （1）老鼠形象可以辨认，可用键盘操纵老鼠上下左右移动； （2）迷宫的墙足够结实，老鼠不能穿墙而过； （3）正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，并给出一条路径，否则提示失败。 提高要求： （1）添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； （2）增加闯关和计分功能； （3）找出走出迷宫的所有路径，以及最短路径。 。 2．需求分析 软件的基本功能：通过键盘控制光标移动实现老鼠在迷宫中的行走、全部路径和最短路径的显示、自定义地图（墙变路，路变墙）。在老鼠闯关只能在地图显示是路的地方行走，不能穿墙，有计时功能，当时间结束时若没有到达指定地点，显示game over，查看排行榜，游戏结束，若成功到达指定位置，进去下一关，直到所有关结束，程序结束；。 输入/输出形式：用户可以通过控制台，根据输入提示。 输入形式： ①方向键、空格键、enter键 输出形式： ①输出地图菜单。 ②输出地图 ③输出是否成功信息、输出排行榜 3．概要设计 （1）主程序流程

图1：主程序流程图 （3）模块调用关系: 本程序中函数包括：main函数，menu函数，menu2函数，mouse类内函数，path 类内函数，change函数， 函数调用关系如下：

图2：函数调用关系 4．详细设计 （1）实现概要设计的数据类型： Mouse类 class mouse { private: int m_x; int m_y; time_t begin ,stop; public: int move_up(int map[x][y],int end);//向上移动 int move_down(int map[x][y],int end);//向下移动 int move_left(int map[x][y],int end);//左 int move_right(int map[x][y],int end);//右 void initialize(int map[x][y],int end){ m_x=S;m_y=S;map[end][end]=9;} void print(int map[x][y],int end);//打印地图

迷宫算法设计

《数据结构与算法设计》课程设计任务书

数据结构与算法设计课程设计 专业班级学号 姓名（签名）完成日期指导教师（签名） 1、程序设计说明书 【设计题目】迷宫设计 【问题描述】 在迷宫中求从入口到出口的一条简单路径。迷宫可用方块来表示，每个方块或者是通道或者是墙。“迷宫求解”这个经典的问题，应用栈这种数据结构设计一个方案，并在图形界面上实现从入口到出口的一条简单路径，设计这个游戏可以加强自己的编程能力，自己找通路时还可以加强观察能力。 【软件功能】 1、求解迷宫通路的图形界面演示程序，根据用户界面提示自定义迷宫。 2、根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上 下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc 键退出； 3、在找迷宫通路的过程中，演示查找的过程并查找成功的一条路径。 4、用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。 【算法思想】 1、以一个长方阵表示迷宫，采用数组对迷宫信息进行存储，数组中的元素的值 表示迷宫对应位置的内容。0表示迷宫对应位置可通过；1表示迷宫对应位置为墙；2表示迷宫对应位置为已经走过的足迹3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；4表示迷宫对应位置为起点，保证起点不可通过。 2、在设计走迷宫算法的过程中，主要是利用栈对路径信息进行存储，类Node， 定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。 3、采用A*算法，找到起点到终点的最短路径； 4、采用回溯算法控制并绘制人物在迷宫图形界面窗口中的位置。 5、用java编程语言，有简单、美观的图形界面。 【逻辑结构设计】 运行程序，进入设置迷宫大小界面，输入行和列的值点击生成迷宫按钮进入迷宫自定义界面，根据操作菜单中的帮助选项，用键盘上的按键进行自定义操作（设置迷宫的起点、终点和墙）按F9或者操作菜单中的A*算法寻找最短路径选项即可实现对应的通路。

迷宫实验报告

实习报告、 题目：编制一个求解迷宫通路的程序 班级：计算机04（2）姓名：王金锭学号：04120087 完成日期：06.03.01 一．需求分析： 1．以二维数组Maze[m+2][n+2]表示迷宫,其中:Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]Maze[i][n+1](0<=i<=m+1)为添加的一圈障碍.数组中以元素值为0表 示通路,1表示障碍,限定迷宫的大小m,n<=10. 2．用户以文件的形式输入迷宫的数据:文件中的第一行的数据为迷宫的行数m和列数n；从第二行至第m+1(每行n个数)为迷宫值，同一行中的两个数字之间用空白 字符相隔。 3．迷宫的入口位置和出口位置可由用户随时设定。 4．若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件(即终端)上，其中，字符“＃”表示障碍，字符“＊”表示路径上的位置，字符“@” 表示“死胡同”，即曾途径然而不能到达出口的位置，余者用空格符印出。若设定 的迷宫不存在通路，则报告相应信息。 5．本程序给出一条成功的通路，并且可以通过用户输入把所有的通路输出到指定的文件中。 6．测试数据见原题，当入口位置为(1，1)，出口位置为(9，8)时，输出数据为： 二．概要设计： 1．设定栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai|ai∈IntSet,i=1,2….,n,n>=0} 数据关系：{ai-1,ai|ai-1,ai∈D,i=1,2…..n} 基本操作： InitStack(&S) 操作结果：构造一个空栈。 DestroyStack(&S)

初始条件：栈S已存在 操作结果：将S清空为空栈。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TURE，否则返回FAULE。 GetTop(S,&e) 初始条件：栈S已存在。 操作结果：若S不空，则以e返回栈顶元素。 Push(&S,e) 初始条件：栈S存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(&S,e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse(S,visit()) 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用visit()。 }ADT Stack 2. 求解迷宫中的一条通路的伪码算法 : 设定当前位置的初值为入口位置; do {若当前位置可通, 则{将当前位置插入栈顶; 若该位置是出口位置,则结束; 否则切换当前位置的东邻方块为新的当前位置; } 否则{ 若栈不空且栈顶位置尚有其他方向未被搜索, 则设定新的当前位置为沿顺时针方向旋转找到的栈顶苇子后的下一个相邻块;若栈不空但粘顶位置的四周均不可通, 则{删去栈顶位置; 若栈不空,则重新测试新的栈顶位置, 直至找到一个可通的相邻块或出栈至空栈; } } }while(栈不空); {栈空说明没有路径存在}

迷宫问题实验报告(c++编写-附源代码)

迷宫问题实验报告 级班年月日姓名学号_ 1．实验题目 以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 2．需求分析 本程序使用VC编写，实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路，或得出没有通路的结论。 ①输入的形式和输入值的范围： A.输入指定的数字，以此选择迷宫的创建方式，分为手动创建迷宫和自动创建迷宫 B. 输入迷宫阵表的行数和列数，行数和列数不超过40行 C. 手动创建迷宫时，需要输入迷宫结点的通畅和障碍情况，0和1分别表示迷宫中的通路和障碍。 ②输出的形式：输出没有通路的结论，或者输出一个长方阵表，其中路径的每个结点都输出→、↓、←、↑之一，表示从当前结点到下一个结点的方向。 ③程序所能达到的功能：实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路（迷宫的入口指定为坐标为（1,1）的结点，迷宫的出口指定为坐标为（迷宫最大行,迷宫最大列）的结点），或得出没有通路的结论。 ④测试数据： 输入数据： A．出现选择生成迷宫方式的菜单时，输入1（即手动输入数据，生成迷宫）； B．输入迷宫的行数和列数，行数输入3，列数输入3； C．输入每个迷宫结点的信息： 0 0 1 1 0 0 1 0 0 输出结果： →↓ 1 1 →↓ 1 0 0 3．概要设计 为了实现上述程序功能，需要定义迷宫的抽象数据类型： typedef struct Maze creat_manual() 初始条件：无 操作结果：手动创建一个迷宫。 B. Maze creat_automatic() 初始条件：无 操作结果：自动创建一个迷宫。

浅谈网页设计中的版式设计

浅谈网页设计中的版式设计 【摘要】网页设计包含视听元素与版式设计两项内容,而网页的版式设计在整个网页设计中具有重要的作用。它决定了网页的艺术风格 和个性特征,形成了网页整体视觉印象,本文拟就网页设计的版式设计谈谈自己的看法。 【关键词】网页设计;版式设计;布局 1.概念 1.1网页设计网页设计是在Internet的发展和数字技术的发展中出现的新艺术形式。它是以Internet为载体,以网络技术和数字技术为基础,依照设计目的、遵循艺术设计规律,实现设计目的与功能,强调艺术与科学密切结合的一种艺术创造化视觉传达活动。它是网络视觉艺术的主要表现形式,也是设计艺术的重要组成部分,它具有媒体相关性、数字技术性和设计艺术性三大基本内涵。 1.2网页版式设计网页版式设计是指在有限的屏幕空间内,按照设计师的想法、意图将网页的形态要数按照一定的艺术规律进行组织和布局,使其形成整体视觉印象,最终达到有效传达信息的视觉设计。它以有效传达信息为目标,利用视觉艺术规律,将网页的文字、图像、动画、音频、视频等元素组织起来,产生感官上的美感和精神上的享受,充分体现了设计师的艺术风格。 2.网页版式设计的作用 网页版式设计是设计师理性思维与感性表达的产物。它决定了网页的艺术风格和个性特征,并以视觉配置为手段影响着网页页面之间导航的方向性,以吸引浏览者注意力,增强网页内容的表达效果。网页版式设计在整个网页的设计中占有很重要的作用。 3.网页版式设计与传统印刷版式设计的差异网页的版式设计同报纸杂志等平面媒体的版式设计有很多共同之处,但网页的排版与书籍杂志的排版又有很大差异。印刷品都有固定的规格尺寸,网页则不然,它的尺寸是由读者来控制的。这使网页设计者不能精确控制页面上每个元素的尺寸和位置。而且,网页的组织 结构不像印刷品那样为线性组合,这给网页的版式设计带来了一定的难度。具体表现如下:

迷宫问题实验报告(优选.)

最新文件---------------- 仅供参考--------------------已改成-----------word文本 --------------------- 方便更改 赠人玫瑰，手留余香。 武汉纺织大学数学与计算机学院 数据结构课程设计报告 迷宫问题求解

学生姓名： 学号： 班级： 指导老师： 报告日期： 一、问题描述 以一个m x n的长方矩阵表示迷宫，1和0分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。 二、需求分析 1、以二维数组maze[10][10]表示迷宫，数组中以元素1表示通路，0表示障碍，迷宫的大小理论上可以不限制，但现在只提供10*10大小迷宫。 2、迷宫的入口和出口需由用户自行设置。

3、以长方形矩阵的形式将迷宫及其通路输出，输出中“#”表示迷宫通路，“1”表示障碍。 4、本程序只求出一条成功的通路。但是只要对函数进行小量的修改，就可以求出其他全部的路径。 5、程序执行命令为：（1）输入迷宫；（2）、求解迷宫；（3）、输出迷宫。 三、概要设计 1、设定栈的抽象数据类型定义： ADT zhan{ 基本操作： InitStack(SqStack &S) 操作结果：构造一个空栈 push（*s，*e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 pop（*s,*e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 getpop（*s，*e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素

stackempty(*s) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 }ADT zhan 2、设定迷宫的抽象数据类型定义 ADT migong{ 基本操作： Status print(MazeType maze)； //显示迷宫 Status Pass(MazeType maze,PosType curpos); //判断当前位 置是否可通 Status FootPrint(MazeType &maze,PosType curpos);//标记当前位置 已经走过 Status MarkPrint(MazeType &maze,PosType curpos);//标记当前位 置不可通PosType NextPos(PosType curpos,DirectiveTypedi);// 进入下一位置 }ADT yanshu 3、本程序包括三个模块 a、主程序模块 void main() { 初始化；

实验报告迷宫问题

实习2栈的应用 本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对栈这种结构的构造方法的理解。 实验课时6课时 程序1：迷宫问题 ［问题描述］ 以一个m×n的长方阵表示迷宫，‘0’和‘1’分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 ［基本要求］ 首先实现一个以顺序表或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），… ［测试数据］ 迷宫的测试数据如下：左上角（1，1）为入口，右下角（3，4）为出口。[实现提示] 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道，可以二维数组存储迷宫数据。 [程序实现] #include #include //1.迷宫位置坐标类型 typedefstruct { intx;//行 inty;//列 }PosType; #defineMAXENGTH25//迷宫最大行列数位25 typedefintMazeType[MAXENGTH][MAXENGTH];//迷宫数列 typedefstruct//定义栈 { intord;//通道块在路径上的序号 PosTypeseat;//通道块在迷宫中的位置 intdi;//走向下一块的方向（0~3表示东、南、西、北） }SElemType;

迷宫问题实验报告用栈解决迷宫问题

数据结构实验报告 题目：用栈解决迷宫问题 ．需求分析 1．以结构体 Maze 表示迷宫，其中 pos 表示该位置是否有障碍； freq 记录该位置被经过的次数；数组 move 表示下一步的方向。 2. 本程序自动随机生成一个12 × 12大小的迷宫，字符“ H”表示有障碍，空符表示通 路。 3. 迷宫的入口为左上角，出口为右下角。 4. 本程序只求出一条成功的通路。 .概要设计 为了实现上述操作，以栈为存储结构。 本程序包含三个模块： 1)主程序模块 :实现人机交互。 2)迷宫生产模块:随机产生一个12× 12的迷 宫。 3)路径查找模块：实现通路的查找。 4)求解迷宫中一条通路的伪代码： do{ 若当前位置可同，则{ 将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；} 否则 { 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针 方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈 至栈空。 } } } while( 栈不空 ) 三. 详细设计栈的设计： typedef struct { Node *base,*top; int length; }Stack; Stack *initstack(); // 初始化栈 void printstack(Stack *s); // 打印栈 Status destroy(Stack *); // 销毁整个栈 Status deltop(Stack *s); // 出栈 Status pushelem(Stack *,ElemType ,ElemType); // 进栈 1. 主程序模块： int main() { printf(" 随机产生一个12× 12 的迷宫， X 字符表示障碍，空符表示通路： \n"); Maze a[N][N]; makemaze(a); printf(" 输入回车键显示路径 ,* 字符表示路径。 \n"); getchar(); findpath(a); while(1); return 0;