PHP双向链表定义与用法示例

发布:smiling　来源: PHP粉丝网　添加日期：2021-09-01 16:07:08　浏览: 评论：0　

本文实例讲述了PHP双向链表定义与用法，分享给大家供大家参考，具体如下：

由于需要对一组数据多次进行移动操作，所以写个双向链表，但对php实在不熟悉，虽然测试各个方法没啥问题，就是不知道php语言深层的这些指针和unset有什么注意的地方，贴出来让大家教育吧，效率没测试....求谅解～

<?php

/**

* **双向链表

* @author zhiyuan12@

*/

/**

* 链表元素结点类

*/

class Node_Element {

  public $pre = NULL; // 前驱

  public $next = NULL; // 后继

  public $key = NULL; // 元素键值

  public $data = NULL; // 结点值

  function __Construct($key, $data) {

    $this->key = $key;

    $this->data = $data;

  }

}

/**

* 双向链表类

*/

class DoubleLinkedList {

  private $head; // 头指针

  private $tail; // 尾指针

  private $current; // 当前指针

  private $len; // 链表长度

  function __Construct() {

    $this->head = self::_getNode ( null, null );

    $this->curelement = $this->head;

    $this->tail = $this->head;

    $len = 0;

  }

  /**

   * @ desc: 读取链表全部结点

   */

  public function readAll() {

    $tmp = $this->head;

    while ( $tmp->next !== null ) {

      $tmp = $tmp->next;

      var_dump ( $tmp->key, $tmp->data );

    }

  }

  public function move($pos1, $pos2) {

    $pos1Node = $this->findPosition ( $pos1 );

    $pos2Node = $this->findPosition ( $pos2 );

    if ($pos1Node !== null && $pos2Node !== null) {

      $tmpKey = $pos1Node->key;

      $tmpData = $pos1Node->data;

      $pos1Node->key = $pos2Node->key;

      $pos1Node->data = $pos2Node->data;

      $pos2Node->key = $tmpKey;

      $pos2Node->data = $tmpData;

      return true;

    }

    return false;

  }

  /**

   * @ desc: 在指定关键词删除结点

   *

   * @param : $key

   *     指定位置的链表元素key

   */

  public function delete($key) {

    $pos = $this->find ( $key );

    if ($pos !== null) {

      $tmp = $pos;

      $last = null;

      $first = true;

      while ( $tmp->next !== null && $tmp->next->key === $key ) {

        $tmp = $tmp->next;

        if (! $first) {

          $this->delNode ( $last );

        } else {

          $first = false;

        }

        $last = $tmp;

      }

      if ($tmp->next !== null) {

        $pos->pre->next = $tmp->next;

        $tmp->next->pre = $pos->pre;

      } else {

        $pos->pre->next = null;

      }

      $this->delNode ( $pos );

      $this->delNode ( $tmp );

    }

  }

  /**

   * @ desc: 在指定位置删除结点

   *

   * @param : $key

   *     指定位置的链表元素key

   */

  public function deletePosition($pos) {

    $tmp = $this->findPosition ( $pos );

    if ($tmp === null) {

      return true;

    }

    if ($tmp === $this->getTail ()) {

      $tmp->pre->next = null;

      $this->delNode ( $tmp );

      return true;

    }

    $tmp->pre->next = $tmp->next;

    $tmp->next->pre = $tmp->pre;

    $this->delNode ( $tmp );

  }

  /**

   * @ desc: 在指定键值之前插入结点

   *

   * @param : $key

   *     //指定位置的链表元素key

   * @param : $data

   *     //要插入的链表元素数据

   * @param : $flag

   *     //是否顺序查找位置进行插入

   */

  public function insert($key, $data, $flag = true) {

    $newNode = self::_getNode ( $key, $data );

    $tmp = $this->find ( $key, $flag );

    if ($tmp !== null) {

      $newNode->pre = $tmp->pre;

      $newNode->next = $tmp;

      $tmp->pre = $newNode;

      $newNode->pre->next = $newNode;

    } else {

      $newNode->pre = $this->tail;

      $this->tail->next = $newNode;

      $this->tail = $newNode;

    }

    $this->len ++;

  }

  /**

   * @ desc: 在指定位置之前插入结点

   *

   * @param : $pos

   *     指定插入链表的位置

   * @param : $key

   *     指定位置的链表元素key

   * @param : $data

   *     要插入的链表元素数据

   */

  public function insertPosition($pos, $key, $data) {

    $newNode = self::_getNode ( $key, $data );

    $tmp = $this->findPosition ( $pos );

    if ($tmp !== null) {

      $newNode->pre = $tmp->pre;

      $newNode->next = $tmp;

      $tmp->pre = $newNode;

      $newNode->pre->next = $newNode;

    } else {

      $newNode->pre = $this->tail;

      $this->tail->next = $newNode;

      $this->tail = $newNode;

    }

    $this->len ++;

    return true;

  }

  /**

   * @ desc: 根据key值查询指定位置数据

   *

   * @param : $key

   *     //指定位置的链表元素key

   * @param : $flag

   *     //是否顺序查找

   */

  public function find($key, $flag = true) {

    if ($flag) {

      $tmp = $this->head;

      while ( $tmp->next !== null ) {

        $tmp = $tmp->next;

        if ($tmp->key === $key) {

          return $tmp;

        }

      }

    } else {

      $tmp = $this->getTail ();

      while ( $tmp->pre !== null ) {

        if ($tmp->key === $key) {

          return $tmp;

        }

        $tmp = $tmp->pre;

      }

    }

    return null;

  }

  /**

   * @ desc: 根据位置查询指定位置数据

   *

   * @param : $pos

   *     //指定位置的链表元素key

   */

  public function findPosition($pos) {

    if ($pos <= 0 || $pos > $this->len)

      return null;

    if ($pos < ($this->len / 2 + 1)) {

      $tmp = $this->head;

      $count = 0;

      while ( $tmp->next !== null ) {

        $tmp = $tmp->next;

        $count ++;

        if ($count === $pos) {

          return $tmp;

        }

      }

    } else {

      $tmp = $this->tail;

      $pos = $this->len - $pos + 1;

      $count = 1;

      while ( $tmp->pre !== null ) {

        if ($count === $pos) {

          return $tmp;

        }

        $tmp = $tmp->pre;

        $count ++;

      }

    }

    return null;

  }

  /**

   * @ desc: 返回链表头节点

   */

  public function getHead() {

    return $this->head->next;

  }

  /**

   * @ desc: 返回链表尾节点

   */

  public function getTail() {

    return $this->tail;

  }

  /**

   * @ desc: 查询链表节点个数

   */

  public function getLength() {

    return $this->len;

  }

  private static function _getNode($key, $data) {

    $newNode = new Node_Element ( $key, $data );

    if ($newNode === null) {

      echo "new node fail!";

    }

    return $newNode;

  }

  private function delNode($node) {

    unset ( $node );

    $this->len --;

  }

}

$myList = new DoubleLinkedList ();

$myList->insert ( 1, "test1" );

$myList->insert ( 2, "test2" );

$myList->insert ( "2b", "test2-b" );

$myList->insert ( 2, "test2-c" );

$myList->insert ( 3, "test3" );

$myList->insertPosition ( 5, "t", "testt" );

$myList->readAll ();

echo "+++";

$myList->deletePosition(0);

$myList->readAll ();

echo "..." . $myList->getLength ();

var_dump ( $myList->findPosition ( 3 )->data );

?>

运行结果：

int(1)

string(5) "test1"

int(2)

string(7) "test2-c"

int(2)

string(5) "test2"

string(2) "2b"

string(7) "test2-b"

string(1) "t"

string(5) "testt"

int(3)

string(5) "test3"

+++int(1)

string(5) "test1"

int(2)

string(7) "test2-c"

int(2)

string(5) "test2"

string(2) "2b"

string(7) "test2-b"

string(1) "t"

string(5) "testt"

int(3)

string(5) "test3"

...6string(5) "test2"