AProg/2017/ex06 の履歴(No.2)

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• AProg/2017/ex06 へ行く。
  • 1 (2017-10-14 (土) 15:47:34)
  • 2 (2017-10-14 (土) 16:04:57)
  • 3 (2017-10-21 (土) 15:13:08)
  • 4 (2017-10-27 (金) 13:30:48)

---

応用プログラミング及び実習 2017年度 第6回†

工事中

注意†

• 実習のすすめ方について AProg/2017/ex00
• Linux環境での操作についてわからないことがあったら Docs/4UNIXBeginners
• 締切に間に合わずチェックを受けられなかった課題は自分で完成させておくこと． 先の回には，過去の課題のプログラムを改造して新たなプログラムを作る課題があります． 締切後には点数はつきませんが，質問等は随時どうぞ．

課題A(self) 締切:今回の演習終了時†

構造体の学習(1)

講義資料の kcard.h, kcard.c, kenshin3.c を作ってコンパイル&実行しよう． kenshin3.c は以下のリンク先から入手すればよい．

kenshin3.c

check 他の2つは，理解を深めるため，コピペしたりしないで，何を書いてるのか考えながらキーボードを叩いて入力しよう．

課題B(self) 締切:今回の演習終了時†

構造体の学習(2) & 郵便番号簿探索プログラム作成の準備(1)

第5回課題C のプログラムと同じことをする，構造体バージョンのプログラムを作ろう．ファイルは次の2つから成るものとする．

ex06zip.h

次のものを含むヘッダファイル

• ex05zip.c と同様の定数 NCHAR の定義（構造体の定義で使う）
• 郵便番号簿データ（郵便番号と住所）を格納するための構造体の定義（詳しくは後述）

ex06b.c

main関数を定義したソースファイル．次のようなものとする．

• 上記ヘッダファイルで定義された構造体の配列を宣言する．配列の大きさは，ex05zip.c と同じように，ソース中で定義した定数 NDATA で表す．
• ファイル zipdataS を読んで，上記の配列の要素に代入する．ex05zip.c と同様に，読み込みの処理はfscanfの戻り値を利用して行うこと．
• ex05zip.c と同様に，データ件数，最初のデータ，最後のデータを printf で出力する

構造体の定義は次のようにすること．

• typedef を用いて，ZIP という型名にする
• ZIP の変数1つは1件分の郵便番号簿データを格納するものとする
• 何をメンバとすべきかはよく考えよう．メンバ名は自分で決めたらよい

課題C(TA&takataka) 締切: 後述†

郵便番号簿探索プログラム作成の準備(2)

• TAチェック課題としての締め切り: 今回の実習終了20分前
• takatakaチェック課題としての締め切り: 月曜13時（提出法については AProg/2017/ex00参照）

↓の課題E で，郵便番号データを読み込んで郵便番号をキーとして線形探索するプログラムを作成する．その準備として，次の2つのものを紙に書きなさい（どこが1の解答でどこが2の解答かわかるように，線を引いて番号を書き入れる等の工夫をしてください）．

1. 課題B で書いた構造体 ZIP の定義
2. 線形探索の関数の定義

線形探索の関数は次の仕様を満たすようにすること

• 関数名は LSearch とする
• 引数は，ZIP の配列，その要素数，探索キーの値（郵便番号）の3つ．順序もこの通りとする
• 戻り値は次のように定める
  • 配列中にキーの値と一致するものが見つかった場合はその要素番号（配列の添字）
  • 見つからなければ -1
• 探索アルゴリズムは線形探索とする．配列中に同じキー値をもつデータが複数含まれている場合のことは考慮しなくてよい（配列の先頭から探して最初に見つけたものの番号を返すようにすればよい）
• この関数中ではscanfもprintfも使わない（デバグ中は別ですが）

課題D(TA) 締切:次回実習開始直後†

他人の作ったプログラムを利用してみる

前回の課題A のソースファイル入手先と同じ場所に，prime.h, prime.o, primedata.txt という3つのファイルがある．次のように cp コマンドを実行すると，これらを手元にコピーすることができる．

$ cp /roes/sample/takataka/aprog20XY/prime*   .     ← 最後の「空白＋ピリオド」を忘れずに

この3つのファイルは，次のようなものである．

• prime.o: 3つの関数を定義したC言語ソースファイルを龍大計算機室の環境のコンパイラ cc でコンパイルして得られたオブジェクトファイル．オブジェクトファイルだから，中身は（普通の）人間には読めません．
• prime.h: 上記3つの関数のプロトタイプ宣言を書いたヘッダファイル．コメントとしてそれぞれの関数の機能と引数の意味が書いてある．
• primedata.txt: いくつかの整数がならんだテキストファイル．less や emacs で中身を眺めてみよう．

これらのファイルを利用するプログラムを書こう．ただし，↓のリンク先に main関数を定義したソースファイルがあるので，これを手元に保存し，そこに書かれたコメントを参考に修正を加えて作ること（mainの中身は，「★★★」の部分以外を修正する必要はないはず）．

ex06prime.c

• check prime.o はオブジェクトファイルなんだから，既に cc -c の手順は済んでるわけですね．後は ex06prime.c の方をコンパイルして，2つのオブジェクトファイルをリンクして実行形式を作る，と．
• check 授業で説明したように，オブジェクトファイルは，ソースをコンパイルして（ほぼ）機械語プログラムの状態にしたものです．上記のように prime.o は龍大計算機室の環境で実行できる機械語プログラムを生成するコンパイラで作ってあるので，それ以外の環境ではおそらく使えません．
• check 完成して動作確認できたら，次のことを考えよう
  • なぜ 4649 と 5963 は出てこない？
  • NDATA を 10 に変更したらどうなる？

課題E(TA) 締切:次回実習終了20分前†

郵便番号簿探索プログラムの作成(1)

課題B と 課題C の結果を組み合わせて，郵便番号データを読み込んで，郵便番号をキーとして線形探索するプログラムを作成しよう．

ファイルの構成は次のようにすること．

ex06zip.h

課題Bと同じヘッダファイル．必要なものを追加

ex06zip.c

課題Cで書いた線形探索の関数を定義．

ex06lsearch.c

main関数を定義（ソースファイル名は イーエックスゼロロクエルサーチ）

実行すると次のような動作をするように作ること．

1. 郵便番号データのファイル zipdataS を読み込む
2. キーの値（検索したい郵便番号）を入力してもらう．それが負の数だったらプログラムを終了
3. LSearch を呼ぶ
4. 戻り値に応じた結果を出力
   • 見つからないときはそのことを知らせる
   • 見つかったときはその郵便番号と住所を出力（0からはじまる郵便番号に注意）
5. 2. に戻る

• check zipdataS はデータ件数が少ないので，探索で見つかる例を探すのが難しいかも．そういう時は，zipdataS を less や emacs で開いて，出てくる郵便番号を使ったらよい．
• check ファイル zipdataS を使って十分動作確認ができたら，fopen の1つ目の引数を

  "/roes/sample/takataka/aprog20XY/zipdata"

  にして実行してみなさい．このように fopen の第1引数にディレクトリ名を含む「パス」を指定すると，プログラムを実行したディレクトリと異なる場所にあるファイルでも開くことができる．チェックを受けるときはこちらのデータを使うこと．ただし，
  • ファイル zipdata にはたくさんの郵便番号データが含まれているので，NDATA は13万以上の数にする必要がある．
  • また，NDATAが小さかった時には正常に動いていたプログラムが，NDATA を大きくしただけで 「Segmentation Fault」，「Bus Error」，「セグメントエラー」といったエラーを出すようになることがあるかもしれない．その場合，ZIPの配列を

    static ZIP hoge[NDATA];

    のように static をつけて宣言すると解決するだろう．なぜこうすると解決するかが気になる人は，高橋に尋ねてください．

課題S（おまけ） 締切: 次回実習開始直後†

郵便番号データのソート

課題B のプログラムをもとにして，郵便番号データをソートして出力するプログラムを作ろう．ただし，ソートのアルゴリズムには，平均の時間計算量が \( O(n\log{n}) \) であるようなものを選び，関数を使って実現すること．