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

作者:袖梨 2022-06-24

 

 代码如下复制代码

/**

 * 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)."
";

//---------------------------------------

//       常用排序算法

//---------------------------------------

//冒泡排序

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))."
";

 

//快速排序

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))."
";

 

/**

 * 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){

    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);

 

/**

 * Class Stack

 * 用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();

 

/**

 * 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(){//打印

    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)."
";

 

相关文章

精彩推荐