//--------------------
// 基本数据结构算法
//--------------------
//二分查找（数组里查找某个元素）
1 function bin_sch($array, $low, $high, $k){ 2 if ( $low <= $high){ 3 $mid = intval(($low+$high)/2 ); 4 if ($array[$mid] == $k){ 5 return $mid; 6 } elseif ( $k < $array[$mid]){ 7 return bin_sch($array, $low, $mid-1, $k); 8 } else { 9 return bin_sch($array, $mid+ 1, $high, $k); 10 } 11 } 12 return -1; 13 }
//顺序查找（数组里查找某个元素）
1 function seq_sch($array, $n, $k){ 2 $array[$n] = $k; 3 for ($i=0; $i<$n; $i++){ 4 if( $array[$i] == $k){ 5 break; 6 } 7 } 8 if ($i<$n){ 9 return $i; 10 } else { 11 return -1; 12 } 13 }
//线性表的删除（数组中实现）
1 function delete_array_element($array , $i) 2 { 3 $len = count($array); 4 for ($j= $i; $j<$len; $j ++){ 5 $array[$j] = $array [$j+1]; 6 } 7 array_pop ($array); 8 return $array ; 9 }
//冒泡排序（数组排序）
思路：每次循环排列出一个最大的数
（一）
1 function bubble_sort( $array) 2 { 3 $count = count( $array); 4 if ($count <= 0 ) return false; 5 for($i=0 ; $i<$count; $i ++){ 6 for($j=$count-1 ; $j>$i; $j--){ 7 if ($array[$j] < $array [$j-1]){ 8 $tmp = $array[$j]; 9 $array[$j] = $array[ $j-1]; 10 $array [$j-1] = $tmp; 11 } 12 } 13 } 14 return $array; 15 }
（二）
//快速排序（数组排序）
思路：先对数组进行分割， 把大的元素数值放到一个临时数组里，把小的元素数值放到另一个临时数组里（这个分割的点可以是数组中的任意一个元素值，一般用第一个元素，即$array[0]），然后继续把这两个临时数组重复上面拆分，最后把小的数组元素和大的数组元素合并起来。这里用到了递归的思想。
（一）
1 function quick_sort($array ) { 2 if (count($array) <= 1) return $array; 3 $key = $array [0]; 4 $left_arr = array(); 5 $right_arr = array(); 6 for ($i= 1; $i<count($array ); $i++){ 7 if ($array[ $i] <= $key) 8 $left_arr [] = $array[$i]; 9 else 10 $right_arr[] = $array[$i ]; 11 } 12 $left_arr = quick_sort($left_arr ); 13 $right_arr = quick_sort( $right_arr); 14 return array_merge($left_arr , array($key), $right_arr); 15 }
（二）
//选择排序
思路：每一趟在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录，其中最简单的是简单选择排序，其过程如下：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并各第i个记录交换之。
//插入排序
思路：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间
//------------------------
// PHP内置字符串函数实现
//------------------------
//字符串长度
1 function strlen ($str) 2 { 3 if ($str == '' ) return 0; 4 $count = 0; 5 while (1){ 6 if ( $str[$count] != NULL){ 7 $count++; 8 continue; 9 }else{ 10 break; 11 } 12 } 13 return $count; 14 }
//截取子串
1 function substr($str, $start, $length=NULL) 2 { 3 if ($str== '' || $start>strlen($str )) return; 4 if (($length!=NULL) && ( $start>0) && ($length> strlen($str)-$start)) return; 5 if (( $length!=NULL) && ($start< 0) && ($length>strlen($str )+$start)) return; 6 if ($length == NULL) $length = (strlen($str ) - $start); 7 8 if ($start < 0){ 9 for ($i=(strlen( $str)+$start); $i<(strlen ($str)+$start+$length ); $i++) { 10 $substr .= $str[$i]; 11 } 12 } 13 if ($length > 0){ 14 for ($i= $start; $i<($start+$length ); $i++) { 15 $substr .= $str[$i]; 16 } 17 } 18 if ( $length < 0){ 19 for ($i =$start; $i<(strlen( $str)+$length); $i++) { 20 $substr .= $str[$i ]; 21 } 22 } 23 return $substr; 24 }
//字符串翻转
function strrev($str) { if ($str == '') return 0 ; for ($i=(strlen($str)- 1); $i>=0; $i --){ $rev_str .= $str[$i ]; } return $rev_str; }
//字符串比较
1 function strcmp($s1, $s2) 2 { 3 if (strlen($s1) < strlen($s2)) return -1 ; 4 if (strlen($s1) > strlen( $s2)) return 1; 5 for ($i =0; $i<strlen($s1 ); $i++){ 6 if ($s1[ $i] == $s2[$i]){ 7 continue; 8 }else{ 9 return false; 10 } 11 } 12 return 0; 13 }
//查找字符串
1 function strstr($str, $substr) 2 { 3 $m = strlen($str); 4 $n = strlen($substr ); 5 if ($m < $n) return false ; 6 for ($i=0; $i <=($m-$n+1); $i ++){ 7 $sub = substr( $str, $i, $n); 8 if ( strcmp($sub, $substr) == 0) return $i; 9 } 10 return false ; 11 }
//字符串替换
1 function str_replace($substr , $newsubstr, $str) 2 { 3 $m = strlen($str); 4 $n = strlen($substr ); 5 $x = strlen($newsubstr ); 6 if (strchr($str, $substr ) == false) return false; 7 for ( $i=0; $i<=($m- $n+1); $i++){ 8 $i = strchr($str, $substr); 9 $str = str_delete ($str, $i, $n); 10 $str = str_insert($str, $i, $newstr); 11 } 12 return $str ; 13 }
//--------------------
// 自实现字符串处理函数
//--------------------
//插入一段字符串
1 function str_insert($str, $i , $substr) 2 { 3 for($j=0 ; $j<$i; $j ++){ 4 $startstr .= $str[$j ]; 5 } 6 for ($j=$i; $j <strlen($str); $j ++){ 7 $laststr .= $str[$j ]; 8 } 9 $str = ($startstr . $substr . $laststr); 10 return $str ; 11 }
//删除一段字符串
1 function str_delete($str , $i, $j) 2 { 3 for ( $c=0; $c<$i; $c++){ 4 $startstr .= $str [$c]; 5 } 6 for ($c=( $i+$j); $c<strlen ($str); $c++){ 7 $laststr .= $str[$c]; 8 } 9 $str = ($startstr . $laststr ); 10 return $str; 11 }
//复制字符串
1 function strcpy($s1, $s2 ) 2 { 3 if (strlen($s1)==NULL || !isset( $s2)) return; 4 for ($i=0 ; $i<strlen($s1); $i++){ 5 $s2[] = $s1 [$i]; 6 } 7 return $s2; 8 }
//连接字符串
1 function strcat($s1 , $s2) 2 { 3 if (!isset($s1) || !isset( $s2)) return; 4 $newstr = $s1 ; 5 for($i=0; $i <count($s); $i ++){ 6 $newstr .= $st[$i ]; 7 } 8 return $newsstr; 9 }
//简单编码函数（与php_decode函数对应）
1 function php_encode($str) 2 { 3 if ( $str=='' && strlen( $str)>128) return false; 4 for( $i=0; $i<strlen ($str); $i++){ 5 $c = ord($str[$i ]); 6 if ($c>31 && $c <107) $c += 20 ; 7 if ($c>106 && $c <127) $c -= 75 ; 8 $word = chr($c ); 9 $s .= $word; 10 } 11 return $s; 12 }
//简单解码函数（与php_encode函数对应）
1 function php_decode($str) 2 { 3 if ( $str=='' && strlen($str )>128) return false; 4 for( $i=0; $i<strlen ($str); $i++){ 5 $c = ord($word); 6 if ( $c>106 && $c<127 ) $c = $c-20; 7 if ($c>31 && $c< 107) $c = $c+75 ; 8 $word = chr( $c); 9 $s .= $word ; 10 } 11 return $s; 12 }
//简单加密函数（与php_decrypt函数对应）
1 function php_encrypt($str) 2 { 3 $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890'; 4 $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359'; 5 if ( strlen($str) == 0) return false; 6 for ($i=0; $i<strlen($str); $i ++){ 7 for ($j=0; $j <strlen($encrypt_key); $j ++){ 8 if ($str[$i] == $encrypt_key [$j]){ 9 $enstr .= $decrypt_key[$j]; 10 break; 11 } 12 } 13 } 14 return $enstr; 15 }
//简单解密函数（与php_encrypt函数对应）
1 function php_decrypt($str) 2 { 3 $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890'; 4 $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359'; 5 if ( strlen($str) == 0) return false; 6 for ($i=0; $i<strlen($str); $i ++){ 7 for ($j=0; $j <strlen($decrypt_key); $j ++){ 8 if ($str[$i] == $decrypt_key [$j]){ 9 $enstr .= $encrypt_key[$j]; 10 break; 11 } 12 } 13 } 14 return $enstr; 15 }
1、首先来画个菱形玩玩，很多人学C时在书上都画过，咱们用PHP画下，画了一半。
思路：多少行for一次，然后在里面空格和星号for一次。
<?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; }
2、冒泡排序，C里基础算法，从小到大对一组数排序。
思路：这题从小到大，第一轮排最小，第二轮排第二小，第三轮排第三小，依次类推……
<?php $arr = array(1,3,5,32,756,2,6); $len = count($arr); for ($i=0;$i<$len-1;$i++){ for ($j=$i+1;$j<$len;$j++){ if($arr[$i]>$arr[$j]){//从小到大 $p = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j]= $p; } } } var_dump($arr);
3、杨辉三角，用PHP写。
思路：每一行的第一位和最后一位是1，没有变化，中间是前排一位与左边一排的和，这种算法是用一个二维数组保存，另外有种算法用一维数组也可以实现，一行 一行的输出，有兴趣去写着玩下。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
<?php //每行的第一个和最后一个都为1，写了6行 for($i=0; $i<6; $i++) { $a[$i][0]=1; $a[$i][$i]=1; } //出除了第一位和最后一位的值，保存在数组中 for($i=2; $i<6; $i++) { for($j=1; $j<$i; $j++) { $a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j]; } } //打印 for($i=0; $i<6; $i++){ for($j=0; $j<=$i; $j++) { echo $a[$i][$j].' '; } echo '<br/>'; }
4、在一组数中，要求插入一个数，按其原来顺序插入，维护原来排序方式。
思路：找到比要插入数大的那个位置，替换，然后把后面的数后移一位。
<?php $in = 2; $arr = array(1,1,1,3,5,7); $n = count($arr); //如果要插入的数已经最大，直接打印 if($arr[$n-1] < $in) { $arr[$n+1] = $in; print_r($arr); } for($i=0; $i<$n; $i++) { //找出要插入的位置 if($arr[$i] >= $in){ $t1= $arr[$i]; $arr[$i] = $in; //把后面的数据后移一位 for($j=$i+1; $j<$n+1; $j++) { $t2 = $arr[$j]; $arr[$j] = $t1; $t1 = $t2; } //打印 print_r($arr); die; } }
5、对一组数进行排序（快速排序算法）。
思路：通过一趟排序分成两部分，然后递归对这两部分排序，最后合并。
<?php function q($array) { if (count($array) <= 1) {return $array;} //以$key为界，分成两个子数组 $key = $array[0]; $l = array(); $r = array(); //分别进行递归排序，然后合成一个数组 for ($i=1; $i<count($array); $i++) { if ($array[$i] <= $key) { $l[] = $array[$i]; } else { $r[] = $array[$i]; } } $l = q($l); $r = q($r); return array_merge($l, array($key), $r); } $arr = array(1,2,44,3,4,33); print_r( q($arr) );
6、在一个数组查找你所需元素（二分查找算法）。
思路：以数组中某个值为界，再递归进行查找，直到结束。
<?php function find($array, $low, $high, $k){ if ($low <= $high){ $mid = intval(($low+$high)/2); if ($array[$mid] == $k){ return $mid; }elseif ($k < $array[$mid]){ return find($array, $low, $mid-1, $k); }else{ return find($array, $mid+1, $high, $k); } } die('Not have...'); } //test $array = array(2,4,3,5); $n = count($array); $r = find($array,0,$n,5)
7、合并多个数组，不用array_merge()，题目来于论坛。
思路：遍历每个数组，重新组成一个新数组。
<?php function t(){ $c = func_num_args()-1; $a = func_get_args(); //print_r($a); for($i=0; $i<=$c; $i++){ if(is_array($a[$i])){ for($j=0; $j<count($a[$i]); $j++){ $r[] = $a[$i][$j]; } } else { die('Not a array!'); } } return $r; } //test print_r(t(range(1,4),range(1,4),range(1,4))); echo '<br/>'; $a = array_merge(range(1,4),range(1,4),range(1,4)); print_r($a);
8、牛年求牛：有一母牛，到4岁可生育，每年一头，所生均是一样的母牛，到15岁绝育，不再能生，20岁死亡，问n年后有多少头牛。（来自论坛）
<?php function t($n) { static $num = 1 for($j=1; $j<=$n; $j++){ if($j>=4 && $j<15) {$num++;t($n-$j);} if($j==20){$num--;} } return $num; } //test echo t(8);