php实现单链表(静态链表)
<?php /* * 单链表的PHP实现 * * @author zhaojiangwei * @since 2011/10/20 */ //结点类 class Node{ private $next = NULL; //下一个结点指针 private $data = NULL; //数据 public function Node($data, $next = NULL){ $this->data = $data; $next && $this->next = $next; } public function getData(){ return $this->data; } public function setData($data){ $this->data = $data; } public function getNext(){ return $this->next; } public function setNext($next){ $this->next = $next; } } //单链表类 class LinkList{ private $data_list = NULL; //结点集 public function LinkList($data = false){ $this->data_list = array(); $title = new Node(NULL); $this->data_list[] = $title; if($data){ if(is_array($data)){ $this->addMoreData($data); }else{ $this->addData($data); } } } //返回第N个结点的值 public function getNodeByNumber($number){ return $this->data_list[$this->findKeyByNumber($number)]->getData(); } //添加一组结点 public function addMoreData($datas){ foreach($datas as $value){ $this->addData($value); } } //添加结点统一入口,供外面调用 //$number 添加在第几个结点的后面 public function addData($data, $number = false){ $node = new Node($data); if($number === FALSE || $number == count($this->data_list)){ $this->insertLastNode($node); }elseif($number > count($this->data_list)){ return false; }else{ $this->insertNode($node, $number); } } //插入一个结点到最后 private function insertLastNode($node){ $node->setNext(NULL); $lastKey = $this->findLastNode(); $insert_key = $this->insertNodeIntoArray($node); $this->data_list[$lastKey]->setNext($insert_key); } //插入一个结点 private function insertNode($node, $number){ $insert_number = $this->findKeyByNumber($number); $node->setNext($this->data_list[$insert_number]->getNext()); $insert_key = $this->insertNodeIntoArray($node); $this->data_list[$insert_number]->setNext($insert_key); } //查找第N个结点对应的数组key private function findKeyByNumber($number){ $i = $key = 0; while($i < $number){ $key = $this->data_list[$key]->getNext(); $i ++; } return $key; } //将结点加入数组 private function insertNodeIntoArray($node){ $this->data_list[] = $node; return $this->getLastKey(); } //删除结点 public function deleteNode($number){ if($number == 0 || $number > count($this->data_list)){ return false; } $pre_key = $this->findKeyByNumber($number - 1); $key = $this->data_list[$pre_key]->getNext(); $this->data_list[$pre_key]->setNext($this->data_list[$key]->getNext()); unset($this->data_list[$key]); } //查找某结点的前一个结点 private function getPreNodeKey($key){ foreach($this->data_list as $k=>$v){ if($v->getNext() == $key){ return $k; } } return false; } //打印链表 public function getData_list(){ return $this->data_list; } //返回数组的最后一个键 private function getLastKey(){ end($this->data_list); return key($this->data_list); } //判断某个键值是否存在 private function ifExistKey($key){ if(array_key_exists($key, $this->data_list)){ return true; } return false; } //查找尾结点 public function findLastNode(){ foreach($this->data_list as $key=>$value){ if($value->getNext() === NULL){ return $key; } } } }?>
