singleLink.php
[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
[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
[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]
<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]
<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
[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頭的雙向鏈表實現—水浒英雄排行榜管理
單向鏈表的缺點分析：不能自我刪除，需要靠輔助節點。
而雙向鏈表，則可以自我刪除，同時在二叉樹，廣義表中都需要使用到一個節點執行兩個或者多個節點的運用！
