此类主要是依靠php强大的数组系统来模拟出单链表类型的数据结构。 本人完全凭借自己的 兴趣来编写此类，并未考虑其实用性，主要是给大家理解一些简单的数据结构知识，同时也训练 一下php中的数组运用能力。
单链表简介：
单链表是最简单的链表表示。用它来表示线性表时，每一个数据元素占用一个结点(node)。一个 结点一般由两个域组成，一个域存放数据元素data； 另一个域存放一个指向链表中下一个结点的指针link，它指出下一个结点 的开始存储地址。而最后一个结点的指针为空。单链表中数据元素之间的逻 辑关系是由结点中的指针指示的，换句话说，指针为数据元素之间的逻辑关系的映象，则逻辑上相邻的两个元素其存储的物理位置不要求紧邻，因此， 这种存储结构为非顺序映像或链式映像。当然，在php没有指针这个概念，但是我们可以用关联数组来模拟。
php数组实现单链表的代码如下：
php class linklist { /** * 成员变量 * @var array $linklist 链表数组 * @var number $listheader 表头索引 * @var number $listlength 链表长度 * @var number $existedcounts 记录链表中出现过的元素的个数，和$listlength不同的是, 删除一 * 个元素之后，该值不需要减1，这个也可以用来为新元素分配索引。 */ protected $linklist =array(); protected $listlength=0; protected $listheader=null; protected $existedcounts=0; /** * 构造函数 * 构造函数可以带一个数组参数，如果有参数，则调用成员方法 * createlist将数组转换成链表，并算出链表长度.如果没有参 * 数，则生成一空链表.空链表可以通过调用成员方法createlist * 生成链表. * @access public * @param array $arr 需要被转化为链表的数组 */ public function __construct($arr='') { $arr!=null&&$this->createlist($arr); } /** * 生成链表的函数 * 将数组转变成链表，同时计算出链表长度。分别赋值给成员标量 * $linklist和$listlength. * @access public * @param array $arr 需要被转化为链表的数组 * @return boolean true表示转换成功，false表示失败 */ public function createlist($arr) { if (!is_array($arr)) return false; $length=count($arr); for($i=0;$i$length;$i++) { if($i==$length-1) { //每个链表结点包括var和next两个索引，var表示结点值，next为下一个结点的索引 //最后一个结点的next为null $list[$i]['var'] =$arr[$i]; $list[$i]['next'] =null; } else { $list[$i]['var'] =$arr[$i]; $list[$i]['next'] =$i+1; } } $this->linklist =$list; $this->listlength =$length; $this->existedcounts =$length; $this->listheader=0; return true; } /** * 将链表还原成一维数组 * @access public * @return array $arr 生成的一维数组 */ public function returntoarray() { $arr=array(); $tmp=$this->linklist[$this->listheader]; for($i=0;$i$this->listlength;$i++) { $arr[]=$tmp['var']; if ($i!=$this->listlength-1) { $tmp=$this->linklist[$tmp['next']]; } } return $arr; } public function getlength() { return $this->listlength; } /** * 计算一共删除过多少个元素 * @access public * @return number $count 到目前为止删除过的元素个数 */ public function getdeletednums() { $count=$this->existedcounts-$this->listlength; return $count; } /** * 通过元素索引返回元素序号 * @access protected * @param $index 元素的索引号 * @return $num 元素在链表中的序号 */ public function getelemlocation($index) { if (!array_key_exists($index,$this->linklist)) return false; $arrindex=$this->listheader; for($num=1;$tmp=$this->linklist[$arrindex];$num++) { if ($index==$arrindex) break; else { $arrindex=$tmp['next']; } } return $num; } /** * 获取第$i个元素的引用 * 这个保护方法不能被外界直接访问，许多服务方法以来与次方法。 * 它用来返回链表中第$i个元素的引用，是一个数组 * @access protected * @param number $i 元素的序号 * @return reference 元素的引用 */ protected function &getelemref($i) { //判断$i的类型以及是否越界 $result=false; if (!is_numeric($i)||(int)$i=0||(int)$i>$this->listlength) return $result; //由于单链表中的任何两个元素的存储位置之间没有固定关系，要取得第i个元素必须从 //表头开始查找，因此单链表是非随机存储的存储结构。 $j=0; $value=&$this->linklist[$this->listheader]; while ($j$i-1) { $value=&$this->linklist[$value['next']]; $j++; } return $value; } /** * 返回第i个元素的值 * @access public * @param number $i 需要返回的元素的序号，从1开始 * @return mixed 第i个元素的值 */ public function getelemvar($i) { $var=$this->getelemref($i); if ($var!=false) { return $var['var']; } else return false; } /** * 在第i个元素之后插入一个值为var的新元素 * i的取值应该为[1,$this->listlength]，如果i=0，表示在表的最前段插入， * 如果i=$this->listlength，表示在表的末尾插入,插入的方法为，将第$i-1个元素 * 的next指向第$i个元素，然后将第$i个元素的next指向第$i+1个元素，这样就实现了插入 * @access public * @param number $i 在位置i插入新元素 * @param mixed $var 要插入的元素的值 * @return boolean 成功则返回true,否则返回false */ public function insertintolist($i,$var) { if (!is_numeric($i)||(int)$i0||(int)$i>$this->listlength) return false; if ($i==0) { //如果$i-0，则在表最前面添加元素，新元素索引为$listlength，这样是确保不会 //覆盖原来的元素，另外这种情况需要重新设置$listheader $this->linklist[$this->existedcounts]['var'] =$var; $this->linklist[$this->existedcounts]['next']=$this->listheader; $this->listheader=$this->existedcounts; $this->listlength++; $this->existedcounts++; return true; } $value=&$this->getelemref($i); $this->linklist[$this->existedcounts]['var'] =$var; $this->linklist[$this->existedcounts]['next']=($i==$this->listlength?null:$value['next']); $value['next']=$this->existedcounts; $this->listlength++; $this->existedcounts++; return true; } /** * 删除第$i个元素 * 删除第$i个元素，该元素为取值应该为[1，$this->listlength],需要注意，删除元素之后， * $this->listlength减1,而$this->existedcounts不变。删除的方法为将第$i-1个元素的 * next指向第$i+1个元素，那么第$i个元素就从链表中删除了。 * @access public * @param number $i 将要被删除的元素的序号 * @return boolean 成功则返回true,否则返回false */ public function delfromlist($i) { if (!is_numeric($i)||(int)$i=0||(int)$i>$this->listlength) return false; if ($i==1) { //若删除的结点为头结点，则需要从新设置链表头 $tmp=$this->linklist[$this->listheader]; unset($this->linklist[$this->listheader]); $this->listheader=$tmp['next']; $this->listlength--; return true; } else { $value =&$this->getelemref($i); $prevvalue=&$this->getelemref($i-1); unset($this->linklist[$prevvalue['next']]); $prevvalue['next']=$value['next']; $this->listlength--; return true; } } /** * 对链表的元素排序 * 谨慎使用此函数，排序后链表将被从新初始化，原有的成员变量将会被覆盖 * @accse public * @param boolean $sorttype='true' 排序方式,true表示升序，false表示降序，默认true */ public function listsort($sorttype='true') { //从新修改关联关系可能会更复杂，所以我选择先还原成一维数组，然后对数组排序，然后再生成链表 $arr=$this->returntoarray(); $sorttype?sort($arr):rsort($arr); $this->createlist($arr); } } ?>
上面这段代码就是php数组实现单链表的源码编写，希望对大家有所帮助。
http://www.bkjia.com/phpjc/446361.htmlwww.bkjia.comtruehttp://www.bkjia.com/phpjc/446361.htmltecharticle我们今天为大家带来的时候如何运用 php数组实现单链表结构 此类主要是依靠php强大的数组系统来模拟出单链表类型的数据结构。 本人完全...