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

　　本文实例讲述了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,)：删除元素

　　顺序链表操作

　　 <?php 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<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>; } } } ?>

　　链式线性表

　　 <?php class 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; } } ?>

　　更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

　　希望本文所述对大家PHP程序设计有所帮助。