練習問題

練習問題の前に

はじめにおこなった小テストの問1, 2, 3, 4, 6, 7, 8, 9, 10 について、もう一度解きましょう。で、自信をもって答えられない問題があるようなら、鎌田に言ってください。 (どうせ、授業の試験では、さらに強化された問題が出題されますから、今のうちに解決しておくのが身のためです。)

練習問題

さて、基本的なデータ構造である queue (待ち行列)をつくりましょう(ソース)。多分、演習 III でもやっているはずだけど。各要素(element)とqueueはそれぞれ、このようなデータ構造にしてみました。

typedef struct element {
    struct element * next;
    int val;
} element_t, * element_tp;

typedef struct queue {
    element_tp head;
    element_tp tail;
} queue_t, * queue_tp;

さて、queue の基本的な機能は以下の二つの関数を実現すればできあがります。

element_tp get_queue(queue_tp q) : q から先頭の要素を取り除き、先頭要素への参照を返す
void put_queue(queue_tp q, element_tp elem): q の最後に elem を加える

途中まで作ってあるので、頑張って完成させてください。 main() にテスト実行用のコードを準備しておきますので、正しく動くように頑張ってください。たとえばこんな感じ。

kamada@shusaku%a.out
get_queue(queue) is ... [address: 10015020] [val:    0]
get_queue(queue) is ... [address: 10015030] [val:    1]
get_queue(queue) is ... [address: 10015040] [val:    2]
get_queue(queue) is ... [address: 10015050] [val:    3]
get_queue(queue) is ... [address: 10015060] [val:    4]
get_queue(queue) is ... [address: 10015070] [val:    5]
get_queue(queue) is ... [address: 10015080] [val:    6]
get_queue(queue) is ... [address: 10015098] [val:    7]
get_queue(queue) is ... [address: 100150a8] [val:    8]
get_queue(queue) is ... [address: 100150b8] [val:    9]
get_queue(queue) is ... [address: NULL]
get_queue(queue) is ... [address: NULL]
get_queue(queue) is ... [address: 100150c8] [val:   10]
get_queue(queue) is ... [address: 100150d8] [val:   11]
get_queue(queue) is ... [address: 100150e8] [val:   12]
get_queue(queue) is ... [address: 100150f8] [val:   13]
get_queue(queue) is ... [address: 10015108] [val:   14]
get_queue(queue) is ... [address: 10015118] [val:   15]
get_queue(queue) is ... [address: 10015128] [val:   16]
get_queue(queue) is ... [address: 10015138] [val:   17]
get_queue(queue) is ... [address: 10015148] [val:   18]
get_queue(queue) is ... [address: 10015158] [val:   19]
get_queue(queue) is ... [address: NULL]
get_queue(queue) is ... [address: NULL]

gdb とかつかってデバッグするといいでしょう。頑張りましょう。

一応、解答例ものせておきますが、一度も作ったことがない人は必ず解くこと。でないと、課題で悲しいことになります。

2001.11.12/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp