PHP实现链表的定义与反转功能示例
发布:smiling 来源: PHP粉丝网 添加日期:2021-09-25 15:42:50 浏览: 评论:0
这篇文章主要介绍了PHP实现链表的定义与反转功能,结合实例形式分析了PHP链表的基本定义、添加、移除、遍历以及两种反转操作相关实现技巧,需要的朋友可以参考下。
本文实例讲述了PHP实现链表的定义与反转功能,分享给大家供大家参考,具体如下:
PHP定义链表及添加、移除、遍历等操作:
- <?php
- class Node
- {
- private $Data;//节点数据
- private $Next;//下一节点
- public function setData($value){
- $this->Data=$value;
- }
- public function setNext($value){
- $this->Next=$value;
- }
- public function getData(){
- return $this->Data;
- }
- public function getNext(){
- return $this->Next;
- }
- public function __construct($data,$next){
- $this->setData($data);
- $this->setNext($next);
- }
- }
- class LinkList
- {
- private $header;//头节点
- private $size;//长度
- public function getSize()
- {
- $i=0;
- $node=$this->header;
- while($node->getNext()!=null)
- {
- $i++;
- $node=$node->getNext();
- }
- return $i;
- }
- public function setHeader($value){
- $this->header=$value;
- }
- public function getHeader(){
- return $this->header;
- }
- public function __construct(){
- header("content-type:text/html; charset=utf-8");
- $this->setHeader(new Node(null,null));
- }
- /**
- *@author MzXy
- *@param $data--要添加节点的数据
- *
- */
- public function add($data)
- {
- $node=$this->header;
- while($node->getNext()!=null)
- {
- $node=$node->getNext();
- }
- $node->setNext(new Node($data,null));
- }
- /**
- *@author MzXy
- *@param $data--要移除节点的数据
- *
- */
- public function removeAt($data)
- {
- $node=$this->header;
- while($node->getData()!=$data)
- {
- $node=$node->getNext();
- }
- $node->setNext($node->getNext());
- $node->setData($node->getNext()->getData());
- }
- /**
- *@author MzXy
- *@param 遍历
- *
- */
- public function get()
- {
- $node=$this->header;
- if($node->getNext()==null){
- print("数据集为空!");
- return;
- }
- while($node->getNext()!=null)
- {
- print('['.$node->getNext()->getData().'] -> ');
- if($node->getNext()->getNext()==null){break;}
- $node=$node->getNext();
- }
- }
- /**
- *@author MzXy
- *@param $data--要访问的节点的数据
- * @param 此方法只是演示不具有实际意义
- *
- */
- public function getAt($data)
- {
- $node=$this->header->getNext();
- if($node->getNext()==null){
- print("数据集为空!");
- return;
- }
- while($node->getData()!=$data)
- {
- if($node->getNext()==null){break;}
- $node=$node->getNext();
- }
- return $node->getData();
- }
- /**
- *@author MzXy
- *@param $value--需要更新的节点的原数据 --$initial---更新后的数据
- *
- */
- public function update($initial,$value)
- {
- $node=$this->header->getNext();
- if($node->getNext()==null){
- print("数据集为空!");
- return;
- }
- while($node->getData()!=$data)
- {
- if($node->getNext()==null){break;}
- $node=$node->getNext();
- }
- $node->setData($initial);
- }
- }
- $lists = new LinkList();
- $lists -> add(1);
- $lists -> add(2);
- $lists -> get();
- echo '<pre>';
- print_r($lists);
- echo '</pre>';
- ?>
反转链表操作:
1. 常用的方法:左右交替,下一个结点保存,上一个结点替换该结点的下个结点,实现替换。
代码:
- function ReverseList($pHead)
- {
- // write code here
- if($pHead == null || $pHead->next == null){
- return $pHead;
- }
- $p = $pHead;
- $q = $pHead->next;
- $pHead->next = null;//$pHead 变为尾指针
- while($q){
- $r = $q->next;
- $q->next = $p;
- $p = $q;
- $q = $r;
- }
- return $p;
- }
2. 使用递归方法。三个结点,头结点,首节点,第二个结点,把首节点后面的所有结点当成第二个结点,依次循环下去,由于要满足 $pHead != null || $pHead->next != null ;所以不会出现遍历不完的情况。
- function ReverseList($pHead)
- {
- // write code here
- if($pHead == null || $pHead->next == null){
- return $pHead;
- }
- $res = ReverseList($pHead->next);
- $pHead->next->next = $pHead;
- $pHead->next = null;
- return $res;
- }
Tags: PHP链表定义 PHP链表反转
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)