Top / AProg / 2015 / ex06

応用プログラミング演習 2015年度 第6回 [edit]

注意 [edit]

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

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

構造体の学習(1)

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

kenshin3.c

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

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

構造体の学習(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) 締切: 後述 [edit]

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

  • TAチェック課題としての締め切り: 今回の演習終了20分前
  • takatakaチェック課題としての締め切り: 再来週(1週お休みなので)木曜17時30分まで(提出法については AProg/2015/ex00参照)

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

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

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

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

課題D(TA) 締切:次回演習開始直後 [edit]

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

自分の aprog2015 ディレクトリへ移動してから,次のように cp コマンドを実行すると,prime.h と prime.o という2つのファイルを手元にコピーすることができる.

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

これらは,次のようなものである.

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

これらのファイルを利用するプログラムを書こう.ただし...

  • ex06d.c というソースファイルを作り,main関数を定義する
  • main では,上記3つの関数を呼んでその動作を確認できるようにする
  • 関数たちに渡す配列の中身は,プログラム中で適当に初期化しておいたらよい.ただし,関数の動作を確認できるような例をよく考えること.ウェブで検索したらいろいろ素数表が見つかりますね.
  • check prime.o は既にオブジェクトファイルになんだから,cc -c の手順は既に済んでるわけですね.後は ex06d.c の方をコンパイルして,2つのオブジェクトファイルをリンクして実行形式を作る,と.
  • check 授業で説明したように,オブジェクトファイルは,ソースをコンパイルして(ほぼ)機械語プログラムの状態にしたものです.上記のように prime.o は龍大計算機室の環境で実行できる機械語プログラムを生成するコンパイラで作ってあるので,それ以外の環境ではおそらく使えません.
  • check TAのN君に教わった,楽しい例:
    {13,103,1033,10333,103333,1033333}

課題E(TA) 締切:次回演習終了20分前 [edit]

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

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

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

ex06zip.h
課題Bと同じヘッダファイル.必要なものを追加
ex06zip.c
課題Cで書いた線形探索の関数を定義.
ex06e.c
main関数を定義

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

  1. 郵便番号データのファイル zipdataS を読み込む
  2. キーの値(検索したい郵便番号)を入力してもらう.それが負の数だったらプログラムを終了
  3. LSearch を呼ぶ
  4. 戻り値に応じた結果を出力
    • 見つからないときはそのことを知らせる
    • 見つかったときはその郵便番号と住所を出力(0からはじまる郵便番号に注意)
  5. 2. に戻る
  • check zipdataS はデータ件数が少ないので,探索で見つかる例を探すのが難しいかも.そういう時は,zipdataS を less や emacs で開いて,出てくる郵便番号を使ったらよい.
  • check ファイル zipdataS を使って十分動作確認ができたら,fopen の1つ目の引数を
    "/roes/sample/takataka/aprog2015/zipdata"
    にして実行してみなさい.このように fopen の第1引数にディレクトリ名を含む「パス」を指定すると,プログラムを実行したディレクトリと異なる場所にあるファイルでも開くことができる.チェックを受けるときはこちらのデータを使うこと.ただし,
    • ファイル zipdata にはたくさんの郵便番号データが含まれているので,NDATA は13万以上の数にする必要がある.
    • また,NDATAが小さかった時には正常に動いていたプログラムが,NDATA を大きくしただけで 「Segmentation Fault」,「Bus Error」,「セグメントエラー」といったエラーを出すようになることがあるかもしれない.その場合,ZIPの配列を
      static ZIP hoge[NDATA];
      のように static をつけて宣言すると解決するだろう.なぜこうすると解決するかが気になる人は,高橋に尋ねてください.

課題S(おまけ) 締切: 次回演習開始直後 [edit]

郵便番号データのソート

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

次回予告 [edit]

次回出題予定の課題の一部は,次回の授業日(11月6日)以前に公開する予定です. 公開したら AProg/2015 からリンクしますので,確認してください.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-10-23 (金) 19:05:19 (702d)