ホーム » スタッフ » 斉藤徹 » 配列の挿入削除問題

2011年6月
« 5月   7月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

配列の挿入削除問題

先週は、配列の固定長サイズによる問題の対応として、malloc() + free() による 動的メモリの管理手法の演習をしていたので、 その続きとして配列の欠点の挿入削除問題を説明。

配列に単純にデータを入れる処理でも、様々な方法がある。 最も簡単な方法は、配列とサイズを保存しデータを追加したい場合は、 末尾に入れる方法。

int array[ 100 ] ;
int size = 0 ;
void entry( int x ) {
array[ size ] = x ;
size++ ;
}

しかしこの方法では、デタラメな順序でデータが与えられれば、配列内は デタラメな順序となり、中身のデータ検索は「単純検索」をするしかなくなり、 処理時間のオーダは、O(N)となってしまう。

データを素早く見つけたいのであれば、2分探索法をするためにも、 配列が昇順に並んでいなければならない。 そうなると、昇順に並んだデータ列の途中に、与えられた情報を挿入する 必要が出てくる。

理解力を確認するために、昇順配列への追加処理ではどんな処理をするか 聞いてみると、「末尾に追加してクイックソートすればいい…」といった 考えの人が多かった。クイックソートはほぼ昇順に並んでいるといった データは苦手であり、O(N^2)になるから極めて遅いって…

void insert( int index , int x ) {    // 領域が重複している時は
for( i = size ; i > index ; i-- ) // 後ろからコピーが必要かも。
array[ i ] = array[ i - 1 ] ;
array[ index ] = x ;
size++ ;
}

しかし、この処理には、O(N)の処理時間を要する。

この対策として次のデータの場所を保存する方式であれば、 挿入作業はO(1)にできることを説明する。 実際のリスト構造でのプログラムは来週とし、 課題未消化のひとが多いので後半は課題時間とした。