欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-08-27 23:09:39
本文实例讲述了php双向链表定义与用法。分享给大家供大家参考,具体如下: 由于需要对一组数据多次进行移动操作,所以写个双向链表。但对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程序设计有所帮助。