List

出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．

レポート提出確認

この授業のトップページからレポートの提出況の確認のページに移動し，レポートの状況を常に確認せよ．

講義

4.1 リスト

要素に一意な順番がついているものをリスト（線形リスト）という．集合は複数の要素をもつがリストではない．

「連結リスト」はポインタを使ってリストを実現したもので，混同しないように注意すること．

リスト全体を x とすると，x の k 番目の要素を x[k] と書く．（C の配列をそのまま使うと添字がずれることに注意）

リストに対して，必要となりそうな操作をまとめたものが P.35 の Table4.1 で基本操作とよぶ．リストと基本操作をセットにしたものが抽象データ型になる．

プログラムを動かすには抽象データ型のデータ部分を具体的なデータ構造で実現する必要がある．一つの抽象データ型を実現するデータ構造は複数ある．データ構造により得意，不得意な基本操作があるので使い道にあったデータ構造を選ぶ．

4.2 スタック

スタック(stack)と後で述べる待ち行列は，一般的なリストと違って要素をリストの中間に挿入したり中間から削除することができない．

なぜ「不便」なデータ構造が重要視されるかというと，配列を使って効率よく実現できるためである．配列は中間への挿入，中間からの削除には大量のデータの移動が必要だが，スタック，待ち行列では中間への操作が起こらない．

スタックはデータの挿入，削除がリストの先頭に対してしかできないリストである．

最初に入れた要素の位置を底(bottom)といい，最も新しい要素の位置を頂上(top) という．頂上へ要素を挿入することを積む(push)，頂上から削除することを降ろす(pop) という．

スタックに新しく要素を積むときは現在の top の次の位置に挿入し， top を新しい要素を指すようにする．降ろす場合は top の要素を削除し，top を一つ前の要素を指すようにする．

効率的に実装できるので割り込みを処理するときに多用される．

4.3 待ち行列

挿入が最も新しい要素の次の位置にされることはスタックと同じだが，削除が最も古い要素に対して行われるのが待ち行列(queue)である．

待ち行列では最も古い要素を先頭(front)，最も新しい要素を末尾(rear)という．末尾へ要素を挿入することを入れる(enqueue)，先頭から削除することを取り出す(dequeue)という．

待ち行列に新しく要素を入れるときは末尾の次の位置に挿入し， rear を新しい要素を指すようにする．取り出す場合は front の要素を取り出し，front を削除した要素の次を指すようにする．

4.3節までが抽象データ型としてのリストやスタック，待ち行列の説明で，4.4節以降が具体的に実現するデータ構造の説明である．

4.4 配列によるデータ構造の実現

4.4.1 リストの実現

一般的なリストは中間へのデータの出し入れがあるため，リストの実現方法として配列は向いていない．（要素を大量にずらす必要があるため）

スタックや待ち行列は中間への出し入れが無いため，配列で効率良く実現できる．

4.4.2 スタックの実現

C の配列 x を使ってスタックを実現するには，要素数が n であるとき， x[0]をスタックの底，x[n-1] を頂上とすればよい．（添字のずれに注意）nをスタックポインタという．

data という変数に要素が1個格納されている場合， data をスタック x に積むには，現在の最新の要素である頂上が x[n-1] であるから，x[n] の位置に data を代入した後，n を 1 増やせばよい．これを一文で行っているのが P.42 の
x[n++] = data;
という文である．後置インクリメント演算子は，値を使った後でインクリメントする．

積むときとは逆に，スタック頂上のデータを降ろしてそれを data という要素 1 個用の変数に格納するには，同様に頂上が x[n-1] であることに注意して，n を 1 減らしてから x[n] の値を data に代入すればよい．これを一文で行っているのが P.42 の
data = x[--n];
という文である．インクリメント，デクリメント演算子は前置されるか後置されるかで，値の変わるタイミングが違う．前置された場合は先に n の値を減らしてからその n の値で配列 x にアクセスする．

インクリメント，デクリメント演算子をつけた値を使うときは前置か後置かに注意を払う必要がある．例えば n に 3 が保存されているとき， data = x[n--] を実行すると data にはx[3] が代入される．そのかわりに data = x[--n] を実行すると，配列 x へのアクセスより先に n がデクリメントされて data にはx[2] が代入される．どちらも実行後の n の値は 2 である．

インクリメント，デクリメントが前置か後置かで動作が変わるプログラムはミスを起こしやすい．
data = x[--n];
を 2 行にわけて書くと
--n;
data = x[n];
となる．この場合はデクリメント演算子が前置でも後置でも動作は変わらないので
n--;
data = x[n];
でも等価である．この授業ではこの前置後置に依存しない書き方を推奨する．その場合後置記法に統一できる．

動作するプログラムとして関数で書かれたものが教科書 p.44 List 4.1 の push 関数と pop 関数である．どちらもif 文の条件式の後に複数の文をブロックにまとめる括弧 {} が無いので条件が成り立ったときに実行される文は
error("stack ....\n");
の 1 文のみである．この文が実行されれば動作が終了するのでそれ以下が実行されるのはif の条件が成り立たなかった場合のみであるため， error関数以下の文は実質的に else ブロックとして働く． push を括弧の省略をせず，else ブロックを使った書き方をすると

void push(ELEM x)
{
  if (n >= STACK_SIZE){
    error("stack overflow\n");
  } else {
    stack[n++] = x;
}

教科書 p.42 の push 関数の
x[n++] = data;
と，pop 関数の
data = x[--n]
に対応するのは，それぞれ 35 行目の
stack[n++] = x;
と 43 行目の
return stack[--n];
である．推奨する2行で書く方法ならそれぞれ
stack[n] = x;
n++;
と
n--;
return stack[n];
になる．

P.43 の List 4.1 をコンパイルし，動作確認せよ．但し，サンプルファイルの 24 行目の

    fprintf(stderr, s);

    fprintf(stderr, "%s", s);

main()

int main(void)

に書き換える必要がある．このプログラムを終了するには行頭で Ctrl-d をキーボードから入力する．

4.4.3 待ち行列の実現

待ち行列では挿入する側(rear)はデータが追加されるばかりなので，配列で実現すると添字は増える一方になる．逆に削除される側(front)は削除だけなのでこれも添字は増える一方となる．このままだと要素の位置が全体的に添字の大きい方向へずれて行くので，配列の最後と最初を連結してリング状にして実現する．

この本では rear は末尾の次の要素の場所としていることに注意．この実装であれば待ち行列が空のとき，front と rear が同じ場所を指す．

配列の最後を超えたときに 0 に戻る計算は C の剰余演算 % で簡単にできる．

n 個めの要素が入れられた場合を考える．このときも front と rear が等しくなるので空の場合と区別がつかない．List 4.2 では要素数 n-1 個が待ち行列に入れられる要素の上限であるとしている．

P.48 の List 4.2 を動作させる実習を行う． List 4.2 も List 4.1 と同様に 29 行目の fprintf(stderr, s) を fprintf(stderr, "%s", s) に書き換える必要がある．

List 4.2 には main ルーチンがないため，テスト用のルーチンを自分で作る必要がある．待ち行列に格納されるデータの型は ELEM 型と書かれているが，これはプログラム中では long 型（倍精度整数型）として定義されている．テストでenqueue や dequeue で扱うデータの型は ELEM 型とする．printf で出力するときの書式は long 型の書式で出力しなければならないので "%d" ではなく "%ld" とする．以下に簡単なテスト用の main ルーチンを示す．

int main(void)
{
    ELEM x;

    enqueue(1);
    enqueue(2);
    enqueue(3);
    x = dequeue();
    printf("%ld\n", x);
    x = dequeue();
    printf("%ld\n", x);
    x = dequeue();
    printf("%ld\n", x);
}

課題

前回レポートのヒント

これは前回レポートが完成できなかった学生のための説明である．この課題はリスト（今回学ぶ）の全要素を出力する print_all関数を作成する課題である．以前に作ったプログラムを流用して，そこから作成を始める．

まず pwd コマンドを実行し， c ディレクトリにいることを確認する．ホームディレクトリにいる場合は cd c で移動する．ls コマンドで存在するファイルを確認せよ．

第1回課題が完成している学生は以下のコマンドを実行して report01.c をコピーして report02.c という名前のファイルを作れ．

jtXXXXXX@sirius:~/c$ cp report01.c report02.c

第1回課題が完成していない場合は第2回授業のList2.1の完成で作った mylist02_1.c をコピー元にすれば良い．この場合は下のコマンドを実行する．

jtXXXXXX@sirius:~/c$ cp mylist02_1.c report02.c

どちらのプログラムのメインルーチンでもデータは10件入力されている．例えば1件目だけを課題の指示通りのフォーマットで出力するなら，関数 print_all は以下のようになる．（課題ページに関数の書き出しを指示してある）

void print_all(void){
    printf("0:key=%d,data=%d\n",table[0].key,table[0].data);
}

上記関数をmain 関数の上に記述し， main 関数の中のデータの設定が終わった後，すなわち n=10; の後に

    print_all();

    0:key=1,data=1

同様にして 3 個までのデータを出力するなら関数 print_all を以下のようにすればよい．

void print_all(void){
    printf("0:key=%d,data=%d\n", table[0].key, table[0].data);
    printf("1:key=%d,data=%d\n", table[1].key, table[1].data);
    printf("2:key=%d,data=%d\n", table[2].key, table[2].data);
}

このようなprintf文を書き連ねる方法は繰り返し回数に応じて printf文の数を変えなければいけない．課題で求められているprint_all()関数は実行時でないと何回繰り返すかわからないのでこのやりかたでは作成できない．プログラムのソースコードはコンパイル時 に確定していないといけないからである．

プログラムは固定済みでも状況によって繰り返し回数を変えるようにするにはループを使う．ループを繰り返すたびに値が更新される変数をループ変数という．ループ変数を i として　i の値を 0,1,2 の順に更新しながら繰り返す処理は以下のように書く．（変数iの定義 int i; が必要なことに注意）

void print_all(void){
    int i;
    for(i = 0 ; i <= 2 ; i++){
        printf("%d:key=%d,data=%d\n", i, table[i].key, table[i].data);
    }
}

これはすぐ上の 3 行出力するルーチンと同じ動作をする． print_all を差し替えて動作テストせよ．

残る問題は完成版 print のループはどの値まで実行すればいいか，という問題である．上のプログラムはtable[0] から table[2]に格納されているデータを出力するものである．項目数はグローバル変数 n に格納されているのだから，出力しなければいけないデータは table[0] から table[n - 1] に格納されているデータである．そのようになるようにループの終了条件を i <= n - 1 に書き換えればよい．作成して実行せよ．

List リスト

出席登録