<?phpfunction quickSort($arr){ $len = count($arr); if ($len <= 1) { return $arr; } $base_num = $arr[0]; $left_arr = array(); $right_arr = array(); for ($i = 1; $i < $len; $i++) { if ($base_num > $arr[$i]) { $left_arr[] = $arr[$i]; } else { $right_arr[] = $arr[$i]; } } $left_arr = quickSort($left_arr); $right_arr = quickSort($right_arr); return array_merge($left_arr, array($base_num), $right_arr);}$arr = array(3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48);print_r(quickSort($arr));?>
归并排序:
归并排序是一种分治算法,它将一个大的问题分成两个或更多的小的子问题来办理。下面是一个利用 PHP 实现归并排序的代码示例:
<?phpfunction mergeSort($array){ if (count($array) == 1) { return $array; } $middle = count($array) / 2; $left = array_slice($array, 0, $middle); $right = array_slice($array, $middle); $left = mergeSort($left); $right = mergeSort($right); return merge($left, $right);}function merge($left, $right){ $result = array(); while (count($left) > 0 && count($right) > 0) { if ($left[0] < $right[0]) { $result[] = array_shift($left); } else { $result[] = array_shift($right); } } while (count($left) > 0) { $result[] = array_shift($left); } while (count($right) > 0) { $result[] = array_shift($right); } return $result;}$array = array(38, 27, 43, 3, 9, 82);$array = mergeSort($array);print_r($array);
冒泡排序:
冒泡排序算法的基本思想是:比较相邻的元素,如果前面的元素比后面的元素大,则交流位置;重复以上操作,直到全体数组有序。
<?phpfunction bubbleSort($arr){ $len = count($arr); for ($i = 0; $i < $len; $i++) { for ($j = 0; $j < $len - $i - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $temp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $temp; } } } return $arr;}$arr = array(3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48);print_r(bubbleSort($arr));?>
插入排序:
插入排序是一种大略的排序算法。它的事理是通过将数组中的数字逐个插入到已排好序的数列中,终极使全体数组有序。
<?phpfunction insert_sort($arr){ for ($i = 1; $i < count($arr); $i++) { $temp = $arr[$i]; $j = $i - 1; while ($j >= 0 && $arr[$j] > $temp) { $arr[$j + 1] = $arr[$j]; $j--; } $arr[$j + 1] = $temp; } return $arr;}$arr = array(3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48);$arr = insert_sort($arr);print_r($arr);?>
在上述代码中,我们循环遍历数组,并从第二个数字开始进行排序。对付每一个数字,我们把它存储在一个临时变量中,然后不断与前面的已排好序的数列进行比较,直到找到一个得当的位置为止。末了,我们将临时变量插入到该位置,以担保全体数列的有序性。
选择排序:选择排序算法的事理是:每一趟从待排序的数列中选出最小的元素,顺次和前面的元素交换位置,直到全部待排序的数列元素排序完毕。
以下是 PHP 代码实现选择排序算法:
<?phpfunction selectionSort(array $arr){ $len = count($arr); for ($i = 0; $i < $len - 1; $i++) { $minIndex = $i; for ($j = $i + 1; $j < $len; $j++) { if ($arr[$j] < $arr[$minIndex]) { $minIndex = $j; } } if ($minIndex != $i) { $temp = $arr[$i]; $arr[$i] = $arr[$minIndex]; $arr[$minIndex] = $temp; } } return $arr;}$arr = [7, 4, 5, 6, 1, 2, 3];$sortedArr = selectionSort($arr);print_r($sortedArr);
搜索算法:二分查找、广搜、DFS二分查找
<?phpfunction binary_search($arr, $x){ $left = 0; $right = count($arr) - 1; while ($left <= $right) { $mid = (int)(($left + $right) / 2); if ($arr[$mid] == $x) { return $mid; } elseif ($arr[$mid] < $x) { $left = $mid + 1; } else { $right = $mid - 1; } } return -1;}$arr = array(1, 3, 4, 5, 6, 8, 9);$x = 5;$result = binary_search($arr, $x);if ($result == -1) { echo "Element not found in the array.";} else { echo "Element found at index " . $result;}?>
上面代码实现了二分查找算法,它须要一个已经排好序的数组和要查找的元素。它利用一个循环来实现查找,并通过判断每次查找的中间元素是否即是要查找的元素,来不断地缩小查找的范围。如果查找到了该元素,函数将返回该元素的索引;如果没有查找到该元素,函数将返回 -1。
广搜广搜算法,又称为宽度优先搜索,是一种图论算法。它通过对图中所有节点均匀遍历一遍,从而找到最短路径。
这是一个 PHP 实现的广搜算法示例代码:
<?php// 定义一个图形的毗邻表$graph = array( 'A' => array('B', 'C'), 'B' => array('A', 'D', 'E'), 'C' => array('A', 'F'), 'D' => array('B'), 'E' => array('B', 'F'), 'F' => array('C', 'E'),);// 定义一个数组来记录访问过的节点$visited = array();// 定义一个行列步队来存储须要访问的节点$queue = array();// 开始节点为 A$start = 'A';// 初始化行列步队并将起始节点加入array_push($queue, $start);// 循环遍历行列步队while (!empty($queue)) { // 从行列步队中取出一个节点 $node = array_shift($queue); // 如果该节点还没有被访问过,则记录访问并加入行列步队 if (!in_array($node, $visited)) { echo $node . "\n"; array_push($visited, $node); foreach ($graph[$node] as $neighbor) { array_push($queue, $neighbor); } }}?>
DFS
DFS,即深度优先搜索,是一种图论算法。它在搜索过程中沿着一条路径一贯走下去,直到没有可以前往的路或找到所需的结果为止。然后再回溯并走另一条路。
下面是一个 PHP 代码示例:
<?phpclass Node { public $value; public $visited = false; public $adjacent = [];}class DFS { private $nodes = []; public function addNode($value) { $this->nodes[$value] = new Node($value); } public function addEdge($value1, $value2) { $this->nodes[$value1]->adjacent[] = $this->nodes[$value2]; } public function search($startValue, $endValue) { $startNode = $this->nodes[$startValue]; $endNode = $this->nodes[$endValue]; $this->dfs($startNode, $endNode); return $endNode->visited; } private function dfs(Node $node, Node $endNode) { if ($node->visited) { return; } $node->visited = true; if ($node == $endNode) { return; } foreach ($node->adjacent as $adjacent) { $this->dfs($adjacent, $endNode); } }}$dfs = new DFS();$dfs->addNode('A');$dfs->addNode('B');$dfs->addNode('C');$dfs->addNode('D');$dfs->addNode('E');$dfs->addEdge('A', 'B');$dfs->addEdge('A', 'C');$dfs->addEdge('B', 'D');$dfs->addEdge('C', 'E');$result = $dfs->search('A', 'E');if ($result) { echo "Found";} else { echo "Not found";}
图算法:最短路径算法(Dijkstra 算法、Bellman-Ford 算法、Floyd 算法)、最小天生树算法(Kruskal 算法、Prim 算法)Dijkstra 算法
Dijkstra算法是一种图论最短路径算法,用于办理单源最短路径问题。该算法利用一种贪心策略,不断地选择到达当前未访问顶点的最小间隔,直到所有顶点都已访问为止。
Dijkstra算法假设图中不存在负权边,否则算法不一定精确。
<?php$graph = [ 'A' => ['B' => 1, 'C' => 4, 'D' => 10], 'B' => ['C' => 3, 'D' => 4, 'E' => 5], 'C' => ['B' => 3, 'E' => 1], 'D' => ['E' => 7], 'E' => []];$start = 'A';$end = 'E';$costs = [ 'B' => 1, 'C' => 4, 'D' => 10, 'E' => INF,];$parents = [ 'B' => 'A', 'C' => 'A', 'D' => 'A', 'E' => null,];$processed = [];function find_lowest_cost_node($costs, $processed) { $lowest_cost = INF; $lowest_cost_node = null; foreach ($costs as $node => $cost) { if ($cost < $lowest_cost && !in_array($node, $processed)) { $lowest_cost = $cost; $lowest_cost_node = $node; } } return $lowest_cost_node;}while (count($processed) < count($graph)) { $node = find_lowest_cost_node($costs, $processed); if (!$node) break; $cost = $costs[$node]; $neighbors = $graph[$node]; foreach ($neighbors as $n => $c) { $new_cost = $cost + $c; if ($costs[$n] > $new_cost) { $costs[$n] = $new_cost; $parents[$n] = $node; } } array_push($processed, $node);}$path = [$end];$parent = $parents[$end];while ($parent) { array_unshift($path, $parent); $parent = $parents[$parent];}echo "最短路径:", implode(' -> ', $path), PHP_EOL;echo "路径长度:", $costs[$end], PHP_EOL;
Bellman-Ford 算法
Bellman-Ford算法是一种单源最短路径算法,用于求图中单个源点到所有其他点的最短路径。它通过重复地更新到其他点的间隔来办理最短路径问题。
下面是一个Bellman-Ford算法的 PHP 实现示例:
<?php// 图的顶点数量和边数量$V = 5;$E = 8;// 出发点$src = 0;// 存储图$graph = array( array(0, 4, 0, 0, 0), array(4, 0, 8, 0, 0), array(0, 8, 0, 7, 0), array(0, 0, 7, 0, 9), array(0, 0, 0, 9, 0));// 初始化间隔数组$dis = array();for ($i = 0; $i < $V; $i++) { $dis[$i] = PHP_INT_MAX;}// 出发点到自己的间隔为 0$dis[$src] = 0;// 循环 $V-1 次,更新最短间隔for ($i = 1; $i <= $V-1; $i++) { for ($j = 0; $j < $E; $j++) { $u = $graph[$j][0]; $v = $graph[$j][1]; $weight = $graph[$j][2]; if ($dis[$u] != PHP_INT_MAX && $dis[$u] + $weight < $dis[$v]) { $dis[$v] = $dis[$u] + $weight; } }}// 检讨负权环for ($i = 0; $i < $E; $i++) { $u = $graph[$i][0]; $v = $graph[$i][1]; $weight = $graph[$i][2]; if ($dis[$u] != PHP_INT_MAX && $dis[$u] + $weight < $dis[$v]) { echo "图中有负权环"; return; }}// 输出最短路径echo "从节点 $src 到其他节点的
Floyd 算法
Floyd 算法是一种用于求解图中所有顶点之间最短路径的算法。Floyd 算法是利用中间顶点更新任意两点间的最短路径的方法。下面是一个 PHP 实现 Floyd 算法的示例代码:
<?php$INF = 999999;function floyd($graph, $n){ for ($k = 0; $k < $n; $k++) { for ($i = 0; $i < $n; $i++) { for ($j = 0; $j < $n; $j++) { if ($graph[$i][$j] > $graph[$i][$k] + $graph[$k][$j]) { $graph[$i][$j] = $graph[$i][$k] + $graph[$k][$j]; } } } } return $graph;}$graph = array( array(0, 3, 8, INF, -4), array(INF, 0, INF, 1, 7), array(INF, 4, 0, INF, INF), array(2, INF, -5, 0, INF), array(INF, INF, INF, 6, 0));$n = count($graph);$result = floyd($graph, $n);for ($i = 0; $i < $n; $i++) { for ($j = 0; $j < $n; $j++) { echo $result[$i][$j] . " "; } echo "\n";}?>
在上面的代码中,首先利用三重循环更新图中任意两点间的最短路径,末了将结果输出。
Kruskal 算法Kruskal 算法是一种用于求最小天生树的算法,紧张思想是按权值从小到大选择边,将所有边排序后,选择具有最小权值的边加入天生树。若选择的边不形成环,则连续选择下一条边。如果形成了环,则舍弃这条边。
以下是一个 PHP 的 Kruskal 算法示例代码:
<?php$n = 6;$m = 9;$e = array();$e[0][0] = 1;$e[0][1] = 2;$e[0][2] = 1;$e[1][0] = 1;$e[1][1] = 3;$e[1][2] = 3;$e[2][0] = 2;$e[2][1] = 3;$e[2][2] = 5;$e[3][0] = 2;$e[3][1] = 4;$e[3][2] = 4;$e[4][0] = 3;$e[4][1] = 4;$e[4][2] = 2;$e[5][0] = 3;$e[5][1] = 5;$e[5][2] = 7;$e[6][0] = 4;$e[6][1] = 5;$e[6][2] = 6;$e[7][0] = 4;$e[7][1] = 6;$e[7][2] = 5;$e[8][0] = 5;$e[8][1] = 6;$e[8][2] = 1;function find($x, $f) { if ($f[$x] == $x) { return $x; } else { $root = find($f[$x], $f); $f[$x] = $root; return $root; }}for ($i = 0; $i < $m; $i++) { for ($j = $i + 1; $j < $m; $j++) { if ($e[$j][2] < $e[$i][2]) { $t = $e[$i]; $e[$i] = $e[$j]; $e[$j] = $t; } }}$sum = 0;$cnt = 0;$f = array();for ($i = 1; $i <= $n; $i++) { $f[$i] = $i;}for ($i = 0; $i < $m; $i++) { $x = find($e[$i][0], $f); $y = find($e[$i][1], $f); if ($x != $y) { $f[$y] = $x; $cnt++; $sum += $e[$i][2]; if ($cnt == $n - 1) { break; } }}printf("%d\n", $sum);?>
Prim 算法
Prim 算法是一种用于打算最小天生树的算法。
下面是一个利用 PHP 实现 Prim 算法的代码示例:
<?php$n = 5; // 顶点数$m = 9; // 边数$inf = PHP_INT_MAX; // 设置无穷大$graph = [ [0, 6, 1, 5, inf], [6, 0, 5, inf, inf], [1, 5, 0, 5, 4], [5, inf, 5, 0, 2], [inf, inf, 4, 2, 0]]; // 毗邻矩阵存储图$dis = array_fill(0, $n, $inf); // 到当前天生树的最短间隔$book = array_fill(0, $n, 0); // 记录当前天生树上的点$book[0] = 1; // 初始以 0 号点为出发点$dis[0] = 0; // 到 0 号点间隔为 0for ($i = 0; $i < $n; $i++) { $min = $inf; $minid = 0; // 找到与当前天生树相连且间隔最短的点 for ($j = 0; $j < $n; $j++) { if ($book[$j] == 0 && $dis[$j] < $min) { $min = $dis[$j]; $minid = $j; } } $book[$minid] = 1; // 标记为当前天生树上的点 for ($j = 0; $j < $n; $j++) { // 更新到当前天生树的间隔 if ($book[$j] == 0 && $graph[$minid][$j] < $dis[$j]) { $dis[$j] = $graph[$minid][$j]; } }}echo array_sum($dis); // 输出生成树的总间隔?>
动态方案:最大子序列和、背包问题、最长公共子序列最大子序列和
下面是一个最大子序列和的 PHP 算法示例:
<?phpfunction maxSubarraySum($arr) { $maxSum = 0; $tempSum = 0; for ($i = 0; $i < count($arr); $i++) { $tempSum += $arr[$i]; if ($tempSum < 0) { $tempSum = 0; } else if ($tempSum > $maxSum) { $maxSum = $tempSum; } } return $maxSum;}$arr = [1, -3, 4, -2, -1, 6];$maxSum = maxSubarraySum($arr);echo "最大子序列和为:" . $maxSum . "\n";?>
在这个算法中,我们利用了一个变量 $maxSum 记录最大子序列和,并利用另一个变量 $tempSum 记录当前子序列的和。在循环遍历数组的同时,我们不断累加当前的数值到 $tempSum 中,如果 $tempSum 小于 0,我们将它重置为 0,否则,如果 $tempSum 大于 $maxSum,我们就将 $maxSum 更新为 $tempSum。循环遍历完成后,我们就可以得到最大子序列和。
背包问题背包问题是一种常见的贪心问题,关于一个背包的大小,以及可选择的物品的大小和代价,哀求选择物品使得总代价最大,但总大小不超过背包的大小。
下面是一个用 PHP 实现的背包问题的代码:
<?php$size = 5;$capacity = 10;$items = [ [2, 6], [2, 3], [6, 5], [5, 4], [4, 6],];$dp = array_fill(0, $capacity + 1, 0);for ($i = 0; $i < $size; $i++) { for ($j = $capacity; $j >= $items[$i][0]; $j--) { $dp[$j] = max($dp[$j], $dp[$j - $items[$i][0]] + $items[$i][1]); }}echo $dp[$capacity];?>
在这个代码中,我们利用一个数组 dp 来储存每种背原谅量下最大代价,然后我们利用两重循环来遍历每个物品,对付每个物品,我们从大到小列举容量,更新 dp 数组。末了,dp[capacity] 的值便是最大代价。
最长公共子序列下面是 PHP 实现最长公共子序列算法的代码:
<?phpfunction lcs($str1, $str2) { $len1 = strlen($str1); $len2 = strlen($str2); $c = array(); for ($i = 0; $i <= $len1; $i++) { $c[$i][0] = 0; } for ($j = 0; $j <= $len2; $j++) { $c[0][$j] = 0; } for ($i = 1; $i <= $len1; $i++) { for ($j = 1; $j <= $len2; $j++) { if ($str1[$i-1] == $str2[$j-1]) { $c[$i][$j] = $c[$i-1][$j-1] + 1; } else { $c[$i][$j] = max($c[$i-1][$j], $c[$i][$j-1]); } } } return $c[$len1][$len2];}?>
利用示例:
<?php$str1 = "ABCBDAB";$str2 = "BDCABA";$result = lcs($str1, $str2);echo "最长公共子序列的长度为:" . $result;?>
字符串算法:KMP、Rabin-Karp、AC 自动机KMP
KMP (Knuth-Morris-Pratt) 算法是一种在字符串匹配问题中的快速模式匹配算法。它的核心思想是在暴力字符串匹配的根本上,通过利用部分匹配信息,避免了不必要的比较,从而大大提高了匹配效率。
下面是用 PHP 实现 KMP 算法的示例代码:
<?php function KMP($str, $pat){ $strLen = strlen($str); $patLen = strlen($pat); $next = array(); getNext($pat, $patLen, $next); $j = 0; for ($i = 0; $i < $strLen; $i ++) { while ($j > 0 && $str[$i] != $pat[$j]) { $j = $next[$j - 1]; } if ($str[$i] == $pat[$j]) { $j ++; } if ($j == $patLen) { return $i - $patLen + 1; } } return -1;}function getNext($pat, $patLen, &$next){ $next[0] = 0; $j = 0; for ($i = 1; $i < $patLen; $i ++) { while ($j > 0 && $pat[$i] != $pat[$j]) { $j = $next[$j - 1]; } if ($pat[$i] == $pat[$j]) { $j ++; } $next[$i] = $j; }} ?>
在利用 KMP 算法时,须要首先打算出模式串的 next 数组,再用 next 数组实现字符串匹配。
Rabin-KarpRabin-Karp 算法是一种字符串匹配算法,通过哈希的思想在一个字符串中查找一个子字符串的位置。该算法的核心思想是:对两个字符串打算哈希值,如果哈希值相同,则比较这两个字符串的字符是否完备相同。
以下是用 PHP 实现 Rabin-Karp 算法的代码示例:
<?phpfunction RabinKarp($text, $pattern){ $n = strlen($text); $m = strlen($pattern); $hashPattern = 0; $hashText = 0; $d = 26; $q = 997; $h = 1; for ($i = 0; $i < $m - 1; $i++) $h = ($h $d) % $q; for ($i = 0; $i < $m; $i++) { $hashPattern = ($d $hashPattern + ord($pattern[$i])) % $q; $hashText = ($d $hashText + ord($text[$i])) % $q; } for ($i = 0; $i <= $n - $m; $i++) { if ($hashPattern == $hashText) { for ($j = 0; $j < $m; $j++) { if ($text[$i + $j] != $pattern[$j]) break; } if ($j == $m) return $i; } if ($i < $n - $m) { $hashText = ($d ($hashText - ord($text[$i]) $h) + ord($text[$i + $m])) % $q; if ($hashText < 0) $hashText = ($hashText + $q); } } return -1;}?>
贪心算法:最小天生树、贪心背包最小天生树
最小天生树算法是指在一个图的顶点凑集中找出一颗树,使得树的所有边的权值和最小。
在 PHP 中,我们可以利用 Prim 算法或者 Kruskal 算法来实现最小天生树。
这里是利用 Prim 算法实现最小天生树的示例代码:
<?php$graph = [ [0, 2, 4, 0, 0, 0], [2, 0, 2, 4, 2, 0], [4, 2, 0, 0, 3, 0], [0, 4, 0, 0, 3, 2], [0, 2, 3, 3, 0, 2], [0, 0, 0, 2, 2, 0],];$n = count($graph);$key = array_fill(0, $n, PHP_INT_MAX);$visited = array_fill(0, $n, false);$key[0] = 0;$parent = array_fill(0, $n, -1);for ($i = 0; $i < $n - 1; $i++) { $min = PHP_INT_MAX; $min_index = -1; for ($j = 0; $j < $n; $j++) { if (!$visited[$j] && $key[$j] < $min) { $min = $key[$j]; $min_index = $j; } } $visited[$min_index] = true; for ($j = 0; $j < $n; $j++) { if (!$visited[$j] && $graph[$min_index][$j] && $graph[$min_index][$j] < $key[$j]) { $key[$j] = $graph[$min_index][$j]; $parent[$j] = $min_index; } }}$min_spanning_tree = 0;for ($i = 1; $i < $n; $i++) { echo $parent[$i] . " - " . $i . " : " . $graph[$i][$parent[$i]] . "\n"; $min_spanning_tree += $graph[$i][$parent[$i]];}echo "最小天生树的权值为:" . $min_spanning_tree . "\n";?>
贪心背包
以下是 PHP 实现的贪心背包算法的示例代码:
<?php$n = 5; // 物品个数$w = 10; // 背原谅量$v = [0, 2, 2, 6, 5, 4]; // 物品代价$c = [0, 6, 3, 5, 4, 6]; // 物品体积$f = [];for ($i = 0; $i <= $n; $i++) { $f[$i] = []; for ($j = 0; $j <= $w; $j++) { if ($i == 0 || $j == 0) { $f[$i][$j] = 0; } else if ($c[$i] <= $j) { $f[$i][$j] = max($f[$i - 1][$j], $f[$i - 1][$j - $c[$i]] + $v[$i]); } else { $f[$i][$j] = $f[$i - 1][$j]; } }}echo $f[$n][$w];?>
该代码实现了一种基于贪心策略的 01 背包问题办理方案。
数学算法:快速幂、欧几里得算法快速幂快速幂算法是求整数次幂的一种有效算法,可以快速打算出幂次为整数的数的幂。
在 PHP 中可以利用 bcpow 函数实现快速幂,其语法如下:
<?php$base = 2;$exponent = 10;$result = bcpow($base, $exponent);echo "$base ^ $exponent = $result\n";
欧几里得算法
欧几里得算法(Euclidean Algorithm)是一种用于求两个数的最大公约数的算法。它是一种辗转相除法的求法,通过把较大的数除以较小的数,直到两数相等或余数为0,末了较小的数即为两数的最大公约数。
下面是一个利用 PHP 实现的欧几里得算法的示例代码:
<?phpfunction gcd($a, $b) { if ($b == 0) { return $a; } return gcd($b, $a % $b);}$a = 60;$b = 48;$result = gcd($a, $b);echo "The gcd of $a and $b is $result\n"; ?>
数据构造算法:二叉搜索树、堆、栈、行列步队、Hash 表二叉搜索树
二叉搜索树是一种分外的二叉树,个中的每个节点都有一个值,并且它的左子节点的值永久小于父节点的值,而右子节点的值永远大于父节点的值。这使得搜索树特殊适宜进行排序和查找操作。
以下是二叉搜索树的一个大略实现:
<?phpclass Node{ public $value; public $left; public $right; public function __construct($value) { $this->value = $value; $this->left = null; $this->right = null; }}class BinarySearchTree{ private $root; public function __construct() { $this->root = null; } public function insert($value) { $node = new Node($value); if ($this->root === null) { $this->root = $node; } else { $this->insertNode($this->root, $node); } } private function insertNode($current, $node) { if ($node->value < $current->value) { if ($current->left === null) { $current->left = $node; } else { $this->insertNode($current->left, $node); } } else { if ($current->right === null) { $current->right = $node; } else { $this->insertNode($current->right, $node); } } } public function search($value) { return $this->searchNode($this->root, $value); } private function searchNode($current, $value) { if ($current === null) { return false; } if ($value === $current->value) { return true; } if ($value < $current->value) { return $this->searchNode($current->left, $value); } else { return $this->searchNode($current->right, $value); } }}?>
堆、栈、行列步队
堆、栈和行列步队是三种基本的数据构造,有不同的特点和运用处景。
堆: 堆是一种分外的树形构造,有最大堆和最小堆两种。堆的性子是父节点的值大于(或小于)子节点的值,它的实现常日利用数组。在 PHP 中,可以利用 SplMaxHeap 和 SplMinHeap 类实现。
栈: 栈是一种后进先出(LIFO)的数据构造,可以利用数组或链表实现。在 PHP 中,可以利用 array_push 和 array_pop 函数实现栈的操作。
行列步队: 行列步队是一种前辈先出(FIFO)的数据构造,可以利用数组或链表实现。在 PHP 中,可以利用 array_push 和 array_shift 函数实现行列步队的操作。
示例代码:
<?php// 堆示例$heap = new SplMaxHeap();$heap->insert(10);$heap->insert(30);$heap->insert(20);foreach ($heap as $value) { echo $value, PHP_EOL;}// 栈示例$stack = [];array_push($stack, 10);array_push($stack, 20);array_push($stack, 30);while (!empty($stack)) { echo array_pop($stack), PHP_EOL;}// 行列步队示例$queue = [];array_push($queue, 10);array_push($queue, 20);array_push($queue, 30);while (!empty($queue)) { echo array_shift($queue), PHP_EOL;} ?>
Hash 表
Hash 表是一种数据构造,用于存储键/值对。它许可快速查找和更新值,由于其利用了哈希算法将键映射到散列数组的索引位置。
下面是一个利用 PHP 的示例代码,用于创建哈希表:
<?php$hashTable = array();// 添加键/值对$hashTable["key1"] = "value1";$hashTable["key2"] = "value2";// 更新值$hashTable["key1"] = "newValue1";// 获取值$value1 = $hashTable["key1"];// 删除键/值对unset($hashTable["key2"]); ?>
请把稳,在 PHP 中,哈希表可以利用数组表示。