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,):删除元素
顺序链表操作
list=array(); $this->size=0; } publicfunctioninitList(){ $this->list=array(); $this->size=0; } //删除链表 publicfunctiondestoryList(){ if(isset($this->list)){ unset($this->list); $this->size=0; } } //清空链表 publicfunctionclearList(){ if(isset($this->list)){ unset($this->list); } $this->list=array(); $this->size=0; } //判断链表是否为空 publicfunctionemptyList(){ if(isset($this->list)){ if($this->size=0) returnTRUE; else returnFALSE; } } //链表长度 publicfunctionlenghtList(){ if(isset($this->list)){ return$this->size; } } //取元素 publicfunctiongetElem($i){ if($i<1||$i>$this->size){ echo"溢出
"; exit(); } if(isset($this->list)&&is_array($this->list)){ return$this->list[$i-1]; } } //是否在链表中 publicfunctionlocateElem($e){ if(isset($this->list)&&is_array($this->list)){ for($i=0;$i<$this->size;$i++){ if($this->list[$i]==$e){ return$i+1; } } return0; } } //前驱 publicfunctionpriorElem($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]; } } //后继 publicfunctionnextElem($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]; } } //插入元素 publicfunctioninsertList($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; } } } //删除元素 publicfunctiondeleteLlist($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--; } } //遍历 publicfunctionprintList(){ if(isset($this->list)&&is_array($this->list)){ foreach($this->listas$value){ echo$value.""; } echo"
"; } } } ?>
链式线性表
head=""; $this->size=0; $this->list=array(); } publicfunctioninitList(){ $this->head=""; $this->size=0; $this->list=array(); } //删除链表 publicfunctiondestoryList(){ if(isset($this->list)&&isset($this->head)){ unset($this->list); unset($this->head); } } //清空链表 publicfunctionclearList(){ if(isset($this->list)){ unset($this->list); } $this->list=array(); $this->size=0; $this->head=""; } //判断链表是否为空 publicfunctionemptyList(){ if(isset($this->list)){ if($this->size==0) returnTRUE; else returnFALSE; } } //链表长度 publicfunctionlenghtList(){ if(isset($this->list)){ return$this->size; } } //取元素 publicfunctiongetElem($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']; } } //是否在链表中 publicfunctionlocateElem($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; } } returnTRUE; } } //前驱 publicfunctionpriorElem($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']; } //后继 publicfunctionnextElem($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']; } //插入元素:后插法 publicfunctioninsertList($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++; } } } } //删除元素 publicfunctiondeleteLlist($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; } } } } publicfunctiontraverstList(){ $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); } publicfunctionprintList($str,$flag){ if($flag){ echo$str."->"; }else{ echo$str."
"; } } //uuid唯一码 publicfunctionuuid($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程序设计有所帮助。