双方向リスト・ハッシュの操作
この演習では、双方向リストとハッシュというデータ構造について学び、各手法をC言語で実装する方法について学びます。
問題の難易度の目安【易】⭐ 【標準】⭐⭐【難】⭐⭐⭐
問題1⭐⭐
与えた入力を元に，双方向リストを先頭から表示し、そのあと、末尾から表示するプログラムを完成させましょう。
./a.out 1 2 3 4
と実行すると、
4 <-> 3 <-> 2 <-> 1
1 <-> 2 <-> 3 <-> 4
と表示します。
Note
授業で習った，双方向リストの挿入を学ぶ。
問題2⭐⭐
このプログラムは、ある値を双方向リストから探すプログラムです。 入力の最初が探す値、それ以降は双方向リストの値となります。
./a.out 61 17 21 22 78 50 61 71 47 93 44
と実行すると、探す値は61、それ以降は双方向リストとなるので、
Found (61)
./a.out 11 17 21 22 78 50 61 71 47 93 44
と実行すると、
Not Found (11)
と表示されます。
Note
授業で習った、双方向リストの検索を学ぶ。 searchを再帰で書いてみるとかっこいいです。
問題3⭐⭐
このプログラムは、任意の個数の値を双方向リストから削除するプログラムです。
双方向リストと削除する値は /で区切られて与えられます。
./a.out 17 21 22 78 50 61 71 47 93 44 / 61
と実行すると、/の前までが双方向リストとして格納され表示します。そのあと、61を削除して表示します。
44 <-> 93 <-> 47 <-> 71 <-> 61 <-> 50 <-> 78 <-> 22 <-> 21 <-> 17
44 <-> 93 <-> 47 <-> 71 <-> 50 <-> 78 <-> 22 <-> 21 <-> 17
また，入力する数字を複数与えて実行すると
./a.out 17 21 22 78 50 61 71 47 93 44 / 44 93
この場合は、44と93を削除しています。
44 <-> 93 <-> 47 <-> 71 <-> 61 <-> 50 <-> 78 <-> 22 <-> 21 <-> 17
47 <-> 71 <-> 61 <-> 50 <-> 78 <-> 22 <-> 21 <-> 17
と表示されます。
リストにない数字を削除しようとした場合は、何も削除せず、エラーも出しません。
Note
授業で習った，双方向リストの削除を学ぶ。
問題4⭐⭐
問題1で作ったプログラムを番兵を用いて再実装します。
番兵バージョンでも、
./a.out 1 2 3 4
と実行すると、
4 <-> 3 <-> 2 <-> 1
と表示します。
Note
授業で習った，番兵を用いた実装方法を学ぶ。
Warning
番兵バージョンなので，headが変わることはありません。 なので，headはグローバル変数として宣言しています。 そのため、問1のようにinsert関数の引数として、headを渡さなくても動作します。
問題5⭐⭐⭐
与えた入力を元に，双方向リストを先頭から表示し、そのあと、末尾から表示するプログラムを完成させましょう。
./a.out 1 2 3 4
と実行すると、
4 <-> 3 <-> 2 <-> 1
1 <-> 2 <-> 3 <-> 4
と表示します。
ただし、このプログラムは番兵バージョンで、reverse_print_listを実装します。 番兵を用いると実装がすっきりすることを問1のreverse_print_listと比較して確認すると良いでしょう。
問題6⭐⭐
このプログラムは，衝突を考慮していないハッシュの実装です。 引数として与えられた数列は、配列に格納されます。
./a.out 3 5 77 109 190 245 832 852 9924 10346
と実行すると
[190 77 0 3 0 5 9924 0 0 0 10346 0 0 0 109 832 852 245 0 ]
と表示され、
./a.out 3 5 77 109 190 245 832 852 9924 10346 25
と実行すると，衝突がおきるため、
collision!
と表示されます。
Note
授業で習った，衝突を考慮していないハッシュの実装について学ぶ．
Note
ここで使うハッシュ関数はk mod 19です。
問題7⭐⭐
チェイン法を使ったハッシュの実装で、衝突に対して考慮されているプログラムを作ります。
./aout 456 3 5 44 25 77 109 190 245 832 852 9924 10346
と実行すると、衝突はおきますが、
190 <-> 456
77
/
3
/
5
9924 <-> 25 <-> 44
/
/
/
10346
/
/
/
109
832
852
245
/
と表示されます。
Note
授業で習った，チェイン法を用いたハッシュの実装について学びます。
問題8⭐⭐⭐
このプログラムは，チェイン法を用いたハッシュの実装で、 ハッシュから該当するデータがあるかどうかを調べるプログラムです。 最初の数字が探す値で、それ以降はハッシュに格納されます。
./a.out 3 456 3 5 44 25 77 109 190 245 832 852 9924 10346
と実行すると、探す値は3となり、
Found
と表示されます。
./a.out 3 456 3 5 44 25 77 109 190 245 832 852 9924 10346
と実行すると、探す値は100となり、
Not Found
と表示されます。
Note
授業で習った，チェイン法を用いたハッシュの検索ついて学びます。
問題9⭐⭐
このプログラムは，線形走査法を用いたハッシュの実装です。
./a.out 3 5 77 109 190 245 832 852 9924 10346
として実行すると、
[190 77 0 3 0 5 9924 0 0 0 10346 0 0 0 109 832 852 245 0 ]
と表示され、
./a.out 3 5 77 109 190 245 832 852 9924 10346 25 91
として実行すると衝突がおき、線形走査法を用いて衝突を回避しているため、
[190 77 0 3 0 5 9924 25 0 0 10346 0 0 0 109 832 852 245 91 ]
と表示されます。
Note
授業で習った，線形走査法のハッシュの実装について学びます。
問題10⭐⭐⭐
渡される配列は、
- 要素数n
- 数字の範囲は0からn
- 同じ値はない
となっているとします。
この配列から、欠けている数字を探しましょう。
./a.out 4 3 0 1
と実行すると、
lack number = 2
と表示され、
./a.out 0 1 2 3
と実行すると、
lack number = 4
と表示されます。