PHP双向链表定义与用法示例
本文实例讲述了PHP双向链表定义与用法。分享给大家供大家参考，具体如下：
由于需要对一组数据多次进行移动操作，所以写个双向链表。但对php实在不熟悉，虽然测试各个方法没啥问题，就是不知道php语言深层的这些指针和unset有什么注意的地方，贴出来让大家教育吧。效率没测试....求谅解～
key=$key;
$this->data=$data;
}
}
/**
*双向链表类
*/
classDoubleLinkedList{
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:读取链表全部结点
*/
publicfunctionreadAll(){
$tmp=$this->head;
while($tmp->next!==null){
$tmp=$tmp->next;
var_dump($tmp->key,$tmp->data);
}
}
publicfunctionmove($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;
returntrue;
}
returnfalse;
}
/**
*@desc:在指定关键词删除结点
*
*@param:$key
*指定位置的链表元素key
*/
publicfunctiondelete($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
*/
publicfunctiondeletePosition($pos){
$tmp=$this->findPosition($pos);
if($tmp===null){
returntrue;
}
if($tmp===$this->getTail()){
$tmp->pre->next=null;
$this->delNode($tmp);
returntrue;
}
$tmp->pre->next=$tmp->next;
$tmp->next->pre=$tmp->pre;
$this->delNode($tmp);
}
/**
*@desc:在指定键值之前插入结点
*
*@param:$key
*//指定位置的链表元素key
*@param:$data
*//要插入的链表元素数据
*@param:$flag
*//是否顺序查找位置进行插入
*/
publicfunctioninsert($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
*要插入的链表元素数据
*/
publicfunctioninsertPosition($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++;
returntrue;
}
/**
*@desc:根据key值查询指定位置数据
*
*@param:$key
*//指定位置的链表元素key
*@param:$flag
*//是否顺序查找
*/
publicfunctionfind($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;
}
}
returnnull;
}
/**
*@desc:根据位置查询指定位置数据
*
*@param:$pos
*//指定位置的链表元素key
*/
publicfunctionfindPosition($pos){
if($pos<=0||$pos>$this->len)
returnnull;
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++;
}
}
returnnull;
}
/**
*@desc:返回链表头节点
*/
publicfunctiongetHead(){
return$this->head->next;
}
/**
*@desc:返回链表尾节点
*/
publicfunctiongetTail(){
return$this->tail;
}
/**
*@desc:查询链表节点个数
*/
publicfunctiongetLength(){
return$this->len;
}
privatestaticfunction_getNode($key,$data){
$newNode=newNode_Element($key,$data);
if($newNode===null){
echo"newnodefail!";
}
return$newNode;
}
privatefunctiondelNode($node){
unset($node);
$this->len--;
}
}
$myList=newDoubleLinkedList();
$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程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。