実験3 アルゴリズム(2) 木構造 - 情報生体システム工学実験II

<<option chkGenerateAnRssFeed>> GenerateAnRssFeed\n<<option chkOpenInNewWindow>> OpenLinksInNewWindow\n<<option chkSaveEmptyTemplate>> SaveEmptyTemplate\n<<option chkToggleLinks>> Clicking on links to tiddlers that are already open causes them to close\n^^(override with Control or other modifier key)^^\n<<option chkHttpReadOnly>> HideEditingFeatures when viewed over HTTP\n<<option chkForceMinorUpdate>> Treat edits as MinorChanges by preserving date and time\n^^(override with Shift key when clicking 'done' or by pressing Ctrl-Shift-Enter^^\n<<option chkConfirmDelete>> ConfirmBeforeDeleting\nMaximum number of lines in a tiddler edit box: <<option txtMaxEditRows>>\nFolder name for backup files: <<option txtBackupFolder>>\n<<option chkInsertTabs>> Use tab key to insert tab characters instead of jumping to next field

\n\n実験3　「アルゴリズム(2) 木構造」手引き\n\n[img[keyboard.jpg]]\n\n1. [[目的]]\n\n2. [[実験内容]]\n\n3. [[実験]]\n \n4. [[課題]]\n\n5. [[担当教員]]\n\n/%\n[[レポート提出状況|exp2-06_report01.html]]\n@@color(red):''再提出締切: 12月22日14:30'' @@%/

[[担当教員]]の項目を参照

\n1. [[目的]]\n\n2. [[実験内容]]\n\n3. [[実験]]\n \n4. [[課題]]\n\n/%\n[[レポート提出状況|./exp2-06_report01.html]]\n@@color(red):''再提出締切: 12月22日14:30'' @@%/

情報生体システム工学実験II

実験3 アルゴリズム(2) 木構造

Ken Kihara

データファイル（[[data_members_unsrt.txt|./data_members_unsrt.txt]] から読み込んだ内容をもとに木構造を持つ会員データベースを構築するプログラムを作成する．\n\n[img[fig_chart.bmp]]\n\n''[実験1]'' \n\nデータファイル（[[data_members_unsrt.txt|./data_members_unsrt.txt]]）を開き，内容を一行ずつ文字列（@@color(blue):char buffer[80]@@）に読み込み，\n名前（@@color(blue):char name@@）とポイント（@@color(blue):int point@@）を切り出してノード（@@color(blue):struct Node@@））に格納するプログラムを作成する．\n\n(手順1) 二分探索木を構成するためのノードを構造体として定義する．\n\n[img[exp01_pr1.bmp]]\n\n[[ヒント|exp01_pr1_hint.bmp]]\n\n(手順2) データファイルを開いて一行ずつデータを読み込む部分を作成する．\n\n[[ヒント|exp01_pr2_hint.bmp]] (前回(第2回)のプログラムも参照)\n\n(手順3) 読み込んだデータをもとに新しいノードを作成する関数@@color(blue):createNode@@を作成する．\n\n[[ヒント|exp01_pr3_hint.bmp]]\n\n(手順4) 関数@@color(blue):createNode@@をmain関数で呼び出す\n\n[[ヒント|exp01_pr4_hint.bmp]]\n\n\n''[実験2]''\n\n(手順1) ノードを二分探索木に追加していく関数@@color(blue):addNode@@関数を作成する．\n\n[[ヒント|exp02_pr1_hint.bmp]]\n\n(手順2) 関数@@color(blue):addNode@@をmain関数で呼び出す．\n\n[[ヒント|exp02_pr2_hint.bmp]]\n\n''[実験3]'' \n\n(手順1) 作成した二分探索木を出力する関数@@color(blue):printNode( )@@を作成する．\n\n[[ヒント|exp03_hint.bmp]]\n\n(手順2) 関数@@color(blue):printNode@@をmain関数で呼び出す．\n\n[[実行例|exp03_result.bmp]]\n

! 概要\n\n本実験は，以下の手順で行う．\n\n[[資料|exp2-06_intro02.pdf]]\n\n# 関数の再帰呼び出しについて学ぶ．\n# 木構造について学ぶ． \n# 各自，「[[実験]]」に記されているプログラムを作成する．\n# 各自，「[[課題]]」に記されているプログラムを作成する．\n# レポートを作成し，提出する．\n\n! 注意事項\n\n# 課題終了後にレポートを作成し，本実験専用のレポート提出用 Webページから期日までにレポートを提出すること．その際，レポートのファイルと，プログラムのファイルの双方を提出すること．\n# 他の人と相談しながら実装を行ってもよい．ただし，他の人にソースコードを渡してはならない．万が一，ソースコードを（@@color(red):部分的であっても@@）コピーしたことが判明した場合は，コピーした者だけでなく，@@color(red):オリジナルのソースコード作成者に対しても@@本実験の単位を出すことができない．\n\n----

\n! 本実験の目的\n\n|基礎的なデータ構造の一つである木構造を理解するとともに，関数の再帰呼び出しを用いて木構造を利用するアルゴリズムを実装する．|\n\nなお，本実験はWindows XP，Windows Vista，LinuxのいずれのOperating System (OS)でも実施可能であるが，本手引きはWindows XPを利用する場合を想定して書かれている． Windows XP以外のOSを利用する場合は，レポートにその旨を明記すること．\n\nまた，知らない単語は実験中に下記の用語サイトやWeb検索エンジンを活用して調べること． Web検索エンジンを用いて語句を調べる際は，ダブルクォーテーション(")を用いて「"TCP/IPとは"」のように，語順を含めた完全に一致するフレーズを検索するとよい．\n\n> e-Words　\n> http://e-words.jp/\n> \n> アスキーデジタル用語辞典　\n> http://yougo.ascii24.com/\n>\n> Wikipedia　\n> http://ja.wikipedia.org/wiki/\n\nC言語について調べる場合は，以下のようなサイトが参考になる．\n\n> 初心者のためのポイント学習C言語\n> http://www9.plala.or.jp/sgwr-t/index.html\n>\n> C言語ポインタと構造体を理解する\n> http://chaichan.web.infoseek.co.jp/src/c.htm\n>\n> C言語入門\n> http://www.stackasterisk.jp/tech/program/c01_01.jsp\n\n本実験の手引きである本Webページに記載されているソースコードは，コピー＆ペーストが行えないよう画像として掲載されている．プログラミングを習得する過程において，サンプルプログラムを書き写す行為はいわば「写経」ともいえる重要な学習過程であり，疎かにしてはならない．\n\n\n----\n\n

\n! 課題\n\n実験を終えた後，以下の課題に取り組むこと．また，考察で指定された課題について考え，レポートを作成すること．\n\n\n''[課題1]'' \n\n木の深さを計算する関数@@color(blue):int countDepth(node *curNode)@@を作成し，実験で作成した二分探索木の深さを求めよ．\n\n[[ヒント|task01_pr1_hint.bmp]]\n\n[[ヒント|task01_pr2_hint.bmp]]\n\n''[課題2]''\n\n指定したポイントを持つ会員を検索する関数\n@@color(blue):node *searchMemberByPoint(node *curNode, int givenPoint)@@\nを作成し，@@color(blue):main@@関数から呼び出して，691点のポイントを持つ会員の名前を出力せよ．なお，全てのノードを探索せず，最低限の個数のノードのみを探索するようにプログラムを作成すること． \n\n[[ヒント|task02_pr1_hint.bmp]]\n\n[[ヒント|task02_pr2_hint.bmp]]\n\n''[考察]''\n\nリストや配列と比較した場合の，二分探索木の特徴や利点について述べよ． \n\n> 本やWebページなどを引用する場合は，@@color(red):引用部と自分自身が書いた部分が明確に区別@@できるようにすること．また，引用のみを書くのではなく，@@color(red):必ず自分自身の考えも書く@@こと． @@color(red):出典@@を書き忘れないよう注意すること．\n\n\n! レポートの作成\n\n# 「実験の目的」，「方法」，「実験結果」，「結論」など，レポートとして一般的に必要な項目について記述すること． \n# 「結果」の項目で，「実験」と「課題」で作成した関数，プログラムを掲載すること．理解するために十分な量のコメントをソースに書いておくこと．''@@color(red):プログラムの実行結果も掲載すること。@@''\n# 「結論」として，この実験で何を学んだかを述べること．\n# 下記のレポートファイルをダウンロードし、ファイル名のnameを名前（例：木原健）、25xxxxxxxxを学籍番号に変更すること．\n# レポートファイルとソースコード（*.cファイル)の双方をMoodleから提出すること．\n\n[[情報生体システム工学実験II テーマ3レポートファイル|ExpII-03_name_25xxxxxxxx.doc]] (Microsoft Word)\n\n! レポートの提出\n\nレポート（上記のレポートファイル''@@color(red):(*.doc，または*.docx)@@''。pdfファイルは不可）と、ソースコード（全ての実験と課題を一度に実行可能な''@@color(red):cファイル@@''）を提出すること． \n\n提出締め切りと提出先は担当教員の指示に従うこと．\n----\n\n\n