主頁 > 知識庫 > php實現(xiàn)映射操作實例詳解

php實現(xiàn)映射操作實例詳解

熱門標(biāo)簽:青白江地圖標(biāo)注 銅川電話機(jī)器人價格 聊城電話外呼系統(tǒng)公司 德陽中江如何申請400開頭電話 AI電話機(jī)器人OEM貼牌 智能電話機(jī)器人好公司門薩維 辦理重慶400電話 江蘇電商外呼系統(tǒng)運營商 沛縣400電話辦理

本文實例講述了php實現(xiàn)映射操作。分享給大家供大家參考,具體如下:

映射

映射,或者射影,在數(shù)學(xué)及相關(guān)的領(lǐng)域經(jīng)常等同于函數(shù)?;诖耍糠钟成渚拖喈?dāng)于部分函數(shù),而完全映射相當(dāng)于完全函數(shù)。

映射(Map)是用于存取鍵值對的數(shù)據(jù)結(jié)構(gòu)(key,value),一個鍵只能對應(yīng)一個值且鍵不能重復(fù)。

實現(xiàn)

映射的實現(xiàn)方式可以使用鏈表或二叉樹實現(xiàn)。

鏈表實現(xiàn):

?php
/**
 * 接口 字典
 * Interface Dict
 * @package app\models
 */
Interface Dict
{
  public function set( $key , $value );
  public function get( $key );
  public function isExist( $key );
  public function delete($key);
  public function getSize();
}
class DictLinkList implements Dict
{
  protected $size=0;
  public $key;
  public $value;
  public $next;
  public function __construct($key=null,$value=null,$next=null)
  {
    $this->key = $key;
    $this->value = $value;
    $this->next = $next;
  }
  public function set($key,$value){
    $node = $this;
    while( $node  $node->next ){
      if( $node->next->key==$key ){
        $node->next->value = $value;
        return $node->next;
      }
      $node = $node->next;
    }
    $node->next = new self($key,$value,$node->next);
    $this->size++;
    return $node->next;
  }
  public function get($key){
    $node = $this;
    while($node){
      if( $node->key ==$key ){
        return $node->value;
      }
      $node = $node->next;
    }
    throw new \Exception('cannot found key');
  }
  public function isExist($key)
  {
    $node = $this;
    while($node){
      if( $node->key ==$key ){
        return true;
      }
      $node = $node->next;
    }
    return false;
  }
  public function delete($key)
  {
    if( $this->size==0)
      throw new \Exception('key is not exist');
    $node = $this;
    while($node->next){
      if( $node->next->key == $key ){
        $node->next = $node->next->next;
        $this->size--;
        break;
      }
      $node = $node->next;
    }
    return $this;
  }
  public function getSize()
  {
    return $this->size;
  }
}

測試:

?php
    $dict = new DictLinkList();
    $dict->set('sun',111); //O(n)
    $dict->set('sun',222);
    $dict->set('w',111);
    $dict->set('k',111);
    var_dump($dict->get('w'));  //O(n)
    var_dump($dict->isExist('v'));  //O(n)
    var_dump($dict->delete('sun'));  //O(n)
    var_dump($dict->getSize());
/******************************************/
//111
//false
//true
//2

二叉樹實現(xiàn)

?php
class DictBtree implements Dict
{
  public $key;
  public $value;
  public $left;
  public $right;
  private $size;
  public function __construct($key=null,$value=null)
  {
    $this->key = $key;
    $this->value = $value;
    $this->left = null;
    $this->right = null;
    $this->size = 0;
  }
  public function set( $key , $value ){
    if( $this->size ==0 ){
      $node = new static( $key,$value );
      $this->key = $node->key;
      $this->value = $node->value;
      $this->size++;
    }else{
      $node = $this;
      while($node){
        if( $node->key == $key ){
          $node->value = $value;
          break;
        }
        if($node->key>$key){
          if($node->left==null){
            $node->left = new static( $key,$value );
            $this->size++;
            break;
          }
          $node = $node->left;
        }else{
          if($node->right==null){
            $node->right = new static( $key,$value );
            $this->size++;
            break;
          }
          $node = $node->right;
        }
      }
    }
    return $this;
  }
  public function get( $key ){
    if( $this->size ==0 )
      throw new \Exception('empty');
    $node = $this;
    while($node) {
      if ($node->key == $key) {
        return $node->value;
      }
      if ($node->key > $key) {
        $node = $node->left;
      } else {
        $node = $node->right;
      }
    }
    throw new \Exception('this key not exist');
  }
  public function isExist( $key ){
    if( $this->size ==0 )
      return false;
    $node = $this;
    while($node) {
      if ($node->key == $key) {
        return true;
      }
      if ($node->key > $key) {
        $node = $node->left;
      } else {
        $node = $node->right;
      }
    }
    return false;
  }
  public function delete($key){
    //找到元素,尋找元素左邊最小元素
    $node = $this->select($key);
    if( $node->right!=null ){
      $node1 = $node->selectMin($node->right);
      //替換當(dāng)前node
      $node->key = $node1->key;
      $node->value = $node1->value;
      //刪除$node->right最小元素,獲取最終元素賦給$node->right
      $nodeMin = $this->deleteMin($node->right);
      $node->right = $nodeMin;
    }else{
      $node1 = $node->selectMax($node->left);
      $node->key = $node1->key;
      $node->value = $node1->value;
      $nodeMax = $this->deleteMax($node->left);
      $node->left = $nodeMax;
    }
    return $this;
  }
  protected function deleteMin( $node ){
//    if( $this->size ==0 )
//      throw new \Exception('empty');
//    $prev = new static();
//    $prev->left = $node;
//    while($prev->left->left!=null){
//
//      $prev = $prev->left;
//    }
//    $prev->left = $prev->left->right;
    if( $node->left==null ){
      $rightNode = $node->right;
      $node->right = null;
      $this->size--;
      return $rightNode;
    }
    $node->left = $this->deleteMin($node->left);
    return $node;
  }
  protected function deleteMax($node){
    if( $node->right==null ){
      $leftNode = $node->left;
      $node->left = null;
      $this->size--;
      return $leftNode;
    }
    $node->right = $this->deleteMax($node->right);
    return $node;
  }
  public function getSize(){
    return $this->size;
  }
  public function select($key){
    $node = $this;
    while($node){
      if($node->key==$key){
        return $node;
      }
      if ($node->key > $key) {
        $node = $node->left;
      } else {
        $node = $node->right;
      }
    }
    throw new \Exception('this key not exist');
  }
  public function selectMin( $node ){
    while($node->left){
      $node = $node->left;
    }
    return $node;
  }
  public function selectMax( $node ){
    while($node->right){
      $node = $node->right;
    }
    return $node;
  }
}

復(fù)雜度分析

鏈表 O(n)

二分搜索樹 O(log n)

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運算技巧總結(jié)》

希望本文所述對大家PHP程序設(shè)計有所幫助。

您可能感興趣的文章:
  • 詳解PHP的Laravel框架中Eloquent對象關(guān)系映射使用
  • ThinkPHP中公共函數(shù)路徑和配置項路徑的映射分析
  • 回答PHPCHINA上的幾個問題:URL映射
  • 解密ThinkPHP3.1.2版本之模塊和操作映射
  • PHP實現(xiàn)路由映射到指定控制器
  • 淺析php設(shè)計模式之?dāng)?shù)據(jù)對象映射模式
  • PHP面向?qū)ο笾I(lǐng)域模型+數(shù)據(jù)映射器實例(分析)
  • 老生常談PHP面向?qū)ο笾畼?biāo)識映射
  • PHP實現(xiàn)的數(shù)據(jù)對象映射模式詳解
  • PHP數(shù)據(jù)對象映射模式實例分析

標(biāo)簽:濟(jì)寧 山南 三亞 南寧 赤峰 鷹潭 迪慶 烏魯木齊

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《php實現(xiàn)映射操作實例詳解》,本文關(guān)鍵詞  php,實現(xiàn),映射,操作,實例,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《php實現(xiàn)映射操作實例詳解》相關(guān)的同類信息!
  • 本頁收集關(guān)于php實現(xiàn)映射操作實例詳解的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章