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

下図のように、型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()
[java] #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;
}
[/java]