ソフトウエア演習B（2000年度）

　２年生のための指導の要点

●学習者（1年生）の前提知識

　ソフトウエア演習Ａを学んできた。

1. WSの基本的な操作は習得している（ファイルの操作等）。
2. プログラミングについては、シェルプログラミングをやっている（if文、case文、for文、while文、until文など；演習Ａ第13回）。
3. 手書きでフローチャートを書いた経験もある（演習Ａ第13回）。
4. muleやviを使うことができる（演習Ａ第４回）。
5. 図を埋め込んだLatex 文書も作ることができる（演習Ａ第６〜１０回）。
6. 電子メール、Web、ftp、telnet等のインターネットサービスも利用できる。

●演習Ｂ指導上の注意点（全体を通して）

1. レポート作成には、必ずmuleもしくはvi を使わせること（テキストエディタは使わない）。
2. ファイルマネージャは使わせないこと（必ずコマンドラインから操作させること）。 　

●学習目標(第１回）

1. 端子記号・データ記号・処理記号・判断記号・ 準備記号を用いたフローチャートが書けるようになる。
2. Ｃ言語でプログラムを組み、コンパイルをし、実行をするという一連の流れができるようになる。

●指導の要点(第１回）

　[フローチャートに関して]

• 各演習には、フローチャートを書くという行為だけでなく、これからプログラミングをする上での重要な概念がたくさん盛り込まれているので、少し解説を加えてください。
  演習1-1：データ交換（２つの変数のデータを交換するには、もうひとつ変数を用いる）
  演習1-2：条件分岐（選択構造）
  演習1-3：反復構造、演習変数の初期化（変数はデフォルトが０ではないということ）
  

　[Ｃ言語について]

• インタプリタ言語とコンパイル言語の違い（シェルプログラムはインタプリタ）を説明し、ひとりでプログラム作成、コンパイル、実行ができるように指導してあげてください。
• コンパイル後にできあがる実行ファイルのデフォルト名がa.outであることを確認してください（変更するには-oオプション）。
• カレントディレクトリにパスが通っていない時は、「./」をつけるか、もしくはフルパスで書かないとファイルを実行できない（実行属性も必要ですが）ことを確認してください。

●レポート評価上の注意

• フローチャートは手書きではなく、WS上でドローツール（Tgif）を用いて書き（EPS形式の画像）、Latexで読み込む形となっているか。
• 表紙をきちんとつけているかを確認すること。
• 合格レポートへのサインは、名前を日付を入れること。

ソフトウエア演習Bのページへ

●演習Ｂ指導上の注意点（全体を通して）

1. レポート作成には、必ずmuleもしくはviで行い（テキストエディタは使わない）、そしてLatex を使わせること。
2. ファイルマネージャは使わせないこと（必ずコマンドラインから操作させること）。 　

●指導の要点

　前回の演習で学んだ知識を使いながら（復習をしながら）、やっていくとよいでしょう。
　特にフロチャートでやった部分は、選択構造（if等）、制御構造（while等） をはじめとして、さらに宣言と式や演算子等の話にもつなげることができます（X,Yとかの変数を利用して代入や加算などを考えたりしたので）。
　printf関数の話なども、前回のHello Worldで出てきた延長線上の話としてできると思います。
　鈴木研には本棚（学生研究室の棚の一番右）に、参考図書が置いてあることも確認しておいてください。

　まだまだ1年生はプログラム（C言語）には慣れていないので、とういよりも初めてまともにプログラムを組むことになりますので、根気よく指導してあげてください。

[重要と思われる点をいくつか]

• C言語のプログラムは「；」で区切る（最初はよく忘れる）。括弧()｛｝は必ず対応をとる。開いたままはだめ。
• C言語で変数を使う際には、あらかじめ宣言をしなければならない。
• 変数や定数を演算子を用いて複雑な計算（評価）を行う、言い換えれば複雑な式を作ることができるが、そのときは演算子の優先順位に気をつける（疑わしいときは括弧で対処）。
• 関数という言葉について。前回いきなりmain関数という言葉が使われ、今回はprintf関数やscanf関数という言葉が登場します。本来はC言語の基本である関数という言葉の意味するところも知って欲しいところですが、おそらく後々の演習で解説でてくると思いますし、今話してもイメージがわかないと思いますので、ある一定の入力に対して結果を返すものという意味でとらえていればよいと思います。（入力部分の書式が定められているから、それに従って書くと、結果が返ってくるみたいな）。
• 演算子の中には代入や計算を行ったりするものと、２つの関係を示すといった条件式で使うものがある（例えば、=と==の違い）
• 制御構造は、条件式がどうなったらループを抜けるのかを理解しているかどうか。ループの中にループを入れる2重ループも可能であること。

●レポート評価上の注意

• プログラムを作成する必須課題（２，３，４，５，６，７）については、すべてプログラム、実行結果、流れ図の3点セットが揃っていることを確認してください。先週やったLatex＋EPS画像によるレポートしか受け取らないでください。
• 必須課題１については、参考文献が提示されているかどうかを確認してください（本なら、著者名、発行年月日、書名、出版社名が提示されているか、ホームページなら、作者名、作成日（記載があれば）、タイトル、URL、そのページを参照した日付が提示されているか）。

ソフトウエア演習Bのページへ

今回は、テキストの内容が盛りだくさんです（つめこみすぎって話しも...）。教える内容がいっぱいありますので、うまく時間を使って（ある程度区切って、わかったかを確認しながら）教えてあげてください。演習内容は、大きくわけて、データ型と関数とスコープの３つがあります。

●学習目標

1. 自分の作成するプログラムにとって適切な、データ型の宣言と入出力の変換仕様の指定を行うことができる。
2. 引数を受け取り、戻り値を返す関数を自分で定義できるようになる。
3. 関数を利用したプログラム中で、ローカル変数とグローバル変数のスコープを説明することができる。

●指導の要点（重要と思われる点を挙げておきます）

• bitとbyteを理解しているかの確認（bitは０と１をあらわす；２進数、１byteは8bit）
• データ型は最低でも、int,float,double,charは理解してもらう。
• データ型や変数の宣言については、メモリについても触れる。（メモリの無駄の話とか、メモリ上の領域確保の話とか）
• 変数宣言の方法（初期値を代入しておく場合と、宣言のみの場合がある）
• 入出力の変換仕様の指定を誤ると、結果がおかしくなることに注意（よくあるミス）。
• 関数による部品化ができる（同じような処理は関数にしたほうが良い場合が多い）
• 関数には、基本的に引数と戻り値がある（データの受け渡し：実引数と仮引数、戻り値の処理）。
• プログラムはすべて関数で成り立っていること（mainも関数であること：省略時はint）
• 再帰は概念的にわかりにくい人が出てくるかもしれないので、理解しているかを確かめる
• コンパイラはプログラムを上から順に解釈していくので、関数原型宣言が必要な場合がある
• ローカル変数とグローバル変数、ならびにスコープは、特に関数を利用したプログラムでは重要である。
• スコープの部分のテキストの例題ではわざと同じ名前の変数を利用している部分があるが、本来はそんなことをせず、わかりやすい変数名にすること（あまりa,b,cなども使わない）。ついでに変数名の注意点として、予約語とか用いることのできる文字の話をしてもよいでしょう。

●レポート評価上の注意

• プログラム中で利用しているデータ型が適切なものかどうか。
• 必須課題２、３、４では、自分で関数を定義し、利用しているかどうか。

ソフトウエア演習Bのページへ

　今回も重要な概念を詰め込みすぎ状態です。１年生が理解したかを一歩づつ確かめながら進めていってください。

●学習目標

1. 配列を利用してデータを整理し、forループなどを利用して効率良くデータを参照できるようになる。
2. ポインタを利用したデータの代入と、関数の参照呼出しができるようになる。
3. argvとargcを用いて、コマンドからの引数をプログラム中で利用することができるようになる。
4. キャスト変換を用いて、データの型を変換することができるようになる。

●指導の要点（重要と思われる点や注意しなければならない点を挙げておきます）

• 配列の添え字は、０からはじまり、配列の要素数-1であること。
• 配列は、ループ（特にfor）の中で利用されることが多い（というか便利）。
• 配列は、１次元だけでなく、２次元や３次元などもある。
• 文字配列の最後は、「\0」で終わる。文字列を扱う関数などは、文字列の最初の要素から順に「\0」が見つかるまで検索し、そこまでを文字列と認識する。つまり、文字配列を扱うときは、最後に「\0」を忘れないようにすべし。
• ポインタ変数で、例えばint *ptrと宣言したときの、ptr、&ptr,*ptrがそれぞれ意味すること。＆はその変数が格納されているアドレスを参照し、*はポインタ変数に格納されているアドレス（つまりポインタ）が示すデータを参照し（ポインタ変数は、データ自体ではなく、データが格納されているアドレスを格納しているものなので）、なにもつけなければ、その変数自体のデータを参照する。例えば、図4.2の場合は、&ptrが0xeffff8f4、*ptrが0xA、ptrが0xEFFFF8Fとなる。p9の上のプログラムとその結果も参考になる。
• ポインタを利用した、関数の参照による呼び出しは、よく利用します（文字列を操作する場合などで）。scanfも実はこの手の関数である。
• 配列をポインタを利用して参照する場合、例えばn[ ]の配列を*(n+1)などと参照する場合の、+1は、実際に1が足されるのではなく、配列nの各要素を格納するのに必要なバイト数分足される。
• argv[0]は、コマンドパスが格納される。引数は、argv[1]から。
• 表4.3の通常算術データ型変換における優先順位と、一見同じに見える1+2+3と1.0+2+3は、実は処理が異なること。
• キャスト変換が複数あった場合は、右から左の順に処理される。
• 文字列をint型に変換したいときは、atoiを利用する。

●レポート評価上の注意

• 事前に初期値を０にしておかなければならいものがそうなっているか（ゼロクリア）。これができていないと、答えが変になる。
• 適切なデータ型が利用されているか（前回の復習の意味も含めつつ）。
• 必須課題３で作成するstr_swap関数の中で、str_copy関数を参照しているか。
• 必須課題４では、キャスト変換を用いることで、プログラムをシンプルにすることができる。
• 必須課題４の棒グラフとは、「****」などのキャラクタで表示できればよい。

ソフトウエア演習Bのページへ

　今回は構造体のみがテーマなので、学ぶべきことはわかりやすいのですが、これまで学習したこと（例えば第４回の配列とポインタ、第３回のメモリ、関数や再帰..などなど）を理解していないと、ちんぷんかんぷんになってしまいます。もし、１年生がよく理解していない場合は、どこでつまずいているのかを明らかにし、そこに戻って指導してあげるようにしてください。なお、今回のテキストの途中に共用体なるものがありますが、課題にも出ていないし、何に利用できるのかテキストを読んでもさっぱりわかりませんので、フォローするか、もしくは後で読んでね程度で詳しくは触れなくてもけっこうです（この下に少し解説しておきましたので、これを読ませても良い）。

●学習目標

1. 構造体の宣言（構造体変数の宣言も含む）ができるようになる。
2. 構造体メンバへの代入と参照ができるようになる。
3. 構造体配列を宣言と初期化をし、メンバの参照ができるようになる。
4. 構造体へのポインタを利用した、メンバへの代入・参照ができるようになる。
5. 構造体型の関数を定義し、構造体型の変数を戻り値とすることができるようになる。
6. ビットフィールドを用いた構造体メンバを宣言し、代入・参照ができるようになる。

●指導の要点

• 構造体は、複数の異なる型の変数をまとめて扱うことができるので便利です。例えば、データベース（コンピュータ入門等で既習）など、共通のデータ形式をもつもの（図書データベースなら、著者、書名、出版社、....など、すべての本で共通のデータを有する）を、プログラム中で処理する際に役に立ちます。もちろんそれだけでなく、テキスト後半の例にもあるように、何かの構造を記述するときや、関数へデータを受け渡すとき、その他いろいろな場面で便利に利用できます。見た目もプログラムがわかりやすくなることが多いです。
• 構造体の宣言の終わりには、;セミコロンをつける。普通はあまり{ }の後に;はつけないので、忘れやすい。
• 構造体メンバの参照は、構造体変数名とメンバ名を「.」で区切る。ポインタの場合は「->」で区切る。
• 構造体は、配列も利用することができる（けっこうわかりやすくて便利）。
• 構造体ポインタ部分の解説（p.4）の*you.heightと*(you.height)、(*you.height）の違いは、ポインタの概念をしっかり理解していないとわからないので、前回の復習の意味でも、わかるかを確認すること。
• 構造体しかビットフィールドは利用できない。
• ビットフィールドでメモリを無駄にとかいう話があるが、メモリ消費量をおさえても、この程度のプログラムではまったく表に出てこない（そもそも最近はマシンパワーがあがっているので、あまり考慮しなくてもよくなった）が、心がけていくことは大切だということ。ちょっとイメージしにくいかもしれないが、大規模なプログラムになると、ひとつひとつの無駄が大きなものとなるので、こういう小さなところで無駄をしないようにしていかないといけない。構造体については、大量のデータを処理するときがあるので、メモリを効率的に利用していかないと、ひとつひとつは小さくとも、総合すると大きな負担となる。
• p11からの構造体の応用では、構造体の利用方法を理解することもあるが、どうやってプログラムを考えていくのかについても参考になる。現実世界の問題を解決するのに、どのようにデータとして表現し（データ構造）、どういう関数を用いて（関数の入出力と機能を考える）プログラムをつくっていのか（アルゴリズム）を考えるといったことは、プログラムを作る上で最初に考えることであるし、非常に重要。プログラムを作る上での仕様書に必要な部分とも言える。

●レポート評価（作成）上の注意

• 必須課題１：ユーザIDというのは、WSにログインするときに使うg031y***のこと。構造体メンバーの型は、性別やパソコンの所持などは、intで表現してもらうこと。
• 必須課題２：講座の学生の情報を全員分打つのは大変なので、同じグループの１年生だけでよい。初期値の代入の方法が指定されている（p4上のプログラム）ので、その方法で行うこと。
• 必須課題３：複素数の加算と乗算の２つの関数を必ず定義して,それを利用したプログラムにすること。
• 必須課題４：ロールプレイングゲームを知らないとイメージしにくい問題ですが（「毒性のある敵」って....）、ようはp5のプログラムで年齢と身長を増加させるプログラムのように、関数を定義して、構造体の値を変化させるものを作ってということ。ちなみに、健康状態（睡眠、混乱、麻痺、毒）については、ビットフィールドを使用するようにと指定されている（睡眠状態かそうでないかの1と0で表現可能）。
• 必須課題５：ほとんどプログラムはテキストに載っている。やることは、main関数を作るくらい。
• 必須課題６：プログラムをすべて出す必要はないので、変更箇所のプログラムの提示と解説、実行結果のみをレポートすること。

●番外編　「共用体」って何に使えるの？

　共用体は、構造体とほぼ構造の面は一緒だが（宣言もそっくり）、同じアドレスからはじまるメモリ領域に複数の型の変数を重ねて割り当て、１つの名前で管理するもの（p.9）である。つまり、共用体のメンバはすべて重なって存在していることになる。ということは、ひとつのメンバに何かの値を代入し、もうひとつのメンバーに何か値を代入したら、先に代入していたメンバの値は壊れてしまう。つまり、格納できるのは１回にどれかのメンバひとつのみである。 あるデータが、実体としては同じなのに、あたかも違った構造を持つデータとしてアクセスできるのが「共用体」の考え方です。こんなたとえがありました→「お弁当箱の「仕切り方」が、中身に応じて変わるのと同じこと」。
　さて、これが実際にどのような場所で利用されるのか？共用体は、構造体のメンバで使われることが多く、知っているとプログラムがシンプルになるときもある。たとえば、企業で個人データを扱う構造体があり、氏名・年齢・給与がメンバだとする。企業には正社員もいればバイトもいるとすれば、給与が月給（特別手当、交通費を含む）であったり、日給（交通費を含む）であったり、時給であったりする。しかし、これらをひとつの個人データの構造体で扱いたい。では、どうするか。構造体のメンバの給与部分を、共用体（＋構造体）で表現すればよい。.（この例は、あくまでも使い方の例なので、月給に特別手当？など、その意味は深くは考えないように）。ちょっと無理があった例ではあるが、本当は、この月給とか日給の構造体のそれぞれの部分に、まったく違ったデータ型、doubleやfloa,charを入れた例を考えたかったけど（本当はこれが大きな利点）、パッと思いつかなかった。 まあ、ご愛嬌。

struct { int payment,bonus,trans } paymonth;
struct { int payment,trans } payday;
struct { int payment } paytime;

struct personaldata {
　char *name;
　int age;
　int paytype; /* 0:paymonth , 1:payday , 2: paytime */
　union {
　　paymonth m;
　　payday d;
　　paytime t;
　　} pay;
　};

　これで、paytypeを見て、pay.m（月給）、pay.d（日給）、pay.t（時給）を使い分ければよい。

つまり、構造体というのは共通の形式のデータを利用するわけなんだけど、同じメンバでも、どうしても違う形式のデータも使いたいということがある。 そんなときに利用するとプログラムが簡潔になって良い場合がある。まあ、他にも利用法はあるだろうが、これが代表的な使いかただと思う。 共用体を単独で用いることはあまりない。

ソフトウエア演習Bのページへ

　今回は、プログラムを効率的に作成する方法などを学びます。大規模なプログラムを作成する場合には、特に有効なものですが、小さなプログラムを作っている限りは、たいして必要性を感じないものも多く、イメージしにくいかもしれませんので、そのあたりを補足してあげてください。分割コンパイルなどは、自分で開発すること以外にも、WSにソフトウエアをインストールする時にも必要な知識となりますので、覚えておいて損はありません。また、プログラム開発につきものの、デバッグは重要ですので、これまでプログラムにミスがあったときにどう対処していたかを振り返ってもらいながら、指導してあげてください。

●学習目標

• コンパイルの流れ（図6.1）の各処理の段階で、何が行われているのかを説明できるようになる。
• プログラムを、ヘッダファイルと関数定義ファイルとメインプログラムの３種類に分割して作成できるようになる。
• makeを用いた分割コンパイルができるようになる。
• プログラムの実行の途中過程を出力して分析していく「トレース」を行うデバッグができるようになる。

●指導の要点

• これまでブラックボックスだったccコマンドは、実はいろいろな処理を行っていること。よく見かけたオブジェクトファイル（***.o）何なのか、プログラム中の#includeによってヘッダファイルをとりこむ意味などがここでわかる。
• コンパイルの仕組み（流れ）はひととり理解しておくとよいだろう。C言語はコンパイル型言語である。あらかじめコンパイル作業を行っておくから（機械語で書かれた実行ファイルを生成する）、インタプリタ型言語よりも処理がはやい。
• ヘッダファイルは、一般に、定数や変数の宣言（マクロ定義など）、関数のプロトタイプ宣言が記述される。
• ヘッダファイルの作成は、プログラム作成（複数になる）を効率的に行う上では有効な手段のひとつである。
• ライブラリも、プログラミングの負担を軽減してくれる。C言語に基本的に用いられる関数（printfなど）は、コンパイル時に自動的にリンクされるので、明示的に指定する必要が無い。
• 分割コンパイルは、「再利用」という観点からも重要。うまく関数を定義したファイルなどを作成しておけば、後で再利用も可能となることもある（入力と出力をあわせればよいだけなので）。
• makeコマンドは、自分で開発するときは、小さいプログラムを作っている限りにおいてあまり利用しないが、他人が作ったソフトをインストールするときなどは必ず利用するコマンドのひとつである。
• syntax errorは、文法上のエラーなので、「；」の入れ忘れ、「”」や括弧の閉じ忘れ、コマンドのスペルミスなどの単純ミスが多い。
• デバッガを利用する際に、肝心のcoreファイルが出力されない設定になっているときがある。対処法はp.16。
• デバッガも使いこなせるようになれば便利であるが（特に大規模）、小さなプログラムにおいては、プログラム中にprintfを挿入して、実行場所や変数の値を確認する手法も手軽でよく活用する。

●レポート評価（作成）上の注意

• 必須課題１：プリプロセッサの出力結果から考察していることが示されていること
• 必須課題２：テキスト中に答えはありません。UNIXでわからないときに調べるコマンドがあったはずです。それを利用すればわかります。
• 必須課題３：第５回に作成したプログラムを利用します。ヘッダファイル、各関数を定義したファイル、メインプログラムの３種類のファイルがあること。
• 必須課題４：Makefile中に、allとcleanが含めてあること。
• 必須課題５：特になし。きちんとプログラムができており、実行結果も示されているか。
• 必須課題６：プログラムを見れば答えがわかる学生も居るでしょうが、デバッガを使った過程が必ず示されていること。

ソフトウエア演習Bのページへ

　今回は、さまざまなライブラリの関数を扱ってみるというものです。ファイルの操作をはじめとして、今後プログラミングの上でよく扱うものが多数含まれています。

●学習目標

• ファイルの読み込み・書き込みができるようになる（fopen,fclose,getc,putc,fgets,fputs,fprintf,fscanf,sprintf,sscanf）
• string.hの文字列操作関数が利用できるようになる（表7.8）
• 動的なメモリ確保ができるようになる（malloc,free）
• 乱数を扱うことができるようになる（rand,srand）
• math.hの数学ライブラリの関数が利用できるようになる（表7.13）

●指導の要点

• 一般によく利用されるライブラリは、標準ライブラリ（libc.a）に入っており、これはコンパイル時に暗黙でリンクされるので、コンパイルの時に明示する必要はない。
• ファイルの読み込み・書き込み（入出力）は、よく使うので、かならずマスターしてもらうこと。１文字、文字列、書式とファイルを扱うためのさまざまな関数が用意されているので、うまく使い分ける。
• fgetsやfputsは格納する文字数を指定するが、最後に文字列の終端を示す「\0」が付加されて格納されるので、格納する文字数-1が入力できる文字数の最大となる。
• 動的メモリ確保は、あらかじめ要素数のわからない配列の取り扱いに有効。p.12の結果や、p.13の図7.1がわかるようになってほしい。
• 確保していないアドレス領域に値を入れてしまうと（ポインタ型変数を宣言し、そのまま配列として扱ったりすると）、その領域はすでに他で使われている可能性があるので、エラーの原因となったりする。
• randで発生する乱数は毎回違うと考えがちだが、初期状態が一緒だと同じ乱数が発生してしまう。初期状態を変更するのが、srand関数。ただし、srand関数への引数が同じだと、結局同じ乱数が発生してしまう。
• 数学ライブラリを扱うときには、コンパイルの時に注意。

●レポート評価（作成）上の注意

• 必須課題１：intro.docは自分で作成する。読み込む単語の長さが一定ではないので、動的確保を用いるとよい。重複する単語がリストされないようにすること。実行結果では、単語の分割がただしくできているかを良く見ること（「,」「.」の読み飛ばしなど）。
• 必須課題２：データファイルlib_ml.datを自分で作成。データファイルには鈴木研の1年生数名、２年生最低１名、３年生最低１名を登録すること。レポートには、必ずデータファイルの内容も示してあること。
• 必須課題３：fortune関数で、各項目（大吉...）の出現確率の分布を出すところが正しく記述し、戻り値を指定しているか。戻り値のカウントには、配列を使うと便利。
• 必須課題４：ベクトルは構造体を利用するとプログラムがきれい（x,y成分を扱うので）。数学ライブラリの練習なので、２乗などは、累乗を求める関数powを活用するようにすること。

ソフトウエア演習Bのページへ

　今回から、アルゴリズムとデータ構造に入るようです。アルゴリズムやデータ構造を効率よく実現することは、プログラミングで最も重要な課題のひとつと言えるでしょう。今回はそのなかでも、データの並べ替え（ソーティング）についてのみ学習することになります。テキストには、プログラムの例がほとんど載っておらず、アルゴリズムの考え方が記されているだけです。１年生がどうプログラムを作っていいのか途方にくれているときには、答えを直接教えずにヒントを出すような感じでお願いします。

●学習目標

• 単純選択法を用いたソーティングができるようになる。
• バブルソート法を用いたソーティングできるようになる。
• クイックソート法を用いたソーティングができるようになる。
• キー比較回数とデータ置換回数でソーティングアルゴリズムの計算量を説明することができる。

●指導の要点

• 各ソート法のアルゴリズムについて、キーの設定（比較）方法とデータの置換を中心に、どのような流れで行われているのかを必ず理解してもらうこと（理解したかを確かめるために、実際にデータがどのようにソートされていくのかの過程を説明してもらうとよい）。
• 各ソート法について、長所短所がある。クイックソートはデータ数が多くなると有利。
• クックソートは再帰を利用するとよいことを確認。

●レポート評価（作成）上の注意

• 全必須課題：結果が並び変わっているので合格とせずに、実際にプログラムを見て、アルゴリズムがあっているか（キーの設定など）を必ず確かめること。
• 必須課題１，２，３：ソーティング前と後の並び方がレポートに提示されていること。また、ソーティングの過程の出力もレポートに提示されていること。
• 必須課題２，３：変更箇所がきちんと示されていること。また、変更箇所がない場合には、「変更箇所なし」と記すこと。
• 必須課題３：クイックソートについては、再帰を利用していること。
• 必須課題４：ファイルの入出力が行われていること。timexコマンドを利用して各種ソーティングプログラムの実行時間を出し、その結果からどういうことが言えるのか（結論）がレポートされていること。（クイックソートが一番速い結果となる）。

ソフトウエア演習Bのページへ

　今回は、アルゴリズムとデータ構造の2回目です。かなり重要な部分です。内容的にも以前と比べてだいぶ難しくなってきました。構造体とポインタを活用することになります（Ｃ言語ではこれができないと）。テキスト中に出てくるリストや木構造を理解してもらうのはもちろんのこと、特に随時変数（構造体）を動的確保しながら、ポインタを利用してつなげていく（つまり各データがポインタによりつながれる、参照される）という概念を理解させてあげてください。

※完全に出来ない場合でも、必ずできたところまでを期限どおりに提出するようにと今一度確認してください！！！　（できないから提出しないとか、表紙だけを提出ということのないように）。

●学習目標

• スタック操作ができるようになる。
• 線形連結リストを利用してデータの並びを実現し、データの追加と削除が行えるようになる。
• 二分探索木において、キーを利用した探索ができるようになる。

●指導の要点

• LIFO（スタック）とFIFO（キュー）の違いがわかる。
• 配列と線形連結リストの違い（追加と削除等が容易→リスト）。配列で追加や削除をするとどうなるかも考えてみよう。
• リストや木構造は、データの値と次のノードへのポインタなど、セットで変数を扱うことになるので、構造体で実現するとシンプル。もちろん、２次元配列などを利用してリスト等を実現することもできる。
• ２分木と完全２分木の違い。（同じ深さで左から右へと要素が詰められているのが完全２分木）。
• 2分探索木は、任意のノードxの左部分木のノードの値はxより小さく、逆に右部分の全てのノードの値はxより大きい。
• ヒープソートは完全２分木において実現する。

●レポート評価（作成）上の注意

• 必須課題１：スタック操作のための２つの関数（push,pop）が正しく使われているか？演算子と数字の区別がきちんとできているか？（例えば負の数字と引き算の演算子の区別。）
• 必須課題２：テキストにほとんどプログラムの手続きが載っている。挿入と削除を行う関数の中で、ポインタの値を書き換えるために、ポインタのポインタを適切に利用できているか？
• 必須課題３：search_node()関数とadd_node()関数を適切に定義しているか？ノードの値を構造体へのポインタとして定義すること（ポインタ操作方法はテキスト本文中にあり）。

ソフトウエア演習Bのページへ

　今回は、アルゴリズムとデータ構造の3回目で、グラフについてです。テキストには、これまで同様にプログラムの例はほとんど載っておらず、考え方のみが示されています。問題解決を行う際には、現実世界をモデル化し、コンピュータによって処理させるということがあります。グラフは、ノードと辺（点と線）や、重み（ノード間のつながりの情報）、方向（辺の方向）等によってモデル化を行うというものです。本課題を通して、そのあたりのイメージもあわせてつかんでもらえたらと思います。

●学習目標

• グラフとはどんなものかを、「ノード」と「辺」、「重み」、「有向」「無向」という言葉を用いながら説明することができる。
• 深さ優先探索を用いたプログラムが書けるようになる。
• 幅優先探索を用いたプログラムが書けるようになる。
• ダイクストラ法を用いて、最短経路長が求められるようになる。
• ダイクストラ法を利用しながら、最短経路が求められるようになる。

●指導の要点

• ここで言う「グラフ」は、グラフと一般に聞く棒グラフや円グラフ等とは異なるということ。
• グラフ探索の目的は、あるノードから到達できるすべてのノードを発見すること。
• テキスト中の深さ優先探索・幅優先探索ともに、探索済みのノードかどうかのチェックのアルゴリズムは、ノード番号の小さい順番にチェックしている。
• 深さ優先探索は、再帰を用いてプログラムを書くことになる（始点に戻ると終了）。
• 幅優先探索の図10.6は一瞬とまどう人がいるかもしれませんが、現在探索しているノード（☆）から、隣接しているノード「１つ分」について、探索していくということ。1つ分が終ったら、まだその処理を行っていないノードへと移っていく。
• 幅優先探索は、キュー構造を用いてプログラミングを行う。
• 重みつきグラフでは、最短経路長など、重みの総和などを利用したて問題解決を行うことができる。
• ダイクストラ法は、最短経路長を問題にしたものであり、10.4.1の解説を見るとわかるが、どんなところを通ったか「経路」については考えないので，そのままでは、「最短経路」が求まらないということ。ダイクストラ法を利用しながら最短経路を求める方法は、10.4.2で解説。
• ダイクストラ法の解説p.9の一番下の部分「囲みの外にある〜最短経路長が最も小さいノードである」というのは、未探索が∞になっているから実現していることに注意。
• graph1.dat、graph2.datのデータ入力を間違わないように。

●レポート評価（作成）上の注意

• 必須課題３は、最短経路長だけでなく、最短経路も求められていること。

ソフトウエア演習Bのページへ

　2回をかけて、ひとつのアプリケーションを設計し、開発してもらいます。これまでの演習の内容を振り返りながら、自分の力でプログラムを書くようにと指導してあげてください（今までの演習で習ったことを利用すれば開発できますので、復習的な位置付けでもあります）。行き詰まる可能性も多々ありますので、演習時間外のフォローもよろしくお願いします。

目標

「拡張機能を１つ以上入れた、住所録管理アプリケーションを作成する」
　（住所録管理アプリケーションの要求は、テキストに載っています）

●第１１回評価上の注意

　４つの提出物があること（仕様書、設計書、プログラムリスト、チェックリスト）。それらの内容が適切であること。
　　（設計書の中には、関数仕様書が含まれます）。
　拡張機能は、オリジナリティがあり、なるべく利便性が高いものを期待します。あまりにもたいしたことないものは、考え直させてください。
　プログラムは実際に動作し、レコードの一覧表示、データの保存・読み込み、新規レコードの追加・削除、レコード内の任意の項目に対して修正ができること。
　ソート機能は、昇順と降順が決まっているか、決まってなければ決めさせましょう。

●第１２回評価上の注意

　プログラムがすべて完成し、利用手引書が用意されていること（実際に利用手引き書を見ながら、操作してみてください）。
　　特に、拡張機能の部分がきちんと動いていること。
　グループ内でメンバーを集めてお披露目会（デモンストレーション）をしてもらってもいいです。

ソフトウエア演習Bのページへ

ichikawa@soft.iwate-pu.ac.jp