这篇文章主要介绍了PHP实现链表的定义与反转功能,结合实例形式分析了PHP链表的基本定义、添加、移除、遍历以及两种反转操作相关实现技巧,需要的朋友可以参考下。

本文实例讲述了PHP实现链表的定义与反转功能，分享给大家供大家参考，具体如下：

PHP定义链表及添加、移除、遍历等操作：

1. <?php 
2. class Node 
3. { 
4.   private $Data;//节点数据 
5.   private $Next;//下一节点 
6.    
7.   public function setData($value){ 
8.     $this->Data=$value; 
9.   } 
10.    
11.   public function setNext($value){ 
12.      $this->Next=$value; 
13.   }   
14.    
15.   public function getData(){ 
16.     return $this->Data; 
17.   } 
18.    
19.   public function getNext(){ 
20.     return $this->Next; 
21.   } 
22.    
23.   public function __construct($data,$next){ 
24.     $this->setData($data); 
25.     $this->setNext($next); 
26.   } 
27. } 
28. class LinkList 
29. { 
30.   private $header;//头节点 
31.   private $size;//长度 
32.   public function getSize() 
33.  { 
34.     $i=0; 
35.     $node=$this->header; 
36.     while($node->getNext()!=null) 
37.     {   
38.   $i++; 
39.       $node=$node->getNext(); 
40.     } 
41.     return $i; 
42.   } 
43.    
44.   public function setHeader($value){ 
45.     $this->header=$value; 
46.   } 
47.    
48.   public function getHeader(){ 
49.     return $this->header; 
50.   } 
51.    
52.   public function __construct(){ 
53.     header("content-type:text/html; charset=utf-8"); 
54.     $this->setHeader(new Node(null,null)); 
55.   } 
56.   /** 
57.   *@author MzXy 
58.   *@param $data--要添加节点的数据 
59.   *  
60.   */ 
61.   public function add($data) 
62.   { 
63.     $node=$this->header; 
64.     while($node->getNext()!=null) 
65.     { 
66.       $node=$node->getNext(); 
67.     } 
68.     $node->setNext(new Node($data,null)); 
69.   } 
70.    /** 
71.   *@author MzXy 
72.   *@param $data--要移除节点的数据 
73.   *  
74.   */ 
75.   public function removeAt($data) 
76.   { 
77.     $node=$this->header; 
78.     while($node->getData()!=$data) 
79.     { 
80.       $node=$node->getNext(); 
81.     } 
82.     $node->setNext($node->getNext()); 
83.     $node->setData($node->getNext()->getData()); 
84.   } 
85.    /** 
86.   *@author MzXy 
87.   *@param 遍历 
88.   *  
89.   */ 
90.   public function get() 
91.   { 
92.     $node=$this->header; 
93.     if($node->getNext()==null){ 
94.       print("数据集为空!"); 
95.       return; 
96.     } 
97.     while($node->getNext()!=null) 
98.     { 
99.       print('['.$node->getNext()->getData().'] -> '); 
100.       if($node->getNext()->getNext()==null){break;} 
101.       $node=$node->getNext(); 
102.     } 
103.   } 
104.    /** 
105.   *@author MzXy 
106.   *@param $data--要访问的节点的数据 
107.   * @param 此方法只是演示不具有实际意义 
108.   *  
109.   */ 
110.   public function getAt($data) 
111.   { 
112.     $node=$this->header->getNext(); 
113.   if($node->getNext()==null){ 
114.       print("数据集为空!"); 
115.       return; 
116.     } 
117.     while($node->getData()!=$data) 
118.     { 
119.       if($node->getNext()==null){break;} 
120.       $node=$node->getNext(); 
121.     } 
122.     return $node->getData();     
123.   } 
124.    /** 
125.   *@author MzXy 
126.   *@param $value--需要更新的节点的原数据 --$initial---更新后的数据 
127.   *  
128.   */ 
129.   public function update($initial,$value) 
130.   { 
131.      $node=$this->header->getNext(); 
132.  if($node->getNext()==null){ 
133.      print("数据集为空!"); 
134.       return; 
135.     } 
136.     while($node->getData()!=$data) 
137.     { 
138.       if($node->getNext()==null){break;} 
139.       $node=$node->getNext(); 
140.     } 
141.  $node->setData($initial);    
142.   } 
143. } 
144. $lists = new LinkList(); 
145. $lists -> add(1); 
146. $lists -> add(2); 
147. $lists -> get(); 
148. echo '<pre>'; 
149. print_r($lists); 
150. echo '</pre>'; 
151. ?> 

反转链表操作：

1. 常用的方法：左右交替，下一个结点保存，上一个结点替换该结点的下个结点，实现替换。

代码：

1. function ReverseList($pHead) 
2. { 
3.   // write code here 
4.   if($pHead == null || $pHead->next == null){ 
5.     return $pHead; 
6.   } 
7.   $p = $pHead; 
8.   $q = $pHead->next; 
9.   $pHead->next = null;//$pHead 变为尾指针 
10.   while($q){ 
11.     $r = $q->next; 
12.     $q->next = $p; 
13.     $p = $q; 
14.     $q = $r; 
15.   } 
16.   return $p; 
17. } 

2. 使用递归方法。三个结点，头结点，首节点，第二个结点，把首节点后面的所有结点当成第二个结点，依次循环下去，由于要满足 $pHead != null || $pHead->next != null ；所以不会出现遍历不完的情况。

1. function ReverseList($pHead) 
2. { 
3.   // write code here 
4.   if($pHead == null || $pHead->next == null){ 
5.     return $pHead; 
6.   } 
7.   $res = ReverseList($pHead->next); 
8.   $pHead->next->next = $pHead; 
9.   $pHead->next = null; 
10.   return $res; 
11. }

Tags: PHP链表定义 PHP链表反转

分享到：