Community Learn Tools Library Leisure
search
English
Home > php教程 > php手册 > PHP实现双向链表、栈，c语言实现双向链表

PHP实现双向链表、栈，c语言实现双向链表

WBOY
Release： 2016-06-13 09:29:49
Original
1327 people have browsed it

PHP实现双向链表、栈，c语言实现双向链表

前期写过一个PHP实现单向链表、实现排序单向链表的一篇文章，传送门：http://www.cnblogs.com/yydcdut/p/3777760.html。双向链表写过了，再拿出来提一提：http://www.cnblogs.com/yydcdut/p/3782661.html。

这次再来分享一下实现双向链表和栈的实现。代码虽然是以前写的了，但是发现PHP写的这些代码很容易看懂！

双向链表                                                                                       

<?<span>php
        </span><span>//</span><span>双向链表</span>
        <span>class</span><span> Hero
        {
            </span><span>public</span> <span>$pre</span>=<span>null</span>;<span>//</span><span>前指针</span>
            <span>public</span> <span>$no</span>;<span>//</span><span>排名</span>
            <span>public</span> <span>$name</span>;<span>//</span><span>名字</span>
            <span>public</span> <span>$next</span>=<span>null</span>;<span>//</span><span>后指针</span>
            
            <span>/*</span><span>*
            *构造函数，申明链表头
            </span><span>*/</span>
            <span>public</span> <span>function</span> __construct(<span>$no</span>='',<span>$name</span>=''<span>)
            {
                </span><span>$this</span>->no=<span>$no</span><span>;
                </span><span>$this</span>->name=<span>$name</span><span>;
            }
            </span><span>/*</span><span>*
            *插入
            </span><span>*/</span>
            <span>static</span> <span>public</span> <span>function</span> addHero(<span>$head</span>,<span>$hero</span><span>)
            {
                </span><span>$cur</span> = <span>$head</span><span>;
                </span><span>$isExist</span>=<span>false</span><span>;
                </span><span>//</span><span>判断目前这个链表是否为空</span>
                <span>if</span>(<span>$cur</span>-><span>next</span>==<span>null</span><span>)
                {
                    </span><span>$cur</span>-><span>next</span>=<span>$hero</span><span>;
                    </span><span>$hero</span>->pre=<span>$cur</span><span>;
                }
                </span><span>else</span><span>
                {
                    </span><span>//</span><span>如果不是空节点，则安排名来添加
                    //找到添加的位置            </span>
                    <span>while</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                    {
                        </span><span>if</span>(<span>$cur</span>-><span>next</span>->no > <span>$hero</span>-><span>no)
                        {</span><span>//</span><span>如果大于了排名，跳出</span>
                            <span>break</span><span>;
                        }
                        </span><span>else</span> <span>if</span>(<span>$cur</span>-><span>next</span>->no == <span>$hero</span>-><span>no)
                        {</span><span>//</span><span>如果等于排名，则代表有这个元素了</span>
                            <span>$isExist</span>=<span>true</span><span>;
                            </span><span>echo</span> "<br>不能添加相同的编号"<span>;
                        }
                        </span><span>$cur</span>=<span>$cur</span>-><span>next</span><span>;
                    }
                    </span><span>if</span>(!<span>$isExist</span><span>)
                    {</span><span>//</span><span>如果元素不存在，执行插入操作</span>
                        <span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                        {</span><span>$hero</span>-><span>next</span>=<span>$cur</span>-><span>next</span><span>;}
                        </span><span>$hero</span>->pre=<span>$cur</span><span>;
                        </span><span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                        {</span><span>$hero</span>-><span>next</span>->pre=<span>$hero</span><span>;}
                        </span><span>$cur</span>-><span>next</span>=<span>$hero</span><span>;            
                    }
                }
            }
            </span><span>//</span><span>遍历</span>
            <span>static</span> <span>public</span> <span>function</span> showHero(<span>$head</span><span>)
            {
                </span><span>$cur</span>=<span>$head</span><span>;
                </span><span>while</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                {
                    </span><span>echo</span> "<br>编号：".<span>$cur</span>-><span>next</span>->no."名字：".<span>$cur</span>-><span>next</span>-><span>name;
                    </span><span>$cur</span>=<span>$cur</span>-><span>next</span><span>;
                }
            }        
            </span><span>static</span> <span>public</span> <span>function</span> delHero(<span>$head</span>,<span>$herono</span><span>)
            {
                </span><span>$cur</span>=<span>$head</span><span>;
                </span><span>$isFind</span>=<span>false</span><span>;
                </span><span>while</span>(<span>$cur</span>!=<span>null</span><span>)
                {
                    </span><span>if</span>(<span>$cur</span>->no==<span>$herono</span><span>)
                    {
                        </span><span>$isFind</span>=<span>true</span><span>;
                        </span><span>break</span><span>;
                    }
                    </span><span>//</span><span>继续找</span>
                    <span>$cur</span>=<span>$cur</span>-><span>next</span><span>;
                }
                </span><span>if</span>(<span>$isFind</span><span>)
                {
                    </span><span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                    {</span><span>$cur</span>->next_pre=<span>$cur</span>-><span>pre;}
                    </span><span>$cur</span>->pre-><span>next</span>=<span>$cur</span>-><span>next</span><span>;
                }
                </span><span>else</span><span>
                {</span><span>echo</span> "<br>没有找到目标"<span>;}            
            }
        }
        </span><span>$head</span> = <span>new</span><span> Hero();
        </span><span>$hero1</span> = <span>new</span> Hero(1,'1111'<span>);
        </span><span>$hero3</span> = <span>new</span> Hero(3,'3333'<span>);
        </span><span>$hero2</span> = <span>new</span> Hero(2,'2222'<span>);
        Hero</span>::addHero(<span>$head</span>,<span>$hero1</span><span>);
        Hero</span>::addHero(<span>$head</span>,<span>$hero3</span><span>);
        Hero</span>::addHero(<span>$head</span>,<span>$hero2</span><span>);
        Hero</span>::showHero(<span>$head</span><span>);
        Hero</span>::delHero(<span>$head</span>,2<span>);
        Hero</span>::showHero(<span>$head</span><span>);
</span>?>
Copy after login

双向链表的插入操作示意图：

<span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
    </span><span>$hero</span>-><span>next</span>=<span>$cur</span>-><span>next</span><span>;
</span><span>$hero</span>->pre=<span>$cur</span><span>;
 </span><span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
    </span><span>$hero</span>-><span>next</span>->pre=<span>$hero</span><span>;
</span><span>$cur</span>-><span>next</span>=<span>$hero</span>;
Copy after login

if($cur->next!=null) $cur->next->pre=$cur->pre; $cur->pre->next=$cur->next;

栈 

<?<span>php

    </span><span>class</span><span> myStack
    {
        </span><span>private</span> <span>$top</span>=-1<span>;
        </span><span>private</span> <span>$maxSize</span>=5<span>;
        </span><span>private</span> <span>$stack</span>=<span>array</span><span>();
        </span><span>public</span> <span>function</span> push(<span>$val</span><span>)
        {
            </span><span>if</span>(<span>$this</span>->top == <span>$this</span>-><span>maxSize)
            {
                </span><span>echo</span> "<br>已经满了"<span>;
            }
            </span><span>$this</span>->top++<span>;
            </span><span>$this</span>->stack[<span>$this</span>->top]=<span>$val</span><span>;
        }
        
        </span><span>public</span> <span>function</span><span> showStack()
        {
            </span><span>if</span>(<span>$this</span>->top==-1<span>)
            {
                </span><span>echo</span> "<br>栈为空！"<span>;
                </span><span>return</span><span> ;
            }
            </span><span>for</span>(<span>$i</span>=<span>$this</span>->top;<span>$i</span>>-1;<span>$i</span>--<span>)
            {
                </span><span>echo</span> "<br>stack[".<span>$i</span>."]=".<span>$this</span>->stack[<span>$i</span><span>];
            }
        }
        
        </span><span>public</span> <span>function</span><span> pop()
        {
            </span><span>if</span>(<span>$this</span>->top==-1<span>)
            {
                </span><span>echo</span> "<br>栈为空！"<span>;
                </span><span>return</span><span> ;
            }
            
            </span><span>$val</span>=<span>$this</span>->stack[<span>$this</span>-><span>top];
            </span><span>$this</span>->top--<span>;
            </span><span>echo</span> "<br>弹出".<span>$val</span><span>;
        }
    }

    </span><span>$mystack</span> = <span>new</span><span> myStack;
    </span><span>$mystack</span>->push('111'<span>);
    </span><span>$mystack</span>->push('222'<span>);
    </span><span>$mystack</span>-><span>showStack();
    </span><span>$mystack</span>-><span>pop();
    </span><span>$mystack</span>-><span>pop();
</span>?>
Copy after login

我是天王盖地虎的分割线                                                                

《PHP实现链表》传送门：http://www.cnblogs.com/yydcdut/p/3777760.html

 

 

 

转载请注明出处：转载请注明出处：http://www.cnblogs.com/yydcdut

java 中用双向链表模拟栈

里只实现了Stack部分功能

public class Stack{

private Node top;

public Stack(){
this.top = null;
}

public void push(Node node){
if(node == null)
return;
if(this.top == null){
this.top = node;
node.setNext(null);
node.setPre(null);
}
else{
this.top.setNext(node);
node.setPre(this.top);
node.setNext(null);
this.top = node;
}
}

public Node pop(){
if(this.top == null)
return null;
Node curr = this.top;
Node pre = curr.getPre();
pre.setNext(null);
this.top = pre;
return curr;
}

public Node top(){
return this.top;
}

public boolean isEmpty(){
return this.top == null ? true : false;
}

public void empty(){
this.top = null;
}

public static void main(String[] args){
Stack stack = new Stack();
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);

System.out.println(stack.isEmpty());
stack.push(n1);
System.out.println(stack.top().getValue());
stack.push(n2);
stack.push(n3);
System.out.println(stack.pop().getValue());
stack.empty();
}
}

class Node {
private int value;
private Node next;
private Node pre;

public Node(int value, Node next, Node pre){
this.value = value;
this.next = next;
this.pre = pre;
}

public Node(int value){
this.value = value;
this.next = null;
this.pre = null;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public Node getPre() {
return pre;
}

public void setPre(Node pre) {
this.pre = pre;
}
}

用链表实现堆栈或队列是什

堆栈或队列数据都需要种容器来盛放
比用内置数组来实现队列
int a[100];
入队操作样实现：已有元素全部移位新元素插入
（当实现效率比较低）

容器选择链表则入队操作样实现：
构造链节点（C结构体）要入队元素填入新节点再利用链表插入操作新节点插入链表

所用链表实现堆栈或队列盛放数据容器选作链表利用链表插入节点、删除节点来实现堆栈、队列相应操作

比用链表实现队列C写下几函数
//入队
void insert(指向队列（链表）指针待入队元素)；
//出队
void delete（指向队列（链表）指针）；
Related labels：
Doubly linked list
source：php.cn
Previous article：PHP无限极分类的实现（不使用递归），php递归 Next article：Apache 无法启动，Apache启动
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
In mobile view, how can I close this navigation bar when the user clicks on the link? When the user clicks a link to browse the website, the navigation bar does not close? I've...
From 2024-04-06 19:23:03
0
1
411
Submit form without button using Javascript/Jquery I'm trying to submit a form without a button by calling a JavaScript function and executin...
From 2024-04-06 14:54:03
0
2
421
Releasing the X-axis after calling Chart.zoom(): a step-by-step guide I set the scroll strategy to setScrollStrategy(AxisScrollStrategies.progressive) and on th...
From 2024-04-04 23:40:56
0
1
1339
How to listen for specific click events but suppress others? My web application contains an HTML table where each row links to a specific URL: <tabl...
From 2024-04-04 16:55:27
0
1
317
Cypress test to intercept Zoom URL I have a test case that ends up redirecting to a Zoom link. I'm trying to avoid the browse...
From 2024-04-04 16:16:37
0
1
340
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template