基本数据结构算法

1. <?  
2. //--------------------  
3. // 基本数据结构算法 
4. //--------------------  
5.  
6. //二分查找（数组里查找某个元素）  
7. function bin_sch($array, $low, $high, $k){   
8.     if ($low <= $high){   
9.         $mid = intval(($low+$high)/2);   
10.         if ($array[$mid] == $k){   
11.             return $mid;   
12.         }elseif ($k < $array[$mid]){   
13.             return bin_sch($array, $low, $mid-1, $k);   
14.         }else{   
15.             return bin_sch($array, $mid+1, $high, $k);   
16.         }   
17.     }   
18.     return -1;   
19. }   
20.  
21. //顺序查找（数组里查找某个元素）  
22. function seq_sch($array, $n, $k){   
23.     $array[$n] = $k;   
24.     for($i=0; $i<$n; $i++){   
25.         if($array[$i]==$k){   
26.             break;   
27.         }   
28.     }   
29.     if ($i<$n){   
30.         return $i;   
31.     }else{   
32.         return -1;   
33.     }   
34. }   
35.  
36. //线性表的删除（数组中实现）  
37. function delete_array_element($array, $i)  
38. {  
39.         $len = count($array);   
40.         for ($j=$i; $j<$len; $j++){  
41.                 $array[$j] = $array[$j+1];  
42.         }  
43.         array_pop($array);  
44.         return $array;  
45. }  
46.  
47. //冒泡排序（数组排序）  
48. function bubble_sort($array)  
49. {  
50.         $count = count($array);  
51.         if ($count <= 0) return false;  
52.  
53.         for($i=0; $i<$count; $i++){  
54.                 for($j=$count-1; $j>$i; $j--){  
55.                         if ($array[$j] < $array[$j-1]){  
56.                                 $tmp = $array[$j];  
57.                                 $array[$j] = $array[$j-1];  
58.                                 $array[$j-1] = $tmp;  
59.                         }  
60.                 }  
61.         }  
62.         return $array;  
63. }  
64.  
65. //快速排序（数组排序）  
66. function quick_sort($array) {  
67.         if (count($array) <= 1) return $array;  
68.  
69.         $key = $array[0];  
70.         $left_arr = array();  
71.         $right_arr = array();  
72.  
73.         for ($i=1; $i<count($array); $i++){  
74.                 if ($array[$i] <= $key)  
75.                         $left_arr[] = $array[$i];  
76.                 else  
77.                         $right_arr[] = $array[$i];  
78.         }  
79.  
80.         $left_arr = quick_sort($left_arr);  
81.         $right_arr = quick_sort($right_arr);  
82.  
83.         return array_merge($left_arr, array($key), $right_arr);  
84. }  
85.  
86.  
87.  
88. //------------------------  
89. // PHP内置字符串函数实现  
90. //------------------------  
91.  
92. //字符串长度  
93. function strlen($str)  
94. {  
95.         if ($str == '') return 0;  
96.  
97.         $count = 0;  
98.         while (1){  
99.                 if ($str[$count] != NULL){  
100.                         $count++;  
101.                         continue;  
102.                 }else{  
103.                         break;  
104.                 }  
105.         }  
106.         return $count;  
107. }  
108.  
109. //截取子串  
110. function substr($str, $start, $length=NULL)  
111. {  
112.         if ($str=='' || $start>strlen($str)) return;  
113.         if (($length!=NULL) && ($start>0) && ($length>strlen($str)-$start)) return;  
114.         if (($length!=NULL) && ($start<0) && ($length>strlen($str)+$start)) return;  
115.         if ($length == NULL) $length = (strlen($str) - $start);  
116.           
117.         if ($start < 0){  
118.                 for ($i=(strlen($str)+$start); $i<(strlen($str)+$start+$length); $i++) {  
119.                         $substr .= $str[$i];  
120.                 }  
121.         }  
122.  
123.         if ($length > 0){  
124.                 for ($i=$start; $i<($start+$length); $i++) {  
125.                         $substr .= $str[$i];  
126.                 }  
127.         }  
128.  
129.         if ($length < 0){  
130.                 for ($i=$start; $i<(strlen($str)+$length); $i++) {  
131.                         $substr .= $str[$i];  
132.                 }  
133.         }  
134.         return $substr;  
135. }  
136.  
137. //字符串翻转  
138. function strrev($str)  
139. {  
140.         if ($str == '') return 0;  
141.         for ($i=(strlen($str)-1); $i>=0; $i--){  
142.                 $rev_str .= $str[$i];  
143.         }  
144.         return $rev_str;  
145. }  
146.  
147.  
148. //字符串比较  
149. function strcmp($s1, $s2)  
150. {  
151.         if (strlen($s1) < strlen($s2)) return -1;  
152.         if (strlen($s1) > strlen($s2)) return 1;  
153.  
154.         for ($i=0; $i<strlen($s1); $i++){  
155.                 if ($s1[$i] == $s2[$i]){  
156.                         continue;  
157.                 }else{  
158.                         return false;  
159.                 }  
160.         }  
161.         return 0;  
162. }  
163.  
164.  
165. //查找字符串  
166. function strstr($str, $substr)  
167. {  
168.         $m = strlen($str);  
169.         $n = strlen($substr);  
170.         if ($m < $n) return false;  
171.  
172.         for ($i=0; $i<=($m-$n+1); $i++){  
173.                 $sub = substr($str, $i, $n);  
174.                 if (strcmp($sub, $substr) == 0)  return $i;  
175.         }  
176.         return false;  
177. }  
178.  
179. //字符串替换  
180. function str_replace($substr, $newsubstr, $str)  
181. {  
182.         $m = strlen($str);  
183.         $n = strlen($substr);  
184.         $x = strlen($newsubstr);  
185.         if (strchr($str, $substr) == false) return false;  
186.  
187.         for ($i=0; $i<=($m-$n+1); $i++){  
188.                 $i = strchr($str, $substr);  
189.                 $str = str_delete($str, $i, $n);  
190.                 $str = str_insert($str, $i, $newstr);  
191.         }  
192.         return $str;  
193. }  
194.  
195.  
196.  
197. //--------------------  
198. // 自实现字符串处理函数 
199. //--------------------  
200.  
201. //插入一段字符串  
202. function str_insert($str, $i, $substr)  
203. {  
204.         for($j=0; $j<$i; $j++){  
205.                 $startstr .= $str[$j];  
206.         }  
207.         for ($j=$i; $j<strlen($str); $j++){  
208.                 $laststr .= $str[$j];  
209.         }  
210.         $str = ($startstr . $substr . $laststr);  
211.  
212.         return $str;  
213. }  
214.  
215. //删除一段字符串  
216. function str_delete($str, $i, $j)  
217. {  
218.         for ($c=0; $c<$i; $c++){  
219.                 $startstr .= $str[$c];  
220.         }  
221.         for ($c=($i+$j); $c<strlen($str); $c++){  
222.                 $laststr .= $str[$c];  
223.         }  
224.         $str = ($startstr . $laststr);  
225.  
226.         return $str;  
227. }  
228.  
229. //复制字符串  
230. function strcpy($s1, $s2)  
231. {  
232.         if (strlen($s1)==NULL || !isset($s2)) return;  
233.  
234.         for ($i=0; $i<strlen($s1); $i++){  
235.                 $s2[] = $s1[$i];  
236.         }  
237.         return $s2;  
238. }  
239.  
240. //连接字符串  
241. function strcat($s1, $s2)  
242. {  
243.         if (!isset($s1) || !isset($s2)) return;  
244.         $newstr = $s1;  
245.         for($i=0; $i<count($s); $i++){  
246.                 $newstr .= $st[$i];  
247.         }  
248.         return $newsstr;  
249. }  
250.  
251. //简单编码函数（与php_decode函数对应）  
252. function php_encode($str)  
253. {  
254.         if ($str=='' && strlen($str)>128) return false;  
255.  
256.         for($i=0; $i<strlen($str); $i++){  
257.                 $c = ord($str[$i]);  
258.                 if ($c>31 && $c<107) $c += 20;  
259.                 if ($c>106 && $c<127) $c -= 75;  
260.                 $word = chr($c);  
261.                 $s .= $word;  
262.         }   
263.  
264.         return $s;   
265. }  
266.  
267. //简单解码函数（与php_encode函数对应）  
268. function php_decode($str)  
269. {  
270.         if ($str=='' && strlen($str)>128) return false;  
271.  
272.         for($i=0; $i<strlen($str); $i++){  
273.                 $c = ord($word);  
274.                 if ($c>106 && $c<127) $c = $c-20;  
275.                 if ($c>31 && $c<107) $c = $c+75;  
276.                 $word = chr($c);  
277.                 $s .= $word;  
278.         }   
279.  
280.         return $s;   
281. }  
282.  
283. //简单加密函数（与php_decrypt函数对应）  
284. function php_encrypt($str)  
285. {  
286.         $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';  
287.         $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';  
288.  
289.         if (strlen($str) == 0) return false;  
290.  
291.         for ($i=0; $i<strlen($str); $i++){  
292.                 for ($j=0; $j<strlen($encrypt_key); $j++){  
293.                         if ($str[$i] == $encrypt_key[$j]){  
294.                                 $enstr .= $decrypt_key[$j];  
295.                                 break;  
296.                         }  
297.                 }  
298.         }  
299.  
300.         return $enstr;  
301. }  
302.  
303. //简单解密函数（与php_encrypt函数对应）  
304. function php_decrypt($str)  
305. {  
306.         $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';  
307.         $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';  
308.         if (strlen($str) == 0) return false;  
309.         for ($i=0; $i<strlen($str); $i++){  
310.                 for ($j=0; $j<strlen($decrypt_key); $j++){  
311.                         if ($str[$i] == $decrypt_key[$j]){  
312.                                 $enstr .= $encrypt_key[$j];  
313.                                 break;  
314.                         }  
315.                 }  
316.         }  
317.         return $enstr;  
318. }  
319. ?>