Heim >Backend-Entwicklung >PHP-Tutorial >PHP实现双向链表、栈_PHP教程

PHP实现双向链表、栈_PHP教程

WBOY
WBOYOriginal
2016-07-13 10:22:55868Durchsuche

PHP实现双向链表、栈

双向链表                                                                                      
 
复制代码
        //双向链表
        class Hero
        {
            public $pre=null;//前指针
            public $no;//排名
            public $name;//名字
            public $next=null;//后指针
            
            /**
            *构造函数,申明链表头
            */
            public function __construct($no='',$name='')
            {
                $this->no=$no;
                $this->name=$name;
            }
            /**
            *插入
            */
            static public function addHero($head,$hero)
            {
                $cur = $head;
                $isExist=false;
                //判断目前这个链表是否为空
                if($cur->next==null)
                {
                    $cur->next=$hero;
                    $hero->pre=$cur;
                }
                else
                {
                    //如果不是空节点,则安排名来添加
                    //找到添加的位置            
                    while($cur->next!=null)
                    {
                        if($cur->next->no > $hero->no)
                        {//如果大于了排名,跳出
                            break;
                        }
                        else if($cur->next->no == $hero->no)
                        {//如果等于排名,则代表有这个元素了
                            $isExist=true;
                            echo "
不能添加相同的编号";
                        }
                        $cur=$cur->next;
                    }
                    if(!$isExist)
                    {//如果元素不存在,执行插入操作
                        if($cur->next!=null)
                        {$hero->next=$cur->next;}
                        $hero->pre=$cur;
                        if($cur->next!=null)
                        {$hero->next->pre=$hero;}
                        $cur->next=$hero;            
                    }
                }
            }
            //遍历
            static public function showHero($head)
            {
                $cur=$head;
                while($cur->next!=null)
                {
                    echo "
编号:".$cur->next->no."名字:".$cur->next->name;
                    $cur=$cur->next;
                }
            }        
            static public function delHero($head,$herono)
            {
                $cur=$head;
                $isFind=false;
                while($cur!=null)
                {
                    if($cur->no==$herono)
                    {
                        $isFind=true;
                        break;
                    }
                    //继续找
                    $cur=$cur->next;
                }
                if($isFind)
                {
                    if($cur->next!=null)
                    {$cur->next_pre=$cur->pre;}
                    $cur->pre->next=$cur->next;
                }
                else
                {echo "
没有找到目标";}            
            }
        }
        $head = new Hero();
        $hero1 = new Hero(1,'1111');
        $hero3 = new Hero(3,'3333');
        $hero2 = new Hero(2,'2222');
        Hero::addHero($head,$hero1);
        Hero::addHero($head,$hero3);
        Hero::addHero($head,$hero2);
        Hero::showHero($head);
        Hero::delHero($head,2);
        Hero::showHero($head);
?>
复制代码
双向链表的插入操作示意图:
 
if($cur->next!=null)
    $hero->next=$cur->next;
$hero->pre=$cur;
 if($cur->next!=null)
    $hero->next->pre=$hero;
$cur->next=$hero;
 
 
QQ截图20140706152241
 
删除操作示意图:
 
if($cur->next!=null)
    $cur->next->pre=$cur->pre;
$cur->pre->next=$cur->next;
 
 
QQ截图20140706152857
 
栈                                                                                              
 
复制代码
 
    class myStack
    {
        private $top=-1;
        private $maxSize=5;
        private $stack=array();
        public function push($val)
        {
            if($this->top == $this->maxSize)
            {
                echo "
已经满了";
            }
            $this->top++;
            $this->stack[$this->top]=$val;
        }
        
        public function showStack()
        {
            if($this->top==-1)
            {
                echo "
栈为空!";
                return ;
            }
            for($i=$this->top;$i>-1;$i--)
            {
                echo "
stack[".$i."]=".$this->stack[$i];
            }
        }
        
        public function pop()
        {
            if($this->top==-1)
            {
                echo "
栈为空!";
                return ;
            }
            
            $val=$this->stack[$this->top];
            $this->top--;
            echo "
弹出".$val;
        }
    }
 
    $mystack = new myStack;
    $mystack->push('111');
    $mystack->push('222');
    $mystack->showStack();
    $mystack->pop();
    $mystack->pop();
?>
复制代码
 
 
栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
 
栈在计算机的实现有多种方式:
 
硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快;
软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种
栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。
 
栈底(Bottom):是固定端,又称为表头。
 
空栈:当表中没有元素时称为空栈。
 
栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。
 
当然,php中的数组API里面带的有push和pop函数。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/845432.htmlTechArticlePHP实现双向链表、栈 双向链表 复制代码 ?php //双向链表 class Hero { public $pre=null;//前指针 public $no;//排名 public $name;//名字 public $next=null;//后指...
Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn