[PHP] 链表数据结构（单链表） - 陶士涵

链表：是一个有序的列表，但是它在内存中是分散存储的，使用链表可以解决类似约瑟夫问题，排序问题，搜索问题，广义表

单向链表，双向链表，环形链表

 

PHP的底层是C，当一个程序运行时，内存分成五个区（堆区，栈区，全局区，常量区，代码区）

规定：基本数据类型，一般放在栈区

复合数据类型，比如对象，放在堆区

 

定义一个类Hero

定义成员属性排名 $no

定义成员属性姓名 $name

定义成员属性昵称 $nickname

定义成员属性 $next，是一个引用，指向下一个Hero对象

定义构造函数，传递参数：$no，$name，$nickname

 

创建一个头head，该head只是一个头，不放入数据

获取$head对象，new Hero()

获取第一个Hero对象$hero，new Hero(1,”宋江”,”及时雨”)

连接两个对象，$head->next=$hero

获取第二个Hero对象$hero2，new Hero(2,”卢俊义”,”玉麒麟”)

连接两个对象，$hero->next=$hero2

 

遍历链表

定义一个函数showHeros()，参数：$head对象

定义一个临时变量$cur来存储 $head对象

while循环，条件$cur->next不为null

打印一下

指针后移，$cur=$cur->next

PHP版：

 

<span style="color: #000000;">php
</span><span style="color: #008000;">/*</span><span style="color: #008000;">*
* 英雄类
</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">class</span><span style="color: #000000;"> Hero{
    </span><span style="color: #0000ff;">public</span> <span style="color: #800080;">$no</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">public</span> <span style="color: #800080;">$name</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">public</span> <span style="color: #800080;">$nickname</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">public</span> <span style="color: #800080;">$next</span>=<span style="color: #0000ff;">null</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">function</span> __construct(<span style="color: #800080;">$no</span>='',<span style="color: #800080;">$name</span>='',<span style="color: #800080;">$nickname</span>=''<span style="color: #000000;">){
        </span><span style="color: #800080;">$this</span>->no=<span style="color: #800080;">$no</span><span style="color: #000000;">;
        </span><span style="color: #800080;">$this</span>->name=<span style="color: #800080;">$name</span><span style="color: #000000;">;
        </span><span style="color: #800080;">$this</span>->nickname=<span style="color: #800080;">$nickname</span><span style="color: #000000;">;
    }
}
</span><span style="color: #0000ff;">class</span><span style="color: #000000;"> LinkListDemo{
    </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">function</span><span style="color: #000000;"> main(){
        </span><span style="color: #800080;">$head</span>=<span style="color: #0000ff;">new</span><span style="color: #000000;"> Hero();
        </span><span style="color: #800080;">$hero1</span>=<span style="color: #0000ff;">new</span> Hero(1,"宋江","及时雨"<span style="color: #000000;">);
        </span><span style="color: #800080;">$head</span>-><span style="color: #008080;">next</span>=<span style="color: #800080;">$hero1</span><span style="color: #000000;">;
        </span><span style="color: #800080;">$hero2</span>=<span style="color: #0000ff;">new</span> Hero(2,"卢俊义","玉麒麟"<span style="color: #000000;">);
        </span><span style="color: #800080;">$hero1</span>-><span style="color: #008080;">next</span>=<span style="color: #800080;">$hero2</span><span style="color: #000000;">;
        LinkListDemo</span>::showHeros(<span style="color: #800080;">$head</span><span style="color: #000000;">);
    }
    </span><span style="color: #008000;">/*</span><span style="color: #008000;">*
    * 展示英雄
    </span><span style="color: #008000;">*/</span>
    <span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">function</span> showHeros(<span style="color: #800080;">$head</span><span style="color: #000000;">){
        </span><span style="color: #800080;">$cur</span>=<span style="color: #800080;">$head</span><span style="color: #000000;">;
        </span><span style="color: #0000ff;">while</span>(<span style="color: #800080;">$cur</span>-><span style="color: #008080;">next</span>!=<span style="color: #0000ff;">null</span><span style="color: #000000;">){
            </span><span style="color: #0000ff;">echo</span> "姓名：".<span style="color: #800080;">$cur</span>-><span style="color: #008080;">next</span>->name."<br>"<span style="color: #000000;">;
            </span><span style="color: #800080;">$cur</span>=<span style="color: #800080;">$cur</span>-><span style="color: #008080;">next</span><span style="color: #000000;">;
        }
    }

}

LinkListDemo</span>::main();

 

java版：

<span style="color: #0000ff;">class</span><span style="color: #000000;"> Hero{
        </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> no;
        </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> String name;
        </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> String nickname;
        </span><span style="color: #0000ff;">public</span> Hero next=<span style="color: #0000ff;">null</span><span style="color: #000000;">;
        </span><span style="color: #0000ff;">public</span><span style="color: #000000;"> Hero(){
            
        }
        </span><span style="color: #0000ff;">public</span> Hero(<span style="color: #0000ff;">int</span><span style="color: #000000;"> no,String name,String nickname) {
            </span><span style="color: #0000ff;">this</span>.no=<span style="color: #000000;">no;
            </span><span style="color: #0000ff;">this</span>.name=<span style="color: #000000;">name;
            </span><span style="color: #0000ff;">this</span>.nickname=<span style="color: #000000;">nickname;
        }

    }
</span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">class</span><span style="color: #000000;"> LinkListDemo {
    </span><span style="color: #008000;">/**</span><span style="color: #008000;">
     * </span><span style="color: #808080;">@param</span><span style="color: #008000;"> args
     </span><span style="color: #008000;">*/</span>
    <span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> main(String[] args) {
        Hero head</span>=<span style="color: #0000ff;">new</span><span style="color: #000000;"> Hero();
        
        Hero hero1</span>=<span style="color: #0000ff;">new</span> Hero(1, "宋江", "及时雨"<span style="color: #000000;">);
        head.next</span>=<span style="color: #000000;">hero1;
        Hero hero2</span>=<span style="color: #0000ff;">new</span> Hero(2, "卢俊义", "玉麒麟"<span style="color: #000000;">);
        hero1.next</span>=<span style="color: #000000;">hero2;
        showHeros(head);
    }
    </span><span style="color: #008000;">/**</span><span style="color: #008000;">
     * 展示英雄
     * </span><span style="color: #808080;">@param</span><span style="color: #008000;"> head
     </span><span style="color: #008000;">*/</span>
    <span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> showHeros(Hero head){
        Hero cur</span>=<span style="color: #000000;">head;
        </span><span style="color: #0000ff;">while</span>(cur.next!=<span style="color: #0000ff;">null</span><span style="color: #000000;">){
            System.out.println(</span>"姓名："+<span style="color: #000000;">cur.next.name);
            cur</span>=<span style="color: #000000;">cur.next;
        }
    }
}</span>