php实现单链表的基本操作

ゝ一纸荒年。 2022-07-19 02:08 195阅读 0赞

<?php
    //定义链表节点
    class LinkNode{
    	public $data=null;
    	public $next=null;
    }
    //初始化
    function init($linkList){
    	$linkList->data=0;//用来记录链表长度  
    	$linkList->next=null;
    }
    //头插法创建链表
    function createHead(&$linkList,$length){
    	for($i=0;$i<$length;$i++){
    		$newNode=new LinkNode();
    		$newNode->data=$i;
    		$newNode->next=$linkList->next;
    		$linkList->next=$newNode;
    		$linkList->data++;
    	}
    }
    //尾插法创建链表
    function createTail(&$linkList,$length){
    	$r=$linkList;
    	for($i=0;$i<$length;$i++){
    		$newNode=new LinkNode();
    		$newNode->data=$i;
    		$newNode->next=$r->next;
    		$r->next=$newNode;
    		$r=$newNode;
    		$linkList->data++;
    	}
    }
    //在指定位置插入指定元素
    function insert($linkList,$pos,$item){
    	if($pos<1 && $pos>$linkList->data+1){
    		echo '插入位置错误';
    	}
    	$p=$linkList;
    	for($i=1;$i<$pos;$i++){
    		$p=$p->next;
    	}
    	$newNode=new LinkNode();
    	$newNode->data=$item;
    	$newNode->next=$p->next;
    	$p->next=$newNode;
    }
    //删除指定位置的元素 
    function delete($linkList,$pos){
    	if($pos<1 && $pos>$linkList->data+1){
    		echo '删除位置不存在';
    	}
    	$p=$linkList;
    	for($i=1;$i<$pos;$i++){
    		$p=$p->next;
    	}
    	$q=$p->next;
    	$p->next=$q->next;
    	unset($q);
    	$linkList->data--;
    }
    //输出链表数据  
    function show($linkList){
    	$p=$linkList->next;
    	while($p!=null){
    		echo $p->data.' ';
    		$p=$p->next;
    	}
    	echo '<br/>';
    }
    
    
    $linkList=new LinkNode();
    init($linkList);
    
    //createHead($linkList,10);
    createTail($linkList,10);
    show($linkList);
    insert($linkList,3,'a');
    show($linkList);
    delete($linkList,3);
    show($linkList);

0 1 2 3 4 5 6 7 8 9   
0 1 a 2 3 4 5 6 7 8 9   
0 1 2 3 4 5 6 7 8 9