当前位置:首页 > PHP教程 > php应用 > 列表

PHP常用算法和数据结构示例(必看篇)

发布:smiling 来源: PHP粉丝网  添加日期:2018-08-09 09:44:11 浏览: 评论:0 
  1. /** 
  2.  * Created by PhpStorm. 
  3.  * User: qishou 
  4.  * Date: 15-8-2 
  5.  * Time: 上午9:12 
  6.  */ 
  7. header("content-type:text/html;charset=utf-8"); 
  8. $arr=array(3,5,8,4,9,6,1,7,2); 
  9. echoimplode(" ",$arr)."<br>"
  10. //--------------------------------------- 
  11. //       常用排序算法 
  12. //--------------------------------------- 
  13. //冒泡排序 
  14. functionBubbleSort($arr){ 
  15.   $length=count($arr); 
  16.   if($length<=1){ 
  17.     return$arr
  18.   } 
  19.   for($i=0;$i<$length;$i++){ 
  20.     for($j=$length-1;$j>$i;$j--){ 
  21.       if($arr[$j]<$arr[$j-1]){ 
  22.         $tmp=$arr[$j]; 
  23.         $arr[$j] =$arr[$j-1]; 
  24.         $arr[$j-1] =$tmp
  25.       } 
  26.     } 
  27.   } 
  28.   return$arr
  29. echo'冒泡排序:' 
  30. echoimplode(' ',BubbleSort($arr))."<br>"
  31.   
  32. //快速排序 
  33. functionQSort($arr){ 
  34.   $length=count($arr); 
  35.   if($length<=1){ 
  36.     return$arr
  37.   } 
  38.   $pivot=$arr[0];//枢轴 
  39.   $left_arr=array(); 
  40.   $right_arr=array(); 
  41.   for($i=1;$i<$length;$i++){//注意$i从1开始0是枢轴 
  42.     if($arr[$i]<=$pivot){ 
  43.       $left_arr[] =$arr[$i]; 
  44.     }else
  45.       $right_arr[] =$arr[$i]; 
  46.     } 
  47.   } 
  48.   $left_arr= QSort($left_arr);//递归排序左半部分 
  49.   $right_arr= QSort($right_arr);//递归排序右半部份 
  50.   returnarray_merge($left_arr,array($pivot),$right_arr);//合并左半部分、枢轴、右半部分 
  51. echo"快速排序:"
  52. echoimplode(' ',QSort($arr))."<br>"
  53.   
  54. //选择排序(不稳定) 
  55. functionSelectSort($arr){ 
  56.   $length=count($arr); 
  57.   if($length<=1){ 
  58.     return$arr
  59.   } //phpfensi.com 
  60.   for($i=0;$i<$length;$i++){ 
  61.     $min=$i
  62.     for($j=$i+1;$j<$length;$j++){ 
  63.       if($arr[$j]<$arr[$min]){ 
  64.         $min=$j
  65.       } 
  66.     } 
  67.     if($i!=$min){ 
  68.       $tmp=$arr[$i]; 
  69.       $arr[$i] =$arr[$min]; 
  70.       $arr[$min] =$tmp
  71.     } 
  72.   } 
  73.   return$arr
  74. echo"选择排序:"
  75. echoimplode(' ',SelectSort($arr))."<br>"
  76.   
  77. //插入排序 
  78. functionInsertSort($arr){ 
  79.   $length=count($arr); 
  80.   if($length<=1){ 
  81.     return$arr
  82.   } 
  83.   for($i=1;$i<$length;$i++){ 
  84.     $x=$arr[$i]; 
  85.     $j=$i-1; 
  86.     while($x<$arr[$j] j="">=0){<!--$arr[$j]--> 
  87.       $arr[$j+1] =$arr[$j]; 
  88.       $j--; 
  89.     } 
  90.     $arr[$j+1] =$x
  91.   } 
  92.   return$arr
  93. echo'插入排序:' 
  94. echoimplode(' ',InsertSort($arr))."<br>"
  95. //--------------------------------------- 
  96. //       常用查找算法 
  97. //--------------------------------------- 
  98. //二分查找 
  99. functionbinary_search($arr,$low,$high,$key){ 
  100.   while($low<=$high){ 
  101.     $mid=intval(($low+$high)/2); 
  102.     if($key==$arr[$mid]){ 
  103.       return$mid+1; 
  104.     }elseif($key<$arr[$mid]){ 
  105.       $high=$mid-1; 
  106.     }elseif($key>$arr[$mid]){ 
  107.       $low=$mid+1; 
  108.     } 
  109.   } 
  110.   return-1; 
  111. $key= 6; 
  112. echo"二分查找{$key}的位置:"
  113. echobinary_search(QSort($arr),0,8,$key); 
  114.   
  115. //顺序查找 
  116. functionSqSearch($arr,$key){ 
  117.   $length=count($arr); 
  118.   for($i=0;$i<$length;$i++){ 
  119.     if($key==$arr[$i]){ 
  120.       return$i+1; 
  121.     } 
  122.   } 
  123.   return-1; 
  124. $key= 8; 
  125. echo"<br>顺序常规查找{$key}的位置:"
  126. echoSqSearch($arr,$key); 
  127. //--------------------------------------- 
  128. //       常用数据结构 
  129. //--------------------------------------- 
  130. //线性表的删除(数组实现) 
  131. functiondelete_array_element($arr,$pos){ 
  132.   $length=count($arr); 
  133.   if($pos<1 pos="">$length){<!--1--> 
  134.     return"删除位置出错!"
  135.   } 
  136.   for($i=$pos-1;$i<$length-1;$i++){ 
  137.     $arr[$i] =$arr[$i+1]; 
  138.   } 
  139.   array_pop($arr); 
  140.   return$arr
  141. $pos= 3; 
  142. echo"<br>除第{$pos}位置上的元素后:"
  143. echoimplode(' ',delete_array_element($arr,$pos))."<br>"
  144.   
  145. /** 
  146.  * Class Node 
  147.  * PHP模拟链表的基本操作 
  148.  */ 
  149. classNode{ 
  150.   public$data='' 
  151.   public$next= null; 
  152. //初始化 
  153. functioninit($linkList){ 
  154.   $linkList->data = 0;//用来记录链表长度 
  155.   $linkList->next = null; 
  156. //头插法创建链表 
  157. functioncreateHead(&$linkList,$length){ 
  158.   for($i=0;$i<$length;$i++){ 
  159.     $newNode=newNode(); 
  160.     $newNode->data =$i
  161.     $newNode->next =$linkList->next;//因为PHP中对象本身就是引用所以不用再可用“&” 
  162.     $linkList->next =$newNode
  163.     $linkList->data++; 
  164.   } 
  165. //尾插法创建链表 
  166. functioncreateTail(&$linkList,$length){ 
  167.   $r=$linkList
  168.   for($i=0;$i<$length;$i++){ 
  169.     $newNode=newNode(); 
  170.     $newNode->data =$i
  171.     $newNode->next =$r->next; 
  172.     $r->next =$newNode
  173.     $r=$newNode
  174.     $linkList->data++; 
  175.   } 
  176. //在指定位置插入指定元素 
  177. functioninsert($linkList,$pos,$elem){ 
  178.   if($pos<1 pos="">$linkList->data+1){<!--1--> 
  179.     echo"插入位置错误!"
  180.   } 
  181.   $p=$linkList
  182.   for($i=1;$i<$pos;$i++){ 
  183.     $p=$p->next; 
  184.   } 
  185.   $newNode=newNode(); 
  186.   $newNode->data =$elem
  187.   $newNode->next =$p->next; 
  188.   $p->next =$newNode
  189. //删除指定位置的元素 
  190. functiondelete($linkList,$pos){ 
  191.   if($pos<1 pos="">$linkList->data+1){<!--1--> 
  192.     echo"位置不存在!"
  193.   } 
  194.   $p=$linkList
  195.   for($i=1;$i<$pos;$i++){ 
  196.     $p=$p->next; 
  197.   } 
  198.   $q=$p->next; 
  199.   $p->next =$q->next; 
  200.   unset($q); 
  201.   $linkList->data--; 
  202. //输出链表数据 
  203. functionshow($linkList){ 
  204.   $p=$linkList->next; 
  205.   while($p!=null){ 
  206.     echo$p->data." "
  207.     $p=$p->next; 
  208.   } 
  209.   echo'<br>' 
  210.   
  211. $linkList=newNode(); 
  212. init($linkList);//初始化 
  213. createTail($linkList,10);//尾插法创建链表 
  214. show($linkList);//打印出链表 
  215. insert($linkList,3,'a');//插入 
  216. show($linkList); 
  217. delete($linkList,3);//删除 
  218. show($linkList); 
  219.   
  220. /** 
  221.  * Class Stack 
  222.  * 用PHP模拟顺序栈的基本操作 
  223.  */ 
  224. classStack{ 
  225.   //用默认值直接初始化栈了,也可用构造方法初始化栈 
  226.   private$top= -1; 
  227.   private$maxSize= 5; 
  228.   private$stack=array(); 
  229.   
  230.   //入栈 
  231.   publicfunctionpush($elem){ 
  232.     if($this->top >=$this->maxSize-1){ 
  233.       echo"栈已满!<br>"
  234.       return
  235.     } 
  236.     $this->top++; 
  237.     $this->stack[$this->top] =$elem
  238.   } 
  239.   //出栈 
  240.   publicfunctionpop(){ 
  241.     if($this->top == -1){ 
  242.       echo"栈是空的!"
  243.       return
  244.     } 
  245.     $elem=$this->stack[$this->top]; 
  246.     unset($this->stack[$this->top]); 
  247.     $this->top--; 
  248.     return$elem
  249.   } 
  250.   //打印栈 
  251.   publicfunctionshow(){ 
  252.     for($i=$this->top;$i>=0;$i--){ 
  253.       echo$this->stack[$i]." "
  254.     } 
  255.     echo"<br>"
  256.   } 
  257.   
  258. $stack=newStack(); 
  259. $stack->push(3); 
  260. $stack->push(5); 
  261. $stack->push(8); 
  262. $stack->push(7); 
  263. $stack->push(9); 
  264. $stack->push(2); 
  265. $stack->show(); 
  266. $stack->pop(); 
  267. $stack->pop(); 
  268. $stack->pop(); 
  269. $stack->show(); 
  270.   
  271. /** 
  272.  * Class Deque 
  273.  * 使用PHP实现双向队列 
  274.  */ 
  275. classDeque{ 
  276.   private$queue=array(); 
  277.   publicfunctionaddFirst($item){//头入队 
  278.     array_unshift($this->queue,$item); 
  279.   } 
  280.   publicfunctionaddLast($item){//尾入队 
  281.     array_push($this->queue,$item); 
  282.   } 
  283.   publicfunctionremoveFirst(){//头出队 
  284.     array_shift($this->queue); 
  285.   } 
  286.   publicfunctionremoveLast(){//尾出队 
  287.     array_pop($this->queue); 
  288.   } 
  289.   publicfunctionshow(){//打印 
  290.     <a href="/tags.php/foreach/" target="_blank">foreach</a>($this->queueas$item){ 
  291.       echo$item." "
  292.     } 
  293.     echo"<br>"
  294.   } 
  295. $deque=newDeque(); 
  296. $deque->addFirst(2); 
  297. $deque->addLast(3); 
  298. $deque->addLast(4); 
  299. $deque->addFirst(5); 
  300. $deque->show(); 
  301.   
  302. //PHP解决约瑟夫环问题 
  303. //方法一 
  304. functionjoseph_ring($n,$m){ 
  305.   $arr= range(1,$n); 
  306.   $i= 0; 
  307.   while(count($arr)>1){ 
  308.     $i=$i+1; 
  309.     $head=array_shift($arr); 
  310.     if($i%$m!= 0){//如果不是则重新压入数组 
  311.       array_push($arr,$head); 
  312.     } 
  313.   } 
  314.   return$arr[0]; 
  315. //方法二 
  316. functionjoseph_ring2($n,$m){ 
  317.   $r= 0; 
  318.   for($i=2;$i<=$n;$i++){ 
  319.     $r= ($r+$m)%$i
  320.   } 
  321.   return$r+ 1; 
  322. echo"<br>".joseph_ring(60,5)."<br>"
  323. echo"<br>".joseph_ring2(60,5)."<br>"

Tags: PHP算法 PHP数据结构

分享到: