大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
data=$data; $this->next=null; } } class SingleLinkList{ public $data; public $next; public function __construct(){ $this->data=null; $this->next=null; } //具有$num个数据元素的单链表的创建——头插法 public function CreateListHead($num){ for($i=0;$i<$num;$i++){ $node=new LNode(); $node->data=mt_rand(100,200); $node->next=$this->next; $this->next=$node; } } //具有$num个数据元素的单链表的创建——尾插法 public function CreateListTail($num){ $tail=$this; for($i=0;$i<$num;$i++){ $node=new LNode(); $node->data=mt_rand(100,200); $tail->next=$node; $tail=$node; } $node->next=null; } //销毁单链表 public function DestroyList(){ //$this相当于头指针,它指向的是头结点,$this->next相当于第一个结点 //之所以需要将$this赋值给$that,是因为$this无法用作变量进行赋值 $that=$this; while($that){ $node=$that->next; unset($that); $that=$node; } } //将单链表清空 public function ClearList(){ $p=$this->next; while($p){ $node=$p->next; unset($node); $p=$node; } $this->next=null; } //判断单链表是否为空 public function ListEmpty(){ if($this->next){ return false; }else{ return true; } } //返回单链表中数据元素的个数 public function ListLength(){ $count=0;//初始化变量 $p=$this->next; while($p){ $count++; $p=$p->next; } return $count; } //返回指定位置的数据元素 public function GetElem($pos){ $count=1; $p=$this->next; while($p && $count<$pos){ $count++; $p=$p->next; } if(!$p || $pos<$count){ return 'ERROR'; } return $p->data; } // 或者 public function GetElem2($pos){ $count=0; $p=$this->next; while($p){ $count++; if($count==$pos){ return $p->data; } $p=$p->next; } return 'ERROR'; } //查找指定元素在单链表中的位序 public function LocateElem($elem){ $count=0; $p=$this->next; while($p){ $count++; if($p->data==$elem){ return $count; } } return 'ERROR'; } //获取指定元素的前面一个元素 public function PriorElem($elem){ $p=$this->next; if($p && $p->data=$elem){ return $p->data.'已经是第一个元素,已无前驱元素'; } while($p && $p->next){ $q=$p->next; if($q->data==$elem){ return $p->data; } $p=$q; } return 'ERROR'; } //获取指定元素的后面一个元素 public function NextElem($elem){ $p=$this->next; while($p && $p->next){ if($p->data==$elem){ return $p->next->data; } $p=$p->next; } if($p && $p->next==null){ return $p->data.'已经是最后一个元素,已无后继元素'; } return 'ERROR'; } //在指定位置之前插入一个节点元素 public function ListInsert($pos,$node){ $p=$this; $count=0; while($p) { $count++; if ($count == $pos) { $node->next = $p->next; $p->next = $node; return 'OK'; } $p=$p->next; } return 'ERROR'; } //或者 这种效率会高一些 public function ListInsert2($pos,$node){ $p=$this; $count=1; while($p && $count<$pos){ $count++; $p=$p->next; } if(!$p || $count>$pos){ return 'ERROR'; } $node->next=$p->next; $p->next=$node; return 'OK'; } //删除单链表指定位置的数据元素 public function ListDelete($pos){ $count=1; $p=$this; while($p && $count<$pos){ $count++; $p=$p->next; } if(!$p || $count>$pos){ return 'ERROR'; } $q=$p->next; $p->next=$q->next; unset($q); return 'OK'; } // 或者 public function ListDelete2($pos){ $count=0; $p=$this; //此处之所以使用$p->next,而不是$p作为判断条件是因为这样可以在链表为空的时候,少一次无谓的循环。 while($p->next){ $count++; if($count==$pos){ $q=$p->next; $p->next=$q->next; unset($q); return 'OK'; } $p=$p->next; } return 'ERROR'; } //单链表的遍历 public function ListTraverse(){ $arr=array(); $p=$this->next; while($p){ $arr[]=$p->data; $p=$p->next; } return $arr; } }