基本数据结构算法

  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. }
  75. //------------------------
  76. // PHP内置字符串函数实现
  77. //------------------------
  78. //字符串长度
  79. function strlen($str)
  80. {
  81. if ($str == '') return 0;
  82. $count = 0;
  83. while (1){
  84. if ($str[$count] != NULL){
  85. $count++;
  86. continue;
  87. }else{
  88. break;
  89. }
  90. }
  91. return $count;
  92. }
  93. //截取子串
  94. function substr($str, $start, $length=NULL)
  95. {
  96. if ($str=='' || $start>strlen($str)) return;
  97. if (($length!=NULL) && ($start>0) && ($length>strlen($str)-$start)) return;
  98. if (($length!=NULL) && ($start<0) && ($length>strlen($str)+$start)) return;
  99. if ($length == NULL) $length = (strlen($str) - $start);
  100. if ($start < 0){
  101. for ($i=(strlen($str)+$start); $i<(strlen($str)+$start+$length); $i++) {
  102. $substr .= $str[$i];
  103. }
  104. }
  105. if ($length > 0){
  106. for ($i=$start; $i<($start+$length); $i++) {
  107. $substr .= $str[$i];
  108. }
  109. }
  110. if ($length < 0){
  111. for ($i=$start; $i<(strlen($str)+$length); $i++) {
  112. $substr .= $str[$i];
  113. }
  114. }
  115. return $substr;
  116. }
  117. //字符串翻转
  118. function strrev($str)
  119. {
  120. if ($str == '') return 0;
  121. for ($i=(strlen($str)-1); $i>=0; $i--){
  122. $rev_str .= $str[$i];
  123. }
  124. return $rev_str;
  125. }
  126. //字符串比较
  127. function strcmp($s1, $s2)
  128. {
  129. if (strlen($s1) < strlen($s2)) return -1;
  130. if (strlen($s1) > strlen($s2)) return 1;
  131. for ($i=0; $i<strlen($s1); $i++){
  132. if ($s1[$i] == $s2[$i]){
  133. continue;
  134. }else{
  135. return false;
  136. }
  137. }
  138. return 0;
  139. }
  140. //查找字符串
  141. function strstr($str, $substr)
  142. {
  143. $m = strlen($str);
  144. $n = strlen($substr);
  145. if ($m < $n) return false;
  146. for ($i=0; $i<=($m-$n+1); $i++){
  147. $sub = substr($str, $i, $n);
  148. if (strcmp($sub, $substr) == 0) return $i;
  149. }
  150. return false;
  151. }
  152. //字符串替换
  153. function str_replace($substr, $newsubstr, $str)
  154. {
  155. $m = strlen($str);
  156. $n = strlen($substr);
  157. $x = strlen($newsubstr);
  158. if (strchr($str, $substr) == false) return false;
  159. for ($i=0; $i<=($m-$n+1); $i++){
  160. $i = strchr($str, $substr);
  161. $str = str_delete($str, $i, $n);
  162. $str = str_insert($str, $i, $newstr);
  163. }
  164. return $str;
  165. }
  166. //--------------------
  167. // 自实现字符串处理函数
  168. //--------------------
  169. //插入一段字符串
  170. function str_insert($str, $i, $substr)
  171. {
  172. for($j=0; $j<$i; $j++){
  173. $startstr .= $str[$j];
  174. }
  175. for ($j=$i; $j<strlen($str); $j++){
  176. $laststr .= $str[$j];
  177. }
  178. $str = ($startstr . $substr . $laststr);
  179. return $str;
  180. }
  181. //删除一段字符串
  182. function str_delete($str, $i, $j)
  183. {
  184. for ($c=0; $c<$i; $c++){
  185. $startstr .= $str[$c];
  186. }
  187. for ($c=($i+$j); $c<strlen($str); $c++){
  188. $laststr .= $str[$c];
  189. }
  190. $str = ($startstr . $laststr);
  191. return $str;
  192. }
  193. //复制字符串
  194. function strcpy($s1, $s2)
  195. {
  196. if (strlen($s1)==NULL || !isset($s2)) return;
  197. for ($i=0; $i<strlen($s1); $i++){
  198. $s2[] = $s1[$i];
  199. }
  200. return $s2;
  201. }
  202. //连接字符串
  203. function strcat($s1, $s2)
  204. {
  205. if (!isset($s1) || !isset($s2)) return;
  206. $newstr = $s1;
  207. for($i=0; $i<count($s); $i++){
  208. $newstr .= $st[$i];
  209. }
  210. return $newsstr;
  211. }
  212. //简单编码函数(与php_decode函数对应)
  213. function php_encode($str)
  214. {
  215. if ($str=='' && strlen($str)>128) return false;
  216. for($i=0; $i<strlen($str); $i++){
  217. $c = ord($str[$i]);
  218. if ($c>31 && $c<107) $c += 20;
  219. if ($c>106 && $c<127) $c -= 75;
  220. $word = chr($c);
  221. $s .= $word;
  222. }
  223. return $s;
  224. }
  225. //简单解码函数(与php_encode函数对应)
  226. function php_decode($str)
  227. {
  228. if ($str=='' && strlen($str)>128) return false;
  229. for($i=0; $i<strlen($str); $i++){
  230. $c = ord($word);
  231. if ($c>106 && $c<127) $c = $c-20;
  232. if ($c>31 && $c<107) $c = $c+75;
  233. $word = chr($c);
  234. $s .= $word;
  235. }
  236. return $s;
  237. }
  238. //简单加密函数(与php_decrypt函数对应)
  239. function php_encrypt($str)
  240. {
  241. $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
  242. $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';
  243. if (strlen($str) == 0) return false;
  244. for ($i=0; $i<strlen($str); $i++){
  245. for ($j=0; $j<strlen($encrypt_key); $j++){
  246. if ($str[$i] == $encrypt_key[$j]){
  247. $enstr .= $decrypt_key[$j];
  248. break;
  249. }
  250. }
  251. }
  252. return $enstr;
  253. }
  254. //简单解密函数(与php_encrypt函数对应)
  255. function php_decrypt($str)
  256. {
  257. $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
  258. $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';
  259. if (strlen($str) == 0) return false;
  260. for ($i=0; $i<strlen($str); $i++){
  261. for ($j=0; $j<strlen($decrypt_key); $j++){
  262. if ($str[$i] == $decrypt_key[$j]){
  263. $enstr .= $encrypt_key[$j];
  264. break;
  265. }
  266. }
  267. }
  268. return $enstr;
  269. }
  270. ?>