C++ 双方向リスト 書いて覚えるための初心者自己中記事
前回は単方向リストについて勉強した。
次は双方向リスト。
単方向リストは次のノードのへのポインタだけだった。
双方向リストは前のノードへのポインタも持っている。
前回使っていた
private: //リストの端(end of list)を表すノード //next に先頭ノードが入れられる Node m_eol;
こいつ。Node m_eol ;
この人は実際には値が入らないノードでした。
ただし、ノードに値を入れたり挿入したり削除したり・・彼がいないと無理でした。
彼のような存在をダミーノードというそうです。
ダミーノードは先頭のノードのポインタを持ちます。
さらに、リスト終端ノードがダミーノードのポインタを持つこともできます。
円になります。
双方向リストでそれをやるそうです。
・・・さて、またドバっとコードが出てきた。
１つずつ考えるか。
template <typename TYPE> class DList { public: struct Node { TYPE value; Node* prev; Node* next; };
private: //リストの端(end of list)を表すノード Node m_eol;
まずノードは双方向リストなので前後のポインタがある。
これは分かる。
DList() { m_eol.prev = m_eol.next = &m_eol; }//前も次も自分 virtual ~DList() { Clear(); }
コンストラクタは、最初だからprevもnextもダミーノード(m_eol)を指すようにしている。前も後ろも自分状態。
//最初のノードを取得 Node* GetFirst() { return m_eol.next; } const Node* GetFirst()const { return m_eol.next; } //最後のノードを取得 Node* GetLast() { return m_eol.prev; } const Node* GetLast()const { return m_eol.prev; } //リストの終端を取得 const Node* Eol() const { return &m_eol; }//終端とはダミーノードのことか
ここら辺はそのままだから大丈夫かな。
//指定したノードの直前に値を挿入 //prev → node → next の順に並ぶようにする Node* Insert(Node* next, const TYPE& value) { assert(next != NULL); Node* node = new Node(); Node* prev = next->prev; node->value = value; node->prev = prev; node->next = next; prev->next = node; next->prev = node; return node; }
渡ってきた引数next は本当のところnext的なものなのかどうか怪しい。
俺にとっては混乱の元。
後述の関数によっては m_eol.next で渡したり &m_eol で渡したりしてるし。
とにかくNode* の何かが渡ってきていて、
assertマクロチェックが入って、
この場限りのNodeポインタ node prev が作られる。
prev には渡ってきたNodeポインタからprev が渡される。
そして作ったnode.value に渡ってきた引数value が入る。
あとnode.prev に渡ってきたprevが入っている作ったprev が入る。
さらにnode.next に渡ってきたnextが入る。
渡ってきたnext->prev が入ったprev->next に今まで色々入れてきたnodeが入る。
・・・・。ちょっと待って。把握できない。
//指定したノードの直前に値を挿入 //prev → node → next の順に並ぶようにする Node* Insert(Node* x_node, const TYPE& value) { assert(x_node != NULL); Node* insert = new Node(); Node* prev = x_node->prev; insert->value = value; insert->prev = prev; insert->next = x_node; prev->next = insert; x_node->prev = insert; return insert; }
名前変えました。ユニークな名前じゃないと無理です。
引数で渡ってきたノードはx_node
挿入するための新作ノードはinsert にしました。
x_nodeの手前にinsertを挿入するってことだよね。
insert のvalueには引数のvalue をいれて、prevとnextにはそれぞれx_nodeのprevとx_node自身を入れると。
手前のノードのnextにはinsertを当てて、
x_nodeのprevにはinsertをあてる。
これならわかる。
最初ので理解できる人は頭良すぎでしょ。
次、
//指定したノードを削除 void Erase(Node* node) { assert(node != NULL); if (node == &m_eol) { return; } Node* prev = node->prev; Node* next = node->next; prev->next = next; next->prev = prev; delete node; }
指定したノードを削除。
削除したら手前と後ろをつなげないとだね。
assertマクロでNULLチェック。if文でダミーノードでないかチェック。
引数で渡ってきた削除予定のノードの前後ノードをそれぞれprev と next に改名。
それぞれを繋げたら、delete。
よし。OK。
//最初の位置に値を挿入 Node* Unshift(const TYPE& value) { return Insert(m_eol.next, value); } //最初のノードを削除 void Shift() { Erase(m_eol.next); } //最後の位置に値を挿入 Node* Push(const TYPE& value) { return Insert(&m_eol, value); } //最後のノードを削除 void Pop() { Erase(m_eol.prev); }
これは大丈夫。そのまま。
次。
//全削除 void Clear() { Node* next; for (Node* node = m_eol.next; node != &m_eol; node = next) { next = node->next; delete node; } m_eol.prev = m_eol.next = &m_eol; }
これもそのまんまだな。
よし、次。
typedef DList<int> List; typedef List::Node Node; //進行方向（メンバ変数ポインタを使って実装） typedef Node* Node::*ShowDirection; const ShowDirection SD_FORWARD = &Node::next; //正順 const ShowDirection SD_BACKWARD = &Node::prev;//逆順
ここだけで完結しないかもだけど。なんぞこれ・・・。
最初の二行は大丈夫。
実質的な三行目。
あぁ。静的でないメンバ関数ポインタだとこんなだった。
～～～～
参考
#typrdef int(Calculator::*Test)();
～～～～
・・カッコどこ行った。引数のカッコも。
いや、メンバ変数ポインタってかいてあるじゃん・・・。
～～～～
参考
そんでメンバ変数ポインタとはこういったものらしい。
int point::*mp = &point::y;
書き方メンバ関数ポインタにならえばいい感じかな。
なになに・・？
ここでいう &point::y
はオブジェクトのアドレスとかではなくて
構造体 point のなかで メンバ変数 y はどの位置にあるのか。
～～～～
なるほど、構造体の中での相対的な位置がわかるのか。
もう一回貼り付け。
typedef DList<int> List; typedef List::Node Node; //進行方向（メンバ変数ポインタを使って実装） typedef Node* Node::*ShowDirection; const ShowDirection SD_FORWARD = &Node::next; //正順 const ShowDirection SD_BACKWARD = &Node::prev;//逆順
構造体Node でのnextの位置、prevの位置を
SD_FORWARD
SD_BACKWARD に入れているんですね。
SDってなんの略だろう。いいや。
これってnextやprevの位置をNode* で返すって事だよね？
次で使うんだろうな。
つぎ、
//リストの中身を出力 void Show(const List& list, ShowDirection dir = SD_FORWARD) { const Node* eol = list.Eol(); const Node* head = eol->*dir; for (const Node* node = head; node != eol; node = node->*dir) { cout << node->value << ' '; } cout << endl; }
Show関数の第二引数はあれだね、デフォルト引数してるんだね。
で、const Node* eol に終端・ダミーノード・m_eol 言い方色々
を入れる。
eol->*dir だと・・・。
そうかNode構造体のメンバ変数ポインタなのだから可能なのか。
あとは、そのまま。dirが次なのか前なのかで方向が変わるわけですね。
凄いなぁ。理解するだけで精いっぱいだわ。
今更ですがダミーノードが先頭ノードと終端ノードをつないで円になっているのを循環リストというそうです。
なので今回のは双方向の循環リストということですね。
はぁ。テキスト終盤になってきたらページの進みが遅い。
ここまで。
