第8回演習問題

演習問題　第8回リスト

8a　リストの挿入
　整数値を要素とする2つの配列、array1, array2を作成し、array1には20個の要素、array2には10個の要素からなるとして、任意の整数値を代入しておく。
　　int array1[20] = {140, , ・・・・・・・・・・} ,
　　　　array2[10] = {51, ・・・・} ;
array1から要素を読み込みリスト1を、同様にarray2からリスト2を生成する。
　リスト1のpos番目の位置の節の後に、リスト2を挿入する関数を作成する。

　　　void insert_list(int pos, NODE *head1, NODE *head2) :　
リスト1のpos番目の節(の後ろに)にリスト2を連結(head1、head2は、それぞれリスト1、リスト2の先頭節を指す)

　上述の関数の動作検証をするために、以下の手順で実行する。
(1) 2つのリストそれぞれに対し、リストの全要素を出力する関数を実行する。
(2)上記の挿入関数を用いて、リスト1のpos(学籍番号の末尾の数字)番目の節の後にリスト2を挿入する。
(3) 挿入位置posを出力し、挿入されたリスト1に対して、リストの全要素を出力する関数を実行する。

8b　リストによる整列: リスト版挿入法の実装
講義中に演習課題から除外する旨、申し上げましたが、演習課題ととします
(a) 第4回の整列法で取り上げた、単純挿入法アルゴリズム(配列)を作成する。
下記のファイルを対象として整列を行い。実行時間を測定する。

　　　ファイル名:integer100KR.dat

(b) このアルゴリズムのリスト版を実装する(SList.c.pdfに含まれるているので、新規に作成する必要はありません)。「第8回リストⅠ: 線形リスト」テキストのp.8の整順列を生成する節の挿入アルゴリズムのコードがそのものになるが、挿入位置が先頭節か、末尾節かによりプログラム・コードは異なるため、各自で考えて作る必要がある(また、dummy nodeを使う場合と使わない場合で対処の仕方は異なる)。
　上記のファイルから、1レコードずつ読み込み、挿入関数を用いて整順列を生成する。
　配列版の挿入法アルゴリズムは、n²の移動回数を必要とするが、リスト版では移動は全く生じない。代わりにn回の節の生成と参照欄の変更が必要とされる。
　実行時間はそれぞれ以下の処理に要する時間を測定する。
配列　: ファイルの読み込み〜整列終了
リスト: ファイルの読み込み〜整列終了
(a), (b)の実行時間を出力し、分析せよ。