構造体・typedef・アロー演算子・スタック・キュー

この演習では、構造体ついて学び、スタックやキューなどのデータ構造について学びます。また、それらをC言語で実装する方法について学びます。

問題の難易度の目安【易】⭐ 【標準】⭐⭐【難】⭐⭐⭐

問題1⭐

出力結果が

名前:さくらみこ
誕生日:3月5日
愛称:みこち

となるように、プログラムを完成させましょう。

Note

構造体の定義・宣言・代入を学びます。

問題2⭐

出力結果が

名前:宝鐘マリン
年齢:大体17歳
愛称:船長

となるように、プログラムを完成させましょう。

Warning

すでにある関数や変数を変更すると正しい理解にならないです。

Note

typedefとアロー演算子を理解。

問題3⭐ ⭐

引数で与えた文字をリストに格納するプログラムを作りましょう。

./a.out p o c i m

と実行すると、

m i c o p

という表示になります。

Note

構造体を使った問題に慣れる目的の問題です。単方向リストという構造になってます。

問題4⭐ ⭐

リストの長さを計算する関数を作りましょう。ただし、その関数は再帰関数にしましょう。

./a.out J u z u t s u

と実行すると、

length = 7

と表示されます。

Note

構造体を使った問題に慣れる＋再帰関数で美しく書く。

問題5⭐ ⭐

リストの要素である文字を大文字に変えて表示する関数を作りましょう。ただし、その関数は再帰関数で、表示は最後に改行を入れましょう。

./a.out a r u k a s

と実行すると、

S A K U R A

と表示されます。

Note

構造体を使った問題に慣れる＋再帰関数で美しく。

Note

大文字にするためには，toupper関数を使うといいでしょう。各自調べましょう。

問題6⭐ ⭐

プログラムはスタックの動作を表示します。入力として、0以上の値を与えたときはスタックに値を追加し、負の数を与えたときは、スタックから値を取り出します。

./a.out  1 2 3 -1 4 5 -1

と実行すると、

[1 ]
[1 2 ]
[1 2 3 ]
3 poped
[1 2 ]
[1 2 4 ]
[1 2 4 5 ]
5 poped
[1 2 4 ]

のような表示になり、

./a.out 1 2 -1 -2 -3 -4

と実行すると、

[1 ]
[1 2 ]
2 poped
[1 ]
1 poped
[]
error:underflow

という表示になります。

Note

授業で習った，スタックの実装を学ぶ。アンダーフローのみ考慮します。

問題7⭐ ⭐

プログラムは非常に簡単なキューの動作をします。入力として、0以上の値を与えたときはキューに値を追加し、負の数を与えたときは、キューから値を取り出します。

./a.out 1 2 3 -1 4 5

と実行すると、

[1 ]
[1 2 ]
[1 2 3 ]
1 dequeued
[2 3 ]
[2 3 4 ]
[2 3 4 5 ]

と表示します。

Note

このプログラムでは、キューがあふれたり、キューに値がないのに値を取り出すなどの操作はされないとします。

問題8⭐ ⭐ ⭐

問題7のキューの実装方法では、tailが配列の最後までいってしまうと、それ以上enqueueできません。しかし、queueが何回かdequeueされているなら、配列の最初のほうは空いています。そこをうまく使えば，enqueueできるはずです。この問題では、その方法を使ってqueueを実装します。

./a.out 1 2 3 4 -1 -1 5 6

と実行すると、

[1 ]
[1 2 ]
[1 2 3 ]
[1 2 3 4 ]
1 dequeued
[2 3 4 ]
2 dequeued
[3 4 ]
[3 4 5 ]
[3 4 5 6 ]

と表示します。

Note

このプログラムでは配列のサイズは5なので，問題7の方法ではenqueueできませんでした。 queueの別実装を学びます。

Warning

ちなみに，このプログラムではアンダーフローもオーバーフローにも対応してません。例えば，引数として 1 2 3 4 5 6 7 など入れてみると，変な結果になると思います。これは次の問題で対応します。

問題9⭐ ⭐ ⭐

問題8のキューの実装方法では、アンダーフローもオーバーフローも対応してませんでした。以下のように動作し、アンダーフローとオーバーフローに対応するようにプログラムを完成させましょう。

./a.out 1 2 3 4 5

と実行すると、

[1 ]
[1 2 ]
[1 2 3 ]
[1 2 3 4 ]
overflow

/a.out 1 2 -1 -1 -1

と実行すると、

[1 ]
[1 2 ]
1 dequeued
[2 ]
2 dequeued
[]
underflow

という表示になります。

問題10⭐ ⭐ ⭐

'(', ')', '{', '}', '<' , '>', という6つの文字を含む文字列が与えられます。以下の条件を満たすときtrueと返し、そうでないときfalseと返すプログラムを作成しましょう。

開きカッコは必ず同じ種類の閉じカッコで閉じている
開きカッコは正しい順番で閉じている．

たとえば、

()
()<>
{()}

はtrueですが、

(}
({)}

はfalseとなります。

/a.out "(<{}>)"

と実行すると、

true

と表示されます。