PHP数组模拟常用数据结构

复制PHP内容到剪贴板

PHP代码:

<?php
/**
* PHP数组实现单链表结构
*   此类主要是依靠PHP强大的数组系统来模拟出单链表类型的数据结构。 本人完全凭借自己的
* 兴趣来编写此类，并未考虑其实用性，主要是给大家理解一些简单的数据结构知识，同时也训练
* 一下PHP中的数组运用能力。
*单链表简介：
* 单链表是最简单的链表表示。用它来表示线性表时，每一个数据元素占用一个结点(node)。一个
* 结点一般由两个域组成，一个域存放数据元素data； 另一个域存放一个指向链表中下一个结点的
* 指针link，它指出下一个结点 的开始存储地址。而最后一个结点的指针为空。单链表中数据元素
* 之间的逻 辑关系是由结点中的指针指示的，换句话说，指针为数据元素之间的逻辑关系的映象，则
* 逻辑上相邻的两个元素其存储的物理位置不要求紧邻，因此， 这种存储结构为非顺序映像或链式映像。
* 当然，在PHP没有指针这个概念，但是我们可以用关联数组来模拟。
* @version 1.0
* @author 玉面修罗<[email protected]>
*/
class LinkList 
{
   /**
    * 成员变量
    * @var array    $linkList       链表数组
    * @var number   $listHeader     表头索引
    * @var number   $listLength     链表长度
    * @var number   $existedCounts  记录链表中出现过的元素的个数，和$listLength不同的是, 删除一
    *                               个元素之后，该值不需要减1，这个也可以用来为新元素分配索引。                          
    */
   protected  $linkList  =array();
   protected  $listLength=0;
   protected  $listHeader=null;
   protected  $existedCounts=0;
   /**
    * 构造函数
    *   构造函数可以带一个数组参数，如果有参数，则调用成员方法
    * createList将数组转换成链表，并算出链表长度.如果没有参
    * 数，则生成一空链表.空链表可以通过调用成员方法createList
    * 生成链表.
    * @access public
    * @param  array $arr 需要被转化为链表的数组
    */
   public function __construct($arr='')
   {
     $arr!=null&&$this->createList($arr);
   }
   /**
    * 生成链表的函数
    *   将数组转变成链表，同时计算出链表长度。分别赋值给成员标量
    * $linkList和$listLength.
    * @access public
    * @param  array $arr 需要被转化为链表的数组
    * @return boolean  true表示转换成功，false表示失败  
    */
  public function createList($arr)
  { 
   if (!is_array($arr)) 
    return false;
   $length=count($arr);
   for($i=0;$i<$length;$i++)
   {   
       if($i==$length-1)
       {
        //每个链表结点包括var和next两个索引，var表示结点值，next为下一个结点的索引
        //最后一个结点的next为null
        $list[$i]['var']  =$arr[$i];
        $list[$i]['next'] =null;
       }
       else 
       {
        $list[$i]['var']  =$arr[$i];
        $list[$i]['next'] =$i+1;
       }
   }
   $this->linkList      =$list;
   $this->listLength    =$length;
   $this->existedCounts =$length;
   $this->listHeader=0;
   return true;
  }
  /**
   * 将链表还原成一维数组
   * @access public
   * @return array    $arr  生成的一维数组
   */
  public function returnToArray()
  { 
   $arr=array();
   $tmp=$this->linkList[$this->listHeader];
    for($i=0;$i<$this->listLength;$i++)
   {
     $arr[]=$tmp['var'];
     if ($i!=$this->listLength-1) 
     {
     $tmp=$this->linkList[$tmp['next']];
     }
   }
   return $arr;
  }
/***************************下面接*******************************/

复制PHP内容到剪贴板

PHP代码:

/***********************接上面**********************************/
/**
   * 返回链表的长度
   * @access public
   * @return number $listLength 链表的长度
   */
  public function getLength()
  {
      return $this->listLength;
  }
  /**
   * 计算一共删除过多少个元素
   * @access public 
   * @return number $count 到目前为止删除过的元素个数
   */
  public function getDeletedNums()
  {
      $count=$this->existedCounts-$this->listLength;
      return $count;
  }
  /**
   * 通过元素索引返回元素序号
   * @access protected
   * @param  $index     元素的索引号
   * @return $num       元素在链表中的序号
   */
  public function getElemLocation($index)
  {
  if (!array_key_exists($index,$this->linkList)) 
   return false;
    $arrIndex=$this->listHeader;
    for($num=1;$tmp=$this->linkList[$arrIndex];$num++)
    {
        if ($index==$arrIndex) 
        break;
        else 
        {
            $arrIndex=$tmp['next'];
        }
    }
    return $num;
  }
  /**
   * 获取第$i个元素的引用
   *   这个保护方法不能被外界直接访问，许多服务方法以来与次方法。
   * 它用来返回链表中第$i个元素的引用，是一个数组
   * @access protected
   * @param  number $i 元素的序号
   * @return reference 元素的引用
   */
  protected function &getElemRef($i)
  {
      //判断$i的类型以及是否越界
      $result=false;
      if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength) 
      return $result;
   //由于单链表中的任何两个元素的存储位置之间没有固定关系，要取得第i个元素必须从
   //表头开始查找，因此单链表是非随机存储的存储结构。
   $j=0;
   $value=&$this->linkList[$this->listHeader];
   while ($j<$i-1)
   {
       $value=&$this->linkList[$value['next']];
       $j++;
   }
   return $value;
  }
  /**
   * 返回第i个元素的值
   * @access public
   * @param  number $i     需要返回的元素的序号，从1开始
   * @return mixed  第i个元素的值
   */
  public function getElemvar($i)
  {
    $var=$this->getElemRef($i);
    if ($var!=false) 
    {
        return $var['var'];
    }
    else return false;
  }
  /**
   *   在第i个元素之后插入一个值为var的新元素
   *   i的取值应该为[1,$this->listLength]，如果i=0，表示在表的最前段插入，
   * 如果i=$this->listLength，表示在表的末尾插入,插入的方法为，将第$i-1个元素
   * 的next指向第$i个元素，然后将第$i个元素的next指向第$i+1个元素，这样就实现了插入
   * @access public
   * @param  number $i   在位置i插入新元素
   * @param  mixed  $var 要插入的元素的值 
   * @return boolean  成功则返回true,否则返回false
   */
  public function insertIntoList($i,$var)
  {
      if (!is_numeric($i)||(int)$i<0||(int)$i>$this->listLength) 
      return false;
      if ($i==0) 
      {
      //如果$i-0，则在表最前面添加元素，新元素索引为$listLength，这样是确保不会
      //覆盖原来的元素，另外这种情况需要重新设置$listHeader
          $this->linkList[$this->existedCounts]['var'] =$var;
          $this->linkList[$this->existedCounts]['next']=$this->listHeader;
          $this->listHeader=$this->existedCounts;
          $this->listLength++;
          $this->existedCounts++;
          return true;    
      }
   $value=&$this->getElemRef($i);
   $this->linkList[$this->existedCounts]['var'] =$var;
   $this->linkList[$this->existedCounts]['next']=($i==$this->listLength?null:$value['next']);
   $value['next']=$this->existedCounts;
   $this->listLength++;
   $this->existedCounts++;
   return true;
  }
  /**
   * 删除第$i个元素
   *   删除第$i个元素，该元素为取值应该为[1，$this->listLength],需要注意，删除元素之后，
   * $this->listLength减1,而$this->existedCounts不变。删除的方法为将第$i-1个元素的
   * next指向第$i+1个元素，那么第$i个元素就从链表中删除了。
   * @access public
   * @param  number $i 将要被删除的元素的序号
   * @return boolean    成功则返回true,否则返回false
   */
  public function delFromList($i)
  {
      if (!is_numeric($i)||(int)$i<=0||(int)$i>$this->listLength) 
      return false;
    if ($i==1) 
    {
    //若删除的结点为头结点，则需要从新设置链表头
      $tmp=$this->linkList[$this->listHeader];
      unset($this->linkList[$this->listHeader]);
      $this->listHeader=$tmp['next'];
      $this->listLength--;
      return true;
    }
    else 
    {
     $value    =&$this->getElemRef($i);
     $prevValue=&$this->getElemRef($i-1);
     unset($this->linkList[$prevValue['next']]);
     $prevValue['next']=$value['next'];
     $this->listLength--;
     return true;
    }
  }
 /**
  * 对链表的元素排序
  *  谨慎使用此函数，排序后链表将被从新初始化，原有的成员变量将会被覆盖
  * @accse public
  * @param  boolean  $sortType='true' 排序方式,true表示升序，false表示降序，默认true   
  */
 public function listSort($sortType='true')
 {
   //从新修改关联关系可能会更复杂，所以我选择先还原成一维数组，然后对数组排序，然后再生成链表
   $arr=$this->returnToArray();
   $sortType?sort($arr):rsort($arr);
   $this->createList($arr);
 }
}
?>

复制PHP内容到剪贴板

PHP代码:

/**
* 循环链表结构
*   循环链表是另外一种形式的链式存储结构。他的特点是表中最后的一个结点的指针
* 是指向头结点的，这样整个链表就构成了一个环。循环链表和单链表有很多相似之处
* 因此我们这里直接继承LinkList类来得到循环链表。
* @version 1.0
* @author 玉面修罗<[[email protected]][email protected][/email]>
*/
class CirLinkList extends LinkList  
{
/**
  * 生成循环链表
  *   这里直接重写父类的createList方法，将最后一个结点的指针指向头结点
  * @access public
  * @param  array $arr 需要被转化为循环链表的数组
  * @return boolean  true表示转换成功，false表示失败
  */
public function createList($arr)
{
        if (parent::createList($arr)) 
        {
                $this->linkList[$this->listLength-1]['next']=$this->listHeader;
                return true;
        }
        else return false;
}
/**
  * 在第i个元素之后插入一个值为var的新元素
  *   这里直接重写父类中的insertIntoList函数，需要注意的是：当$i=0,表示插入到头结点之前，
  * 并且新元素变成头结点;当$i=$this->listLength时，表示插到链表最后，并把指针域指向头结点。
  * 虽然它们在环中的位置可以说是相同的，但是意义不同。
  * @access public
  * @param  number $i   在位置i插入新元素
  * @param  mixed  $var 要插入的元素的值 
  * @return boolean  成功则返回true,否则返回false
  */
public function insertIntoList($i,$var)
{
        if (parent::insertIntoList($i,$var)) 
        {
         //insertIntoList会使listLength加1，所以这里listLength-1实际是原来的listLength
                if ($i==0||$i=$this->listLength-1) 
                {
                   $elem=&parent::getElemRef($this->listLength);
                   $elem['next']=$this->listHeader;
                   return true;
                }
        }
        else return false;
}
/**
*删除第$i个元素
*  和父类中的此方法相比，只是当$i=1的时候，需要把尾结点的指针指向新的头结点
* @access public
* @param  number $i 将要被删除的元素的序号
* @return boolean    成功则返回true,否则返回false
*/
public function delFromList($i)
{
        if (parent::delFromList($i)&&$i==1) 
        {
           $elem=&$this->getElemRef($this->listLength);
           $elem['next']=$this->listHeader;
           return true;        
        }
        else return false;
}
}
/**********************************************************************************/

复制PHP内容到剪贴板

PHP代码:

/**
 * 循环链表的运用
 * 问题：现在将a-z26个小写字母按照字母表的顺序逆时针围绕成一个圈，现在从a开始取字母：取字母的
 * 方法为跳1取，比如先取了a,跳过a后面的一个字母b,然后取c,然后取e............如此反复下去，
 * 直到26个字母全部取完，将取出的字母连成一个字符串，请输出此字符串.
 */
class CatchChar extends CirLinkList  
{
  private $objectString;
 /**
  * 求字符串的方法
  *  @access public
  *  @return boolean 
  */
   public function createString()
   {
         $str='';
         $arrIndex=$this->listHeader;
        while ($this->listLength!=0) 
         {
             $curr=$this->linkList[$arrIndex];
        $this->delFromList($this->getElemLocation($arrIndex));
        $arrIndex=@$this->linkList[$curr['next']]['next'];
        $str.=$curr['var'];
      }
     
         $this->objectString=$str;
         return true;
   }
  /**
   * 取出字符串
   */
  public function getString()
  {
      return $this->objectString;
  }
}

复制PHP内容到剪贴板

PHP代码:

<?php
$test=new CatchChar(range('a','z'));
$test->createString();
echo $test->getString();
?>

复制内容到剪贴板

代码:

acegikmoqsuwybfjnrvzhpxldt

复制PHP内容到剪贴板

PHP代码:

/**
* 栈(stack)
* 简介：
* 栈(stack)是限定仅在表尾进行插入和删除操作的线性表。因此对栈来说，表尾端有其特殊含义
*，称为栈顶(top),相应的，表头端称为栈底(bottom),不含元素的空表称为空栈。
* 对栈中元素的操作是按后进先出(Last In First Out,简称LIFO)的原则进行的，即最后压入的
* 元素最先弹出。
*  类中还是用PHP的数组来实现栈结构，只是封装了一些操作，为什么封装呢？因为
* 我们要限定对栈的操作只能在表头进行插入和删除，如果是普通的数组的话，不能保证
* 其它元素不被修改。
* @version 1.0
* @author 玉面修罗<[[email protected]][email protected][/email]>
*/
class Stack 
{
/**
* @var array  $stack              栈数组
* @var number $stackLength        栈的长度
* @var number $top                栈顶索引,通常比栈数组最大索引大一
* @var number $base               栈底元素索引，通常都是0
* @var number $maxLength          最大栈长
* @var number STACKINCREMENT      栈长的增长幅度
*/
private $stack            =array();
private $stackLength      =null;
private $top              =null;
private $base             =null;
private $maxLength        =100;
const   STACKINCREMENT    =10;

public function __construct()
{   
    $this->top          =0;
    $this->base         =0;
    $this->stackLength  =0;
}
/**
  * 判断是否为空栈
  * @return boolean TRUE表示栈空，FLASE表示栈非空
  */
  public function isEmpty()
  {
          if ($this->stackLength==0) 
          return true;
          else return false;
  }
/**
  * 将栈清空
  */
public function clearStack()
{
   unset($this->stack);
   $this->__construct();
   if($this->isEmpty()) 
   return true;
   else return false;
}
/**
* 获取栈长
*/
public function getStackLength()
{
        return $this->stackLength;
}
/**
*获取栈顶元素的值
* @return mixed $topVal 栈顶元素的值 
*/
public function getTopValue()
{
        if ($this->isEmpty()) 
    return false;
    else
    return $this->stack[$this->top-1];
}
/**
* 获取栈数组
*/
public function getStackArray()
{
        return $this->stack;
}
/**
  * 增加栈的最大长度
  * @param number $length 长度增量
  */
private function addMaxLength($length)
{
    return  $this->maxLength+=$length;
}
/**
  * 元素进栈
  *   将新的元素进栈，进栈之前需要判断栈的长度是否超过最大长度，如果超过，
  * 则自动增加栈长,
  * @param  mixed $newVal 新的元素值
  */
public function push($newVal)
{
    if ($this->stackLength==$this->maxLength) 
    $this->maxLength=$this->addMaxLength(self::STACKINCREMENT);
    $this->stack[$this->stackLength]=$newVal;
    $this->top++;
    $this->stackLength++;
    return true;
}
/**
* 元素出栈
*  将元素弹出栈，先要判断堆栈是否为空，如果为空，则返回FALSE。
* @return mixed $var 弹出的元素值
*/
public function pop()
{
        if ($this->isEmpty()) 
        return false;
        else 
        {
        $var=$this->stack[$this->top-1];
        unset($this->stack[$this->top-1]);
        $this->top--;
        $this->stackLength--;
        return $var;
        }
}
}

复制PHP内容到剪贴板

PHP代码:

$myStack=new stack();//新建一个空栈
$myStack->push(5);//插入5
$myStack->push(89);//插入89
$myStack->push(54);//插入54
echo $myStack->getStackLength();//3
echo '<br>';
echo $myStack->getTopValue();//54
echo '<br>';
$myStack->pop();
$myStack->pop();
echo $myStack->getTopValue();//5
$myStack->clearStack();//销毁栈

复制PHP内容到剪贴板

PHP代码:

class DataConver 
{
   public static function converse($i)
   {
     if ($i<=0||!is_int($i)) 
     {
      echo '请输入一个正十进制整数！';
      return false;
     }
     $stack=new Stack();
     while ((int)$i) 
     {
      $stack->push($i%8);
      $i=$i/8;
     }
     while (!$stack->isEmpty()) 
     {
      $var.=$stack->pop();
     }
     return $var;
   }
}
echo DataConver::converse(10);//12
echo DataConver::converse(1246);//2336

复制PHP内容到剪贴板

PHP代码:

/**
* 迷宫类
*  迷宫为$x*$y的数组，每个数组元素中又包含flag和seat。
* flag为标签，-1表示此位置不可通过，0表示可以通过，1表示可以通过但是曾经路过这里。
* seat为位置，x表示行号，y表示列号。
* 初始化迷宫的所有道路flag为-1,即不可通，然后我们设置入口，出口，所有可通过的道路
* 来新建一个已知的迷宫。
*@author 玉面修罗<[[email protected]][email protected][/email]>
*@version 1.0
*/
class Maze 
{
/**
* @var array  $maze  迷宫数组
* @var number $width 迷宫的列数
* @var number $hight 迷宫的行数
* @var array  $start 起点位置
* @var array  $end   终点位置
*/
  private $maze  =array();
  private $width =0;
  private $hight =0;
  private $start =null;
  private $end   =null;
/**
  * 构造函数
  *   构造一个$x*$y的迷宫
  * @var number $x 迷宫的行数
  * @var number $y 迷宫的列数
  */
  public function __construct($x,$y)
  {  
    if ($this->checkSite($x,$y)) 
    {
     $x=(int)$x;
     $y=(int)$y; 
           for($i=0;$i<$x;$i++)
           {
             for($j=0;$j<$y;$j++)
             {
                     $this->maze[$i][$j]['site']=array('x'=>$i,'y'=>$j);//设置坐标字段，x为行号，y为列号
                     $this->maze[$i][$j]['flag']=-1;//设置坐标位置属性，默认为不可通过
             }
           }
           $this->width=$x;
           $this->hight=$y;
    }
  }
  /**
   * 检测数据合法性
   *
   * @param  number $x
   * @param  number $y
   * @return boolean
   */
protected function checkSite($x,$y)
{
        if ($x<0||!is_numeric($x)||$y<0||!is_numeric($y)) 
           return  false;        
          else return true;
}
/**
  * 设置入口
  * @var    number $x 入口行号
  * @var    number $y 入口列号
  * @return boolean
  */
public function initStart($x,$y)
{   
        if (!$this->checkSite($x,$y)||$x>=$this->width||$y>=$this->hight) 
    return false;
        $this->start=array('x'=>$x,'y'=>$y);
        $this->maze[$x][$y]['flag'] =0;
        return true;
}
/**
  * 设置出口
  * @var    number $x 出口行号
  * @var    number $y 出口列号
  * @return boolean
  */
public function initEnd($x,$y)
{
        if (!$this->checkSite($x,$y)||$x>=$this->width||$y>=$this->hight) 
     return false;
        $this->end=array('x'=>$x,'y'=>$y);
        $this->maze[$x][$y]['flag'] =0;
        return true;
}
/**
* 获取入口
*/
public function getStart()
{
  return $this->start;
}
/**
* 获取出口
*/
public function getEnd()
{
        return $this->end;
}
/**
* 设置迷宫通路
* @param array $var
*/
public function setPassWay($var)
{  
   if (!is_array($var)) 
        return false;
   $var=array_values($var);
   if (!$this->checkSite($var[0],$var[1])||$var[0]>=$this->width||$var[1]>=$this->hight) 
   {
           return false;
   }
   $this->maze[$var[0]][$var[1]]['flag']=0;
   return true;
}
/**
 *设置标签
 */
public function setFlag($postion,$i)
{
  $this->maze[$postion['x']][$postion['y']]['flag']=$i;        
}
/**
 *获取标签
 */
public function getFlag($postion)
{
        return $this->maze[$postion['x']][$postion['y']]['flag'];
}
/**
 *将迷宫打印输出
 */
public function printMaze()
{
   $str='<table width="343" height="337" border="1" cellpadding="0" cellspacing="0">';
             for($i=0;$i<=$this->width;$i++)
            {
             $str.='<tr>';
             for($j=0;$j<=$this->hight;$j++)
             {
         if($i==0)
         {
          if($j==0)
          $str.='<td> </td>';
          else $str.='<td>'.($j-1).'</td>';        
         }
         else 
         {
           if ($j==0) 
           $str.='<td>'.($i-1).'</td>';
           else
           {
                   switch ($this->maze[$i-1][$j-1]['flag']) 
                   {
                     case -1: $str.='<td bgcolor="#000000"> </td>'; break;
                     case 0:  $str.='<td> </td>';                    break;  
                     case 1:  $str.='<td bgcolor="#FF0000"> </td>'; break;
                   }
           } 
         } 
       }
       $str.='</tr>';
            }
            $str.='</table>';
            echo $str;
           }        
}

复制PHP内容到剪贴板

PHP代码:

$newMaze=new Maze(10,10);//新建一个迷宫
$newMaze->initStart(1,0);//(1,0)为入口
$newMaze->initEnd(8,9);//(8,9)为出口
$wayArray=array(0 =>array(1,1),1 =>array(1,2),2 =>array(2,1),
                3 =>array(2,2), 4 =>array(3,1), 5 =>array(4,1),
                6 =>array(5,1), 7 =>array(6,1), 8 =>array(7,1),
                9 =>array(3,2), 10=>array(5,2),11=>array(8,2),
                12=>array(3,3),13=>array(5,3),14=>array(6,3),
                15=>array(8,3),16=>array(1,4),17=>array(2,4),
                18=>array(3,4),19=>array(6,4),20=>array(8,4),
                21=>array(1,5),22=>array(2,5),23=>array(4,5),
                24=>array(5,5),25=>array(6,5),26=>array(7,5),
                27=>array(8,5),28=>array(1,6),29=>array(2,6),
                30=>array(4,6),31=>array(5,6),32=>array(8,6),
                33=>array(3,7),34=>array(4,7),35=>array(5,7),
                36=>array(6,7),37=>array(8,7),38=>array(1,8),
                39=>array(2,8),40=>array(3,8),41=>array(4,8),
                42=>array(5,8),43=>array(6,8),44=>array(7,8),
                45=>array(8,8));
for($i=0;$i<count($wayArray);$i++)
$newMaze->setPassWay($wayArray[$i]);//设置所有通路
$newMaze->printMaze();//在浏览器输出迷宫

复制PHP内容到剪贴板

PHP代码:

/**
* 迷宫探索者类
* 此类用自己的方法组合栈和迷宫来寻找路径
* 主方法算法如下：
*  设定当前位置的初值为入口位置；
* do{
*   若 当前位置可通
*   则{
*      将当前位置插入栈顶；
*      若该位置是出口位置，则结束；
*      否则切换当前位置的东邻方块为新的当前位置；
*     }
*   否则，
*    若 栈不空且栈顶位置尚有其他方向未经探索，
*      则 设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
*    若 栈不空但栈顶位置的四周均不可通，
*      则{
*         删去栈顶位置，
*         若栈不空，则重新测试新的栈顶位置，
*         直至找到一个可通的相邻或出栈至栈空；
*        }
*   }
* while(栈不空)
* @author 玉面修罗<[[email protected]][email protected][/email]>
* @version 1.0
*/
class MazeExplorer 
{
/**
  * @var  Maze  $maze   迷宫
  * @var  Stack $stack  栈
  * @var  array $curpos 当前位置
  * @var  array $path   所求路径
  */
  private $maze;
  private $stack;
  private $curpos;
  private $path;
/**
  * 构造函数
  *  初始化$maze为需要求路径的迷宫 
  *$stack为一个空栈 $curpos为迷宫入口
  */
public function __construct(Maze $maze)
{
  $this->maze  =$maze;
  $this->stack =new Stack();
  $this->curpos=$this->maze->getStart();
}
/**
* 检查通道块是否可通
*  通道块可通的概念为：此块可以通过，而且以前未曾走过。这个是通过检测块的
* flag字段来判断，由前面对flag的设置可知这里只有flag为0才可通
* @param  array   $postion 通道块坐标
* @return boolean 可通过则返回TRUE ，否则FLASE
*/
private function pass($postion)
{
  if ($this->maze->getFlag($postion)===0)
  return true;
  else return false; 
}
/**
* 留脚印
*  在经过的地方留下自己的脚印，也就是把flag设置为1
* @param  array   $postion 通道块坐标
*/
private function footPrint($postion)
{
   $this->maze->setFlag($postion,1);
}
/**
* 设置下一个通道块
*  设置下一步的方向，1,2,3,4分别为东南西北。
* @param  array  $postion  当前位置
* @param  number $dirction 方向
* @return array  新的位置
*/
private function nextPostion($positon,$dirction)
{
   $positon['dir']=1;
   switch((int)$dirction)
   {
    case 1: $positon['y']++;break;
    case 2: $positon['x']++;break;
    case 3: $positon['y']--;break;
    case 4: $positon['x']--;break;
    default:return false;
   }
  return $positon;
}
/**
* 探索路径
*  类的主方法，用来探索迷宫的路径。
*/
public function searchPath()
{
  $this->curpos['dir']=1;
  do{
    if ($this->pass($this->curpos))//当前位置可以通过 
    {
     $this->footPrint($this->curpos);//留下脚印
     $this->stack->push($this->curpos);//加入路径
     if (array_slice($this->curpos,0,2,true)==$this->maze->getEnd()) //到达终点
     {
     $this->path=$this->stack->getStackArray();
     return true;
     }
        $this->curpos=$this->nextPostion($this->curpos,1);//下一个位置为当前位置的东面
    }
    else//不可通过 
    {
     if (!$this->stack->isEmpty()) 
     {
        $seat=$this->stack->pop();
        while ($seat['dir']==4&&!$this->stack->isEmpty()) 
        {
         $this->footPrint($seat);
         $seat=$this->stack->pop();
        }
        if ($seat['dir']<4) 
        {
         $seat['dir']++; //换下一个方向搜索
         $this->stack->push($seat);
         $this->curpos=$this->nextPostion($seat,$seat['dir']);//设定当前位置的该方向上的相邻块
        }
     }
    }
    }
  while (!$this->stack->isEmpty());
  return false;
}
/**
* 获取结果路径
*/
public function getPath()
{
return $this->path;
}
}

复制PHP内容到剪贴板

PHP代码:

$cloneMaze=clone $newMaze;//克隆刚才的迷宫，因为探索过程中会做许多记号，以免破坏原来的迷宫
$explorer=new MazeExplorer($cloneMaze);让探索者进入迷宫
if($explorer->searchPath())//探索者开始探索道路
$pathArray=$explorer->getPath();//找到了通路
else echo '这个迷宫没有通路！';//没有找到通路，迷宫是个死胡同
for($i=0;$i<count($pathArray);$i++)
{
  $newMaze->setFlag(array('x'=>$pathArray[$i]['x'],'y'=>$pathArray[$i]['y']),1);
}
$newMaze->printMaze();//打印路径

引用:

原帖由 玉面修罗 于 2007-2-6 18:51 发表
最近在家看资料，过完年又要马上去北京，去了北京之后肯定会很忙，所以以后有空再写点别的，把一些常用的排序算法用PHP写下。感谢大家支持。

引用:

原帖由 刀客羽朋 于 2007-2-7 08:50 发表
修罗，很棒。