首页 > 语言 > PHP > 正文

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

2024-05-05 00:02:10
字体:
来源:转载
供稿:网友

本文实例讲述了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教程频道。
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表

图片精选