目次
双方向リンクリスト(難易度:★★★☆☆)
問題
下図のように、型Tの要素を保持する各ノードが前後にリンクされたデータ構造を「双方向リンクリスト」と呼ぶ。
リストに要素が存在しない場合でも、ノードを統一的に取り扱うために、ダミーのノードを保持している(下図参照)。
上記を理解した上で、テストコードの 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++問題集【第4回】
目次 2次元世界の水たまり(難易度:★★★☆☆) 2次元世界の水たまり(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席) […]
コメントなし

競技プログラミング風 C++問題集【第3回】
目次 双方向リンクリスト(難易度:★★★☆☆) 双方向リンクリスト(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。v […]
コメントなし

競技プログラミング風 C++問題集【第1回】
はじめに 今回から4回にわたって「競技プログラミング風 C++問題集」をお届けする。 出題形式は以前の「競技プログラミング風 標準C++ライブラリ入門」と同じだ。 各問題は、「問題文」「テストコード」「ヒント」「解答例」 […]
コメントなし
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |