⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 迷宫问题_数据结构与算法_数据结构算法_c语言_c 语言之家.htm

📁 严蔚民版的数据结构的完整课件
💻 HTM
📖 第 1 页 / 共 3 页
字号:
🔍
123 
          <TD></TD></TR>
        <TR>
          <TD background="迷宫问题_数据结构与算法_数据结构算法_C语言_C 语言之家.files/banbg.gif" 
          width=20>　</TD>
          <TD background="迷宫问题_数据结构与算法_数据结构算法_C语言_C 语言之家.files/banbg.gif" 
          height=20 width=530>当前位置：<A class=class 
            href="http://www.cstudyhome.com/wenzhang06/">网站首页</A>&gt;&gt;<A 
            class=class 
            href="http://www.cstudyhome.com/wenzhang06/type.asp?typeid=11">C语言</A>&gt;&gt;<A 
            class=class 
            href="http://www.cstudyhome.com/wenzhang06/BigClass.asp?typeid=11&amp;BigClassid=33">数据结构算法</A>&gt;&gt;<A 
            class=class 
            href="http://www.cstudyhome.com/wenzhang06/SmallClass.asp?typeid=11&amp;BigClassID=33&amp;SmallClassID=60">数据结构与算法</A></TD>
          <TD background="迷宫问题_数据结构与算法_数据结构算法_C语言_C 语言之家.files/banbg.gif" 
          height=20 width=107>双击自动滚屏</TD>
          <TD background="迷宫问题_数据结构与算法_数据结构算法_C语言_C 语言之家.files/banbg.gif" 
          width=91><INPUT name=close onclick="window.close();return false;" type=button value=关闭窗口> 
          </TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<TABLE align=center border=3 borderColor=#e2ca9f cellPadding=0 cellSpacing=0 
style="BORDER-COLLAPSE: collapse" width=750>
  <TBODY>
  <TR><!--<td width="20%" align="middle" valign="top" background="images/002.jpg" bordercolor="#e2ca9f"> </td> 
<td width="80%">-->
    <TD width="100%">
      <TABLE border=0 borderColor=#e2ca9f cellPadding=0 cellSpacing=0 
      width="100%">
        <TBODY>
        <TR>
          <TD align=middle vAlign=top width="95%">
            <TABLE border=1 borderColor=#e2ca9f cellPadding=0 cellSpacing=0 
            width="100%">
              <TBODY>
              <TR>
                <TD align=middle 
                background="迷宫问题_数据结构与算法_数据结构算法_C语言_C 语言之家.files/002.jpg" 
                borderColor=#e2ca9f vAlign=top width="69%">
                  <TABLE align=center border=0 cellPadding=0 cellSpacing=0 
                  width="100%">
                    <TBODY>
                    <TR>
                      <TD height=40 width="100%"></TD></TR>
                    <TR>
                      <TD>
                        <FORM action=Readnews.asp?newsid=4810&amp;id2=4810 
                        method=post name=form1>
                        <CENTER><!-- <input type=submit name=aa value="点击关闭浮动图标" width=20 title="点击广告支持本站">--></CENTER></FORM></TD></TR>
                    <TR>
                      <TD align=middle bgColor=#dddddd height=20 
                      style="FONT-SIZE: 18px" vAlign=bottom 
                        width="85%"><STRONG><FONT color=#003399 size=4><B>迷宫问题 
                        </B></FONT></STRONG></TD><BR></TR>
                    <TR>
                      <TD align=middle width="100%"><BR></TD></TR>
                    <TR>
                      <TD align=middle style="FONT-SIZE: 9pt" 
                        width="100%">发表日期：2004年12月12日&nbsp;&nbsp;出处：原创&nbsp;&nbsp;作者：SET&nbsp;&nbsp;已经有536位读者读过此文</TD></TR>
                    <TR>
                      <TD align=middle width="100%"><!--下面的这一句是设置阅读文本区的宽度-->
                        <TABLE align=center border=0 cellPadding=0 cellSpacing=0 
                        style="TABLE-LAYOUT: fixed" width="90%">
                          <TBODY>
                          <TR>
                            <TD align=middle width="100%"></TD></TR>
                          <TR>
                            <TD style="WORD-WRAP: break-word"><FONT 
                              class=news><BR>
                              <P>/*为解决迷宫问题可按如下方式对迷宫进行转化&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*设有迷宫：&nbsp; 
                              ‘H’为边界，‘01’等为迷宫中的结点。为讨论方便设：起点总为01，终点总为16&nbsp;&nbsp; 
                              &nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HHHHHHHHHHHHHHHHHHHHHHHHHH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              &nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              01&nbsp;&nbsp;&nbsp; 02&nbsp;&nbsp;&nbsp; 
                              03&nbsp;&nbsp;&nbsp; 04 
                              HH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              &nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HH&nbsp;&nbsp;&nbsp; 
                              HHHHHHHHHHHHHH&nbsp;&nbsp;&nbsp; 
                              HH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HH 05&nbsp;&nbsp;&nbsp; 06&nbsp;&nbsp;&nbsp; 07 HH 
                              08 
                              HH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HH&nbsp;&nbsp;&nbsp; HH&nbsp;&nbsp;&nbsp; 
                              HH&nbsp;&nbsp;&nbsp; HH&nbsp;&nbsp;&nbsp; 
                              HH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ 
                              <BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HH 09 HH 10 HH 11&nbsp;&nbsp;&nbsp; 12 
                              HH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HH&nbsp;&nbsp;&nbsp; HH&nbsp;&nbsp;&nbsp; 
                              HHHHHHHHHHHHHH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/&nbsp;<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HH 13 HH 14&nbsp;&nbsp;&nbsp; 15&nbsp;&nbsp;&nbsp; 
                              16&nbsp; 
                              &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              &nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              HHHHHHHHHHHHHHHHHHHHHHHHHH&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*上图可转化为4 
                              x 
                              4无向图:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              01--02--03--04 
                              &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              |&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              | 
                              &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              05--06--07&nbsp; 
                              08&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              |&nbsp;&nbsp; |&nbsp;&nbsp; |&nbsp;&nbsp; 
                              |&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              09&nbsp; 10&nbsp; 
                              11--12&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              |&nbsp;&nbsp; 
                              |&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              13&nbsp; 
                              14--15--16&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*而无向图可用序偶表示，如上图中‘01--02’可表示为&lt;01,02&gt;,&lt;02,01&gt;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*其他结点间的连线也可依此方法表示&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*这样的话，记录迷宫就是记录表示迷宫中所有结点连线的序偶&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*在此程序中是用二维数组来实现的，即mg[5][17],现取其中一列说明其含义&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*如：mg[][5]={0}-------&gt;表示结点5是否被访问过，0=未访问，1=已访问&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {1}-------&gt;表示结点5在‘上’方向上是否与其他结点有连线，1=与结点1有连线&nbsp;&nbsp;*/&nbsp;<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {6}-------&gt;表示结点5在‘右’方向上是否与其他结点有连线，6=与结点6有连线&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {9}-------&gt;表示结点5在‘下’方向上是否与其他结点有连线，9=与结点9有连线&nbsp;&nbsp;*/ 
                              <BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {0}-------&gt;表示结点5在‘左’方向上是否与其他结点有连线，0=与其他结点无连线&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*数组mg中其他结点也以同样方式表示&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*现在要在迷宫中找最短出路就可转化为对无向图的广度优先遍历&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*具体由两个函数来实现&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*search1依靠队列queue实现从01-&gt;16的正向找路&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;1）从队列中取结点i，&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;2）按顺时针方向检查结点i的4个方向v&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              若i在方向v上能与结点w相连，则检查w是否被访问过&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              &lt;1&gt;若没有被访问过，则擦掉i到w的连线，并置w为已访问&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ 
                              <BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              若w=16,则说明已达到终点，跳出search1；否则w进队&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              &lt;2&gt;否则擦掉w到i的连线 
                              &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*照上述方法广度优先遍历图，若没结果则返回1，说明迷宫无路可走&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/&nbsp;<BR>/*若search1找到路，则search2从终点16开始倒走&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*此时由于 
                              search1的处理，从终点开始的结点i的四个方向一般只剩一个方向上有连线了&nbsp;&nbsp;&nbsp;*/&nbsp;<BR>/*这样search2只要边走边保存走过的结点就可得迷宫的最短出路了&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*特殊情况是有几个方向可以连到结点u时，此时有几条路是假的，如v-&gt;u，若v-&gt;u有连线说明此路不通&nbsp;*/<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>&nbsp;&nbsp; 
                              /*1&nbsp; 2&nbsp; 3&nbsp; 4&nbsp; 5&nbsp; 6&nbsp; 
                              7&nbsp; 8&nbsp; 9 10 11 12 13 14 15 16*/<BR>int 
                              mg[5][17]={{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                              0, 0, 0, 
                              0},<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {0, 0, 0, 0, 0, 1, 0, 0, 4, 5, 6, 7, 8, 9,10, 0, 
                              0},<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {0, 2, 3, 4, 0, 6, 7, 0, 0, 0, 0,12, 0, 0,15,16, 
                              0},<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {0, 5, 0, 0, 8, 9,10,11,12,13,14, 0, 0, 0, 0, 0, 
                              0},<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              {0, 0, 1, 2, 3, 0, 5, 6, 0, 0, 0, 0,11, 0, 
                              0,14,15}};<BR>char t[9][18]={0};<BR>int 
                              search1()<BR>&nbsp; {int qa=0, qe=0, 
                              queue[100]={0};<BR>&nbsp;&nbsp; int i, j, u=1, v, 
                              w, end=16;<BR>&nbsp;&nbsp; 
                              mg[0][u]=1;<BR>&nbsp;&nbsp; 
                              queue[0]=u;<BR>&nbsp;&nbsp; 
                              while(qa&lt;=qe)<BR>&nbsp;&nbsp;&nbsp;&nbsp; 
                              {v=queue[qa++];<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              for (i=1; i&lt;5; i++)<BR>&nbsp;{if (mg[i][v]==0) 
                              continue;<BR>&nbsp; w=mg[i][v];<BR>&nbsp; if 
                              (mg[0][w]==0)<BR>&nbsp;&nbsp;&nbsp; 
                              {mg[i][v]=0;<BR>&nbsp;&nbsp;&nbsp;&nbsp; 
                              mg[0][w]=1;<BR>&nbsp;&nbsp;&nbsp;&nbsp; if 
                              (w==end) return(1);<BR>&nbsp;&nbsp;&nbsp;&nbsp; 
                              queue[++qe]=w;<BR>&nbsp;&nbsp;&nbsp; }<BR>&nbsp; 
                              else<BR>&nbsp;&nbsp;&nbsp; for (j=1; j&lt;5; 
                              j++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if 
                              (mg[j][w]==v) 
                              mg[j][w]=0;<BR>&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp; 
                              }<BR>&nbsp;&nbsp; return(0);<BR>&nbsp; 
                              }<BR>search2(r)<BR>&nbsp; int *r;<BR>&nbsp; {int 
                              f, i, j, k, u, v;<BR>&nbsp;&nbsp; for (i=0, u=16; 
                              ;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp; 
                              {r[i]=u;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if 
                              (u==1) return;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                              for (j=1; j&lt;5; j++)<BR>&nbsp;{if (mg[j][u]==0) 
                              continue;<BR>&nbsp; v=mg[j][u];<BR>&nbsp; for
123

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -