PHP常用算法和数据结构示例(必看篇)
实例如下：
"; //快速排序 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))."
"; //选择排序(不稳定) functionSelectSort($arr){ $length=count($arr); if($length<=1){ return$arr; } 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))."
"; //插入排序 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+1]=$arr[$j]; $j--; } $arr[$j+1]=$x; } return$arr; } echo'插入排序：'; echoimplode('',InsertSort($arr))."
"; //--------------------------------------- //常用查找算法 //--------------------------------------- //二分查找 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"
顺序常规查找{$key}的位置："; echoSqSearch($arr,$key); //--------------------------------------- //常用数据结构 //--------------------------------------- //线性表的删除(数组实现) functiondelete_array_element($arr,$pos){ $length=count($arr); if($pos<1||$pos>$length){ return"删除位置出错!"; } for($i=$pos-1;$i<$length-1;$i++){ $arr[$i]=$arr[$i+1]; } array_pop($arr); return$arr; } $pos=3; echo"
除第{$pos}位置上的元素后："; echoimplode('',delete_array_element($arr,$pos))."
"; /** *ClassNode *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){ 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){ 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'
'; } $linkList=newNode(); init($linkList);//初始化 createTail($linkList,10);//尾插法创建链表 show($linkList);//打印出链表 insert($linkList,3,'a');//插入 show($linkList); delete($linkList,3);//删除 show($linkList); /** *ClassStack *用PHP模拟顺序栈的基本操作 */ classStack{ //用默认值直接初始化栈了，也可用构造方法初始化栈 private$top=-1; private$maxSize=5; private$stack=array(); //入栈 publicfunctionpush($elem){ if($this->top>=$this->maxSize-1){ echo"栈已满！
"; 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"
"; } } $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(); /** *ClassDeque *使用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(){//打印 foreach($this->queueas$item){ echo$item.""; } echo"
"; } } $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"
".joseph_ring(60,5)."
"; echo"
".joseph_ring2(60,5)."
";
以上这篇PHP常用算法和数据结构示例(必看篇)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。