3

最近、面接に行ったところ、「STL の連結リスト、スタック、キュー、ツリー、文字列、文字配列などの追加のストレージを使用せずに、以下の二重連結リストが回文であるかどうかを確認してほしい」と依頼されました。しかし、完璧な解決策を提供することはできませんでした。

以下は、双方向にリンクされたリストの画像です。

二重連結リストの例

これは宿題の質問ではなく、共有すべき解決策を見つけるための質問です。

4

5 に答える 5

4

ここでの問題は、要素が複数の文字になる可能性のある自然イテレータがあるにもかかわらず、一連の文字に対して操作を実行したいということです。そこで、 を使用して、必要な方法で動作する別の反復子型を定義しますboost::iterator_facade。(多くの場合、この種のことboost::iterator_adaptorはさらに便利ですが、この場合は役に立ちません。)

この図は生の C ライクな構造体とポインターのセットアップを示しているので、カスタムの双方向リンク リストは次のように定義されていると仮定します。

struct list_node {
    list_node* prev;
    list_node* next;
    const char* data;
};

class LinkedList {
public:
    list_node* head() const;
    list_node* tail() const;
    // ...
};

カスタム反復子クラスには、list_node*ポインターと配列の要素へのポインターが含まれている必要がありますchar。

#include <boost/iterator_facade.hpp>
class ListCharIter :
    public boost::iterator_facade<
        ListCharIter,                      // Derived class for CRTP
        const char,                        // Element type
        std::bidirectional_iterator_tag >  // Iterator category
{
public:
    ListCharIter() : m_node(nullptr), m_ch(nullptr) {}

    // "Named constructors":
    static ListCharIter begin(const LinkedList& listobj);
    static ListCharIter end(const LinkedList& listobj);

private:
    list_node* m_node;
    const char* m_ch;
    ListCharIter(list_node* node, const char* where)
        : m_node(node), m_ch(where) {}

    // Methods iterator_facade will use:
    char dereference() const;
    bool equal(const ListCharIter& other) const;
    void increment();
    void decrement();
    // And allow boost to use them:
    friend class boost::iterator_core_access;
};

末尾イテレータの場合のみ、m_ch最後のノードの終端を指すことができます'\0'。要素を持たないリストの特殊なケースでは、開始と終了の両方で逆参照できない単一の反復子に対して、両方のメンバーを null に設定します。

inline ListCharIter ListCharIter::begin(const LinkedList& listobj)
{
    list_node* node = listobj.head();
    const char* str = nullptr;
    if (node) {
        str = node->data;
    }
    return ListCharIter(node, str);
}

inline ListCharIter ListCharIter::end(const LinkedList& listobj)
{
    list_node* node = listobj.tail();
    const char* nul = nullptr;
    if (node) {
        nul = node->data;
        while (*nul != '\0') ++nul; // Find the '\0'.
    }
    return ListCharIter(node, nul);
}

dereference()そしてequal()自明です：

inline char ListCharIter::dereference() const
{ return *m_ch; }

inline bool ListCharIter::equal(const ListCharIter& other) const
{ return this->m_node == other.m_node && this->m_ch == other.m_ch; }

そして最後に、前進または後退するための基本的な考え方は、m_chそれが理にかなっている場合にのみ変更するか、m_nodeそうでない場合に変更することです。

inline void ListCharIter::increment()
{
    ++m_ch;
    // If m_node->next is null, we're advancing
    // past the end of the entire list.
    while (*m_ch == '\0' && m_node->next) {
        m_node = m_node->next;
        m_ch = m_node->data; // Start of new node.
        // while loop repeats if m_node contains "".
    }
}

inline void ListCharIter::decrement()
{
    if (m_ch == m_node->data) {
        // Already at the start of this node.
        do {
            m_node = m_node->prev;
            m_ch = m_node->data; // Start of new node.
            // while loop repeats if m_node contains "".
        } while (*m_ch == '\0');

        // Find the char before the terminating nul.
        while (m_ch[1] != '\0') ++m_ch;
    } else {
        --m_ch;
    }
}

これで、通常の回文アルゴリズム (および他の多くのアルゴリズム) でそのカスタム イテレータを使用できます。

template<typename BidirIter>
bool is_palindrome(BidirIter start, BidirIter stop)
{
    for (;;) {
        if (start == stop) return true;
        if (*start != *stop) return false;
        ++start;
        if (start == stop) return true;
        --stop;
    }
}

bool is_palindrome(const LinkedList& the_list)
{
    return is_palindrome(ListCharIter::begin(the_list),
                         ListCharIter::end(the_list));
}
于 2013-09-24T16:40:07.220 に答える
3

start と end の 2 つの反復子を宣言します。次に、リストをループして、それらを同時にデクリメント/インクリメントし、各ステップで比較します。注: このアルゴリズムは、演算子が適切にオーバーライドされていることを前提としていますが、数値リストだけでなく、あらゆる種類のリストに対しても機能します。

for(int i=0;i<list.size()/2;i++){
    if(*start!=*end) return false;
    start++;
    end--;
}
return true;

ここで重要なのは、実際にリストを直接操作するのではなく、反復子を使用していることです。

于 2013-09-24T14:53:40.560 に答える
3 
template<typename List>
bool isPalindrome(List const &list) {
   auto b = list.begin();
   auto e = list.end();
   while (b != e) {
     --e;
     if (b == e) // for lists with exactly 1 or an even number of elements
        break;
     if (*b != *e)
       return false;
     ++b;
   }
   return true;
}

>リスト反復子は (ほとんどの実装で) ランダム アクセスではないため、orを使用することはできません>=。したがって、等しいかどうかしか比較できません。 std::distanceはオプションですが、randomaccess 以外のイテレータの場合は、大量のインクリメントを行うだけで、処理が遅くなります。代わりに、ループの途中にあるチェックで大なりケースが処理されるため、等値比較のみを使用して関数全体を記述できます。

于 2013-09-24T15:08:17.923 に答える