本文实例讲述了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,)：删除元素
顺序链表操作
PHP;">
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 "溢出
"; 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 "
"; } } } ?>
"; 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 "
"; } } } ?>
链式线性表
PHP;">
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 "溢出
"; 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."
"; } } //uuid 唯一码 public function uuid($prefix = '') { $chars =md5(uniqid(mt_rand(),true)); $uuid = substr($chars,8) . '-'; $uuid .=substr($chars,8,4) . '-'; $uuid .=substr($chars,12,16,4) . '-'; $uuid .= substr($chars,20,12); return $prefix. $uuid; } } ?>
"; 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."
"; } } //uuid 唯一码 public function uuid($prefix = '') { $chars =md5(uniqid(mt_rand(),true)); $uuid = substr($chars,8) . '-'; $uuid .=substr($chars,8,4) . '-'; $uuid .=substr($chars,12,16,4) . '-'; $uuid .= substr($chars,20,12); return $prefix. $uuid; } } ?>
更多关于PHP相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》及《》
希望本文所述对大家PHP程序设计有所帮助。
