課題(2002年度)のヒント

• くどいようですが、webPage.c の中を見る必要はありません。 みなさんは、webPage.h で公開された機能を触るだけでいいのです。
• プログラムで input.def を触る必要はありませんし、プログラムから見ないようにしましょう。 最初に与えられた page (index.html 相当)から、traceNthLink(page,i) でリンクをたどるのが基本です。

• 課題 1 と課題 2 は、別々に解いた方が解きやすいでしょう。たとえば、こんな感じ。 problem1/2Solver では、それぞれ、再帰を使いたければつかって、繰り返し文で行きたければそうすればいいんです。

  
  void problem1Solver(Page_tp page) { .... }
  void problem2Solver(Page_tp page) { .... }
  
  void userSearch(Page_tp page) {
      problem1Solver(page); /* まず、課題 1 を解いて */
      problem2Solver(page); /* 次に、課題 2 を解いて */
  }	
  

まずは課題 1 について。ポイントは、

• HTML でないファイルのリンクをたどるのは無理があります。isHTML(page) かどうか確認しましょう。
• まずは、リンクをたどって子供のページを見れるようにすることです。たとえば、page の子供たちの name を 表示させるならば、以下でOKでしょう？

  for(i = 0; i < getNumLinks(page); i++) {
      Page_tp child = traceNthLink(page, i);
      printf("Name: %s", getName(child));
  }
  

• たどれるページについて各リンクをたどるのですが、1 回しかたどらないようにすることです。 同じページについて、何度もたどっていると、グラフに cycle があるときに無限ループになります。
• あとは、segmentation fault とかではまったら、 gdb でみましょう。 たとえば、page のアドレスや、その page の内容が見たかったら、

  
  (gdb) print page [return]  /* アドレス値が分かる */
  (gdb) print *page [return] /* 中身が分かる */
  

  とかで見れます。多分、あり得ないアドレス値が入っているんでしょう。

• 深さ優先探索をするなら、多分再帰が楽でしょう。で、link をたどるごとに「深さ」の値を足していきたいなら、

  void p2search(Page_tp page, int depth) {
       ......
       Page_tp child = ....;
       p2search(child, depthd+1);
       ......
  }
  

  という作りにすると便利です。枝に向かうほど depth が大きくなります。大域変数の int depth とか作ると訳が分からなくなります。やめときましょう。
• 深さ優先探索をする場合は、はじめてたどったところや、新たな良い解を見つけたときは、計算を続ける という形になるんでしょうね。但し、index.html の深さは 0 なので要注意です。
• 幅優先探索をする場合は、ring buffer とかをつかうと楽が出来るでしょうね。