課題(2002年度)

• 実行の結果求まるはずのデータを公開しました。
  こんな感じになるはずです。 皆さんのプログラムは、結果を print する必要はありません。
  
• 実行結果が違う人が多くなりそうなので、 webPage.cを採点機能付きにしました。 reload してから持っていってください。 解答ファイルである problem1ans.defと、 problem2ans.defがコンパイルに必要になります。 こちらも持っていきましょう。

課題の締め切りですが、2 段階に設定しています。 最初の締め切りは、11/5 です。出せる人は、11/5 までに提出するように頑張りましょう。 出せなかった人は、現在の状況を連絡するように。
皆さんの状況をもとに 11/5 の夜にヒントを出します。最終締め切りは、11/13 にします。 このあと、解答例を紹介することにする予定です。

もし、最終締め切りに間に合わなかった場合でも、解答例などを参考にシッカリとした解説などを送ってくれれば、評価します。 とはいえ、自作プログラムではないので、点数は低くなりますけど。

それから、他の人に色々アドバイスをもらった場合は、必ずレポート冒頭にその旨明記してください。 何の断りもなく他人のプログラムに酷似したプログラムを提出した場合、確認の上、僕の演習分の点数はなくなると思ってください。

さて、この演習ページには例えば

"compile_app_gcc.html"から"compile_link.html"へのリンク

さて、これらのリンクをたどることでいろんなページに行くことができるのですが、 ページの中には、

• HTML: hyper text で、リンクなども持つ
• 一般テキスト: C や Java のソースなど、リンク情報を持たないもの

というわけで、僕の方で Page_t というWEB Page を表す構造体(中身は内緒)と、 利用可能な関数群を準備しました。webPage.hで宣言してあります。

• char * getName(Page_tp page): Page の名前を返す
• int isHTML(Page_tp page): HTML text (リンクを含むページ) であるかどうかを返す。
• int getNumLinks(Page_tp page): 含まれる link の数を返す
• Page_tp traceNthLink(Page_tp page, int num): n 番目の link 先のページを返す
• UserArea_tp userArea(Page_tp page): 各 page に関するユーザ用の記述領域(宣言)

皆さんに与えられた仕事は、このリンク空間を"index.html"からリンクをたどりながら探索し、以下の課題をこなすことです。

• 問題1: index.html からたどり着くことにできる各ページについて、どれだけリンクで参照されているかを調べましょう。 但し、数えるのは、index.html からたどりつくことの出来るリンクに関してのみ、カウントしてください。
  各 Page_tp page に対して、

  
  	userArea(page)->inverseLink
  

  に結果を格納しましょう。

  index.html ページに関しては、 本来は、見つかったページからのリンクだけをカウントするはずです。 でも、それよりカウント数が一つ多い(最初の index.html へのアクセスを余分に数えた)場合でも OK にしています。

• 問題2: 各ページが index.html から何回リンクを経由してたどり着くことができるか、その最小値を求めましょう。
  但し、index.html 自身と、到達不可能なページは初期値 0 のままで構いません。
  各 Page_tp page に対して、

  
  	userArea(page)->depth
  

  に結果を格納しましょう。

main program は、初期セットアップが終わってから、index.html の page に対して、 userProg.cの中の

void userSearch(Page_tp page)

ファイル群の説明をしておきますと、

• webPage.h: 提供ライブラリの宣言。変更の必要なし。ライブラリの使い方が載っている
• webPage.c: 提供ライブラリの実装。変更の必要なし。見る必要もなし(見てもいいけど、、)。
• input.def: 問題例で、どのようなリンク情報が含まれているかを示す。 webPage.c で使っているので、一緒にもっていって下さい。編集すると、問題が変化します。

• userArea.h: ユーザメモ領域用構造体 UserArea の定義。必要に応じて、編集しても良い。
• userProg.c: ユーザプログラムを実装する場所。頑張って作りましょう

• Makefile: Makefile も置いておきます。make とやると、自動でコンパイルが進むことでしょう。(copy&paste すると、行頭のtubが space に変わるかもしれないので注意)

% make
gcc -g -Wall   -c -o webPage.o webPage.c
gcc -g -Wall   -c -o userProg.o userProg.c
gcc -o webSearch  webPage.o userProg.o
% ./webSearch        今のところ、userSearch(page)は、単に page の中身を表示しているだけ
Name: index.html
HTML?: true
uara depth 0
uara inverse link 0

プログラムが完成し、その解説ができたら課題を提出しましょう(提出法)。 提出物は、プログラム解説と、皆さんの変更／作成したプログラムです。 くれぐれも、名前や学番を忘れないようにしてください。 書き忘れていましたが、演習の感想もお願いします。

それから、この課題は、再帰関数の扱いと、 pointer を辿る skill と、有向グラフのイメージがあれば、特に難しくないはずです。 あと、debugger が結構役立つと思います(segmentation fault とかを起こしやすそうだし)。

オプション課題

• このプログラムでは、リンクが後から増減することは考えていません。
  リンクの増減に対応した Page_t の実装、ならびに、inverseLink, depth の再計算法を考えて、実装してみましょう。
• このプログラム、Java で書くとどうなるのでしょうか？ 考えて実装してみましょう。