php实现数据结构线性表（顺序和链式）

链表操作

1、     InitList(L)：初始化链表

2、     DestroyList(L)：删除连接

3、     ClearList(L)：清空链表

4、     ListEmpty(L)：判断是否为空

5、     ListLength(L)：链表长度

6、     getElem(L,i)：取出元素

7、     LocateElem(L,e)：判断e是否在链表中

8、     PriorElem(L,i)：前驱

9、     NextElem(L,i)：后继

10、   ListInsert(L,i,e)：插入元素

11、   ListDelete(L,i,)：删除元素

顺序链表操作

class ArrayList{

   private $list;

   private $size; 

   //构造函数

   public function __construct(){

      $this->list=array();

      $this->size=0;

   } 

   public function initList(){

      $this->list=array();

      $this->size=0;

   } 

   //删除链表

   public function destoryList(){

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

         unset($this->list);

        $this->size=0;

      }

   } 

   //清空链表

   public function clearList(){

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

        unset($this->list);        

      }

      $this->list=array();

      $this->size=0;

   } 

   //判断链表是否为空

   public function emptyList(){

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

         if($this->size=0)

           return TRUE;

        else

          return FALSE;

      }

   } 

   //链表长度

   public function lenghtList(){

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

        return $this->size;

      }

   } 

   //取元素

   public function getElem($i){

      if($i$this->size){

        echo "溢出
";

        exit();

      }

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

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

      }      

   }

  

   //是否在链表中

   public function locateElem($e){

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

     

        for($i=0;$isize;$i++){  

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

              return $i+1;         

           }

        }

        return 0;

      }

   } 

   //前驱

   public function priorElem($i){

      if($i$this->size){

        echo "溢出";

        exit();

      }

      if($i==1){

        echo "没有前驱";

        exit();      

      }

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

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

      }

   }

  

   //后继

   public function nextElem($i){

      if($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$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$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;$jsize;$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$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=$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$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$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$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;

   }

}

?>