单链表crud操作之_水浒英雄排行算法_学习笔记_源代码图解_PPT文档整理

单向链表完成英雄排行管理

查询英雄

添加英雄

删除英雄

修改英雄

//首先需要基础知识。知道什么是变量，有一些面向对象编程基础。

//知道三大控制语句 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’
英雄的编号是’.$cur->next->no.’名字’.$cur->next->name.’外号=’.$cur->next->nickname;

//如果只写到这里，就会是死循环了

//所有要让$cul移动

$cur=$cur->next;

}

}

echo’
***********当前的英雄排行情况是**************’;

showHeros($head);

?>

在上面的代码中，添加英雄的时候用的一个比较笨的方法，现在用一个比较好的方法做添加工作。

1.直接在链表最后加

singleLink2.php

[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’
英雄的编号是’.$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’
***********当前的英雄排行情况是**************’;

showHeros($head);

?>

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

[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’
英雄的编号是’.$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’
***********当前的英雄排行情况是**************’;

showHeros($head);

?>

执行过程分析图

图片大，在新窗口中打开图片，观看完整图片

如上图所示，当加入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]

单向链表完成英雄排行管理

查询英雄

添加英雄

删除英雄

修改英雄

//定义英雄类

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’
不能抢位置，’.$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’
英雄的编号是’.$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’
***********当前的英雄排行情况是**************’;

showHeros($head);

?>

以上的是增加功能。

=============

我们现在再加入删除功能：

分析图

图片大，在新窗口中打开图片，观看完整图片

现在有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]

单向链表完成英雄排行管理

查询英雄

添加英雄

删除英雄

修改英雄

//定义英雄类

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’
不能抢位置，’.$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’
英雄的编号是’.$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’
没有你要删除的英雄的编号’.$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’
***********当前的英雄排行情况是**************’;

showHeros($head);

echo’
***********删除后的英雄排行情况是**************’;

delHero($head,1);

delHero($head,21); //删除一个不存在的

showHeros($head);

?>

========

继续添加修改功能：

singleLink6.php

[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’
不能抢位置，’.$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’
英雄的编号是’.$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’
没有你要删除的英雄的编号’.$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’
你需要修改的’.$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’
***********当前的英雄排行情况是**************’;

showHeros($head);

echo’
***********删除后的英雄排行情况是**************’;

//delHero($head,1);

delHero($head,21); //删除一个不存在的

showHeros($head);

echo’
***********修改后的英雄排行情况是**************’;

$hero=new Hero(1,’胡汉三’,’右白虎’);

updateHero($head,$hero);

showHeros($head);

?>

关键是运用，如用环形链表解决丢手帕问题。

为什么没有思想，就是没有算法和数据结构，无从下手。

把这个单链表的案例，自己敲下来，就会发现没有这么难。

使用带head头的双向链表实现—水浒英雄排行榜管理

单向链表的缺点分析：不能自我删除，需要靠辅助节点。

而双向链表，则可以自我删除，同时在二叉树，广义表中都需要使用到一个节点执行两个或者多个节点的运用！