韩顺平_PHP软件工程师玩转算法公开课(第一季)03_单链表crud操作之_水浒英雄排行算法_学习笔记_源代码图解_PPT文档整理
韩顺平_PHP程序员玩转算法公开课(第一季)03_单链表crud操作之_水浒英雄排行算法_学习笔记_源代码图解_PPT文档整理文西马龙：http://blog.csdn.net/wenximalong/
singleLink.php
单向链表完成英雄排行管理在上面的代码中，添加英雄的时候用的一个比较笨的方法，现在用一个比较好的方法做添加工作。
查询英雄 添加英雄 删除英雄 修改英雄 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
单向链表完成英雄排行管理
查询英雄 添加英雄 删除英雄 修改英雄 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
单向链表完成英雄排行管理
查询英雄 添加英雄 删除英雄 修改英雄 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
单向链表完成英雄排行管理以上的是增加功能。
查询英雄 添加英雄 删除英雄 修改英雄 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
单向链表完成英雄排行管理========
查询英雄 添加英雄 删除英雄 修改英雄 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
单向链表完成英雄排行管理关键是运用，如用环形链表解决丢手帕问题。
查询英雄 添加英雄 删除英雄 修改英雄 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头的双向链表实现—水浒英雄排行榜管理
单向链表的缺点分析：不能自我删除，需要靠辅助节点。
而双向链表，则可以自我删除，同时在二叉树，广义表中都需要使用到一个节点执行两个或者多个节点的运用！
韩顺平_PHP程序员玩转算法公开课_学习笔记_源代码图解_PPT文档整理_目录
PHP之友评论