スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

【質問】リストに関しての要素の持たせ方

リストについて考えれば考えるほど段々意味が解らなくなっきました。

CBULLET1、CBULLET2、CBULLET3 (それぞれは弾クラス)のように
専用のリストクラスを作ってしまう方法があるのですが、
練習がてらに使おうと思った template を使わずじまいに終わってしまうので
さすがに勿体ないなぁと思ってます。

で、疑問が色々出てくるんですが、整理するとこういう感じでした。

■弾クラスは前後のポインタを知っている必要があるのか?
  ・リストクラスなるものに全てを任せ、前後を知る必要はない
  ・弾クラスは前後のポインタを知っている必要がある

例えば、弾クラスにリストクラスを定義(仮に CLIST m_List)し、
弾を生成する関数でこのような関数を呼ぶとします。

void CBULLET1::CreateShot(~){
 諸々処理();
 m_List.PushBack(生成した弾); // リストの末尾に要素を追加
}

このようにすると、CLISTクラス内で生成した弾を最後尾に繋げて行くので
先頭が NULL なら先頭要素とする。
末尾が NULL でなければ末尾要素とする。

では、先頭と末尾の間にある要素の前後のポインタはどこが管理していればいいのか。
という疑問が出ました。
前回はグローバル変数でした。

これをうまいこと管理するにはどうすればいいんでしょう…
こう考えると、弾クラスにはやはり前後の要素を持たせる必要がありそうですよね~


■先頭、末尾要素はどこで管理するのか?
これも前回はグローバル変数でした。

しかし、どこかで先頭・末尾を管理しておいた方が描画したりする時に便利かと思います。
例えば、弾クラスに static で宣言してしまうやり方もあるかもしれませんし、
上に書いたとおり、CLIST が管理する、等々方法はいくつかあると思います。

先頭・末尾はそれぞれの弾クラスで一つずつしかないので
弾クラスに持たせるべきなのか、リストクラスに持たせるべきなのか
…と、ソースを書きながら疑問ばかりで行ったり来たり;


とりあえず、今は template 以前の問題ですね;
こういうのをクラス設計と言うのでしょうか…。
うーん…今日の晩もこれで潰れそうだ;
もういっちょ頑張ってみるか~

とりあえず、ランニングしてこよう。
煮詰まったら何か別のことすればいいって誰か言ってたし!

この記事へのコメント

リスト構造について - 御津凪 - 2010年06月24日 01:07:27

私の場合だと、そのような構造は以下のような感じで扱ってます。

template<class T>
class ListNode {
typedef ListNode<T> This;
public:
ListNode(){
mNext = mPrev = this;
}
~ListNode(){
Disconnect();
}
// 指定ノードを自身の後ろに接続
void Connect( This* pNode ){
pNode->mNext = mNext;
pNode->mPrev = this;
mNext->mPrev = pNode;
mNext = pNode;
}
// 自身の接続を解除
void Disconnect(){
mNext->mPrev = mPrev;
mPrev->mNext = mNext;
mNext = mPrev = this;
}
// 次のノードを参照
This* Next(){ return mNext; }
// 前のノードを参照
This* Prev(){ return mPrev; }
private:
This* mNext;
This* mPrev;
};

書き下ろしなので間違いがあるかもしれません。

上記クラスはノード自身が連結を制御するようにしています。
参考までにどうぞ。

No title - DVDM♪管理人♪ - 2010年06月24日 20:41:32

>>御津凪さん
御回答ありがとうございます><
そっか~、ノードクラスの中に繋げる処理入れたらいいんですね。

ちょっと疑問なのですが、リストの先頭や末尾のポインタは
どのように管理しているのでしょうか?

No title - 御津凪 - 2010年06月25日 02:12:28

こんな感じです。
上記のクラスから少し変更しているのでまとめて載せます。
(結果長くなってしまいましたが)

// 弾ノードクラス
class BulletNode {
public:
BulletNode( int dummy = 0 ) : mDummy(NULL){ }

void Exec( void ){ printf("value = %dn", mDummy); }
private:

int mDummy;
};

// リストノードテンプレートクラス
template<class T>
class ListNode {
typedef ListNode<T> This;
public:
ListNode( BulletNode* pNode = NULL ) : mData(pNode){ mNext = mPrev = this; }
~ListNode(){
Disconnect();
if(mData){ delete mData; }
}
// 指定ノードを自身の後ろに接続
void Connect( This* pNode ){
pNode->mNext = mNext;
pNode->mPrev = this;
mNext->mPrev = pNode;
mNext = pNode;
}
// 自身の接続を解除
void Disconnect(){
mNext->mPrev = mPrev;
mPrev->mNext = mNext;
mNext = mPrev = this;
}
// 次のノードを参照
This* Next(){ return mNext; }
// 前のノードを参照
This* Prev(){ return mPrev; }

T* GetData(){ return mData; }
void SetData( T* pData ){ mData = pData; }
private:
This* mNext;
This* mPrev;
T* mData;
};

typedef ListNode<BulletNode> BulletListNode;

// 弾リスト
class BulletList {
public:
BulletList() : mRoot(){ }
~BulletList(){
RemoveAll();
}

// リンク全体を削除
void RemoveAll(){
BulletListNode* node = mRoot.Next();
while(node != &mRoot){
BulletListNode* tmp = node;
node = node->Next();
delete tmp;
}
}
// リンク全体の接続を削除
void DisconnectAll(){
BulletListNode* node = mRoot.Next();
while(node != &mRoot){
BulletListNode* tmp = node;
node = node->Next();
tmp->Disconnect();
}
}
// リストを実行
void Exec(){
BulletListNode* node = mRoot.Next();
while(node != &mRoot){
BulletListNode* tmp = node;
node = node->Next();
tmp->GetData()->Exec();
}
}
// 項目追加
bool Append( BulletNode* pNode ){
BulletListNode* node = new BulletListNode(pNode);
if(node){
mRoot.Prev()->Connect(node);
}
return (node != NULL);
}
BulletListNode* GetRootNode(){
return &mRoot;
}

private:
BulletListNode mRoot;
};

ちなみに、ListNode と BulletNode は一つにまとめたほうが効率がいいです。
そこから継承して弾の動作とか行わせればいいので。

あと、すごく適当に作ったのでおそらくそのままでは使い辛いと思いますので注意。

No title - DVDM♪管理人♪ - 2010年06月25日 22:34:26

>>御津凪さん
返信ありがとうございます!

> // 指定ノードを自身の後ろに接続
> void Connect( This* pNode ){
> pNode->mNext = mNext;
> pNode->mPrev = this;
> mNext->mPrev = pNode;
> mNext = pNode;
> }

指定ノード pNode はリンクさせるもの(今回だと弾)だと思うのですが
mNext, this が何を指している(表している)かがよく解りません;

ListNode クラスのコンストラクタに
mNext = mPrev = this; と書いていて
この mNext には this ポインタが入っているので

> pNode->mNext = mNext;
> pNode->mPrev = this;

は同じ所を指しているのでは・・・と思いました。


> BulletListNode* node = mRoot.Next();
> while(node != &mRoot){
今まで先頭と末尾を表す要素が無いと駄目だと思ってましたが
「一周したら」にする方法もあるんですね~

リストって結構難しいんですね;

No title - 御津凪 - 2010年06月25日 22:56:08

二回以上 Connect メンバ関数を読んだ時を考えると、
おのずとわかるかと思います。
紙に書いてみると分かりやすいかも。
ほんとは図があると分かりやすいんですけどね…。

このようなリストは Wikipedia に纏まってます。
連結リストでググると出てきます。
ちなみにこのような方式のリストは双方向循環リストといいます。

No title - なも - 2010年06月27日 11:06:11

いつの間にか移転してたw

えと、弾のリストですか。
御津凪さん書いてますけど双方向リストがいいです。

欲を出せば双方向循環リストならより使い勝手がいいかも。

新要素に前後アドレス設定した後に
新要素の次の要素に新しい要素のアドレス設定を
忘れなければさほど躓くところはない…と思います。

>mNext->mPrev = pNode;
>mNext = pNode;
この部分ですね。

No title - なも - 2010年06月27日 11:07:59

ってか普通にソース見たら循環してたw

お目汚しすんまそん--;

No title - DVDM♪管理人♪ - 2010年06月28日 02:13:32

>>御津凪さん
この土日、Connect 関数について絵を描きながらデバッグで追いかけたにも関わらず

pNode->mNext = mNext;
pNode->mPrev = this;

この二行が読み取れませんでした;
他の関数がやってることは理解できたんですけどね;

結局循環リストではなく単に双方向リストクラスを作ることにしました。
せっかくコード提示して頂いたのに申し訳ないです:



>>なもたん
前のとこにソース載っけるとそれはもう凄い勢いで崩れるんだわ><
前にも使ってたFC2のブログをお借りした訳さ!

リストは単なる双方向リストにしたよw

No title - 御津凪 - 2010年06月28日 02:38:55

そうですか。
暇ができたらサンプルでも作っておきますかね。
自作ライブラリ用の、ですけど。

ともかく、用途によって最適なリスト構造があるので、
手探りで学ぶのもいいかもしれませんね。

双方向循環リストは、ノード自体を一人の人間として、
mNext と mPrev をそれぞれ左手がつないでいる相手、
右手がつないでいる相手と考えると分かるかも。

たとえば一人の時は自分自身の手を組む状態。
一人やってきて、両手をつなげば二人の輪(循環リスト)。
もう一人来れば、三人の輪(循環リスト)…
と増えていきます。

ここで問題の Connect 関数の処理の意味ですが、
this を自分、 pNode を今つなごうとしている人と考えると、(mNextを左手、mPrevを右手を考えると)

// (a)今つなごうとしている人の左手を自分の左手でつないでいる人につなぐ。
pNode->mNext = mNext;
// (b)今つなごうとしている人の右手を自分の左手でつなぐ。
pNode->mPrev = this;
// (c)自分の左手でつながっていた相手の右手を今つなごうとしている人につなぐ((a) の相手側の処理)。
mNext->mPrev = pNode;
// (d)自分の左手を今つなごうとしている人につなぐ((b) の自分側の処理)。
mNext = pNode;

と置き換えられます。
実践してみると面白いかも。

No title - DVDM♪管理人♪ - 2010年06月29日 23:36:33

>>御津凪さん
丁寧に解説ありがとうございます!
手をつなぐ感覚で見てみたら理解が早かったです。
結構ややこしいですね;

トラックバック

URL :

検索フォーム
プロフィール

DVDM

Author:DVDM
自作ゲームの開発過程ブログ。
赤髪愛なら誰にも負けない。

 
Pixiv バナー


ブロとも申請フォーム
最新記事
カテゴリ
最新コメント
最新トラックバック
RSSリンクの表示
リンク
ブロとも一覧
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。