C/C++ - 構造的プログラミング編 第4回 〜線形リスト〜

基本ツリー構造体

メンバ

まず、これ以降で共通して使うデータ構造として、次のような自己参照構造体を考えます。

struct CPbasicTree{
 CPbasicTree* pParent;
 CPbasicTree* pPrev;
 CPbasicTree* pNext;
 CPbasicTree* pChildren;
 CPbasicTree(void);
 virtual ~CPbasicTree(void);
 CPbasicTree* mInsert(CPbasicTree* rInstance);
 void mErase(void);
};

仮想デストラクタを採用していることから分かるように、これ以降で、拡張を行う場合は、 この構造体を継承します。

4つあるメンバ変数ですが、それぞれ、文字通り、親インスタンス・前インスタンス・次インスタンス・ 子インスタンスへのアクセスに使います。

コンストラクタは、単純に全てのメンバ変数を NULL で初期化します。

CPbasicTree::CPbasicTree(void):
 pParent(0),pPrev(0),pNext(0),pChildren(0){}

インスタンスの追加

では、まず子インスタンスを先頭要素とする子リストの末尾の要素として 新しいインスタンスを追加するメンバ関数である、mInsert() について考えて見ます。

CPbasicTree* CPbasicTree::mInsert(CPbasicTree* rInstance){
 rInstance->pParent=this;
 if(!pChildren) return pChildren=rInstance->pPrev=rInstance;
 rInstance->pPrev=pChildren->pPrev;
 pChildren->pPrev=pChildren->pPrev->pNext=rInstance;
 return rInstance;
}

このように追加すると、pChildren を先頭要素とするリストが構築される わけですが、ここではルールとして、1行目にあるように、追加されたインスタンスの pParent には 自分自身を入れます。次に4行目を見ますが、必ず、pChildren->pPrev 、つまり、 先頭要素の前の要素として、自分自身を参照させます。

こうすることで、このリストでは、先頭要素から pNext を辿ると、最終的に、 追加したインスタンスの pNext つまり、NULL で止まるような線形リストとなり、 同時に、先頭要素から pPrev を辿ると、最後に追加したインスタンスにアクセスし、 それ以降、順番にアクセスできる環状リストのようになります。

子インスタンスの削除

続いて、子インスタンスを先頭要素とする子ツリーを全て消去するメンバ関数である、 mErase() を考えて見ます。

void CPbasicTree::mErase(void){
 for(CPbasicTree *itr=pChildren,*next=0;itr;itr=next){
  next=itr->pNext;
  itr->mErase();
  delete itr;
 }
  pChildren=0;
}

3行目にあるように、子インスタンスは、さらに自分の子インスタンスの mErase() を 連鎖的に呼びます。そして、4行目の delete オペレータにより、それぞれのインスタンスの 仮想デストラクタが呼び出される仕組みを作っておきます。

スタック

スタックとは、LIFO を実現するためのデータ構造です。 つまり、一番最後に追加したデータが、最初に取り出される構造になります。

ポップ操作とプッシュ操作

先程の、基本ツリー構造体を使う場合、mInsert() で追加されたインスタンスは、 必ず、pChildren->pPrev に入ります。つまり、スタックを実現するためには、 追加に先程の mInsert() を使ったならば、

CPbasicTree* CVStack::mPop(void){
 CPbasicTree* itr=pChildren;
 if(!itr) return itr;
 if(itr!=itr->pPrev){
  itr=itr->pPrev;
  pChildren->pPrev=itr->pPrev;
 }else pChildren=0;
 itr->pParent=itr->pPrev=itr->pPrev->pNext=0;	
 return itr;
}

という形で、取り出します。複雑に見えますが、やってることの本質は、 1行目と4行目ですね。1行目で pChildren を itr に代入しているので、4行目で行っていることは、 末尾のインスタンス、つまり、最後に挿入されたインスタンスを意味するわけですね。

あとは、取り出したインスタンスをリストから取り除いて、つなぎなおす作業になります。

スタックヘッダクラス

実際にスタックを使う場合には、CPbasicTree を継承した スタック内のインスタンスとなるべき構造体の他にもう1つ、その子リストとして スタックのインスタンスを持ち、その追加、削除の作業を行うという作業を代行する ヘッダと呼ばれるものが必要となります。これを、クラス CVStack として定義します。

class CVStack : CPbasicTree{
public:	
 CVStack(void);
 ~CVStack(void);
 void mPush(CPbasicTree* rInstance);
 CPbasicTree* mPop(void);
 bool mIsEmpty(void);
};

これまでの説明をまとめるならば、CVStack::mPush() は、CPbasicTree::mInsert() を呼び出し、 CVStack::~CVStack(void) は、CPbasicTree::mErase() を呼び出せばいいことになります。

ところで、CVStack::mIsEmpty() ですが、CVStack::mPop() の6行目にあるように、 子インスタンスがなくなった場合、pChildren を NULL にしますので、これをチェックします。

キュー

キューとは、FIFO を実現するためのデータ構造です。 つまり、最初に挿入したインスタンスが、必ず最初に取り出されます。

ポップ操作とプッシュ操作

スタックとの決定的な違いは結局、取り出し方であると言えます。

CPbasicTree* CVQueue::mPop(void){
 CPbasicTree* itr=pChildren;
 if(!itr) return itr;
 if(itr->pNext){
  pChildren=pChildren->pNext;	
  itr->pNext->pPrev=itr->pPrev;
 }else pChildren=0;
 itr->pParent=itr->pPrev=itr->pNext=0;
 return itr;
}

スタックでは取り出すべきインスタンスが、pChildren->pPrev であったのが、 ここでは、pChildren となるというそれだけの話です。

したがって、この mPop() の実装を除いて、スタックと全く同じインターフェースを持ちます。

エンキューとデキュー

では、実際にこのキューを使ってみます。たとえば、int 型のデータを持たせるために、

struct CPintData : CPbasicTree{
 int pData;
 CPintData(int nData=0);
};

などと簡単に構造体を作ってみます。当然、このインスタンスは、

new CPintData(5);

などとすれば作ることが出来ます。

キューのヘッダ queue を、

CVQueue queue;

などと作れば、後は、

queue.mPush(new CPintData(5));

などとすれば 5 という値がエンキューされます。デキューする場合のお決まりの手順として、

CPbasicTree* itr=0;
int n=0;
while(!queue.mIsEmpty()){
 if(dynamic_cast<CPintData*>(itr=queue.mPop()))
 n=static_cast<CPintData*>(itr)->pData;
 delete itr;
 ...
}

という使い方をします。 もちろん、ダウンキャストする先の型が CPintData* だと分かっているのならば、 dynamic_cast は必要ありません。

線形リスト

スタックとキューは、末尾への追加と末尾の取り出し、あるいは先頭の取り出しにのみ 操作が限定された線形リストと考えることが出来ます。これに加えて、先頭への追加と、 リストの途中へのインスタンスの追加と取り出しという作業を備えたものが線形リストとなります。

木構造基底クラス

ところで、末尾を取り除く mPopBack(), 先頭を取り除く mPopFront(), 末尾に追加する mPushBack() はそれぞれ既に前回実装しています。 改めてここで実装しなおしてもいいのですが、これらは、前回の CVStack, CVQueue と共通に 使うものなので、ここで、改めてクラスの継承関係を考え直し、

class CSstdTree : protected CPbasicTree{
public:
 CPbasicTree* mPopBack(void);
 CPbasicTree* mPopFront(void);
 CPbasicTree* mPushBack(CPbasicTree* rInstance);
 CPbasicTree* mPushFront(CPbasicTree* rInstance);	
 bool mIsEmpty(void);
};

として前もって実装しておきます。こうすることで、CVStack, CVQueue では、 CPbasicTree からではなく、この CSstdTree を継承すれば、mPop() は、 CVStack ならば CSstdTree::mPopFront()を、CVQueue ならば CSstdTree::mPopBack() を呼び出せば済むように実装できます。

リストヘッダクラス

前回と同様、ヘッダが必要となるので、まず、これを CVList としてクラス化してみます。 CSstdTree を用いることで、結果的にこのように定義できます。

class CVList : public CSstdTree{
public:
 CPbasicTree* mInsert(
   CPbasicTree* rInstance, CPbasicTree* tInstance=0
  );
 CPbasicTree* mRelease(
   CPbasicTree* beginItr=0, CPbasicTree* endItr=0
  );	
 ~CVList(void);
};

CVQueue, CVStack と違い、mPushBack() などは共通に使い回すために、 public に継承します。

子インスタンスの挿入

まず、CVList::mInsert() は、引数が1つ増えて、tInstance というイテレータの後ろに 挿入できるように拡張されます。

CPbasicTree* CVList::mInsert(
 CPbasicTree* rInstance, CPbasicTree* tInstance){
 if(!tInstance) return CSstdTree::mInsert(rInstance);
 rInstance->pParent=this;
 rInstance->pNext=tInstance->pNext;
 tInstance->pNext->pPrev=rInstance;
 rInstance->pPrev=tInstance;
 return tInstance->pNext=rInstance;
}

子インスタンスの解放

もう1つある、mRelease() ですが、mErase()と違い、引数の2つに加え戻り値があります。 これは、簡単に言えば、第1引数で指定されたイテレータから、第2引数で指定されたイテレータの 直前までをリストとして取り出すような機能を実装します。

CPbasicTree* CVList::mRelease(
 CPbasicTree* beginItr, CPbasicTree* endItr){
 if(beginItr==endItr){
  if(beginItr) return 0;
  beginItr=pChildren;
  endItr=0;
 }
 if(beginItr==pChildren) pChildren=endItr;
 beginItr->pPrev->pNext=endItr;
 if(endItr){
  endItr->pPrev->pNext=0;
  endItr->pPrev=beginItr->pPrev;
 }
 return beginItr;
}

結果的に、7行目のように beginItr->pPrev->pNext を endItr として、 10行目のように endItr->pPrev を beginItr->pPrev となるようにつなぎかえることになります。

ところで、mRelease() をこのように実装した場合、返ってきたリストは、 現状の mInsert() では追加できません。もし、それに対応させるならば、mInsert() で、 追加する rInstance->pNext があるかどうかをチェックし、その上で、rInstance->pPrev を 追加するインスタンスリストの末尾として考慮した上でつなぎかえる必要があります。


文章作成 : yukki-ts (-+-twilight serenade-+- [stage])