newとdelete
そろそろ前期中間試験だけれど、オブジェクト指向の授業は3回のレポートの 実施予定のくせに、すでに2回目の課題も終わりそう。 今年の専攻科の受講生は、4人中3人はEIのOBだし、1名も最初の段階でも 構造体や文字列の話もそれなりに通じるし、1回目の課題でoperator() を 使って課題をしたり十分な理解力。このため授業進度が例年より早まっている。
ということで今日は、前々回の純粋基底クラスによるプログラムの例の中で、 詳しく説明していなかった new , delete について説明をしよう。 C言語の malloc() と free() について説明し、new int[ n ] やら、new Person( … ) といった使い方を紹介する予定。(今日は授業前にメモ作成)
配列の挿入削除問題
先週は、配列の固定長サイズによる問題の対応として、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)にできることを説明する。 実際のリスト構造でのプログラムは来週とし、 課題未消化のひとが多いので後半は課題時間とした。
ポインタと型
例年、文字列-数値変換(atoi,itoa)の課題をやっていると、 「型」という視点が弱いことがわかる。 そこで型など基本的な間違ったプログラム例をあげて、 型の違いで動かないという例を様々なパターンで説明する。 またポインタの概念についても説明を行う。
型の間違いの例の前に、関数でも引数の型の話の中で、 #include の説明も兼ねて、プロトタイプ宣言と古いK&R文法を紹介。 動かない例の中では、引数の型間違い,"C"と'C'の違い,未初期化ポインタの使用,配列あふれなどを説明する。
次に、ポインタの説明。 ポインタ+整数での指示場所の移動や、p[i] は *(p+i) と等価であることの説明など。 ポインタをずらしながらのループの説明がまだ。 for(…; p++ )