東京工業大学情報理工学院情報工学系 2018年度午前 3.

Author

祭音Myyura

Description

1) (短絡評価，優先順位, 結合性)

次の問いに答えよ。

a) C言語の演算子である論理積「&&」と論理和「||」の評価方法は短絡評価なので、オペランドの評価順序に注意が必要である。すなわち、2つの式 \(e_1\), \(e_2\) に対して、

i) \(e_1\) && \(e_2\) の評価では、まず \(e_1\) を評価し、\(e_1\) の評価結果が真 (0 でない整数) の場合のみ、\(e_2\) を評価する。\(e_1\) 評価結果が偽 (0) の場合は、\(e_2\) は評価されない。
ii) \(e_1\) || \(e_2\) の評価では、まず \(e_1\) を評価し、\(e_1\) の評価結果が偽 (0) の場合のみ、\(e_2\) を評価する。\(e_1\) の評価結果が真 (0 でない整数) の場合は、\(e_2\) は評価されない。

短絡評価に注意して、図 3.1 のプログラムの出力結果を答えよ。なお printf の返り値は (ヌル文字を除いた)出力文字数である。

#include <stdio.h>
int main() {
    if (0 && printf("A")) { printf("B"); }
    if (1 && printf("C")) { printf("D"); }
    if (0 || printf("E")) { printf("F"); }
    if (1 || printf("G")) { printf("H"); }
}

図3.1: 短絡評価に注意が必要なプログラム

b) 異なる演算子からなる式では、優先順位に従って、どの演算子を先に適用するかが決まる。例えば、C言語では、引き算「-」よりも割り算「/」の優先順位が高いので, 1 - 2 / 3 は 1 - (2 / 3) と同じ意味になる。C言語では、直接メンバー選択「.」と間接メンバー選択「->」は同じ優先順位である。また、アドレス演算「&」と間接演算「*」は同じ優先順位である. 直接メンバー選択「.」と間接メンバー選択「->」はアドレス演算「&」と間接演算「*」よりも優先順位が高い。次の式にカッコをつけて優先順位を明確にせよ。

i) *x->y
ii) &x.y

なお、間接メンバー選択を使った式 e->id は (*e).id と同等である (ただし、e は式，id は識別子)。

c) 同じ優先順位を持つ演算子からなる式では、結合性に従って、どの演算子を先に適用するかが決まる。例えば、C言語では、引き算「-」は左側の演算子を優先 (左結合) するので、1 - 2 - 3 は (1 - 2) - 3 と同じ意味になる。また代入「=」は右結合なので、x = y = 2 は x = (y = 2) と同じ意味になる。 C言語では、直接メンバー選択「.」と間接メンバー選択「->」は左結合、また，アドレス演算「&」と間接演算「*」は右結合である。次の式にカッコをつけて結合性を明確にせよ。

i) x->y->z
ii) *&x

2) (線形リスト・挿入)

次の問いに答えよ。

a) (素朴なプログラム) 図 3.2 はC言語による線形リストの素朴な挿入プログラムである。図 3.2 中の関数 insert1 は, 昇順にデータがソートされるように、線形リスト head 中に新たなデータ data を挿入する。この動作となるように, 図 3.2 中の空欄 [ A ] ~ [ D ] に最も適切な式を、図 3.5 の選択肢群から選んで, その番号を解答せよ. 同じ選択肢を何度選んでもよい。例えば、図 3.2 の main 関数の実行終了直前の線形リストは図 3.3 の通りになる。なお、NULL は「どこも指していないことを示す, 特別なポインタ値 (ヌルポインタ) であり、値は 0 である。

#include <stdio.h>
#include <stdlib.h>
typedef struct CELL {
    int data; struct CELL *next;
} CELL;
CELL * CELL_alloc (int data) {
    CELL *p = malloc (sizeof (CELL));
    p->data = data; p->next = NULL; return p;
}
CELL * insert1 (CELL *head, int data) {
    CELL *new = CELL_alloc (data);
    CELL *p = head;
    if (空欄[ A ] || 空欄[ B ]) { // 先頭に挿入する条件
        new->next = p;           // 先頭に挿入
        return new;
    } else {
        while (空欄[ C ] && 空欄[ D ]) { // 挿入箇所を探す
            p = p->next;
        }
        new->next = p->next; p->next = new;
        return head;
    }
}
int main () {
    CELL *head = NULL;
    head = insert1 (head, 10);
    head = insert1 (head, 20);
    head = insert1 (head, 30);
}

図3.2: 素朴な挿入プログラム

図3.3: main関数終了直前の線形リスト

b) (ポインタのポインタを使うプログラム) 図 3.2 のプログラムでは、空リストや先頭に挿入する場合、場合分けが必要になり、プログラムの見通しが悪い。この場合分けを不要にするには、先頭にダミーセルを置く方法や、ポインタのポインタを使う方法がある。ここでは図 3.4 に示す通りポインタのポインタを使う。ただし、構造体 CELL と関数 CELL_a11oc は図 3.2 と同じとする。図 3.4 中の関数 insert2 が、図 3.2 中の関数 insert1 と同じ挿入結果を得られるように, 図 3.4 中の空欄 [ E ] ~ [ G ] に最も適切な式を、図 3.5 の選択肢群から選んで, その番号を解答せよ. 同じ選択肢を何度選んでもよい。

void insert2 (CELL **head_p, int data) {
    CELL *new = CELL_alloc (data);
    CELL **p = head_p;
    while (空欄[ E ] && 空欄[ F ]) {
        p = 空欄[ G ]; // 次の next メンバーを指す
    }
    new->next = *p;
    *p = new;
}
int main () {
    CELL *head = NULL;
    insert2 (&head, 10);
    insert2 (&head, 20);
    insert2 (&head, 30);
}

図3.4: ポインタのポインタを用いた挿入プログラム

(1) p == NULL   (2) p != NULL   (3) p->next == NULL   (4) p->next != NULL   (5) (*p) == NULL
(6) (*p) != NULL   (7) data < p->data   (8) p->data < data   (9) data < p->next->data
(10) p->next->data < data   (11) data < (*p)->data   (12) (*p)->data < data   (13) p->next
(14) (*p)->next   (15) *p->next   (16) &*p->next   (17) &(*p)->next   (18) (&*p)->next

図3.5: 選护肢群

3) (線形リスト・逆順並び替え)

次の問いに答えよ、ただし、構造体 CELL は図 3.2 と同じとする。

a) (素朴な再帰) 図 3.6 の reverse1 は、再帰を用いた, 線形リストを逆順に並び替えるプログラムである。図 3.3 の線形リスト head を引数として reverse1 を呼び出した時, reverse1 からリターンする直前の線形リストの接続状況を図 3.3 のような形式で示せよ. また、図にはその時点で変数 head と p が線形リストのどの要素を指しているかも明示すること. reverse1 は再帰呼び出しのため複数回リターンすることに注意せよ (リターンする回数分の図が必要。実行時系列順に解答すること).

CELL * reverse1 (CELL *head) {
    CELL *p = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    p = reverse1 (head->next);
    head->next->next = head;
    head->next = NULL;
    return p;
}

図3.6: 素朴な再帰で逆順にするプログラム

b) (途中状態を引数で渡す再帰) 図 3.7 の reverse2 も与えられた線形リストを逆順に並び替えるプログラムである。 reverse2 (head, NULL); という形式で呼び出して用いる。再帰呼び出しの際に、 reverse2 の第 1 引数は「元のリストをある位置で分割した後半のリスト」、第 2 引数は「元のリストを同じ位置で分割した前半を逆順に並び替えたリスト」となる. 新たに reverse2 を呼び出しするたびに、第 1 引数から先頭要素を削除し, その先頭要素を第 2 引数の先頭に加える。空欄 [ H ] と [ J ] に式を、[ I ] に代入文を入れて、プログラムを完成させよ。

CELL * reverse2 (CELL *head1, CELL *head2) {
    if (head1 == NULL) {
        return head2;
    }
    CELL *new_head1 = [ 空欄 H ];
    [ 空欄 I ];
    CELL *new_head2 = [ 空欄 J ];
    return reverse2 (new_head1, new_head2);
}

図3.7: 途中状態を引数で渡す, 再帰逆順プログラム

c) (ループ) 図 3.8 の reverse3 も与えられた線形リストを逆順に並び替えるプログラムである。ループを使って線形リストを先頭から走査し、ポインタを逆順にしていく. 図 3.9 に示すように、変数 p1, p2, p3 は連続する3つの要素を指し、1 回のループで1つのポインタを逆向きに張替える. 次に p1, p2, p3 が指す要素を右に1つずらす。空欄 [ K ], [ L ], [ M ] に、代入文をそれぞれ1つずつ入れて、プログラムを完成させよ。

CELL *reverse3 (CELL *head) {
    CELL *p1 = NULL, *p2 = head, *p3;
    while (p2 != NULL) {
        [ 空欄 K ];
        p2->next = p1; // 逆向きにリンク
        [ 空欄 L ];
        [ 空欄 M ];
    }
    return p1;
}

図3.8: ループで逆順にするプログラム

図3.9: 1回のループで、ポインタを1つ張替え、変数p1，p2, p3を1つ右に移動させる

Kai

1)

a)

CDEFH

b)

i) *(x->y)
ii) &(x.y)

c)

i) (x->y)->z
ii) *(&x)

2)

a)

空欄[ A ]: p == NULL
空欄[ B ]: data < p->data
空欄[ C ]: p->next != NULL
空欄[ D ]: p->next->data < data

b)

空欄[ E ]: (*p) != NULL
空欄[ F ]: (*p)->data < data
空欄[ G ]: &(*p)->next

3)

a)

 10  ->  20  ->  30  ->  NULL

 10  ->  20  ->  NULL
        (20) <-  30 (the p)

 10  ->  NULL
(10) <-  20  <-  30 (the p)

b)

空欄[ H ]: head1->next
空欄[ I ]: head1->next = head2
空欄[ J ]: head1

c)

空欄[ K ]: p3 = p2->next
空欄[ L ]: p1 = p2
空欄[ M ]: p2 = p3

東京工業大学 情報理工学院 情報工学系 2018年度 午前 3.