PHP implements data structure linear table (sequential and chained)_PHP tutorial

Linked list operations

1. InitList(L): Initialize the linked list

2. DestroyList(L): Delete the connection

3. ClearList(L): Clear the linked list

4. ListEmpty(L): Determine whether it is empty

5. ListLength(L): List length

6. getElem(L,i): Take out the element

7. LocateElem(L,e): Determine whether e is in the linked list

8. PriorElem(L,i): precursor

9. NextElem(L,i): Successor

10. ListInsert(L,i,e): Insert element

11. ListDelete(L,i,): Delete element

Sequential linked list operations

class ArrayList{

private $list;

private $size;

//Constructor

public function __construct(){

$this->list=array();

$this->size=0;

}

public function initList(){

$this->list=array();

$this->size=0;

}

//Delete linked list

public function destroyList(){

if(isset($this->list)){

unset($this->list);

$this->size=0;

}

}

//Clear the linked list

public function clearList(){

if(isset($this->list)){

unset($this->list);

}

$this->list=array();

$this->size=0;

}

//Judge whether the linked list is empty

public function emptyList(){

if(isset($this->list)){

if($this->size=0)

return TRUE;

else

return FALSE;

}

}

//Length of linked list

public function lenghtList(){

if(isset($this->list)){

return $this->size;

}

}

//Get element

public function getElem($i){

if($i<1||$i>$this->size){

echo "overflow
";

exit();

}

if(isset($this->list)&&is_array($this->list)){

return $this->list[$i-1];

} 

}

//Whether it is in the linked list

public function locateElem($e){

if(isset($this->list)&&is_array($this->list)){

for($i=0;$i<$this->size;$i++){

if($this->list[$i]==$e){

                return $i+1;                                     

}

}

return 0;

}

}

//Forerunner

public function priorElem($i){

if($i<1||$i>$this->size){

echo "overflow";

exit();

}

if($i==1){

echo "No precursor";

        exit();      

      }

      if(isset($this->list)&&is_array($this->list)){

        return $this->list[$i-2];

      }

   }

  

   //后继

   public function nextElem($i){

      if($i<1||$i>$this->size){

        echo "溢出";

        exit();

      }

      if($i==$this->size){

        echo "没有后继";

        exit();      

      }

      if(isset($this->list)&&is_array($this->list)){

        return $this->list[$i];

      }

   }

  

   //插入元素

   public function insertList($i,$e){

      if($i<1||$i>$this->size+1){

        echo "插入元素位置有误";

        exit();

      }

      if(isset($this->list)&&is_array($this->list)){

       

        if($this->size==0){

           $this->list[$this->size]=$e;

           $this->size++;

        }else{

           $this->size++;

           for($j=$this->size-1;$j>=$i;$j--){

              $this->list[$j]=$this->list[$j-1];

           }

           $this->list[$i-1]=$e;

        }      

      }

     

   }

  

  

   //删除元素

   public function deleteLlist($i){

      if($i<1||$i>$this->size){

        echo "删除元素位置有误";

        exit();

      }

      if(isset($this->list)&&is_array($this->list)){

        if($i==$this->size){

           unset($this->list[$this->size-1]);         

        }else{

           for($j=$i;$j<$this->size;$j++){             

              $this->list[$j-1]=$this->list[$j];

           }

           unset($this->list[$this->size-1]);

         }

      $this->size--;

      }

   }

  

   //遍历

   public function printList(){

      if(isset($this->list)&&is_array($this->list)){

        foreach ($this->list as $value){

           echo $value." ";

        }

        echo "
";

      }

   }

  

  

 

}

 

?>

 

 

 

//链式线性表

 

class LinkList {

   private $head;

   private $size;

   private $list;

  

   public function__construct(){

      $this->head="";

      $this->size=0;

      $this->list=array();    

   }

  

  

  

   public functioninitList(){

      $this->head="";

      $this->size=0;

      $this->list=array(); 

   }

  

   //删除链表

   public functiondestoryList(){

      if(isset($this->list)&&isset($this->head)){

        unset($this->list);

        unset($this->head);

      }

   }

  

   //清空链表

   public functionclearList(){

      if(isset($this->list)){

        unset($this->list);     

      }

      $this->list=array();

      $this->size=0;

      $this->head="";

   }

  

   //判断链表是否为空

   public functionemptyList(){

      if(isset($this->list)){

        if($this->size==0)

           returnTRUE;

        else

           returnFALSE;

      }

   }

  

   //链表长度

   public functionlenghtList(){

      if(isset($this->list)){

        return$this->size;

      }

   }

  

  

   //取元素

   public function getElem($i){

      if($i<1||$i>$this->size){

        echo "溢出
";

        exit();

      }

      if(isset($this->list)&&is_array($this->list)){

        $j=1;

        //头指针

        $tmp=$this->head;

        while($i>$j){                 

           if($this->list[$tmp]['next']!=null){           

              $tmp=$this->list[$tmp]['next'];

              $j++;           

           }                  

        }

        return   $this->list[$tmp]['data'];               

      }    

     

   }

  

   //是否在链表中

   public functionlocateElem($e){

      if(isset($this->list)&&is_array($this->list)){

        $tmp=$this->head;

        while($this->list[$tmp]['data']!=$e){

           if($this->list[$tmp]['next']!=null){

              $tmp=$this->list[$tmp]['next'];

           }else{

              returnFALSE;

           }

        }

        return TRUE;

          

      }

   }

  

   //前驱

   public functionpriorElem($i){

      if($i<1||$i>=$this->size){

        echo "溢出";

        exit();

      }

      if($i==1){

        echo "没有前驱";

        exit();      

      }

     

      $tmp=$this->head;

      $j=1;

      while($i>$j+1){

        if($this->list[$tmp]['next']!=null){

           $j++;

           $tmp=$this->list[$tmp]['next'];

        }

      }

     

      return$this->list[$tmp]['data'];

     

     

   }

  

   //后继

   public functionnextElem($i){

      if($i<1||$i>$this->size){

        echo "溢出";

        exit();

      }

      if($i==$this->size){

        echo "没有后继";

        exit();      

      }

      $j=1;

      $tmp=$this->head;

      while($i>=$j){

        if($this->list[$tmp]['next']!=null){

           $j++;

           $tmp=$this->list[$tmp]['next'];

        }

      }

      return$this->list[$tmp]['data'];

   }

  

  

   //插入元素:后插法

   public functioninsertList($i,$e){ 

      if(isset($this->list)&&is_array($this->list)){

        //空表

        if($this->size==0){

           $this->head=$this->uuid();

           $this->list[$this->head]['data']=$e;

           $this->list[$this->head]['next']=NULL;

           $this->size++;

        }else{

           if($i<1||$i>$this->size){

           echo"插入元素位置有误";

           exit();

           }

           $j=1;

           $tmp=$this->head;

           while($i>$j){

              if($this->list[$tmp]['next']!=null){

                 $j++;

                 $tmp=$this->list[$tmp]['next'];

              }                    

           }

           $find=$tmp;

           $id=$this->uuid();

           if($this->list[$find]['next']==null){

              //尾部

              $this->list[$find]['next']=$id;

              $this->list[$id]['data']=$e;

              $this->list[$id]['next']=null;

              $this->size++;

           }else{

              //中间

              $this->list[$id]['next']=$this->list[$find]['next'];

              $this->list[$find]['next']=$id;

              $this->list[$id]['data']=$e;

              $this->size++;

           }    

        }            

      }      

   }

  

  

   //删除元素

   public functiondeleteLlist($i){

      if($i<1||$i>$this->size){

        echo "删除元素位置有误";

        exit();

      }

     

      if(isset($this->list)&&is_array($this->list)){

       

        if($i==1){

           //删除头元素

           $this->head=$this->list[$this->head]['next'];

        }else{

           $tmp=$this->head;

           $j=1;

           while($i>$j+1){

              if($this->list[$tmp]['next']!=null){

                 $j++;

                 $tmp=$this->list[$tmp]['next'];

              }

           }

           //找到删除元素的前驱

           $find=$tmp;

           //删除的元素

           if($this->list[$find]['next']!=null){

              //不是最后一个元素

              $delete=$this->list[$find]['next'];

              $this->list[$find]['next']=$this->list[$delete]['next'];

           }else{

              $this->list[$tmp]['next']=null;

           }            

        }      

      }

   } 

  

   public functiontraverstList(){

      $tmp=$this->head;

      while($this->list[$tmp]['next']!=NULL){

        $this->printList($this->list[$tmp]['data'],TRUE);

        $tmp=$this->list[$tmp]['next'];       

      }

      $this->printList($this->list[$tmp]['data'],FALSE);

   }

  

   public functionprintList($str,$flag){

      if($flag){

        echo$str."->";

      }else {

        echo$str."
";

      }

     

     

   }

  

  

   //uuid 唯一码

   public   function uuid($prefix = '') {

    $chars =md5(uniqid(mt_rand(), true));

    $uuid  = substr($chars,0,8) . '-';

    $uuid .=substr($chars,8,4) . '-';

    $uuid .=substr($chars,12,4) . '-';

    $uuid .=substr($chars,16,4) . '-';

    $uuid .= substr($chars,20,12);

    return $prefix. $uuid;

   }

}

?>