リスト構造について
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造について説明する。
配列の利点と欠点
今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。
int find( int array[] , int left , int right , int key ) { // データは left から right-1までに入っているとする。 while( left < right ) { int mid = (left + right) / 2 ; // 中央の場所 if ( array[ mid ] == key ) return mid ; // 見つかった else if ( array[ mid ] > key ) right = mid ; // 左半分にある else left = mid + 1 ; // 右半分にある } return -1 ; // 見つからない }
しかし、配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。
void entry( int array[] , int* psize , int key ) { // データを入れるべき場所を探す処理 for( int i = 0 ; i < *psize ; i++ ) // O(N) の処理だけど、 if ( array[ i ] > key ) // O(log N) でも書けるけど break ; // 単純に記載する。 if ( i < *psize ) { // 要素を1つ後ろにずらす処理 for( int j = *psize ; j > i ; j-- ) // O(N)の処理 array[ j ] = array[ j - 1 ] ; array[ i ] = key ; } else { array[ *psize ] = key ; } (*psize)++ ; }
これで判るように、データを配列に追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。
この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。
順序が重要なデータ列で途中へのデータ挿入削除
例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
通常は、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、回覧板を回すことができる。
101 102 103 104 105 106 [ 105 | 106 | -1 | 102 | 104 | 103 ]
このように次のデータの場所という概念を使うと、データの順序を維持して扱うことができる。
struct LIST { int data ; int next ; } ; struct LIST array[] = { /*0*/ { 11 , 2 } , /*1*/ { 67 , 3 } , // 末尾にデータ34を加える /*2*/ { 23 , 4 } , // { 23 , 5 } , /*3*/ { 89 , -1 } , // 末尾データの目印 /*4*/ { 45 , 1 } , /*5*/ { 0 , 0 } , // { 34 , 4 } , } ; for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) { printf( "%d¥n" , array[ idx ].data ) ; }
この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。
しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。
UMLと構造図
UMLの構造図の書き方の説明。 詳しくは、参考ページのUML入門などが、分かりやすい。
クラス図
クラス図は、構造図の中の基本的な図で、 枠の中に、上段:クラス名、中段:属性(要素)、下段:メソッド(関数)を記載する。 属性やメソッドの可視性を示す場合は、”-“:private、”+”:public、”#”:protected 可視性に応じて、”+-#”などを記載する。
関連
クラスが他のクラスと関係がある場合には、その関係の意味に応じて、直線や矢印で結ぶ。
(a)関連(association):単純に関係がある場合、
(b)集約(aggregation):部品として持つが、弱い結びつき。関係先が消滅しても別に存在可能。
(c)コンポジション(composition):部品として持つが強い結びつき。関係先と一緒に消滅。
(d)依存(dependency):依存関係にあるだけ
(e)派生(generalization):派生・継承した関係
(f)実現(realization): Javaでのinterfaceによる多重継承
上図の例では、乗り物クラスVehicleから自動車がCarが派生し、 自動車は、エンジン(Engine)を部品として持つ。エンジンは車体と一緒に廃棄なら、コンポジション(部品の実体を持つ)で実装する。
自動車は、同じく車輪(Wheel)を4つ持つが、自動車を廃棄してもタイヤは別に使うかもしれないので、集約(部品への参照を持つ)で実装する。 集約で実装する場合は、C++などであれば、ポインタで部品を持ち、部品の廃棄(delete)は、別に行うことになる。
is-a 、has-a の関係
前の課題でのカモノハシクラスで、羽や足の情報をどう扱うべきかで、悩んだ場合と同じように、 クラスの設計を行う場合には、部品として持つのか、継承として機能を持つのか悩む場合がある。 この場合には、“is-a”の関係、“has-a”の関係で考えると、部品なのか継承なのか判断しやすい。
たとえば、上の乗り物(Vehicle)クラスと、車(Car)のクラスは、”Car is-a Vehicle” といえるので、is-a の関係。 “Car is-a Engine”と表現すると、おかしいことが判る。 車(Car)とエンジン(Engine)のクラスは、”Car has-a Engine”といえるので、has-a の関係となる。 このことから、CarはVehicleからの派生であり、Carの属性としてEngineを部品として持つ設計となる。
オブジェクト図
クラス図だけで表現すると、複雑なクラス関係では、イメージが分かりづらい場合がでてくる。 この場合、具体的な値を図に書き込んだオブジェクトで表現すると、説明がしやすい場合がある。 このように具体的な値で記述するクラス図は、オブジェクト図と言う。 書き方としては、クラス名の下に下線を引き、中段の属性の所には具体的な値を書き込んで示す。
その他の構成図
その他の構成図としては、コンポーネント図(物理的な構成要素から、システムの構造を表現する図)、 配置図(ハードウェアとアプリケーションの関係を図示したもの)、パッケージ図(パッケージ同士の関係をグループ化した図) なども用いる。