PHP常用算法和数据结构示例(必看篇)
发布:smiling 来源: PHP粉丝网 添加日期:2018-08-09 09:44:11 浏览: 评论:0
- /**
- * Created by PhpStorm.
- * User: qishou
- * Date: 15-8-2
- * Time: 上午9:12
- */
- header("content-type:text/html;charset=utf-8");
- $arr=array(3,5,8,4,9,6,1,7,2);
- echoimplode(" ",$arr)."<br>";
- //---------------------------------------
- // 常用排序算法
- //---------------------------------------
- //冒泡排序
- functionBubbleSort($arr){
- $length=count($arr);
- if($length<=1){
- return$arr;
- }
- for($i=0;$i<$length;$i++){
- for($j=$length-1;$j>$i;$j--){
- if($arr[$j]<$arr[$j-1]){
- $tmp=$arr[$j];
- $arr[$j] =$arr[$j-1];
- $arr[$j-1] =$tmp;
- }
- }
- }
- return$arr;
- }
- echo'冒泡排序:'
- echoimplode(' ',BubbleSort($arr))."<br>";
- //快速排序
- functionQSort($arr){
- $length=count($arr);
- if($length<=1){
- return$arr;
- }
- $pivot=$arr[0];//枢轴
- $left_arr=array();
- $right_arr=array();
- for($i=1;$i<$length;$i++){//注意$i从1开始0是枢轴
- if($arr[$i]<=$pivot){
- $left_arr[] =$arr[$i];
- }else{
- $right_arr[] =$arr[$i];
- }
- }
- $left_arr= QSort($left_arr);//递归排序左半部分
- $right_arr= QSort($right_arr);//递归排序右半部份
- returnarray_merge($left_arr,array($pivot),$right_arr);//合并左半部分、枢轴、右半部分
- }
- echo"快速排序:";
- echoimplode(' ',QSort($arr))."<br>";
- //选择排序(不稳定)
- functionSelectSort($arr){
- $length=count($arr);
- if($length<=1){
- return$arr;
- } //phpfensi.com
- for($i=0;$i<$length;$i++){
- $min=$i;
- for($j=$i+1;$j<$length;$j++){
- if($arr[$j]<$arr[$min]){
- $min=$j;
- }
- }
- if($i!=$min){
- $tmp=$arr[$i];
- $arr[$i] =$arr[$min];
- $arr[$min] =$tmp;
- }
- }
- return$arr;
- }
- echo"选择排序:";
- echoimplode(' ',SelectSort($arr))."<br>";
- //插入排序
- functionInsertSort($arr){
- $length=count($arr);
- if($length<=1){
- return$arr;
- }
- for($i=1;$i<$length;$i++){
- $x=$arr[$i];
- $j=$i-1;
- while($x<$arr[$j] j="">=0){<!--$arr[$j]-->
- $arr[$j+1] =$arr[$j];
- $j--;
- }
- $arr[$j+1] =$x;
- }
- return$arr;
- }
- echo'插入排序:'
- echoimplode(' ',InsertSort($arr))."<br>";
- //---------------------------------------
- // 常用查找算法
- //---------------------------------------
- //二分查找
- functionbinary_search($arr,$low,$high,$key){
- while($low<=$high){
- $mid=intval(($low+$high)/2);
- if($key==$arr[$mid]){
- return$mid+1;
- }elseif($key<$arr[$mid]){
- $high=$mid-1;
- }elseif($key>$arr[$mid]){
- $low=$mid+1;
- }
- }
- return-1;
- }
- $key= 6;
- echo"二分查找{$key}的位置:";
- echobinary_search(QSort($arr),0,8,$key);
- //顺序查找
- functionSqSearch($arr,$key){
- $length=count($arr);
- for($i=0;$i<$length;$i++){
- if($key==$arr[$i]){
- return$i+1;
- }
- }
- return-1;
- }
- $key= 8;
- echo"<br>顺序常规查找{$key}的位置:";
- echoSqSearch($arr,$key);
- //---------------------------------------
- // 常用数据结构
- //---------------------------------------
- //线性表的删除(数组实现)
- functiondelete_array_element($arr,$pos){
- $length=count($arr);
- if($pos<1 pos="">$length){<!--1-->
- return"删除位置出错!";
- }
- for($i=$pos-1;$i<$length-1;$i++){
- $arr[$i] =$arr[$i+1];
- }
- array_pop($arr);
- return$arr;
- }
- $pos= 3;
- echo"<br>除第{$pos}位置上的元素后:";
- echoimplode(' ',delete_array_element($arr,$pos))."<br>";
- /**
- * Class Node
- * PHP模拟链表的基本操作
- */
- classNode{
- public$data=''
- public$next= null;
- }
- //初始化
- functioninit($linkList){
- $linkList->data = 0;//用来记录链表长度
- $linkList->next = null;
- }
- //头插法创建链表
- functioncreateHead(&$linkList,$length){
- for($i=0;$i<$length;$i++){
- $newNode=newNode();
- $newNode->data =$i;
- $newNode->next =$linkList->next;//因为PHP中对象本身就是引用所以不用再可用“&”
- $linkList->next =$newNode;
- $linkList->data++;
- }
- }
- //尾插法创建链表
- functioncreateTail(&$linkList,$length){
- $r=$linkList;
- for($i=0;$i<$length;$i++){
- $newNode=newNode();
- $newNode->data =$i;
- $newNode->next =$r->next;
- $r->next =$newNode;
- $r=$newNode;
- $linkList->data++;
- }
- }
- //在指定位置插入指定元素
- functioninsert($linkList,$pos,$elem){
- if($pos<1 pos="">$linkList->data+1){<!--1-->
- echo"插入位置错误!";
- }
- $p=$linkList;
- for($i=1;$i<$pos;$i++){
- $p=$p->next;
- }
- $newNode=newNode();
- $newNode->data =$elem;
- $newNode->next =$p->next;
- $p->next =$newNode;
- }
- //删除指定位置的元素
- functiondelete($linkList,$pos){
- if($pos<1 pos="">$linkList->data+1){<!--1-->
- echo"位置不存在!";
- }
- $p=$linkList;
- for($i=1;$i<$pos;$i++){
- $p=$p->next;
- }
- $q=$p->next;
- $p->next =$q->next;
- unset($q);
- $linkList->data--;
- }
- //输出链表数据
- functionshow($linkList){
- $p=$linkList->next;
- while($p!=null){
- echo$p->data." ";
- $p=$p->next;
- }
- echo'<br>'
- }
- $linkList=newNode();
- init($linkList);//初始化
- createTail($linkList,10);//尾插法创建链表
- show($linkList);//打印出链表
- insert($linkList,3,'a');//插入
- show($linkList);
- delete($linkList,3);//删除
- show($linkList);
- /**
- * Class Stack
- * 用PHP模拟顺序栈的基本操作
- */
- classStack{
- //用默认值直接初始化栈了,也可用构造方法初始化栈
- private$top= -1;
- private$maxSize= 5;
- private$stack=array();
- //入栈
- publicfunctionpush($elem){
- if($this->top >=$this->maxSize-1){
- echo"栈已满!<br>";
- return;
- }
- $this->top++;
- $this->stack[$this->top] =$elem;
- }
- //出栈
- publicfunctionpop(){
- if($this->top == -1){
- echo"栈是空的!";
- return;
- }
- $elem=$this->stack[$this->top];
- unset($this->stack[$this->top]);
- $this->top--;
- return$elem;
- }
- //打印栈
- publicfunctionshow(){
- for($i=$this->top;$i>=0;$i--){
- echo$this->stack[$i]." ";
- }
- echo"<br>";
- }
- }
- $stack=newStack();
- $stack->push(3);
- $stack->push(5);
- $stack->push(8);
- $stack->push(7);
- $stack->push(9);
- $stack->push(2);
- $stack->show();
- $stack->pop();
- $stack->pop();
- $stack->pop();
- $stack->show();
- /**
- * Class Deque
- * 使用PHP实现双向队列
- */
- classDeque{
- private$queue=array();
- publicfunctionaddFirst($item){//头入队
- array_unshift($this->queue,$item);
- }
- publicfunctionaddLast($item){//尾入队
- array_push($this->queue,$item);
- }
- publicfunctionremoveFirst(){//头出队
- array_shift($this->queue);
- }
- publicfunctionremoveLast(){//尾出队
- array_pop($this->queue);
- }
- publicfunctionshow(){//打印
- <a href="/tags.php/foreach/" target="_blank">foreach</a>($this->queueas$item){
- echo$item." ";
- }
- echo"<br>";
- }
- }
- $deque=newDeque();
- $deque->addFirst(2);
- $deque->addLast(3);
- $deque->addLast(4);
- $deque->addFirst(5);
- $deque->show();
- //PHP解决约瑟夫环问题
- //方法一
- functionjoseph_ring($n,$m){
- $arr= range(1,$n);
- $i= 0;
- while(count($arr)>1){
- $i=$i+1;
- $head=array_shift($arr);
- if($i%$m!= 0){//如果不是则重新压入数组
- array_push($arr,$head);
- }
- }
- return$arr[0];
- }
- //方法二
- functionjoseph_ring2($n,$m){
- $r= 0;
- for($i=2;$i<=$n;$i++){
- $r= ($r+$m)%$i;
- }
- return$r+ 1;
- }
- echo"<br>".joseph_ring(60,5)."<br>";
- echo"<br>".joseph_ring2(60,5)."<br>";
Tags: PHP算法 PHP数据结构
相关文章
- ·php:树形结构的算法(2013-11-13)
- ·php三种常用的排序算法(2014-08-02)
- ·最简单的php中字符串匹配算法教程(2015-04-06)
- ·PHP全排列算法实现程序代码(2015-04-08)
- ·用PHP实现URL转换短网址的算法示例(2016-07-27)
- ·php算法实例分享(2021-06-11)
- ·php 算法之实现相对路径的实例(2021-08-13)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)