Home > Article > Backend Development > Singly linked list crud operation_Water Margin hero ranking algorithm_study notes_source code illustration_PPT document organization_PHP tutorial
Singly linked list crud operation_Water Margin hero ranking algorithm_study notes_source code illustration_PPT document organization_PHP tutorial
- WBOYOriginal
- 2016-07-14 10:07:321071browse
singleLink.php
[php]
One-way linked list completes hero ranking management
// First of all, the basic knowledge is required. Know what variables are and have some basics in object-oriented programming.
//Know the three major control statements if for while
//Define hero class
class Hero{
public $no;//ranking
public $name;//real name
public $nickname;//nickname
Public $next=null;//$next is a reference pointing to another Hero object instance.
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
// Now use a comparison method, immediately improve, so to facilitate understanding
$hero->next=$hero2;
$cur=$head;
while($cur->next!=null){
$cur=$cur->next;
}
}
echo'
public function __construct($no='',$name='',$nickname=''){
$head=new Hero();
//Write a function specifically for adding heroes
function addHero($head,$hero){
to
}
$cur->next=$hero;
// 2. Add to the hero's ranking (here I hope to ensure the order of the linked list)
}
// In order not to change the direction of $ head here, we can use a temporary variable
$cur=$head;
while($cur->next!=null){
$cur=$cur->next;
}
}
//Add
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
$hero=new Hero(6,'Lin Chong','Leopard Head');
addHero($head,$hero);
$hero=new Hero(3,'Wu Yong','Zhi Duoxing');
addHero($head,$hero);
// When the output is output, Lin Chong ranks in front of Wu Yong, and Lin Chong is No. 6, which should be ranked behind Wu Yong. This is the disadvantage of the last adding to the linked list.
echo'
The picture is large, open the picture in a new window to view the full picture
public function __construct($no='',$name='',$nickname=''){
$head=new Hero();
//Write a function specifically for adding heroes
function addHero($head,$hero){
// 1. At the end of the linked list, add
$cur=$cur->next;
}
to out ’’s ’ ’ s ’ out out out out out out out out out outmb out out together out together up to to 3 after- s t-luse to spouse to swipe at .
// Started from the head, the value of the $ head head must not change, and it cannot traverse our single linked list after the change.
function showHeros($head){
while($cur->next!=null){
?>
Execution process analysis diagram
The picture is large, open the picture in a new window to view the full picture
As shown in the figure above, when adding character No. 3, cur points to the character node No. 2, cur->next points to the address 0x1234, which is the character node No. 6. At this time, the address of character No. 3 is 0x345. Execute $hero->next=$cur->next; that is, let the next of the node of character No. 3 point to the node address of character No. 6, 0x1234, as shown by the dotted blue line ① in the figure; then $cur->next= $hero; That is, change the next of the character node No. 2 from pointing to the address 0x1234 to the address 0x345 of the character node No. 3. As shown in the ③ dotted blue line in the figure, the original ② solid line is disconnected.
This puts the No. 3 character behind the No. 2 character.
There is no good way. You can’t learn by just watching. Type the code yourself, draw pictures and analyze by yourself to deepen your understanding.
Added improvements: Heroes with the same ranking will not be allowed to join the linked list.
Modify the while loop code in singleLink3.php as follows:
singleLink4.php
[html]
Query Hero
Add Hero
Delete Hero
Modify Hero
//Define hero class
class Hero{
public $no;//ranking
public $name;//real name
public $nickname;//nickname
Public $next=null;//$next is a reference pointing to another Hero object instance.
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
$cur=$head;
// 2. Add to the hero's ranking (here I hope to ensure the order of the linked list)
IF ($ FLAG == False) {// Only when $ flag is false, it means that the insertion will be executed without repeating. If the $flag flag is not added, although the above else if judgment is made and duplicates are encountered, they will still be inserted.
$hero->next=$cur->next;
$cur->next=$hero;
}
}
having having to use a temporary variable to not change the direction of $head –
echo '& lt; br/& gt; hero's number is'. $ Cur- & GT; NEXT-& GT; NO.'. cur->next->nickname;
becoming ’s having to come up ’ ’ s ’ out out.
$cur=$cur->next;
}
}
//Add
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
?>
The above are added functions.
=============
We now add the delete function:
Analysis Chart
The picture is large, open the picture in a new window to view the full picture
There are now 3 character nodes, and the character node No. 3 needs to be deleted.
(1) First, there is a variable cur pointing to the head node, that is, $cur=$head; $cur->next!=null is established, enter the while loop, and perform if judgment, $cur->next-> ;no is 1, which is not equal to $herono being 3, and cur takes a step downward.
(2) At this time, cur points to the character node No. 1, $cur->next!=null is established, enters the while loop, and performs if judgment,
$cur->next->no is 3, which is equal to $herono being 3. When the position is found, break out of the while loop. We need to remove this No. 3 character node. How should we get it? Assume that the address of character node No. 3 is 0x123 and that of character node No. 7 is 0x456. Now we need to change the next value of character node No. 1 to 0x456, so that character node No. 3 is no longer in this singly linked list. Some people may have doubts: Doesn’t character node No. 3 also have a next value, pointing to 0x456? That is, it points to character node No. 7. Don’t worry, character node No. 3 is already a garbage object at this time, because it is available in php, java and c#. It is stipulated that if an object does not have any reference pointing to it, it is garbage. This must be clear. The garbage collection mechanism will recycle the No. 3 character node. This is the idea of removing the No. 3 character node.
Delete code
$cur->next=$cur->next->next;
Note: Will there be any problem if you just delete the end?
Delete the last node, that is, delete the character No. 7, then cur will locate the character node No. 3. At this time, $cur->next->next is the next attribute value of the character node No. 7, character No. 7 The node is the last node, and its next attribute value is null, then $cur->next=$cur->next->next; is to set the next attribute value of the No. 3 character node to null, then at this time Character node No. 3 is the last node and the end.
singleLink5.php
[html]
Query Hero
Add Hero
Delete Hero
Modify Hero
//Define hero class
class Hero{
public $no;//ranking
public function __construct($no='',$name='',$nickname=''){
$head=new Hero();
//Write a function specifically for adding heroes
function addHero($head,$hero){
to
IF ($ FLAG == False) {// Only when $ flag is false, it means that the insertion will be executed without repeating. If the $flag flag is not added, although the above else if judgment is made and duplicates are encountered, they will still be inserted.
$hero->next=$cur->next;
$cur->next=$hero;
}
}
having having to use a temporary variable to not change the direction of $head –
echo '& lt; br/& gt; hero's number is'. $ Cur- & GT; NEXT-& GT; NO.'. cur->next->nickname;
becoming ’s having to come up ’ ’ s ’ out out.
$cur=$cur->next;
}
}
//Delete a hero from the linked list
function delHero($head,$herono){
$cur=$cur->next;
}
$cur->next=$cur->next->next;
}else{
echo'
There is no number of the hero you want to delete'.$herono;
}
}
//Add
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
$hero=new Hero(6,'Lin Chong','Leopard Head');
addHero($head,$hero);
$hero=new Hero(3,'Wu Yong','Zhi Duoxing');
addHero($head,$hero);
$hero=new Hero(1,'Song Jiang','Timely Rain');
public function __construct($no='',$name='',$nickname=''){
$head=new Hero();
//Write a function specifically for adding heroes
function addHero($head,$hero){
to
IF ($ FLAG == False) {// Only when $ flag is false, it means that the insertion will be executed without repeating. If the $flag flag is not added, although the above else if judgment is made and duplicates are encountered, they will still be inserted.
$hero->next=$cur->next;
$cur->next=$hero;
}
}
$cur=$cur->next;
}
$cur->next=$cur->next->next;
}else{
echo'
There is no number of the hero you want to delete'.$herono;
}
}
//Modify the hero
function updateHero($head,$hero){
// Let’s find this hero first
while($cur->next!=null){
if($cur->next==null){
echo '& lt; br/& gt; you need to modify'. $ Hero-& GT; no.
with with with with echo'
updateHero($head,$hero);
showHeros($head);
?>
The key is application, such as using a circular linked list to solve the problem of losing a handkerchief.
Why there is no idea, there is no algorithm and data structure, and there is no way to start.
If you knock down this singly linked list case yourself, you will find that it is not that difficult.
Using a two-way linked list with header to implement - Water Margin hero ranking management
http://www.bkjia.com/PHPjc/477873.html
//The first node is the head node, so use $cur->next to point to the next node. There is nothing in the head node and it is empty
echo '& lt; br/& gt; hero's number is'. $ Cur- & GT; NEXT-& GT; NO.'. cur->next->nickname;
// If you only write here, it will be a dead cycle
showHeros($head);
?>
In the above code, a relatively stupid method was used when adding heroes, but now a better method is used to add heroes.
1. Add
directly at the end of the linked list
singleLink2.php
[php]
One-way linked list completes hero ranking management
//Define hero class
class Hero{
public $no;//ranking
public $name;//real name
public $nickname;//nickname
Public $next=null;//$next is a reference pointing to another Hero object instance.
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
// Find the linked list at the end, never move $ head;
$cur=$head;
while($cur->next!=null){
$cur=$cur->next; // Started from the head, the value of the $ head head must not change, and it cannot traverse our single linked list after the change.
function showHeros($head){
//The first node is the head node, so use $cur->next to point to the next node. There is nothing in the head node and it is empty
echo '& lt; br/& gt; hero's number is'. $ Cur- & GT; NEXT-& GT; NO.'. cur->next->nickname;
// If you only write here, it will be a dead cycle
showHeros($head);
?>
2. Join according to the ranking of heroes (here I hope to ensure the order of the linked list)
When you work in the future, you may have such a need. Someone gives you a bunch of strings and asks you to sort them according to a certain attribute of the strings, and the sorting is done in memory.
How to add them in order?
★Be sure to talk about ideas first and then write code. Analysis chart
Assume, let’s take a very extreme example.
(1) Add character No. 1 first, first cur points to the head node, cur->next is empty, add character No. 1 directly after the head node;
(2) Add character No. 2, first cur points to the head node, cur->next now points to character node No. 1, cur->next->no is 1 and $hero->no is 2 is compared, and it is found that 1 is not greater than 2, so cur takes a step downward. At this time, cur points to the character node No. 1, and then judges whether cur->next->no is greater than 2, because at this time cur- >next is empty and there is no way to go. We can only add character No. 2 after the character node No. 1.
(3) Add character No. 6, first cur points to the head node, cur->next now points to character node No. 1, cur->next->no is 1 and $hero->next is 6 is compared, and it is found that 1 is not greater than 6, so cur takes a step downwards. At this time, cur points to the character node No. 1, and then judges that cur->next->no is 2 and $hero->no is 6 is compared, and it is found that 2 is not greater than 6, so cur takes a step downward. At this time, cur points to the character node No. 2, and then judges whether cur->next->no is greater than 6, because at this time cur- >next is empty and there is no way to go. We can only add character No. 6 after the character node No. 2.
(4) Add character No. 3, first cur points to the head node, cur->next now points to character node No. 1, cur->next->no is 1 and $hero->next is 3 is compared, and it is found that 1 is not greater than 3, so cur takes a step downwards. At this time, cur points to the character node No. 1, and then judges that cur->next->no is 2 and $hero->no is 3 is compared and found that 2 is not greater than 3, so cur takes a step downward. At this time, cur points to the character node No. 2, and then judges cur->next->no to be 6 and $hero->no Compare 3 and find that 6 is greater than 3. We have found the position and find a way to add character No. 3 through an operation.
singleLink3.php
[php]
One-way linked list completes hero ranking management
//Define hero class
class Hero{
public $no;//ranking
public $name;//real name
public $nickname;//nickname
Public $next=null;//$next is a reference pointing to another Hero object instance.
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
// Find the linked list at the end, never move $ head;
$cur=$head;
// 2. Add to the hero's ranking (here I hope to ensure the order of the linked list)
// Thinking: Be sure to talk first, and then write the code
while($cur->next!=null){
>
//Join
$hero->next=$cur->next;
$cur->next=$hero;
}
having having to use a temporary variable to not change the direction of $head –
$cur=$head; //The first node is the head node, so use $cur->next to point to the next node. There is nothing in the head node and it is empty
echo '& lt; br/& gt; hero's number is'. $ Cur- & GT; NEXT-& GT; NO.'. cur->next->nickname;
becoming ’s having to come up ’ ’ s ’ out out.
$cur=$cur->next;
}
}
//Add
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
$hero=new Hero(6,'Lin Chong','Leopard Head');
addHero($head,$hero);
$hero=new Hero(3,'Wu Yong','Zhi Duoxing');
addHero($head,$hero);
// When the output is output, Lin Chong is in front of Wu Yong, and Lin Chong is No. 6, which should be ranked behind Wu Yong. This is the disadvantage of the last adding to the linked list.
echo'
showHeros($head);
One-way linked list completes hero ranking management
public function __construct($no='',$name='',$nickname=''){
$head=new Hero();
//Write a function specifically for adding heroes
function addHero($head,$hero){
to
// Find the linked list at the end, never move $ head; // Thinking: Be sure to talk first, and then write the code
$flag=false; //Indicates there are no duplicate numbers
while($cur->next!=null){
>
break;
}else if($cur->next->no==$hero->no){
$ Flag = TRUE; // If you enter here, it means that there are repeated, placed to true
echo'
Cannot grab the seat, '.$hero->no.'The seat is already occupied';
Cannot grab the seat, '.$hero->no.'The seat is already occupied';
$cur=$cur->next;
}
to out ’’s ’ ’ s ’ out out out out out out out out out outmb out out together out together up to to 3 after- s t-luse to spouse to swipe at .
//Join
// Started from the head, the value of the $ head head must not change, and it cannot traverse our single linked list after the change.
function showHeros($head){
$cur=$head;
while($cur->next!=null){
//The first node is the head node, so use $cur->next to point to the next node. There is nothing in the head node and it is empty $hero=new Hero(6,'Lin Chong','Leopard Head');
addHero($head,$hero);
$hero=new Hero(3,'Wu Yong','Zhi Duoxing');
addHero($head,$hero);
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
// When the output is output, Lin Chong is in front of Wu Yong, and Lin Chong is No. 6, which should be ranked behind Wu Yong. This is the disadvantage of the last adding to the linked list.
echo'
showHeros($head);
One-way linked list completes hero ranking management
public $name;//real name
public $nickname;//nickname
Public $next=null;//$next is a reference pointing to another Hero object instance.
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
// Find the linked list at the end, never move $ head;
$cur=$head;
// 2. Add to the hero's ranking (here I hope to ensure the order of the linked list)
// Thinking: Be sure to talk first, and then write the code
$flag=false; //Indicates there are no duplicate numbers
while($cur->next!=null){
>
break;
}else if($cur->next->no==$hero->no){
$ Flag = TRUE; // If you enter here, it means that there are repeated, placed to true
echo'
Cannot grab the seat, '.$hero->no.'The seat is already occupied';
Cannot grab the seat, '.$hero->no.'The seat is already occupied';
$cur=$cur->next;
}
to out ’’s ’ ’ s ’ out out out out out out out out out outmb out out together out together up to to 3 after- s t-luse to spouse to swipe at .
//Join
// Started from the head, the value of the $ head head must not change, and it cannot traverse our single linked list after the change.
function showHeros($head){
$cur=$head;
while($cur->next!=null){
//The first node is the head node, so use $cur->next to point to the next node. There is nothing in the head node and it is empty $cur=$head; //Let $cur point to $head;
$flag=false; //Flag bit, assuming not found
while($cur->next!=null){
if($cur->next->no==$herono){ // Find the next node of the $ Cur is the node that should be deleted.
break;
There is no number of the hero you want to delete'.$herono;
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;//real name
public $nickname;//nickname
Public $next=null;//$next is a reference pointing to another Hero object instance.
$this->no=$no;
$this->name=$name;
$this->nickname=$nickname;
}
}
// Find the linked list at the end, never move $ head;
$cur=$head;
// 2. Add to the hero's ranking (here I hope to ensure the order of the linked list)
// Thinking: Be sure to talk first, and then write the code
$flag=false; //Indicates there are no duplicate numbers
while($cur->next!=null){
>
break;
}else if($cur->next->no==$hero->no){
$ Flag = TRUE; // If you enter here, it means that there are repeated, placed to true
echo'
Cannot grab the seat, '.$hero->no.'The seat is already occupied';
Cannot grab the seat, '.$hero->no.'The seat is already occupied';
$cur=$cur->next;
}
to out ’’s ’ ’ s ’ out out out out out out out out out outmb out out together out together up to to 3 after- s t-luse to spouse to swipe at .
//Join
//是从head开始遍历的，$head头的值千万不能变，变化后就不能遍历我们的单链表了
function showHeros($head){
//遍历[必须要知道什么时候，到了链表的最后]
//这里为了不去改变$head的指向，我们可以使用一个临时的变量
$cur=$head;
while($cur->next!=null){
//第一个节点为头结点，所以用$cur->next指向下一个节点，头结点里什么都没有是空的
echo'
英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
英雄的编号是'.$cur->next->no.'名字'.$cur->next->name.'外号='.$cur->next->nickname;
//如果只写到这里，就会是死循环了
//所有要让$cul移动
$cur=$cur->next;
}
}
//从链表中删除某个英雄
function delHero($head,$herono){
//首先要找到这个英雄在哪里
$cur=$head; //让$cur指向$head;
$flag=false; //Flag bit, assuming not found
while($cur->next!=null){
if($cur->next->no==$herono){ // Find the next node of the $ Cur is the node that should be deleted.
break;
There is no number of the hero you want to delete'.$herono;
IF ($ Cur-& GT; Next-& GT; No == $ Hero-& GT; NO) {
break;
$cur=$cur->next;
}
using using the flag ‐
// After exiting the WHILE cycle, if $ Cur-& GT; Next == NULL indicates that the cur is to the end of the team, and no }else{
// The number cannot be modified, and the name and nickname can only be modified
$cur->next->name=$hero->name;
$cur->next->nickname=$hero->nickname;
}
}
//Add
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
$hero=new Hero(6,'Lin Chong','Leopard Head');
addHero($head,$hero);
$hero=new Hero(3,'Wu Yong','Zhi Duoxing');
addHero($head,$hero);
$hero=new Hero(1,'Song Jiang','Timely Rain');
addHero($head,$hero);
$hero=new Hero(2,'Lu Junyi','Yu Qilin');
addHero($head,$hero);
// When the output is output, Lin Chong is in front of Wu Yong, and Lin Chong is No. 6, which should be ranked behind Wu Yong. This is the disadvantage of the last adding to the linked list.
echo'
showHeros($head); //delHero($head,1);
delHero($head,21); //Delete a non-existent
showHeros($head);
echo'
$hero=new Hero(1,'Hu Hansan','Youbaihu'); Disadvantage analysis of one-way linked list: it cannot delete itself and needs to rely on auxiliary nodes. 
Doubly linked lists can delete themselves. At the same time, in binary trees and generalized tables, one node needs to be used to perform the application of two or more nodes!
Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：In PHP, why does </script> not generate syntax parsing errors_PHP TutorialNext article：In PHP, why does </script> not generate syntax parsing errors_PHP Tutorial