文西马龙：http://blog.csdn.net/wenximalong/
singleLink.php
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<body>
<h1>单向链表完成英雄排行管理</h1>
<hr/>
<a href="#">查询英雄</a>
<a href="#">添加英雄</a>
<a href="#">删除英雄</a>
<a href="#">修改英雄</a>
<?php
//首先需要基础知识。知道什么是变量，有一些面向对象编程基础。
//知道三大控制语句 if for while
//定义英雄类
class Hero{
public $no;//排名
public $name;//真实名字
public $nickname;//外号
public $next=null;//$next是一个引用，指向另外一个Hero的对象实例。
//构造函数
public function __construct($no='',$name='',$nickname=''){
//赋值
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
//创建一个head头，该head只是一个头，不放入数据
$head=new Hero();
//创建一个英雄
$hero=new Hero(1,'宋江','及时雨');
//链接
$head->next=$hero;
$hero2=new Hero(2,'卢俊义','玉麒麟');
//链接
//现在使用的是比较二的方法，马上改进，这样是为了方便理解
$hero->next=$hero2;
//单链表的遍历，必须要从head头节点开始找
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'<br/>英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
echo'<br/>***********当前的英雄排行情况是**************';
showHeros($head);
?>
</body>
</html>
在上面的代码中，添加英雄的时候用的一个比较笨的方法，
现在用一个比较好的方法做添加工作。
1.直接在链表最后加
singleLink2.php
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<body>
<h1>单向链表完成英雄排行管理</h1>
<hr/>
<a href="#">查询英雄</a>
<a href="#">添加英雄</a>
<a href="#">删除英雄</a>
<a href="#">修改英雄</a>
<?php
//定义英雄类
class Hero{
public $no;//排名
public $name;//真实名字
public $nickname;//外号
public $next=null;//$next是一个引用，指向另外一个Hero的对象实例。
//构造函数
public function __construct($no='',$name='',$nickname=''){
//赋值
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
//创建一个head头，该head只是一个头，不放入数据
$head=new Hero();
//写一个函数，专门用于添加英雄
function addHero($head,$hero){
//1.直接在链表最后加
//要找到链表的最后，千万不能动$head;
$cur=$head;
while($cur->next!=null){
$cur=$cur->next;
}
//当退出while循环的时候，此时$cur就是链表的最后
//加入hero
$cur->next=$hero;
//2.按照英雄的排行加入（这里我希望能够保证链表的顺序）
}
//单链表的遍历，必须要从head头节点开始找
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'<br/>英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
//添加
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
$hero=new Hero(6,'林冲','豹子头');
addHero($head,$hero);
$hero=new Hero(3,'吴用','智多星');
addHero($head,$hero);
//在输出的时候，林冲就排在了吴用的前面了，而林冲是6号，应当排在吴用的后面，这就是直接在链表最后添加的弊端。
echo'<br/>***********当前的英雄排行情况是**************';
showHeros($head);
?>
</body>
</html>
2.按照英雄的排行加入（这里我希望能够保证链表的顺序）
以后参加工作的时候，有可能会有这样的需求，别人给你一堆字符串，让你按照字符串的某一个属性进行排序，而且是在内存中完成排序。
怎样按照顺序来添加呢？
★一定要先谈思路，再写代码。分析图
图片大，在新窗口中打开图片，观看完整图片
假设，做一个很极端的例子。
（1）先加1号人物，首先cur指向head节点，cur->next为空，直接把1号人物加在head节点后面；
（2）再加2号人物，首先cur指向head节点，cur->next此时指向1号人物节点，cur->next->no为1和$hero->no为2进行比较，发现1不大于2，所以cur就向下面走一步，此时cur指向了1号人物节点，然后再去判断cur->next->no是否大于2，因为此时cur->next为空了，没法走了，只能把2号人物加在1号人物节点的后面。
（3）再加6号人物，首先cur指向head节点，cur->next此时指向1号人物节点，cur->next->no为1和$hero->next为6进行比较，发现1不大于6，所以cur就向下面走一步，此时cur指向1号人物节点，然后再去判断cur->next->no为2和$hero->no为6进行比较，发现2不大于6，所以cur就向下面走一步，此时cur指向了2号人物节点，然后再去判断cur->next->no是否大于6，因为此时cur->next为空了，没法走了，只能把6号人物加在2号人物节点的后面。
（4）再加3号人物，首先cur指向head节点，cur->next此时指向1号人物节点，cur->next->no为1和$hero->next为3进行比较，发现1不大于3，所以cur就向下面走一步，此时cur指向1号人物节点，然后再去判断cur->next->no为2和$hero->no为3进行比较，发现2不大于3，所以cur就向下面走一步，此时cur指向了2号人物节点，然后再去判断cur->next->no为6和$hero->no为3进行比较，发现6大于3，找到位置了，通过一种操作想办法把3号人物加进去。
singleLink3.php
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<body>
<h1>单向链表完成英雄排行管理</h1>
<hr/>
<a href="#">查询英雄</a>
<a href="#">添加英雄</a>
<a href="#">删除英雄</a>
<a href="#">修改英雄</a>
<?php
//定义英雄类
class Hero{
public $no;//排名
public $name;//真实名字
public $nickname;//外号
public $next=null;//$next是一个引用，指向另外一个Hero的对象实例。
//构造函数
public function __construct($no='',$name='',$nickname=''){
//赋值
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
//创建一个head头，该head只是一个头，不放入数据
$head=new Hero();
//写一个函数，专门用于添加英雄
function addHero($head,$hero){
//1.直接在链表最后加
//要找到链表的最后，千万不能动$head;
$cur=$head;
//2.按照英雄的排行加入（这里我希望能够保证链表的顺序）
//思路：一定要先谈思路，再写代码
while($cur->next!=null){
if($cur->next->no>=$hero->no){
//找到位置了
break; //一旦break，就跳出了while循环
}
//继续
$cur=$cur->next;
}
//当退出while循环的时候，位置找到
//加入
//让hero加入
$hero->next=$cur->next;
$cur->next=$hero;
}
//单链表的遍历，必须要从head头节点开始找
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'<br/>英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
//添加
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
$hero=new Hero(6,'林冲','豹子头');
addHero($head,$hero);
$hero=new Hero(3,'吴用','智多星');
addHero($head,$hero);
//在输出的时候，林冲就排在了吴用的前面了，而林冲是6号，应当排在吴用的后面，这就是直接在链表最后添加的弊端。
echo'<br/>***********当前的英雄排行情况是**************';
showHeros($head);
?>
</body>
</html>
执行过程分析图
图片大，在新窗口中打开图片，观看完整图片
如上图所示，当加入3号人物的时候，cur指向2号人物节点，cur->next指向地址0x1234，即是6号人物节点，此时3号人物的地址为0x345。执行$hero->next=$cur->next;即让3号人物的节点的next指向6号人物节点地址0x1234，图中的①虚蓝线所示；然后$cur->next=$hero;即把2号人物节点的next由指向地址0x1234改为指向3号人物节点地址0x345，图中的③虚蓝线所示，原来的②实线断开。
这样就把3号人物插在了2号人物的后面。
没有好办法，光看是学不会的，自己动手敲代码，自己画图分析，加深理解。
再加改进功能：不让有相同排名的英雄加入链表。
把singleLink3.php中的while循环代码修改如下：
singleLink4.php
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<body>
<h1>单向链表完成英雄排行管理</h1>
<hr/>
<a href="#">查询英雄</a>
<a href="#">添加英雄</a>
<a href="#">删除英雄</a>
<a href="#">修改英雄</a>
<?php
//定义英雄类
class Hero{
public $no;//排名
public $name;//真实名字
public $nickname;//外号
public $next=null;//$next是一个引用，指向另外一个Hero的对象实例。
//构造函数
public function __construct($no='',$name='',$nickname=''){
//赋值
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
//创建一个head头，该head只是一个头，不放入数据
$head=new Hero();
//写一个函数，专门用于添加英雄
function addHero($head,$hero){
//1.直接在链表最后加
//要找到链表的最后，千万不能动$head;
$cur=$head;
//2.按照英雄的排行加入（这里我希望能够保证链表的顺序）
//思路：一定要先谈思路，再写代码
$flag=false; //表示没有重复的编号
while($cur->next!=null){
if($cur->next->no>$hero->no){
//找到位置了
break;
}else if($cur->next->no==$hero->no){
$flag=true; //如果进入此处，就说明有重复的了，置为true
echo'<br/>不能抢位置，'.$hero->no.'位置已经有人了';
}
//继续
$cur=$cur->next;
}
//当退出while循环的时候，位置找到
//加入
//让hero加入
if($flag==false){ //只有当$flag为false的时候，说明没有遇到重复的，才会执行插入。如果不加$flag标志位，虽然上面的else if判断了，遇到重复的，但是仍然会插入。
$hero->next=$cur->next;
$cur->next=$hero;
}
}
//单链表的遍历，必须要从head头节点开始找
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'<br/>英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
//添加
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
$hero=new Hero(6,'林冲','豹子头');
addHero($head,$hero);
$hero=new Hero(3,'吴用','智多星');
addHero($head,$hero);
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
//在输出的时候，林冲就排在了吴用的前面了，而林冲是6号，应当排在吴用的后面，这就是直接在链表最后添加的弊端。
echo'<br/>***********当前的英雄排行情况是**************';
showHeros($head);
?>
</body>
</html>
以上的是增加功能。
=============
我们现在再加入删除功能：
分析图
图片大，在新窗口中打开图片，观看完整图片
现在有3个人物节点，要把3号人物节点删除。
（1）首先有一个变量cur指向了head节点，即$cur=$head；$cur->next!=null成立，进入while循环，进行if判断，$cur->next->no为1，则和$herono为3不相等，cur向下走一步。
（2）此时cur指向了1号人物节点，$cur->next!=null成立，进入while循环，进行if判断，
$cur->next->no为3，则和$herono为3相等，找到位置了就break跳出了while循环。就要把这个3号人物节点拿掉，应该怎么拿呢？假设3号人物节点地址为0x123，7号人物节点地址为0x456，现在就是要把1号人物节点的next值改为0x456，这样3号人物节点就不在此单链表中了。有人会有疑惑：3号人物节点不是也有next值，指向0x456吗即指向7号人物节点的，不用担心，此时3号人物节点已经是垃圾对象了，因为在php、java和c#中都有规定，如果一个对象没有任何一个引用指向它，它就是垃圾了，这一点一定要清楚，垃圾回收机制就会把3号人物节点回收了， 这就是拿掉3号人物节点的思路。
删除代码
$cur->next=$cur->next->next;
注意：当你刚好删除的末尾会不会有问题呢？
删除最后一个节点，即要删除7号人物，那么cur就定位到了3号人物节点，此时$cur->next->next就是 7号人物节点的next属性值，7号人物节点是最后一个节点，它的next属性值为null，那么$cur->next=$cur->next->next;就是把3号人物节点的next属性值置为null，那么此时3号人物节点就是最后一个节点了就是末尾了。
singleLink5.php
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<body>
<h1>单向链表完成英雄排行管理</h1>
<hr/>
<a href="#">查询英雄</a>
<a href="#">添加英雄</a>
<a href="#">删除英雄</a>
<a href="#">修改英雄</a>
<?php
//定义英雄类
class Hero{
public $no;//排名
public $name;//真实名字
public $nickname;//外号
public $next=null;//$next是一个引用，指向另外一个Hero的对象实例。
//构造函数
public function __construct($no='',$name='',$nickname=''){
//赋值
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
//创建一个head头，该head只是一个头，不放入数据
$head=new Hero();
//写一个函数，专门用于添加英雄
function addHero($head,$hero){
//1.直接在链表最后加
//要找到链表的最后，千万不能动$head;
$cur=$head;
//2.按照英雄的排行加入（这里我希望能够保证链表的顺序）
//思路：一定要先谈思路，再写代码
$flag=false; //表示没有重复的编号
while($cur->next!=null){
if($cur->next->no>$hero->no){
//找到位置了
break;
}else if($cur->next->no==$hero->no){
$flag=true; //如果进入此处，就说明有重复的了，置为true
echo'<br/>不能抢位置，'.$hero->no.'位置已经有人了';
}
//继续
$cur=$cur->next;
}
//当退出while循环的时候，位置找到
//加入
//让hero加入
if($flag==false){ //只有当$flag为false的时候，说明没有遇到重复的，才会执行插入。如果不加$flag标志位，虽然上面的else if判断了，遇到重复的，但是仍然会插入。
$hero->next=$cur->next;
$cur->next=$hero;
}
}
//单链表的遍历，必须要从head头节点开始找
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'<br/>英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
//从链表中删除某个英雄
function delHero($head,$herono){
//首先要找到这个英雄在哪里
$cur=$head; //让$cur指向$head;
$flag=false; //标志位，假设没有找到
while($cur->next!=null){
if($cur->next->no==$herono){
$flag=true; //进入if语句就说明找到了，置为true
//找到 $cur的下一个节点就是应该被删除的节点。
break;
}
$cur=$cur->next;
}
if($flag){ //如果flag为真，就删除
//删除
$cur->next=$cur->next->next;
}else{
echo'<br/>没有你要删除的英雄的编号'.$herono;
}
}
//添加
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
$hero=new Hero(6,'林冲','豹子头');
addHero($head,$hero);
$hero=new Hero(3,'吴用','智多星');
addHero($head,$hero);
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
//在输出的时候，林冲就排在了吴用的前面了，而林冲是6号，应当排在吴用的后面，这就是直接在链表最后添加的弊端。
echo'<br/>***********当前的英雄排行情况是**************';
showHeros($head);
echo'<br/>***********删除后的英雄排行情况是**************';
delHero($head,1);
delHero($head,21); //删除一个不存在的
showHeros($head);
?>
</body>
</html>
========
继续添加修改功能：
singleLink6.php
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
</head>
<body>
<h1>单向链表完成英雄排行管理</h1>
<hr/>
<a href="#">查询英雄</a>
<a href="#">添加英雄</a>
<a href="#">删除英雄</a>
<a href="#">修改英雄</a>
<?php
//定义英雄类
class Hero{
public $no;//排名
public $name;//真实名字
public $nickname;//外号
public $next=null;//$next是一个引用，指向另外一个Hero的对象实例。
//构造函数
public function __construct($no='',$name='',$nickname=''){
//赋值
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
//创建一个head头，该head只是一个头，不放入数据
$head=new Hero();
//写一个函数，专门用于添加英雄
function addHero($head,$hero){
//1.直接在链表最后加
//要找到链表的最后，千万不能动$head;
$cur=$head;
//2.按照英雄的排行加入（这里我希望能够保证链表的顺序）
//思路：一定要先谈思路，再写代码
$flag=false; //表示没有重复的编号
while($cur->next!=null){
if($cur->next->no>$hero->no){
//找到位置了
break;
}else if($cur->next->no==$hero->no){
$flag=true; //如果进入此处，就说明有重复的了，置为true
echo'<br/>不能抢位置，'.$hero->no.'位置已经有人了';
}
//继续
$cur=$cur->next;
}
//当退出while循环的时候，位置找到
//加入
//让hero加入
if($flag==false){ //只有当$flag为false的时候，说明没有遇到重复的，才会执行插入。如果不加$flag标志位，虽然上面的else if判断了，遇到重复的，但是仍然会插入。
$hero->next=$cur->next;
$cur->next=$hero;
}
}
//单链表的遍历，必须要从head头节点开始找
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'<br/>英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
//从链表中删除某个英雄
function delHero($head,$herono){
//首先要找到这个英雄在哪里
$cur=$head; //让$cur指向$head;
$flag=false; //标志位，假设没有找到
while($cur->next!=null){
if($cur->next->no==$herono){
$flag=true; //进入if语句就说明找到了，置为true
//找到 $cur的下一个节点就是应该被删除的节点。
break;
}
$cur=$cur->next;
}
if($flag){ //如果flag为真，就删除
//删除
$cur->next=$cur->next->next;
}else{
echo'<br/>没有你要删除的英雄的编号'.$herono;
}
}
//修改英雄
function updateHero($head,$hero){
//还是先找到这个英雄
$cur=$head; //$cur就是跑龙套的
while($cur->next!=null){
if($cur->next->no==$hero->no){
break;
}
//继续下走
$cur=$cur->next;
}
//这次不使用flag标志位了
//当退出while循环后，如果$cur->next==null说明cur到队尾了，也没有找到
if($cur->next==null){
echo'<br/>你需要修改的'.$hero->no.'不存在';
}else{
//编号不能修改，只能修改名字和昵称
$cur->next->name=$hero->name;
$cur->next->nickname=$hero->nickname;
}
}
//添加
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
$hero=new Hero(6,'林冲','豹子头');
addHero($head,$hero);
$hero=new Hero(3,'吴用','智多星');
addHero($head,$hero);
$hero=new Hero(1,'宋江','及时雨');
addHero($head,$hero);
$hero=new Hero(2,'卢俊义','玉麒麟');
addHero($head,$hero);
//在输出的时候，林冲就排在了吴用的前面了，而林冲是6号，应当排在吴用的后面，这就是直接在链表最后添加的弊端。
echo'<br/>***********当前的英雄排行情况是**************';
showHeros($head);
echo'<br/>***********删除后的英雄排行情况是**************';
//delHero($head,1);
delHero($head,21); //删除一个不存在的
showHeros($head);
echo'<br/>***********修改后的英雄排行情况是**************';
$hero=new Hero(1,'胡汉三','右白虎');
updateHero($head,$hero);
showHeros($head);
?>
</body>
</html>
关键是运用，如用环形链表解决丢手帕问题。
为什么没有思想，就是没有算法和数据结构，无从下手。
把这个单链表的案例， 自己敲下来，就会发现没有这么难。
使用带head头的双向链表实现—水浒英雄排行榜管理
单向链表的缺点分析：不能自我删除，需要靠辅助节点。
而双向链表，则可以自我删除，同时在二叉树，广义表中都需要使用到一个节点执行两个或者多个节点的运用！