-1

テンプレート化された連結リストに入っている値を再帰関数(再帰メソッド)を使って見つけたいです。自分が悩んでいるのは再起関数の仮引数です。よく見る解決策は連結リストのheadを再起関数の呼び出しで渡す方法です。しかし、今回自分がやりたいことは再起関数をその関数外で呼び出すときに探したい値だけを渡す方法です。以下のコードでは値を探す再起関数(findValue)でエラーが出てしまいます。その理由としてはこのように出てきました:Invalid use of non-static data member 'head'
つまり、headが非静的メンバなので仮引数に使用できないということだと思います。

テンプレート化しているのでいろいろなデータタイプでその値があるかを探し、見つかればtrue, なければfalseを返したいです。再起関数、findValueの仮引数currentLinkをheadに設定することができればいけるとおもったのですが、これはできないとエラーがでてしまいました。
このあたりに詳しい方よろしくお願いします。

追記:教授からヒントがありました。リストクラスのプライベートに新たなメソッドをつくり、このメソッドがfindValueの仮引数内で呼び出されることにより、currentLink=headの設定がされ、この再起関数が機能するらしいです。つまり、このfindValueの仮引数内で呼び出されるメソッドをつくれればうまくいくと思います。わかりそうな方よろしくお願いします。

List.h

template <typename T>
class Link
{
private:
    T value;
    Link* next;
public:
    //constructor
    Link(T value, Link* next = nullptr): value(value), next(next){}
    //destructor
    virtual ~Link(){}
    //return value
    T getValue(){return this->value;}
    //return next
    Link* getNext(){return this->next;}
    //set next
    void setNext(Link* next){this->next = next;}
};

template <typename T>
class List
{
private:
    Link<T>* head;
public:
    List():head(nullptr){}
    //virtual ~List();
    void addHead(T value)
    {
        Link<T>* newLink;
        newLink = new Link<T>(value);
        newLink->setNext(head);
        head = newLink;
    }

  

    T getHead()
    {
       
        return head->getValue();
    }

    bool findValue(T value, Link<T>* currentLink = head)
    {
        bool find = false;

        if(currentLink == nullptr)
        {
            return false;
        }
        else if (currentLink->getValue() == value)
        {
            find = true;
        }
        else
        {
            find = findValue(value, currentLink->getNext());
        }
        return find;
    }

};

main.cpp

#include <iostream>
#include "List.h"

using namespace std;

int main() {

    int size = 5;
    List<int> numbers;
    for(int i = 0; i < size; i++)
    {
        numbers.addHead(i);
    }

    if(numbers.findValue(2) == true)
    {
        cout << "find" << endl;
    }
    else
    {
        cout << "not found" << endl;
    }
    return 0;
}
6
  • おそらくテンプレート化されていない処理の記事がこちらでしょう。Search an element in a Linked List (Iterative and Recursive) これを参考に移植してみてはどうでしょう? あとは再帰処理ではない記事とかも。Linked List Template and Binary Search Tree
    – kunif
    2021年5月29日 12:03
  • 記事の提供ありがとうございます。最初の記事は再起関数を呼び出すときにheadを渡しています。このheadを呼び出し時に渡さず、探したい値だけを渡す方法を探しています。この記事を読みよい点を自分のコードにもいかせそうですが、自分のやりたいこととは少し違っています。もし、なにか思い当たることがありましたら、ぜひともコメントください。よろしくお願いします。 2021年5月29日 12:27
  • この記事が応用できるのでは? デフォルト引数
    – kunif
    2021年5月29日 12:43
  • そうです。これです。引数のデフォルト値をやりたいです。情報提供ありがとうございます。しかし、headをデフォルト値で渡そうとするとheadは非静的なメンバのためデフォルト値にとして使えませんと出てきてしまいます。なにかよい解決策ないでしょうか。 2021年5月29日 13:11
  • 解決策を発見いたしました。記事の提供ありがとうございました。提供してくださった記事に関連した記事を調べていたところ再帰的に連結リストのリンクをdeleteするという記事を見つけその方法を自分の目的に当てはめてみました。本当にありがとうございました。 2021年5月29日 13:29

2 件の回答 2

0

解決策を発見いたしました。やろうとしていたことは少し的外れみたいでした。

プライベートで上記のfindvalueと似たrecFindValueを定義します。recFindValueの仮引数には探す値、valueと値を探すリンク、currentLinkを設定します。引数のデフォルト値についてコメントで触れていますが、引数のデフォルト値は使いません。そしてほかは上記のfindValueと同じです。

実際のfindValueは何をするかというと、ただ探す値を受け取りそれをrecFindValueに渡し、それに加え連結リストの先頭、headを渡します。つまり、recFindValueを呼び出します。
そして、recFindValueから返ってきた結果をreturnします。

つまり、こういうコードになります。変わっている部分周辺だけここには表示します。

List.h

template <typename T>
class List
{
private:
    Link<T>* head;

    bool recFindValue(T value, Link<T>* currentLink)
    {
        if(currentLink == nullptr)
        {
            return false;
        }
        else if (currentLink->getValue() == value)
        {
            return true;
        }
        else
        {
            return recFindValue(value, currentLink->getNext());
        }

    }
    
public:
    List():head(nullptr){}

    bool findValue(T value)
    {
        return recFindValue(value, head);
    }
}
0

もらったヒントは再帰を主題と考えるとしたら、ちょっと微妙な感じですね。

ヒントに絡むやり方的にはC++では以下のような機能があり、パラメータの違う同名の関数を作れます。
関数のオーバーロード
デフォルト引数にメンバ変数を指定する方法

再帰とは違いますが同じ名前の関数を呼び出しているとは言えます。

bool findValue(T value) // 開始ノードのポインタ無しの関数を定義
{
    return findValue(value, head); // headを開始ノードに指定して下記関数呼び出し
}

bool findValue(T value, Link<T>* currentLink) // デフォルト引数は使わない
{
    if(currentLink == nullptr)
    {
        return false;
    }
    else if (currentLink->getValue() == value)
    {
        return true;
    }
    return findValue(value, currentLink->getNext());
}

再帰の主題を追及する場合は、こちらの記事が参考になるでしょう。
引数にある構造体のポインタにデフォルト値をセットしたい
C++ クラスのデフォルト引数について

デフォルト引数を有効なものでは無い値にして、それが指定されたら本来使いたい初期値を使うわけです。

bool findValue(T value, Link<T>* currentLink = nullptr) // デフォルト引数はnullptrとする
{
    if(currentLink == nullptr) // パラメータがnullptrの場合の処理
    {
        if (head != nullptr) // headがnullptrでないなら開始ノードをheadにする
        {
            currentLink = head;
        }
        else // headがnullptrなら要素は空なのでfalse
        {
            return false;
        }
    }

    if (currentLink->getValue() == value)
    {
        return true;
    }
    else if (currentLink->getNext() == nullptr) // nextがnullptrなら次のノードが無いので終了
    {
        return false;
    }
    return findValue(value, currentLink->getNext()); // 再帰
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。