PHP数据结构之二线性表中的顺序表的PHP实现

谁践踏了优雅 2022-07-19 01:54 103阅读 0赞

线性表 
（一）基本特点：最基本、最简单、最常用的一种数据结构 
在这种结构中： 
1.存在一个唯一的被称为“第一个”的数据元素； 
2.存在一个唯一的被称为“最后一个”的数据元素； 
3.除第一个元素外，每个元素均有唯一一个直接前驱； 
4.除最后一个元素外，每个元素均有唯一一个直接后继。 
  
（二）定义： 
线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。 
当n=0时，称为空表。  
当n>0时，将非空的线性表记作： (a1，a2，…an)          
a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。 
（三）线性表顺序存储 ：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 
顺序存储的线性表的特点： 
1.线性表的逻辑顺序与物理顺序一致； 
2.数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。 
线性表中的顺序表的PHP实现 
<?php 
/\*\* 
 \* 顺序表基本操作 
 \* 
 \*包括 
 \*1.顺序表的初始化 \_\_contruct() 
 \*2.清空顺序表 \_\_destruct() 
 \*3.判断顺序表是否为空 isEmpty() 
 \*4.返回顺序表的长度 getLength() 
 \*5.根据下标返回顺序表中的某个元素 getElement() 
 \*6.返回顺序表中某个元素的位置 getElementPosition() 
 \*7.返回顺序表中某个元素的直接前驱元素 getElementPredecessorr() 
 \*8.返回某个元素的直接后继元素 getElementSubsequence() 
 \*9.指定下标位置返回元素 getElemForPos() 
 \*10.根据下标或者元素值删除顺序表中的某个元素 getDeleteElement() 
 \*11.根据元素位置删除顺序表中的某个元素 getDeleteEleForPos() 
 \*12.在指定位置插入一个新的结点 getInsertElement() 
 \*/ 
header("content-type:text/html;charset=utf-8"); 
class OrderLinearList\{ 
    public $oll;//顺序表 
    /\*\* 
     \* 顺序表初始化 
     \* 
     \* @param mixed $oll 
     \* @return void 
     \*  \*/ 
    public function \_\_construct($oll=array())\{ 
        $this->oll=$oll; 
    \} 
    /\*\* 
     \* 清空顺序表 
     \*@return void 
     \*/ 
     public function \_\_destruct()\{ 
        foreach($this->oll as $key=>$value)\{ 
            unset($this->oll\[$key\]); 
        \} 
     \} 
     /\*\* 
      \* 判断顺序表是否为空 
      \* @return boolean 为空返回true,否则返回false 
      \* \*/ 
     public function isEmpty()\{ 
        if(count($this->oll) > 0)\{ 
            return false; 
        \}else\{ 
            return true; 
        \} 
      \} 
      /\*\* 
       \* 返回顺序表的长度 
       \* @return int 
       \* \*/ 
     public function getLength()\{ 
        return count($this->oll); 
     \} 
    /\*\* 
     \* 返回顺序表中下标为$key的元素 
     \* 
     \* @param mixed $key 顺序表元素的下标 
     \* @return mixed 
     \* \*/ 
     public function getElement($key)\{ 
        return $this->oll\[$key\]; 
     \} 
    /\*\* 
     \* 返回顺序表中某个元素的位置 
     \* 
     \* @param mixed $value 顺序表中某个元素的值 
     \* @return int 从1开始,如果返回-1表示不存在该元素 
     \* \*/ 
    public function getElementPosition($value)\{ 
        $i=0; 
        foreach($this->oll as $val)\{ 
            $i++; 
            if(strcmp($value,$val) === 0)\{ 
                return $i; 
            \} 
        \} 
        return -1; 
    \} 
    /\*\* 
     \* 返回顺序表中某个元素的直接前驱元素 
     \* 
     \*@param mixed  $value顺序表中某个元素的值 
     \*@param bool $tag 如果$value为下标则为1,如果$value为元素值则为2 
     \*@return array array('value'=>...)直接前驱元素值，array('key'=>...)直接前驱元素下标 
     \*\*/ 
     public function getElementPredecessorr($value,$tag=1)\{ 
        $i=0; 
        foreach($this->oll as $key=>$val)\{ 
            $i++; 
            if($tag ==1 )\{ 
                if(strcmp($key,$value) === 0)\{ 
                    if($i == 1)\{ 
                        return false; 
                    \} 
                    prev($this->oll); 
                    prev($this->oll); 
                    return array('value'=>current($this->oll),'key'=>key($this->oll)); 
                \} 
            \} 
            if($tag == 2)\{ 
                if(strcmp($val,$value) === 0)\{ 
                    if($i == 1)\{ 
                        return false; 
                    \} 
                    prev($this->oll); 
                    prev($this->oll); 
                    return array('value'=>current($this->oll),'key'=>key($this->oll)); 
                \} 
            \} 
        \} 
     \} 
     /\*\* 
      \* 返回某个元素的直接后继元素 
     \* 
     \*@param mixed  $value顺序表中某个元素的值 
     \*@param bool $tag 如果$value为下标则为1,如果$value为元素值则为2 
     \*@return array array('value'=>...)直接后继元素值，array('key'=>...)直接后继元素下标 
     \*\*/ 
      public function getElementSubsequence($value,$tag=1)\{ 
        $i=0; 
        $len=count($this->oll); 
        foreach($this->oll as $key=>$val)\{ 
            $i++; 
            if($tag ==1 )\{ 
                if(strcmp($key,$value) == 0)\{ 
                    if($i == $len)\{ 
                        return false; 
                    \} 
                    return array('value'=>current($this->oll),'key'=>key($this->oll)); 
                \} 
            \} 
            if($tag == 2)\{ 
                if(strcmp($val,$value) == 0)\{ 
                    if($i == $len)\{ 
                        return false; 
                    \} 
                    return array('value'=>current($this->oll),'key'=>key($this->oll)); 
                \} 
            \} 
        \} 
        return false; 
     \} 
     /\*\* 
      \* 在指定位置插入一个新的结点 
      \* 
      \* @param mixed $p 新结点插入位置,从1开始 
      \* @param mixed $value 顺序表新结点的值 
      \* @param mixed $key 顺序表新结点的下标 
      \* @param bool $tag 是否指定新结点的下标,1表示默认下标,2表示指定下标 
      \* @return bool 插入成功返回true，失败返回false 
      \* \*/ 
      public function getInsertElement($p,$value,$key=null,$tag=1)\{ 
        $p=(int)$p; 
        $len=count($this->oll); 
        $oll=array(); 
        $i=0; 
        if($p > $len || $p < 1)\{ 
            return false; 
        \} 
        foreach($this->oll as $k=>$v)\{ 
            $i++; 
            if($i==(int)$p)\{ 
                if($tag == 1)\{ 
                    $oll\[\]=$value; 
                \}else if($tag == 2)\{ 
                    $keys=array\_keys($oll); 
                    $j=0; 
                    if(is\_int($key))\{ 
                        while(in\_array($key,$keys,true))\{ 
                            $key++; 
                        \} 
                    \}else\{ 
                        while(in\_array($key,$keys,true))\{ 
                            $j++; 
                            $key.=(string)$j; 
                        \} 
                    \} 
                    $oll\[$key\]=$value; 
                \}else\{ 
                    return false; 
                \} 
                    $key=$k; 
                    $j=0; 
                    $keys=array\_keys($oll); 
                    if(is\_int($key))\{ 
                        $oll\[\]=$v; 
                    \}else\{ 
                        while(in\_array($key,$keys,true))\{ 
                            $j++; 
                            $key.=(string)$j; 
                        \} 
                        $oll\[$key\]=$v; 
                    \} 
            \}else\{ 
                if($i>$p)\{ 
                    $key=$k; 
                    $j=0; 
                    $keys=array\_keys($oll); 
                    if(is\_int($key))\{ 
                        $oll\[\]=$v; 
                    \}else\{ 
                        while(in\_array($key,$keys,true))\{ 
                            $j++; 
                            $key.=(string)$j; 
                        \} 
                        $oll\[$key\]=$v; 
                    \} 
                \}else\{ 
                    if(is\_int($k))\{ 
                        $oll\[\]=$v; 
                    \}else\{ 
                        $oll\[$k\]=$v; 
                    \} 
                \} 
            \} 
        \} 
        $this->oll=$oll; 
        return true; 
      \} 
      /\*\* 
       \* 根据元素位置返回顺序表中的某个元素 
       \* 
       \* @param int $position 元素位置从1开始 
       \* @return array  array('value'=>...)元素值，array('key'=>...)元素下标 \*/ 
      public function getElemForPos($position)\{ 
        $i=0; 
        $len=count($this->oll); 
        $position=(int)$position; 
        if($position > $len || $position < 1)\{ 
            return false; 
        \} 
        foreach($this->oll as $val)\{ 
            $i++; 
            if($i == $position)\{ 
                return array('value'=>current($this->oll),'key'=>key($this->oll)); 
            \} 
        \} 
      \} 
      /\*\* 
       \* 根据下标或者元素值删除顺序表中的某个元素 
       \* 
       \* @param mixed $value 元素下标或者值 
       \* @param int $tag 1表示$value为下标，2表示$value为元素值 
       \* @return bool 成功返回true,失败返回false 
       \* \*/ 
      public function getDeleteElement($value,$tag=1)\{ 
        $len=count($this->oll); 
           foreach($this->oll as $k=>$v)\{ 
                if($tag == 1)\{ 
                    if(strcmp($k,$value) === 0)\{ 
                    \}else\{ 
                        if(is\_int($k))\{ 
                            $oll\[\]=$v; 
                        \}else\{ 
                            $oll\[$k\]=$v; 
                        \} 
                    \} 
                \} 
                if($tag ==2)\{ 
                    if(strcmp($v,$value) === 0)\{ 
                    \}else\{ 
                        if(is\_int($k))\{ 
                            $oll\[\]=$v; 
                        \}else\{ 
                            $oll\[$k\]=$v; 
                        \} 
                    \} 
                \} 
           \} 
           $this->oll=$oll; 
           if(count($this->oll) == $len)\{ 
                return false; 
           \} 
           return true; 
      \} 
      /\*\* 
       \* 根据元素位置删除顺序表中的某个元素 
       \* 
       \* @param int $position 元素位置从1开始 
       \* @return bool 成功返回true,失败返回false 
       \* \*/ 
      public function getDeleteEleForPos($position)\{ 
        $len=count($this->oll); 
        $i=0; 
        $position=(int)$position; 
        if($position > $len || $position < 1)\{ 
            return false; 
        \} 
        foreach($this->oll as $k=>$v)\{ 
            $i++; 
            if($i == $position)\{ 
            \}else\{ 
            if(is\_int($k))\{ 
                    $oll\[\]=$v; 
                \}else\{ 
                    $oll\[$k\]=$v; 
                \} 
            \} 
        \} 
        $this->oll=$oll; 
           if(count($this->oll) == $len)\{ 
                return false; 
           \} 
           return true; 
      \} 
\} 
?> 
$oll=new OrderLinearList(array('xu'=>'徐典阳',32,"是吧",'dianyang'=>10,455)); 
//判断顺序表是否为空,返回false说明不为空 
var\_dump($oll->isEmpty()); 
echo " "; 
//返回顺序表的长度 返回6 
echo $oll->getLength(); 
echo " "; 
//根据下标返回顺序表中的某个元素 
var\_dump($oll->getElement(1)); 
echo " "; 
//返回顺序表中某个元素的位置 
echo $oll->getElementPosition("是吧"); 
echo " "; 
//返回顺序表中某个元素的直接前驱元素 
var\_dump($oll->getElementPredecessorr("是吧",2)); 
echo " "; 
//返回顺序表中某个元素的直接后继元素 
var\_dump($oll->getElementSubsequence("是吧",2)); 
echo " "; 
//根据元素位置返回顺序表中的某个元素 
var\_dump($oll->getElemForPos(2)); 
echo " "; 
//根据下标或者元素值删除顺序表中的某个元素 
var\_dump($oll->getDeleteElement('徐典阳',$tag=2)); 
echo " "; 
//根据元素位置删除顺序表中的某个元素 
var\_dump($oll->getDeleteEleForPos(1)); 
echo " "; 
$oll->getInsertElement(3,"徐珍",$key="xuzheng",$tag=2); 
var\_dump($oll->oll); 
echo " "; 
?>