Home php教程 php手册 php实现数据结构线性表(顺序和链式)

php实现数据结构线性表(顺序和链式)

Jun 13, 2016 am 10:56 AM
php initialization delete and accomplish operate data structure Linear surface linked list order

链表操作

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;

   }

}

?>

 

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian

CakePHP Date and Time CakePHP Date and Time Sep 10, 2024 pm 05:27 PM

CakePHP Date and Time

CakePHP File upload CakePHP File upload Sep 10, 2024 pm 05:27 PM

CakePHP File upload

CakePHP Routing CakePHP Routing Sep 10, 2024 pm 05:25 PM

CakePHP Routing

CakePHP Project Configuration CakePHP Project Configuration Sep 10, 2024 pm 05:25 PM

CakePHP Project Configuration

Discuss CakePHP Discuss CakePHP Sep 10, 2024 pm 05:28 PM

Discuss CakePHP

CakePHP Quick Guide CakePHP Quick Guide Sep 10, 2024 pm 05:27 PM

CakePHP Quick Guide

How To Set Up Visual Studio Code (VS Code) for PHP Development How To Set Up Visual Studio Code (VS Code) for PHP Development Dec 20, 2024 am 11:31 AM

How To Set Up Visual Studio Code (VS Code) for PHP Development

See all articles