コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > バックエンド開発 > PHPチュートリアル > PHP の 2 つのマッピング方法 (リンク リストとバイナリ ツリー) についての簡単な説明

PHP の 2 つのマッピング方法 (リンク リストとバイナリ ツリー) についての簡単な説明

青灯夜游
リリース： 2023-04-09 19:20:01
転載
3506 人が閲覧しました

この記事では、PHP がリンク リストまたはバイナリ ツリーを使用してマッピングを実装する方法を紹介します。一定の参考値があるので、困っている友達が参考になれば幸いです。

PHP の 2 つのマッピング方法 (リンク リストとバイナリ ツリー) についての簡単な説明

[推奨学習: 「PHP ビデオ チュートリアル 」]

マッピング

マップまたは投影は、数学および関連分野では関数と同一視されることがよくあります。これに基づいて、部分マッピングは部分関数に相当し、完全マッピングは完全関数に相当します。

マップは、キーと値のペアにアクセスするために使用されるデータ構造 (キー、値) です。1 つのキーは 1 つの値にのみ対応し、キーを繰り返すことはできません。

実装

マッピングの実装は、リンク リストまたはバイナリ ツリーを使用して実装できます。

PHP の 2 つのマッピング方法 (リンク リストとバイナリ ツリー) についての簡単な説明

リンク リストの実装: 

<?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(&#39;cannot found key&#39;);
    }


    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(&#39;key is not exist&#39;);

        $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(&#39;sun&#39;,111); //O(n)
        $dict->set(&#39;sun&#39;,222);
        $dict->set(&#39;w&#39;,111);
        $dict->set(&#39;k&#39;,111);
        var_dump($dict->get(&#39;w&#39;));   //O(n)
        var_dump($dict->isExist(&#39;v&#39;));   //O(n)
        var_dump($dict->delete(&#39;sun&#39;));    //O(n)
        var_dump($dict->getSize());
        
/******************************************/
//111
//false
//true
//2
ログイン後にコピー

バイナリ ツリーの実装 

<?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(&#39;empty&#39;);
        $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(&#39;this key not exist&#39;);
    }

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

            //替换当前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(&#39;empty&#39;);

//        $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(&#39;this key not exist&#39;);
    }

    public function selectMin( $node ){
        while($node->left){

            $node = $node->left;
        }
        return $node;
    }


    public function selectMax( $node ){
        while($node->right){

            $node = $node->right;
        }
        return $node;
    }
}
ログイン後にコピー

複雑さの分析

リンク リスト O(n)

二分探索木 O(log n)

プログラミング関連の知識については、プログラミング ビデオをご覧ください。 ！

以上がPHP の 2 つのマッピング方法 (リンク リストとバイナリ ツリー) についての簡単な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル：
php マッピング
ソース：cnblogs.com
前の記事：PHP に受け継がれた生活のさまざまな側面を数えてみましょう 次の記事：この世の最後の旅
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
URL パラメータから取得した PHP 配列が期待どおりに動作しない カテゴリ ID を含む URL パラメータがあり、それを次のような配列として扱いたいと考えています: http://example.com?cat[]=3,9,13 PHP では、...
から 2024-04-06 22:09:02
0
1
1428
ApacheのどこにCustomLogディレクティブを配置すればよいですか 私はphp:7.2-apachedockerを使用しています。ヘルスチェック URL ログイン アクセス ログを無効にする必要があります。このリンクに基づいて、Customlog ...
から 2024-04-06 22:03:59
0
1
990
戻り値の変数の形式は何ですか? 私はphpの初心者です。コードを見つけました: if($x<time()){return[false,'error'];} ロジックや変数は重要ではありませんが、[false...
から 2024-04-06 21:55:20
0
1
778
opentbs を使用して odt ファイルを生成するときに発生する問題: 同じキーの値が別の列ではなく同じ行に表示されます。 PHPでodtを作成するためにOpenTbsというライブラリを使っていますが、列と行が動的に生成されるので利用しています。行と列の作成方法は知っていますが、それらを整理する方法がわ...
から 2024-04-06 20:18:18
0
1
483
ループするために MySQL の結果を ID ごとにグループ化する mysqlにフライトデータを含むテーブルがあります。 codeigniter3Journey_idair_idFlightDurationout_or_inflightdurati...
から 2024-04-06 17:27:56
0
1
406
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート