php实现数据结构线性表（链式）

xiaoxiao2021-04-14 34

<?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){ return true; }else{ return false; } } } //链表长度 public function lengthList(){ if (isset($this->list)){ return $this->size; }else{ return false; } } //取元素 public function getElem($i){ if ($i<1||$i>$this->size){ die('failed'); } 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{ return false; } } return true; } } //前驱 public function priorElem($i){ if ($i<1||$i>$this->size){ die('failed'); } if ($i==1){ die('no prior'); } $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){ die('failed'); } if ($i==$this->size){ die('no next'); } $tmp=$this->head; $j=1; 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; }else{ if ($i<1||$i>$this->size){ die('failed'); } $tmp=$this->head; $j=1; 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 deleteList($i){ if ($i<1||$i>$this->size){ die('failed'); } 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[$tmp]['next']!=null){ //不是最后一个元素 $delete=$this->list[$find]['next']; $this->list[$find]['next']=$this->list[$delete]['next']; }else{ $this->list[$tmp]['next']=null; } } } } public function tracerstList(){ $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,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; } }

转载请注明原文地址: https://ju.6miu.com/read-669737.html

技术

最新回复(0)