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

php  /  管理员 发布于 7年前   146

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

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

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程序设计有所帮助。

您可能感兴趣的文章:

• 实现php删除链表中重复的结点
• PHP实现链表的定义与反转功能示例
• php数据结构之顺序链表与链式线性表示例
• PHP实现合并两个排序链表的方法
• PHP获取链表中倒数第K个节点的方法
• PHP从尾到头打印链表实例讲解