ページ 1 / 1
クラスを用いた連結リストの実装
Posted: 2014年4月17日(木) 22:38
by チコォ
初めまして。初投稿です。よろしくお願いします。
最近オブジェクト指向に触れるようになりました
今、C++で連結リストをクラス構造を用いて実装しようとしています
一言で言うと、2つのクラスをうまく連携させる方法は無いのか?という質問です
試したプログラムはおおよそ以下のとおりの構造です
・[クラスA]データと次へのポインタ(C言語ならば構造体扱い)
メンバ関数は、
データのセッタ
リストに追加
リストから削除
・[クラスB]連結リストを管理するクラス
メンバ変数にルートとなるクラスAのポインタ
メンバ関数は
リストに追加する関数
リストから削除する関数
printfで表示して列挙する関数(デバッグ用)
と、せっかくメンバ関数という道具を使えるようになったからには
データを管理するクラスA側でリンクリストに追加/削除する処理をさせたいのです。
しかし、リンクリストの追加/削除のために
どこかでクラスAに対して、クラスBの参照を渡す必要があるわけですが…この一手間を省きたい。
なにかもうすこしスマートなやり方は存在しませんか?
Re: クラスを用いた連結リストの実装
Posted: 2014年4月17日(木) 22:41
by softya(ソフト屋)
すいません。良く分かりません。
クラスAがクラスBの参照をもつ必要性はなんでしょうか?
Re: クラスを用いた連結リストの実装
Posted: 2014年4月17日(木) 22:43
by h2so5
クラスAの存在意義が分かりません。リスト操作はすべてクラスB経由でいいと思いますが。
Re: クラスを用いた連結リストの実装
Posted: 2014年4月18日(金) 09:50
by usao
質問者様の文章内容を無理矢理想像すると…
例えばこんな形とかになっているんでしょうか?
コード:
//[クラスA]
class Node
{
public:
//データのセッタ
void SetData( const Data &rData ){ m_Data=rData; }
//リストrListに自身を追加?
void AddToList( List &rList ) //引数に「参照を渡す必要がある」
{ rList.AddNode( this ); } //うーん…
//リストrListから自身を削除?
bool RemoveFromList( List &rList ) //引数に「参照を渡す必要がある」
{ return rList.RemoveNode( this ); } //うーん…
private:
Node *m_pNextNode; //次のノードへのポインタ:これはListクラスからいじくられるということか?
Data m_Data; //何らかのデータ
friend class List; //※Listクラスからm_pNextNodeをいじくるために…
};
//[クラスB]
class List
{
public: //←?
void AddNode( Node *pNode ); //リストの(末尾に?)pNodeを繋げる
bool RemoveNode( Node *pNode ); //リストにpNodeが繋がっていれば切り離す
public:
void DebugShowAll(); //列挙する関数(デバッグ用)
private:
Node *m_pRootNode; //ルートへのポインタ
};
Re: クラスを用いた連結リストの実装
Posted: 2014年4月18日(金) 21:04
by チコォ
返信ありがとうございます。
実際のコードを記載しました。
「試したプログラムでは」などと言いましたが、
実際はプログラムを完成させる前に質問していました…申し訳ありませんでした。
故にNo1で説明したものとは一部異なり、また
>どこかでクラスAに対して、クラスBの参照を渡す必要があるわけですが
という部分、実際は2つのクラスを相互に参照しようとするとコンパイルが通らないことが判明しました。
コノ点に関しても解決方法をご教示していただきたいです。
以下、ソースと詳細の説明です。そしてそれがお三方への返答になるものと思います。
コード:
class LINKLIST;
class OBJECT{
public:
int val;
int idx;
OBJECT(){}
OBJECT(int val){
this->val = val;
}
void init(int val){
this->val = val;
}
//ここで自身をリンクリストへ追加処理をさせたい
void regist(LINKLIST *list){
//idx = list->add(this);//この行でコンパイルエラー
}
//ここで自身をリンクリストからの削除処理をさせたい
void remove(){
}
};
class LINKLIST{
public:
struct NODE{
OBJECT *p_data;
NODE *next;
};
NODE root;
NODE *tail;
int length;
LINKLIST(){
length = 0;
root.next = NULL;
tail = &root;
}
//リストニオブジェクト追加
//リストの何番目に追加されたか その数値を返す
int add(OBJECT *obj){
NODE *p = tail->next = new NODE;
p->p_data = obj;
p->next = NULL;
tail = p;
int idx = length;
length++;
return idx;
}
//インデックスを指定してそのオブジェクトを削除
void del(int idx){
NODE *p = &root;
for(int i = 0; i < idx; i++){
p = p->next;
}
NODE *p2 = p->next;
p->next = p2->next;
delete p2;
length--;
}
//列挙
void print(){
NODE *p = root.next;
while(p != NULL){
printf("enum:%d\n", p->p_data->val );
p = p->next;
}
}
//全削除
void all_delete(){
NODE *p = root.next;
NODE *p2;
while(p != NULL){
printf("delete:%d\n", p->p_data->val );
p2 = p;
p = p->next;
delete p2;
}
}
~LINKLIST(){
all_delete();
}
};
class SUB_A : public OBJECT{
public:
int a;
};
class SUB_B : public OBJECT{
public:
int b;
};
int _tmain(int argc, _TCHAR* argv[]){
//オブジェクト生成
OBJECT obj[5];
SUB_A sub_a;
SUB_B sub_b;
//初期化
obj[0].init(100);
obj[1].init(101);
obj[2].init(102);
obj[3].init(103);
obj[4].init(104);
sub_a.init(200);
sub_b.init(300);
//リスト管理クラス
LINKLIST list;
//オブジェクトをリストへ追加
list.add(&obj[0]);
list.add(&obj[1]);
list.add(&obj[2]);
list.add(&obj[3]);
list.add(&obj[4]);
list.add(&sub_a);
list.add(&sub_b);
//インデックスを指定しリストからオブジェクト削除
list.del(0);
list.del(0);
list.del(1);
//リスト列挙表示
list.print();
//全削除
//list.all_delete();
getchar();
return 0;
}
リストの中身となるオブジェクトは、
頻繁にリンクリストから登録(再登録)/削除をするものであるという想定であり、
ソースの通り、リストに追加するオブジェクトは
OBJECTクラスに限らずそれを継承したクラスをリストに追加するということが普通です。
リストから一個のオブジェクトを削除するには
その対象がリストのルートから何番目に存在するのかを表すインデックス値が必要となりますが、
単純に配列として定義したオブジェクトのみをリストに追加する場合ならともかく、
継承したオブジェクトも追加する場合など、まばらにオブジェクトの変数を定義するときには
インデックス値を管理することが困難となるでしょう。
この問題を解消するために、オブジェクト自身で追加/削除処理を行いたいと考えており、
今回質問させていただきました。
Re: クラスを用いた連結リストの実装
Posted: 2014年4月18日(金) 21:18
by softya(ソフト屋)
>継承したオブジェクトも追加する場合など、まばらにオブジェクトの変数を定義するときにはインデックス値を管理することが困難となるでしょう。
この想定の意味が分かりません。配列ではなくポインタリストで管理されているように見えるので、継承していようと関係ないはずですが。
Re: クラスを用いた連結リストの実装
Posted: 2014年4月18日(金) 21:30
by h2so5
コンパイルエラーが出るのはLINKLISTのメンバ変数の定義がOBJECTよりも後にあるためです。
また、OBJECTがidxとして自分自身のインデックスを持っているようですが、途中の要素が削除されてインデッスクがずれたり、同一オブジェクトが複数回追加された場合はどうするのでしょうか。
Re: クラスを用いた連結リストの実装
Posted: 2014年4月18日(金) 21:51
by softya(ソフト屋)
LINKLISTの代わりにSTLのlistで検証してみましたが、支障なく削除の管理などを行えると思います。と言うことでOBJECTがLINKLISTの参照を持つ必要性が確認できませんでした。
私にはOBJECTがLINKLISTの参照を持つ理由がやはり分からないという結論です。
Re: クラスを用いた連結リストの実装
Posted: 2014年4月19日(土) 08:11
by チコォ
[quote="h2so5" id=3,14958#postingbox,118930]コンパイルエラーが出るのはLINKLISTのメンバ変数の定義がOBJECTよりも後にあるためです。
。[/quote]
メンバ変数の定義ですか?
OBJECTより前にLINKLISTを定義しても今度は「OBJECTが定義されてないよ」とエラーが出ます
頭に
コード:
class LINKLIST;
int LINKLIST::add(OBJECT *obj);
とでも書き加えれば良いのかと思いましたがやはり通らず。
2つのクラスが相互に関わることはできないんでしょうか
>OBJECTがidxとして自分自身のインデックスを持っているようですが、途中の要素が削除されてインデッスクがずれたり、
そのとおりですね!ありがとうございます 気が付きませんでした
別の方法を考えます
>同一オブジェクトが複数回追加された場合はどうするのでしょうか。
前提条件として同じものは一度しか追加されることはないです
付け加えます
Re: クラスを用いた連結リストの実装
Posted: 2014年4月19日(土) 10:40
by へにっくす
チコォ さんが書きました:メンバ変数の定義ですか?
OBJECTより前にLINKLISTを定義しても今度は「OBJECTが定義されてないよ」とエラーが出ます
そりゃprintとall_deleteでOBJECTの中身を表示させようとしてるからな。
コンパイル通すだけなら、以下のようにすればできますが。
コメントの「// ◇」の部分参照。
コード:
#include <stdio.h> // ◇ 必要なヘッダ
#include <tchar.h> // ◇ 必要なヘッダ
class OBJECT; // ◇こういうクラスがあるよという宣言。ここでは中身は宣言されていない。当然、idx、valなんぞあるわけない。
class LINKLIST{
public:
struct NODE{
OBJECT *p_data;
NODE *next;
};
NODE root;
NODE *tail;
int length;
LINKLIST(){
length = 0;
root.next = NULL;
tail = &root;
}
//リストニオブジェクト追加
//リストの何番目に追加されたか その数値を返す
int add(OBJECT *obj){
NODE *p = tail->next = new NODE;
p->p_data = obj;
p->next = NULL;
tail = p;
int idx = length;
length++;
return idx;
}
//インデックスを指定してそのオブジェクトを削除
void del(int idx){
NODE *p = &root;
for(int i = 0; i < idx; i++){
p = p->next;
}
NODE *p2 = p->next;
p->next = p2->next;
delete p2;
length--;
}
//列挙
void print(){
NODE *p = root.next;
while(p != NULL){
// printf("enum:%d\n", p->p_data->val ); // ◇ p->p_data の内容を参照したら駄目。
printf("enum pointer: %p\n", p->p_data); // ◇参照できるのはポインタのアドレスだけ。
p = p->next;
}
}
//全削除
void all_delete(){
NODE *p = root.next;
NODE *p2;
while(p != NULL){
// printf("delete:%d\n", p->p_data->val ); // ◇ p->p_data の内容を参照したら駄目。
printf("delete: %p\n", p->p_data); // ◇参照できるのはポインタのアドレスだけ。
p2 = p;
p = p->next;
delete p2;
}
root.next = NULL; // ◇全部削除したよという印。
}
~LINKLIST(){
all_delete(); // デストラクタ
}
};
// ◇ ここで初めて、OBJECTの内容が宣言される。
class OBJECT{
public:
int val;
int idx;
OBJECT(){}
OBJECT(int val){
this->val = val;
}
void init(int val){
this->val = val;
}
//ここで自身をリンクリストへ追加処理をさせたい
void regist(LINKLIST *list){
idx = list->add(this); // ◇コメント解除
}
//ここで自身をリンクリストからの削除処理をさせたい
void remove(){
}
};
class SUB_A : public OBJECT{
public:
int a;
};
class SUB_B : public OBJECT{
public:
int b;
};
int _tmain(int argc, _TCHAR* argv[]){
//オブジェクト生成
OBJECT obj[5];
SUB_A sub_a;
SUB_B sub_b;
//初期化
obj[0].init(100);
obj[1].init(101);
obj[2].init(102);
obj[3].init(103);
obj[4].init(104);
sub_a.init(200);
sub_b.init(300);
//リスト管理クラス
LINKLIST list;
//オブジェクトをリストへ追加
list.add(&obj[0]);
list.add(&obj[1]);
list.add(&obj[2]);
list.add(&obj[3]);
list.add(&obj[4]);
list.add(&sub_a);
list.add(&sub_b);
//インデックスを指定しリストからオブジェクト削除
list.del(0);
list.del(0);
list.del(1);
//リスト列挙表示
list.print();
//全削除
list.all_delete();
getchar();
return 0;
}
実行結果。
コード:
enum pointer: 00B3FA34
enum pointer: 00B3FA44
enum pointer: 00B3F9F8
enum pointer: 00B3FA04
delete: 00B3FA34
delete: 00B3FA44
delete: 00B3F9F8
delete: 00B3FA04
Re: クラスを用いた連結リストの実装
Posted: 2014年4月19日(土) 11:26
by Milla
1.循環参照状態のクラスのプロパティは実体であってはならない
2.ヘッダーファイルでどちらかのクラスを前方宣言しておかないと、クラス宣言の無限ループが起こる
3.実体がなくとも、プロパティの持つ関数は呼べる。ただし、実体のないプロパティの中のプロパティを触った時点で参照エラーを起こす。
A.h
コード:
#pragma once
class CB;
class CA
{
private:
CB* objB;
public:
CA();
~CA();
void hoge();
void puyo();
};
A.cpp
コード:
#include "A.h"
#include "B.h"
CA::CA()
{
}
CA::~CA()
{
}
void CA::hoge()
{
objB->puyo();
}
void CA::puyo()
{
}
B.h
コード:
#pragma once
class CA;
class CB
{
private:
CA* objA;
public:
CB();
~CB();
void hoge();
void puyo();
};
B.cpp
コード:
#include "A.h"
#include "B.h"
CB::CB()
{
}
CB::~CB()
{
}
void CB::hoge()
{
objA->puyo();
}
void CB::puyo()
{
}