PHP实现各种经典算法详解

摘要：<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找（数组里查找某个元素） function bin_sch($array, $low, $high, ...

1. <?

2. //--------------------

3. // 基本数据结构算法

4. //--------------------

5. //二分查找（数组里查找某个元素）

6. function bin_sch($array, $low, $high, $k){

7. if ( $low <= $high){

8. $mid = intval(($low+$high)/2 );

9. if ($array[$mid] == $k){

10. return $mid;

11. }elseif ( $k < $array[$mid]){

12. return bin_sch($array, $low, $mid-1, $k);

13. }else{

14. return bin_sch($array, $mid+ 1, $high, $k);

15. }

16. }

17. return -1;

18. }

19. //顺序查找（数组里查找某个元素）

20. function seq_sch($array, $n, $k){

21. $array[$n] = $k;

22. for($i=0; $i<$n; $i++){

23. if( $array[$i]==$k){

24. break;

25. }

26. }

27. if ($i<$n){

28. return $i;

29. }else{

30. return -1;

31. }

32. }

33. //线性表的删除（数组中实现）

34. function delete_array_element($array , $i)

35. {

36. $len = count($array);

37. for ($j= $i; $j<$len; $j ++){

38. $array[$j] = $array [$j+1];

39. }

40. array_pop ($array);

41. return $array ;

42. }

43. //冒泡排序（数组排序）

44. function bubble_sort( $array)

45. {

46. $count = count( $array);

47. if ($count <= 0 ) return false;

48. for($i=0 ; $i<$count; $i ++){

49. for($j=$count-1 ; $j>$i; $j--){

50. if ($array[$j] < $array [$j-1]){

51. $tmp = $array[$j];

52. $array[$j] = $array[ $j-1];

53. $array [$j-1] = $tmp;

54. }

55. }

56. }

57. return $array;

58. }

59. //快速排序（数组排序）

60. function quick_sort($array ) {

61. if (count($array) <= 1) return $array;

62. $key = $array [0];

63. $left_arr = array();

64. $right_arr = array();

65. for ($i= 1; $i<count($array ); $i++){

66. if ($array[ $i] <= $key)

67. $left_arr [] = $array[$i];

68. else

69. $right_arr[] = $array[$i ];

70. }

71. $left_arr = quick_sort($left_arr );

72. $right_arr = quick_sort( $right_arr);

73. return array_merge($left_arr , array($key), $right_arr);

74. }

76. //------------------------

77. // PHP内置字符串函数实现

78. //------------------------

79. //字符串长度

80. function strlen ($str)

81. {

82. if ($str == "" ) return 0;

83. $count = 0;

84. while (1){

85. if ( $str[$count] != NULL){

86. $count++;

87. continue;

88. }else{

89. break;

90. }

91. }

92. return $count;

93. }

94. //截取子串

95. function substr($str, $start, $length=NULL)

96. {

97. if ($str== "" || $start>strlen($str )) return;

98. if (($length!=NULL) && ( $start>0) && ($length> strlen($str)-$start)) return;

99. if (( $length!=NULL) && ($start< 0) && ($length>strlen($str )+$start)) return;

100. if ($length == NULL) $length = (strlen($str ) - $start);

102. if ($start < 0){

103. for ($i=(strlen( $str)+$start); $i<(strlen ($str)+$start+$length ); $i++) {

104. $substr .= $str[$i];

105. }

106. }

107. if ($length > 0){

108. for ($i= $start; $i<($start+$length ); $i++) {

109. $substr .= $str[$i];

110. }

111. }

112. if ( $length < 0){

113. for ($i =$start; $i<(strlen( $str)+$length); $i++) {

114. $substr .= $str[$i ];

115. }

116. }

117. return $substr;

118. }

119. //字符串翻转

120. function strrev($str)

121. {

122. if ($str == "") return 0 ;

123. for ($i=(strlen($str)- 1); $i>=0; $i --){

124. $rev_str .= $str[$i ];

125. }

126. return $rev_str;

127. }

129. //字符串比较

130. function strcmp($s1, $s2)

131. {

132. if (strlen($s1) < strlen($s2)) return -1 ;

133. if (strlen($s1) > strlen( $s2)) return 1;

134. for ($i =0; $i<strlen($s1 ); $i++){

135. if ($s1[ $i] == $s2[$i]){

136. continue;

137. }else{

138. return false;

139. }

140. }

141. return 0;

142. }

144. //查找字符串

145. function strstr($str, $substr)

146. {

147. $m = strlen($str);

148. $n = strlen($substr );

149. if ($m < $n) return false ;

150. for ($i=0; $i <=($m-$n+1); $i ++){

151. $sub = substr( $str, $i, $n);

152. if ( strcmp($sub, $substr) == 0) return $i;

153. }

154. return false ;

155. }

156. //字符串替换

157. function str_replace($substr , $newsubstr, $str)

158. {

159. $m = strlen($str);

160. $n = strlen($substr );

161. $x = strlen($newsubstr );

162. if (strchr($str, $substr ) == false) return false;

163. for ( $i=0; $i<=($m- $n+1); $i++){

164. $i = strchr($str, $substr);

165. $str = str_delete ($str, $i, $n);

166. $str = str_insert($str, $i, $newstr);

167. }

168. return $str ;

169. }

171. //--------------------

172. // 自实现字符串处理函数

173. //--------------------

174. //插入一段字符串

175. function str_insert($str, $i , $substr)

176. {

177. for($j=0 ; $j<$i; $j ++){

178. $startstr .= $str[$j ];

179. }

180. for ($j=$i; $j <strlen($str); $j ++){

181. $laststr .= $str[$j ];

182. }

183. $str = ($startstr . $substr . $laststr);

184. return $str ;

185. }

186. //删除一段字符串

187. function str_delete($str , $i, $j)

188. {

189. for ( $c=0; $c<$i; $c++){

190. $startstr .= $str [$c];

191. }

192. for ($c=( $i+$j); $c<strlen ($str); $c++){

193. $laststr .= $str[$c];

194. }

195. $str = ($startstr . $laststr );

196. return $str;

197. }

198. //复制字符串

199. function strcpy($s1, $s2 )

200. {

201. if (strlen($s1)==NULL || !isset( $s2)) return;

202. for ($i=0 ; $i<strlen($s1); $i++){

203. $s2[] = $s1 [$i];

204. }

205. return $s2;

206. }

207. //连接字符串

208. function strcat($s1 , $s2)

209. {

210. if (!isset($s1) || !isset( $s2)) return;

211. $newstr = $s1 ;

212. for($i=0; $i <count($s); $i ++){

213. $newstr .= $st[$i ];

214. }

215. return $newsstr;

216. }

217. //简单编码函数（与php_decode函数对应）

218. function php_encode($str)

219. {

220. if ( $str=="" && strlen( $str)>128) return false;

221. for( $i=0; $i<strlen ($str); $i++){

222. $c = ord($str[$i ]);

223. if ($c>31 && $c <107) $c += 20 ;

224. if ($c>106 && $c <127) $c -= 75 ;

225. $word = chr($c );

226. $s .= $word;

227. }

228. return $s;

229. }

230. //简单解码函数（与php_encode函数对应）

231. function php_decode($str)

232. {

233. if ( $str=="" && strlen($str )>128) return false;

234. for( $i=0; $i<strlen ($str); $i++){

235. $c = ord($word);

236. if ( $c>106 && $c<127 ) $c = $c-20;

237. if ($c>31 && $c< 107) $c = $c+75 ;

238. $word = chr( $c);

239. $s .= $word ;

240. }

241. return $s;

242. }

243. //简单加密函数（与php_decrypt函数对应）

244. function php_encrypt($str)

245. {

246. $encrypt_key = "abcdefghijklmnopqrstuvwxyz1234567890";

247. $decrypt_key = "ngzqtcobmuhelkpdawxfyivrsj2468021359";

248. if ( strlen($str) == 0) return false;

249. for ($i=0; $i<strlen($str); $i ++){

250. for ($j=0; $j <strlen($encrypt_key); $j ++){

251. if ($str[$i] == $encrypt_key [$j]){

252. $enstr .= $decrypt_key[$j];

253. break;

254. }

255. }

256. }

257. return $enstr;

258. }

259. //简单解密函数（与php_encrypt函数对应）

260. function php_decrypt($str)

261. {

262. $encrypt_key = "abcdefghijklmnopqrstuvwxyz1234567890";

263. $decrypt_key = "ngzqtcobmuhelkpdawxfyivrsj2468021359";

264. if ( strlen($str) == 0) return false;

265. for ($i=0; $i<strlen($str); $i ++){

266. for ($j=0; $j <strlen($decrypt_key); $j ++){

267. if ($str[$i] == $decrypt_key [$j]){

268. $enstr .= $encrypt_key[$j];

269. break;

270. }

271. }

272. }

273. return $enstr;

274. }

275. ?>