━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題３
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (リストの基本操作)

(1) リスト l1 = [10, 20, 30, 40, 50] に対して，次の基本操作を順に実行した後の
　　リスト l2 が何かを答えよ．

        insert(l1, 1, 0);
        delete(l1, 5);
        l2 = sub(l1, 3);

(2) リスト l = [10, 20, 30] に対して次のプログラムを実行した後の val の値が
　　何かを答え，その値が何を意味するかを説明せよ．

        int val = 0;
        while (! empty(l)) {
            val += access(l, 1);
            delete(l, 1);
        }

──────────────────────────────────────

●答 (リストの基本操作)

(1) l2 = [20, 30, 50]
(2) val の値は 60．これは，リスト l の要素の総和を表す．

[解説]

(1) リスト l1 は insert() 実行後に [0, 10, 20, 30, 40, 50] となり，
delete() 実行後 に [0, 10, 20, 30, 50] となる．

この問題で使う三つの基本操作は，次の機能をもつ．
        insert(l, k, a) … リスト l の位置 k に要素 a を挿入する
        delete(l, k) … リスト l の位置 k の要素を削除する
        sub(l, k) … リスト l の位置 k 以降の部分リストを返す
なお，列の先頭位置を(0でなく) 1 で表していることに注意する．

(2) ループの実行前と反復ごとの l と val は，次のように変化する．

        回数    l               val
        -----------------------------------------
        0       [10, 20, 30]    0
        1       [20, 30]        10 (＝  0 + 10)
        2       [30]            30 (＝ 10 + 20)
        3       []              60 (＝ 30 + 30)

反復ごとに，リストの先頭要素が val に加算され，リストから取り除かれる．
プログラムの動作が分かりにくい場合には，この問題で考えたように，
小さな具体例での各変数の値の変化を考えるとよい．
なお，基本操作 delete() が削除値を返す機能をもつなら，直前の access() が不要で，
ループ中に val += delete(l, 1); だけを実行すればよい．

このアルゴリズムは，基本操作を組み合わせて，より複雑な処理を実現する例である．
列に対する基本操作としては，空判定，(先頭要素の)参照，(先頭要素の)削除，
の三つが使われている．これらを使って，列の走査(一つずつ全ての要素の処理)を
しながら総和を計算するという，より複雑な処理が実現されている．

列は，先頭要素と残りのリストとに分けて，効率的に反復処理できることが多い．
処理位置を限定して効率化する考え方は，スタックやキューなどのデータ構造で
活用される．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/