php数据结构之顺序链表与链式线性表示例

<?phpclass 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<1||$i>$this->size){    echo "溢出<br>";    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;$i<$this->size;$i++){      if($this->list[$i]==$e){       return $i+1;      }    }    return 0;   }  }  //前驱  public function priorElem($i){   if($i<1||$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<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 "<br>";   }  }}?>

<?phpclass LinkList {  private $head;  private $size;  private $list;  public function __construct(){   $this->head="";   $this->size=0;   $this->list=array();  }  public function initList(){   $this->head="";   $this->size=0;   $this->list=array();  }  //删除链表  public function destoryList(){   if(isset($this->list)&&isset($this->head)){    unset($this->list);    unset($this->head);   }  }  //清空链表  public function clearList(){   if(isset($this->list)){    unset($this->list);   }   $this->list=array();   $this->size=0;   $this->head="";  }  //判断链表是否为空  public function emptyList(){   if(isset($this->list)){    if($this->size==0)      returnTRUE;    else      returnFALSE;   }  }  //链表长度  public function lenghtList(){   if(isset($this->list)){    return$this->size;   }  }  //取元素  public function getElem($i){   if($i<1||$i>$this->size){    echo "溢出<br>";    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 function locateElem($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 function priorElem($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 function nextElem($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 function insertList($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 function deleteLlist($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 function traverstList(){   $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 function printList($str,$flag){   if($flag){    echo$str."->";   }else {    echo$str."<br>";   }  }  //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;  }}?>