📄 迷宫问题.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0042)http://vip.6to23.com/dcyu/TurboC/DS/2.html -->
<HTML><HEAD><TITLE>Turbo C</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<STYLE type=text/css>BODY {
SCROLLBAR-FACE-COLOR: #ffffff
}
INPUT {
FONT-SIZE: 12px; FONT-FAMILY: "宋体"
}
INPUT {
FONT-SIZE: 12px; FONT-FAMILY: "宋体"
}
.border {
BORDER-RIGHT: 1px dotted; BORDER-TOP: 1px dotted; BORDER-LEFT: 1px dotted; COLOR: #000000; BORDER-BOTTOM: 1px dotted; BORDER-COLLAPSE: collapse; BACKGROUND-COLOR: #efefef
}
.border {
BORDER-RIGHT: 1px dotted; BORDER-TOP: 1px dotted; BORDER-LEFT: 1px dotted; COLOR: #000000; BORDER-BOTTOM: 1px dotted; BORDER-COLLAPSE: collapse; BACKGROUND-COLOR: #efefef
}
.input {
FONT-SIZE: 9pt; FONT-FAMILY: 宋体,Verdana, Arial, Helvetica, sans-serif
}
.links {
FONT-SIZE: 9pt; COLOR: #000000; FONT-FAMILY: 宋体,Verdana, Arial, Helvetica, sans-serif
}
</STYLE>
<META content="sumipntg 011, default" name="Microsoft Theme">
<META content="MSHTML 6.00.2800.1400" name=GENERATOR></HEAD>
<BODY text=#000066 vLink=#666699 aLink=#990099 link=#3333cc bgColor=#ffffff
background=迷宫问题.files/sumtextb.htm>
<P> </P>
<DIV align=center>
<P><BR><A href="http://www.6to23.com/vip/asp/"><BR></A></P>
<TABLE height=24 cellSpacing=0 cellPadding=0 width=689 align=center border=0>
<TBODY>
<TR>
<TD width=94>
<P align=center><FONT color=#0000ff size=2> </FONT><A
href="http://vip.6to23.com/dcyu/TurboC/summarize.html"><FONT color=#0000ff
size=2>概述</FONT></A></P></TD>
<TD width=94>
<P align=center><A
href="http://vip.6to23.com/dcyu/TurboC/basic.html"><FONT color=#0000ff
size=2>初级篇</FONT></A></P></TD>
<TD width=94>
<P align=center><A
href="http://vip.6to23.com/dcyu/TurboC/advance.html"><FONT color=#0000ff
size=2>中级篇</FONT></A></P></TD>
<TD width=94>
<P align=center><A
href="http://vip.6to23.com/dcyu/TurboC/senior.html"><FONT color=#0000ff
size=2>高级篇</FONT></A></P></TD>
<TD width=94>
<P align=center><A
href="http://vip.6to23.com/dcyu/TurboC/sutra.html"><FONT color=#0000ff
size=2>经典篇</FONT></A></P></TD>
<TD width=94>
<P align=center><A
href="http://vip.6to23.com/dcyu/TurboC/algorithm.html"><FONT color=#0000ff
size=2>算法篇</FONT></A></P></TD>
<TD width=94>
<P align=center><FONT size=2> </FONT><A
href="http://vip.6to23.com/dcyu/TurboC/DS.html"><FONT color=#0000ff
size=2><SPAN
style="BACKGROUND-COLOR: #00ff00">数据结构</SPAN></FONT></A></P></TD>
<TD width=100>
<P align=center><A href="http://vip.6to23.com/dcyu/index.html"><FONT
color=#0000ff size=2>回到首页</FONT></A> </P></TD></TR></TBODY></TABLE>
<TABLE height=542 cellSpacing=0 cellPadding=0 width=619 border=0>
<TBODY>
<TR>
<TD vAlign=top width=138 bgColor=#ffffff height=493>
<TABLE height=482 cellSpacing=0 cellPadding=0 width=686
background=迷宫问题.files/vccode.htm border=0>
<TBODY>
<TR>
<TD align=left width="100%" height=21>2.迷宫问题
<P><FONT color=#0000ff>问题</FONT>：找到迷宫中的一条出路，找到打印出路径，找不到这打印出Path not
found。</P>
<P><FONT
color=#0000ff>算法</FONT>：实现迷宫的算法很多，有用栈实现和回溯实现以及用队列实现的，这里介绍用堆栈实现的</P>
<P>例子，下面是程序的一个部分。</P>
<P><BR>typedef struct { <BR> int x;<BR> int y;<BR>}
PosType;<BR><BR>typedef struct { <BR> int
ord;<BR> PosType seat;<BR> int di;<BR>}
SElemType;<BR><BR>typedef struct {<BR> int td;<BR> int
foot;<BR> int mark;<BR>} MazeType;<BR><BR>typedef struct
{<BR> SElemType *base;<BR> SElemType *top;<BR> int
stacksize;<BR>} Stack;<BR><BR>int Maze[20][30];<BR>MazeType
maze[20][30];</P>
<P><BR>Status InitStack(Stack *s)<BR>/* The stack s has been created
and is initialized to be empty.
*/<BR>{<BR> s->base=(SElemType
*)malloc(STACK_INIT_SIZE*sizeof(SElemType));<BR> if(!s->base)
Error("Overflow");<BR> s->top=s->base;<BR> s->stacksize=STACK_INIT_SIZE;<BR> return
OK;<BR>} /* InitStack */<BR><BR>Status DestroyStack(Stack *s)<BR>/*
The stack s has been destroyed.
*/<BR>{<BR> s->top=NULL;<BR> s->stacksize=0;<BR> free(s->base);<BR> s->base=NULL;<BR> return
OK;<BR>} /* DestroyStack */<BR><BR>Status ClearStack(Stack *s)<BR>/*
The stack has been clear to be maximum.
*/<BR>{<BR> s->top=s->base;<BR> s->stacksize=STACK_INIT_SIZE;<BR> return
OK;<BR>} /* ClearStack */<BR><BR>Boolean StackEmpty(Stack *s)<BR>/*
Check if the stack s is empty.
*/<BR>{<BR> if(s->top==s->base) return
TRUE;<BR> else return FALSE;<BR>} /* StackEmpty */<BR><BR>int
StackLength(Stack *s)<BR>/* Gain the length of the stack s.
*/<BR>{<BR> if(s->top>s->base) return
(int)(s->top-s->base);<BR> else return 0;<BR>} /*
StackLength */<BR><BR>Status Push(Stack *s,SElemType e)<BR>/* The
element e has been pushed into the stack s.
*/<BR>{<BR> if(s->top-s->base>=s->stacksize)<BR>{<BR> s->base=(SElemType
*)realloc(s->base,<BR> (s->stacksize+STACKINCREMENT)*sizeof(SElemType));<BR> if(!s->base)
Error("Overflow");<BR> s->top=s->base+s->stacksize;<BR> s->stacksize+=STACKINCREMENT;<BR>}<BR> *s->top++=e;<BR> return
OK;<BR>} /* Push */<BR><BR>SElemType Pop(Stack *s,SElemType e)<BR>/*
The element e has been removed from the stack s.
*/<BR>{<BR> if(s->top==s->base)
Error("Pop");<BR> e=*--s->top;<BR> return e;<BR>} /*
Pop */<BR><BR>Status GetTop(Stack *s,SElemType *e)<BR>/* The element
e has got to the top of the stack
s.*/<BR>{<BR> if(s->top==s->base)
Error("GetTop");<BR> *e=*(s->top-1);<BR> return
OK;<BR>} /* GetTop */<BR><BR>/* Traverse the stack s using
'visiting' function. */<BR>/* Status StackTraverse(Stack *s,Status
(* visit)(SElemType *se))<BR>{<BR> SElemType p;<BR> int
result;<BR> if(s->top==s->base) return
ERROR;<BR> p=s->base;<BR> while(!(p==s->top))<BR> {<BR>
result=(*visit)(p);<BR> p++;<BR> }<BR> return
OK;<BR>} */<BR><BR>Boolean Pass(PosType curpos)<BR>/* Check if the
current position can be passed.
*/<BR>{<BR> if(maze[curpos.x][curpos.y].td==1&&<BR> maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0)<BR> return
TRUE;<BR> else return FALSE;<BR>} /* Pass */<BR><BR>void
MarkPrint(PosType seat)<BR>/* Mark the position seat.
*/<BR>{<BR> maze[seat.x][seat.y].mark=-1;<BR>/* Marking '-1'
symbolize the current position cannot be put. */<BR>} /* MarkPrint
*/<BR><BR>void FootPrint(PosType curpos)<BR>/* The foot of the
curpos of the maze has been set 'true'.
*/<BR>{<BR> maze[curpos.x][curpos.y].foot=1;<BR>} /* FootPrint
*/<BR><BR>PosType NextPos(PosType seat,int
di)<BR>{<BR> switch(di)<BR> {<BR> case 1: seat.y++;
return seat; /* Eastward */<BR><BR> case 2: seat.x++; return
seat; /* Southward */<BR><BR> case 3: seat.y--; return seat;
/* Westward */<BR><BR> case 4: seat.x--; return seat; /*
Northward */<BR><BR> default: seat.x=0; seat.y=0; return
seat;<BR> }<BR>} /* NextPos */<BR><BR><BR>/* The key to the
program. */<BR>/* Pre: The maze array & the startplace & the
endplace.<BR>Post: Find the one traverse of the maze and perform the
mazepath.<BR>Uses: The ADT stack class.<BR>*/<BR><BR>Status
MazePath(PosType start,PosType end)<BR>{<BR> PosType
curpos;<BR> int curstep;<BR> SElemType e;<BR> Stack
*s,stack;<BR> stack.base=(SElemType
*)malloc(STACK_INIT_SIZE*sizeof(SElemType));<BR> if(!stack.base)
Error("Overflow");<BR> stack.top=stack.base;<BR> stack.stacksize=STACK_INIT_SIZE;<BR> s=&stack;<BR> curpos=start;<BR> curstep=1;<BR> do<BR> {<BR>
if(Pass(curpos))<BR> {<BR>
FootPrint(curpos);<BR> e.ord=curstep;
e.seat=curpos; e.di=1;<BR>
gotoxy((curpos.y+1)*2,curpos.x+2);<BR>
putch('@');<BR> delay(8000); /* pospone time.
*/<BR> Push(s,e);<BR>
if(curpos.x==end.x&&curpos.y==end.y) /* Proceed recursively.
*/<BR> {<BR>
DestroyStack(s);<BR> return
TRUE;<BR> }<BR> curpos=NextPos(curpos,1); /*
Try next position. */<BR> curstep++;<BR>
}<BR> else<BR> {<BR>
if(!StackEmpty(s))<BR>
{<BR> e=Pop(s,e); /* Removed e from s.
*/<BR>
while(e.di==4&&!StackEmpty(s)) /* Four directions have been
checked<BR>
and s is not empty. */<BR>
{<BR>
MarkPrint(e.seat);<BR>
gotoxy((e.seat.y+1)*2,e.seat.x+2);<BR>
putch('@');<BR> delay(8000); /*
Pospone time. */<BR>
gotoxy((e.seat.y+1)*2,e.seat.x+2);<BR>
putch(' ');<BR> e=Pop(s,e); /*
Remove e from s. */<BR>
curstep--;<BR> }<BR>
if(e.di<4) /* The current position hasnot been checked.
*/<BR>
{<BR>
e.di++;<BR> Push(s,e); /* Insert
e into s. */<BR>
curpos=NextPos(e.seat,e.di); /* Try next position.
*/<BR> }<BR>
}<BR>
}<BR> }<BR> while(!StackEmpty(s));<BR> DestroyStack(s);<BR> return
FALSE;<BR>} /* MazePath */<BR></P>
<P>完整的程序见：</P>
<P>程序：<A href="http://vip.6to23.com/dcyu/TurboC/DS/maze.zip"><FONT
color=#0000ff>maze.zip</FONT></A><FONT
color=#0000ff> </FONT><FONT
color=#0000ff> </FONT><A
href="http://vip.6to23.com/dcyu/TurboC/DS/1.html"><FONT
color=#0000ff>上一页</FONT></A><FONT
color=#0000ff>
</FONT><A href="http://vip.6to23.com/dcyu/TurboC/DS/2.html"><FONT
color=#0000ff>下一页</FONT></A></P>
<P> </P></TD></TR>
<TR>
<TD align=left width="100%" height=21>
</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<HR align=center width=740 color=#8fb373 noShade SIZE=1>
<TABLE cellSpacing=0 cellPadding=0 width="90%" border=0>
<TBODY>
<TR bgColor=#949231>
<TD height=3></TD></TR></TBODY></TABLE>
<TABLE height=37 width=490>
<TBODY>
<TR>
<TD vAlign=top align=left width=486 height=8>
<P align=center><FONT size=2><FONT face=Arial>Copyright
2001-2002</FONT>，<FONT face=Arial>dcyu, All rights reserved</FONT>，
上次更新：2002-10-13</FONT> <FONT color=#000000><BR></FONT><FONT
color=#000080 size=2>E-mail : <A
href="mailto:dcyu@163.net">dcyu@163.net</A> QQ :
28009316 </FONT></P></TD></TR>
<TR>
<TD class=mainfont vAlign=top align=left width=486 height=17>
<P align=center><FONT size=2>建议使用IE 5.0以上版本进行浏览
最佳显示分辨率800*600</FONT></P></TD></TR></TBODY></TABLE> </DIV></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -