PHP常用算法和数据结构示例(必看篇)

1. /** 
2.  * Created by PhpStorm. 
3.  * User: qishou 
4.  * Date: 15-8-2 
5.  * Time: 上午9:12 
6.  */ 
7. header("content-type:text/html;charset=utf-8"); 
8. $arr=array(3,5,8,4,9,6,1,7,2); 
9. echoimplode(" ",$arr)."<br>"; 
10. //--------------------------------------- 
11. //       常用排序算法 
12. //--------------------------------------- 
13. //冒泡排序 
14. functionBubbleSort($arr){ 
15.   $length=count($arr); 
16.   if($length<=1){ 
17.     return$arr; 
18.   } 
19.   for($i=0;$i<$length;$i++){ 
20.     for($j=$length-1;$j>$i;$j--){ 
21.       if($arr[$j]<$arr[$j-1]){ 
22.         $tmp=$arr[$j]; 
23.         $arr[$j] =$arr[$j-1]; 
24.         $arr[$j-1] =$tmp; 
25.       } 
26.     } 
27.   } 
28.   return$arr; 
29. } 
30. echo'冒泡排序：' 
31. echoimplode(' ',BubbleSort($arr))."<br>"; 
32.   
33. //快速排序 
34. functionQSort($arr){ 
35.   $length=count($arr); 
36.   if($length<=1){ 
37.     return$arr; 
38.   } 
39.   $pivot=$arr[0];//枢轴 
40.   $left_arr=array(); 
41.   $right_arr=array(); 
42.   for($i=1;$i<$length;$i++){//注意$i从1开始0是枢轴 
43.     if($arr[$i]<=$pivot){ 
44.       $left_arr[] =$arr[$i]; 
45.     }else{ 
46.       $right_arr[] =$arr[$i]; 
47.     } 
48.   } 
49.   $left_arr= QSort($left_arr);//递归排序左半部分 
50.   $right_arr= QSort($right_arr);//递归排序右半部份 
51.   returnarray_merge($left_arr,array($pivot),$right_arr);//合并左半部分、枢轴、右半部分 
52. } 
53. echo"快速排序："; 
54. echoimplode(' ',QSort($arr))."<br>"; 
55.   
56. //选择排序(不稳定) 
57. functionSelectSort($arr){ 
58.   $length=count($arr); 
59.   if($length<=1){ 
60.     return$arr; 
61.   } //Vevb.com 
62.   for($i=0;$i<$length;$i++){ 
63.     $min=$i; 
64.     for($j=$i+1;$j<$length;$j++){ 
65.       if($arr[$j]<$arr[$min]){ 
66.         $min=$j; 
67.       } 
68.     } 
69.     if($i!=$min){ 
70.       $tmp=$arr[$i]; 
71.       $arr[$i] =$arr[$min]; 
72.       $arr[$min] =$tmp; 
73.     } 
74.   } 
75.   return$arr; 
76. } 
77. echo"选择排序："; 
78. echoimplode(' ',SelectSort($arr))."<br>"; 
79.   
80. //插入排序 
81. functionInsertSort($arr){ 
82.   $length=count($arr); 
83.   if($length<=1){ 
84.     return$arr; 
85.   } 
86.   for($i=1;$i<$length;$i++){ 
87.     $x=$arr[$i]; 
88.     $j=$i-1; 
89.     while($x<$arr[$j] j="">=0){<!--$arr[$j]--> 
90.       $arr[$j+1] =$arr[$j]; 
91.       $j--; 
92.     } 
93.     $arr[$j+1] =$x; 
94.   } 
95.   return$arr; 
96. } 
97. echo'插入排序：' 
98. echoimplode(' ',InsertSort($arr))."<br>"; 
99. //--------------------------------------- 
100. //       常用查找算法 
101. //--------------------------------------- 
102. //二分查找 
103. functionbinary_search($arr,$low,$high,$key){ 
104.   while($low<=$high){ 
105.     $mid=intval(($low+$high)/2); 
106.     if($key==$arr[$mid]){ 
107.       return$mid+1; 
108.     }elseif($key<$arr[$mid]){ 
109.       $high=$mid-1; 
110.     }elseif($key>$arr[$mid]){ 
111.       $low=$mid+1; 
112.     } 
113.   } 
114.   return-1; 
115. } 
116. $key= 6; 
117. echo"二分查找{$key}的位置："; 
118. echobinary_search(QSort($arr),0,8,$key); 
119.   
120. //顺序查找 
121. functionSqSearch($arr,$key){ 
122.   $length=count($arr); 
123.   for($i=0;$i<$length;$i++){ 
124.     if($key==$arr[$i]){ 
125.       return$i+1; 
126.     } 
127.   } 
128.   return-1; 
129. } 
130. $key= 8; 
131. echo"<br>顺序常规查找{$key}的位置："; 
132. echoSqSearch($arr,$key); 
133. //--------------------------------------- 
134. //       常用数据结构 
135. //--------------------------------------- 
136. //线性表的删除(数组实现) 
137. functiondelete_array_element($arr,$pos){ 
138.   $length=count($arr); 
139.   if($pos<1 pos="">$length){<!--1--> 
140.     return"删除位置出错!"; 
141.   } 
142.   for($i=$pos-1;$i<$length-1;$i++){ 
143.     $arr[$i] =$arr[$i+1]; 
144.   } 
145.   array_pop($arr); 
146.   return$arr; 
147. } 
148. $pos= 3; 
149. echo"<br>除第{$pos}位置上的元素后："; 
150. echoimplode(' ',delete_array_element($arr,$pos))."<br>"; 
151.   
152. /** 
153.  * Class Node 
154.  * PHP模拟链表的基本操作 
155.  */ 
156. classNode{ 
157.   public$data='' 
158.   public$next= null; 
159. } 
160. //初始化 
161. functioninit($linkList){ 
162.   $linkList->data = 0;//用来记录链表长度 
163.   $linkList->next = null; 
164. } 
165. //头插法创建链表 
166. functioncreateHead(&$linkList,$length){ 
167.   for($i=0;$i<$length;$i++){ 
168.     $newNode=newNode(); 
169.     $newNode->data =$i; 
170.     $newNode->next =$linkList->next;//因为PHP中对象本身就是引用所以不用再可用“&” 
171.     $linkList->next =$newNode; 
172.     $linkList->data++; 
173.   } 
174. } 
175. //尾插法创建链表 
176. functioncreateTail(&$linkList,$length){ 
177.   $r=$linkList; 
178.   for($i=0;$i<$length;$i++){ 
179.     $newNode=newNode(); 
180.     $newNode->data =$i; 
181.     $newNode->next =$r->next; 
182.     $r->next =$newNode; 
183.     $r=$newNode; 
184.     $linkList->data++; 
185.   } 
186. } 
187. //在指定位置插入指定元素 
188. functioninsert($linkList,$pos,$elem){ 
189.   if($pos<1 pos="">$linkList->data+1){<!--1--> 
190.     echo"插入位置错误！"; 
191.   } 
192.   $p=$linkList; 
193.   for($i=1;$i<$pos;$i++){ 
194.     $p=$p->next; 
195.   } 
196.   $newNode=newNode(); 
197.   $newNode->data =$elem; 
198.   $newNode->next =$p->next; 
199.   $p->next =$newNode; 
200. } 
201. //删除指定位置的元素 
202. functiondelete($linkList,$pos){ 
203.   if($pos<1 pos="">$linkList->data+1){<!--1--> 
204.     echo"位置不存在！"; 
205.   } 
206.   $p=$linkList; 
207.   for($i=1;$i<$pos;$i++){ 
208.     $p=$p->next; 
209.   } 
210.   $q=$p->next; 
211.   $p->next =$q->next; 
212.   unset($q); 
213.   $linkList->data--; 
214. } 
215. //输出链表数据 
216. functionshow($linkList){ 
217.   $p=$linkList->next; 
218.   while($p!=null){ 
219.     echo$p->data." "; 
220.     $p=$p->next; 
221.   } 
222.   echo'<br>' 
223. } 
224.   
225. $linkList=newNode(); 
226. init($linkList);//初始化 
227. createTail($linkList,10);//尾插法创建链表 
228. show($linkList);//打印出链表 
229. insert($linkList,3,'a');//插入 
230. show($linkList); 
231. delete($linkList,3);//删除 
232. show($linkList); 
233.   
234. /** 
235.  * Class Stack 
236.  * 用PHP模拟顺序栈的基本操作 
237.  */ 
238. classStack{ 
239.   //用默认值直接初始化栈了，也可用构造方法初始化栈 
240.   private$top= -1; 
241.   private$maxSize= 5; 
242.   private$stack=array(); 
243.   
244.   //入栈 
245.   publicfunctionpush($elem){ 
246.     if($this->top >=$this->maxSize-1){ 
247.       echo"栈已满！<br>"; 
248.       return; 
249.     } 
250.     $this->top++; 
251.     $this->stack[$this->top] =$elem; 
252.   } 
253.   //出栈 
254.   publicfunctionpop(){ 
255.     if($this->top == -1){ 
256.       echo"栈是空的！"; 
257.       return; 
258.     } 
259.     $elem=$this->stack[$this->top]; 
260.     unset($this->stack[$this->top]); 
261.     $this->top--; 
262.     return$elem; 
263.   } 
264.   //打印栈 
265.   publicfunctionshow(){ 
266.     for($i=$this->top;$i>=0;$i--){ 
267.       echo$this->stack[$i]." "; 
268.     } 
269.     echo"<br>"; 
270.   } 
271. } 
272.   
273. $stack=newStack(); 
274. $stack->push(3); 
275. $stack->push(5); 
276. $stack->push(8); 
277. $stack->push(7); 
278. $stack->push(9); 
279. $stack->push(2); 
280. $stack->show(); 
281. $stack->pop(); 
282. $stack->pop(); 
283. $stack->pop(); 
284. $stack->show(); 
285.   
286. /** 
287.  * Class Deque 
288.  * 使用PHP实现双向队列 
289.  */ 
290. classDeque{ 
291.   private$queue=array(); 
292.   publicfunctionaddFirst($item){//头入队 
293.     array_unshift($this->queue,$item); 
294.   } 
295.   publicfunctionaddLast($item){//尾入队 
296.     array_push($this->queue,$item); 
297.   } 
298.   publicfunctionremoveFirst(){//头出队 
299.     array_shift($this->queue); 
300.   } 
301.   publicfunctionremoveLast(){//尾出队 
302.     array_pop($this->queue); 
303.   } 
304.   publicfunctionshow(){//打印 
305.     <a href="/tags.php/foreach/" target="_blank">foreach</a>($this->queueas$item){ 
306.       echo$item." "; 
307.     } 
308.     echo"<br>"; 
309.   } 
310. } 
311. $deque=newDeque(); 
312. $deque->addFirst(2); 
313. $deque->addLast(3); 
314. $deque->addLast(4); 
315. $deque->addFirst(5); 
316. $deque->show(); 
317.   
318. //PHP解决约瑟夫环问题 
319. //方法一 
320. functionjoseph_ring($n,$m){ 
321.   $arr= range(1,$n); 
322.   $i= 0; 
323.   while(count($arr)>1){ 
324.     $i=$i+1; 
325.     $head=array_shift($arr); 
326.     if($i%$m!= 0){//如果不是则重新压入数组 
327.       array_push($arr,$head); 
328.     } 
329.   } 
330.   return$arr[0]; 
331. } 
332. //方法二 
333. functionjoseph_ring2($n,$m){ 
334.   $r= 0; 
335.   for($i=2;$i<=$n;$i++){ 
336.     $r= ($r+$m)%$i; 
337.   } 
338.   return$r+ 1; 
339. } 
340. echo"<br>".joseph_ring(60,5)."<br>"; 
341. echo"<br>".joseph_ring2(60,5)."<br>";