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

本文实例讲述了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"

更多关于php相关内容感兴趣的读者可查看本站专题：《php数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《php数组(array)操作技巧大全》、《php常用遍历算法与技巧总结》及《php数学运算技巧总结》

希望本文所述对大家php程序设计有所帮助。