競技プログラミング風 C++問題集【第3回】


目次

双方向リンクリスト(難易度:★★★☆☆)

問題

下図のように、型Tの要素を保持する各ノードが前後にリンクされたデータ構造を「双方向リンクリスト」と呼ぶ。

競技プログラミング風C++問題集【第3回】_01

リストに要素が存在しない場合でも、ノードを統一的に取り扱うために、ダミーのノードを保持している(下図参照)。

競技プログラミング風C++問題集【第3回】_02

上記を理解した上で、テストコードの ToDo 部分にコードを記述し、以下を実装しなさい。

1.prev, next を相互にリンクする関数 void reLink(Node* prev, Node* nexe)
2.T型要素を持つ双方向リンクリストクラス DblLnkList<T>() のコンストラクタ
3.T型の要素を持つノードをリスト末尾に追加するメンバ関数 void push_back(const T&)
4.要素数を返すメンバ関数 size_t size()

#include <iostream>       //  標準入出力ライブラリ
#include <string>
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
template<typename T>
struct Node {
public:
    Node(const T& body = T())
        : m_body(body)
    {
        m_prev = m_next = nullptr;
    }
public:
    Node<T> *m_prev;    //  直前ノードへのポインタ
    Node<T> *m_next;    //  直後ノードへのポインタ
    T       m_body;     //  ノード要素
};
template<typename T>
void reLink(Node<T>* prev, Node<T>* next) {     //  prev と next を双方向にリンクする
    //  DoDo: ここに prev と next を双方向にリンクするコードを記述
}

template<typename T>
class DblLnkList {  //  双方向リンクリスト クラス
public:
    DblLnkList() {   //  コンストラクタ
        //  ToDo: ここに双方向リンクリスト初期化コードを記述
    }
    void    push_back(const T& body) {
        //  ToDo: ここにコードを追加し、要素bodyを持ったノードをリスト末尾に追加
    }
    size_t  size() const {
        //  ToDo: ここに要素数を返すコードを記述
        return 0;
    }
private:
    Node<T>*    m_dummy;    //  ダミーノードへのポインタ
    size_t      m_size;     //  要素数
    friend int main();
};
int main() {
    //  relink のテスト
    Node<string> n1, n2;
    reLink<string>(&n1, &n2);
    DO_TEST(n1.m_prev == nullptr);
    DO_TEST(n1.m_next == &n2);
    DO_TEST(n2.m_prev == &n1);
    DO_TEST(n2.m_next == nullptr);
    //  コンストラクタのテスト
    DblLnkList<string> lst;
    DO_TEST( lst.m_dummy != nullptr );
    auto* dummy = lst.m_dummy;
    DO_TEST( dummy->m_next == dummy );
    DO_TEST( dummy->m_prev == dummy );
    DO_TEST( lst.m_size == 0 );
    //  push_back のテスト
    lst.push_back("abc");
    DO_TEST( lst.m_size == 1 );
    lst.push_back("xyzzz");
    DO_TEST( lst.m_size == 2 );
    auto* first = dummy->m_next;
    DO_TEST(first->m_body == "abc");
    auto* last = dummy->m_prev;
    DO_TEST(last->m_body == "xyzzz");
    //  size() のテスト
    DO_TEST( lst.size() == 2 );
    lst.push_back("314");
    DO_TEST( lst.size() == 3 );
    //
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 C++問題集【第16回】

目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

競技プログラミング風 C++問題集【第15回】

目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

競技プログラミング風 C++問題集【第14回】

目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第13回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

競技プログラミング風 C++問題集【第12回】

目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第11回】

目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

競技プログラミング風 C++問題集【第10回】

目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

競技プログラミング風 C++問題集【第9回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

競技プログラミング風 C++問題集【第8回】

目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

競技プログラミング風 C++問題集【第7回】

目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP