0

二分探索木を使用して文字列のマップのように動作するクラスを実装する必要があります。これは私が実装したクラスです：

template<class T>
class StringMapper {
private:
    // Pair
    struct Pair {
        std::string el1;
        T el2;
    };

    // Nod
    struct Node {
        Pair* data;
        Node* left;
        Node* right;
        Node()
        {
            data = new Pair;
        }
        ~Node()
        {
            delete data;
        }
        int nod_size()
        {
             // code here
        }
    };
    Node* root;
public:
    StringMapper()
    {
        root = 0;
    }
    ~StringMapper() {}
    void insert(std::string from, const T& to)
    {
        // code here
    }

    bool find(std::string from,const T& to) const
    {
        return find(root, to);
    }

    bool find(Node* node, const T& value) const
    {
        // code here
    }

    bool getFirstPair(std::string& from, T& to)
    {
        if(root != 0)
        {
            from = root->data->el1;
            to = root->data->el2;
            return true;
        }
        return false;
    }
    bool getNextPair(std::string& from, T& to)
    {
        if(root != 0)
        {

        }
        return false;
    }

    int size() const
    {
        return root->nod_size();
    }
};

正直なところ、関数の実装方法がわかりませんgetNextPair()。
誰かが私を助けてくれるなら、私はそれをいただければ幸いです。

4

2 に答える 2

1

インターフェイスは内部イテレータです。反復のどこにいるかへのある種のポインターを保持し、それをgetFirstPair（）で設定する必要があります。

これを追加すると、getNextPair（）は次のものに移動します。これを行うのは少し難しいですが、それはあなたの任務なので、私はあなたに任せます。

実際std::mapには、外部イテレータを使用します。これにより、反復の状態がデータ構造から分離されます。主な利点は、複数の反復を同時に実行できることです。

于 2011-03-06T21:22:57.970 に答える
1

getNextPairのアルゴリズムをスローするだけでなく、「現在の」ペアを指すある種の内部イテレータを保持する必要があります。それを取得したら、次のペアのアルゴリズムを理解するために、いくつかのノードを含むツリーを作成し、ツリー内の任意のノードを指定して、ツリー内の次のノードを見つける方法を確認します。

于 2011-03-06T21:46:31.097 に答える