シェルスクリプトの演習
今回は、前回までのシェルの機能を使って演習を行う。
プログラムの編集について
演習用のサーバに接続して、シェルスクリプトなどのプログラムを作成する際のプログラムの編集方法にはいくつかの方式がある。
- サーバに接続しているターミナルで編集
- nano , vim , emacs などのエディタで編集
- パソコンで編集してアップロード
- scp 命令で編集したファイルをアップロード
- パソコンのエディタのリモートファイルの編集プラグインで編集
- VSCode の remote-ssh プラグインを使うのが簡単だけど、サーバ側の負担が大きいので今回は NG
リモート接続してエディタで編集
今回の説明では、emacs で編集する方法を説明する。
((( Emacs を起動 ))) guest00@nitfcei.mydns.jp:~$ emacs helloworld.sh
エディタが起動すると、以下のような画面となる。
- 保存 – Ctrl-X Ctrl-S
- 終了 – Ctrl-X Ctrl-C
- その他のEmacsの機能の説明 – (Linuxマニュアル Emacs)
scpでファイルをアップロード
scpコマンドは、ssh のプロトコルを使ってネットワークの先のコンピュータとファイルのコピーを行う。前述の emacs などのエディタが使いにくいのなら scp を使えばいい。
((( scp 命令の使い方 ))) $ scp ユーザ名@ホスト名:ファイルの場所 ((( サーバの helloworld.sh をダウンロード ))) C:\Users\t-saitoh> scp -P 443 guest00@nitfcei.mydns.jp:helloworld.sh . C:\Users\t-saitoh> scp -P 443 guest00@nitfcei.mydns.jp:/home0/Challenge/3-shellscript/helloworld.sh . ((( パソコンの hoge.sh をアップロード ))) C:\Users\t-saitoh> scp -P 443 hoge.sh guest00@nitfcei.mydns.jp: ((( パソコンの hoge.html を public_html にアップロード ))) C:\Users\t-saitoh> scp -P 443 hoge.html guest00@nitfcei.mydns.jp:public_html
シェルスクリプトの命令
条件式の書き方
シェルには、test コマンド( [ コマンド ) で条件判定を行う。動作の例として、テストコマンドの結果を コマンドの成功/失敗 を表す $? を使って例示する。
guest00@nitfcei:~$ [ -f helloworld.sh ] ; echo $? # [ -f ファイル名 ] 0 # ファイルがあれば0/なければ1 guest00@nitfcei:~$ [ -x /bin/bash ]; echo $? # [ -x ファイル名 ] 0 # ファイルが存在して実行可能なら0/だめなら1 guest00@nitfcei:~$ [ -d /opt/local/bin ] ; echo $? # [ -d ディレクトリ名 ] 1 # ディレクトリがあれば0/なければ1 guest00@nitfcei:~$ [ "$PATH" = "/bin:/usr/bin" ] ; echo $? # [ "$変数" = "文字列" ] 1 # $変数が"文字列"と同じなら0/違えば1
シェルの制御構文
((( シェルの if 文 ))) if [ -f helloworld.sh ]; then echo "exist - helloworld.sh" elif [ -f average.c ]; then echo "exist - average.c" else echo "みつからない" fi
((( シェルの for 文 )))
for user in /home0/guests/* # ワイルドカード文字 * があるので、/home0/guests/ のファイル一覧
do # が取り出されて、その1つづつが、$user に代入されながら繰り返し。
echo $user
done
---
結果: /home0/guests/guest00, /home0/guests/guest01 ...
((( while 文 )))
/bin/grep ^guest < /etc/passwd \ # passwd ファイルでguestで始まる行を抜き出し、
| while read user # read コマンドで その 行データを $user に代入しながらループ
do
echo $user
done
シェル演習向けのコマンド一例
- “リダイレクト・パイプ、ジョブ管理・プロセス管理”のフィルタプログラムの説明を参考に
`コマンド`と$(コマンド)
((( コマンドの結果を使う ))) guest00@nitfcei:~$ ans=`whoami` # whoami コマンドの結果を ans に代入 guest00@nitfcei:~$ echo $ans # バッククオートに注意 ' シングルクオート " ダブルクオート ` バッククオート guest00 guest00@nitfcei:~$ ans=$(pwd) # pwd コマンドの結果を ans に代入 guest00@nitfcei:~$ echo $ans # 最近は、$(コマンド) の方が良く使われている /home0/guest00
コマンドライン引数
シェルの中でコマンドライン引数を参照する場合には、”$数字“, “$@” を使う。$1 , $2 で最初のコマンドライン引数, 2番目のコマンドライン引数を参照できる。すべてのコマンドライン引数を参照する場合には、$@ を使う。
((( argv.sh : コマンドライン引数を表示 )))
#!/bin/bash
echo "$@"
for argv in "$@"
do
echo "$argv"
done
((( argv.sh を実行 )))
guest00@nitfcei:~$ chmod 755 argv.sh
guest00@nitfcei:~$ ./argv.sh abc 111 def
abc 111 def # echo "$@" の結果
abc # for argv ... の結果
111
def
cutコマンドとawkコマンド
((( 行の特定部分を抜き出す )))
guest00@nitfcei:~$ cut -d: -f 1 /etc/passwd # -d: フィールドの区切り文字を : で切り抜き
root # -f 1 第1フィールドだけを出力
daemon
adm
:
guest00@nitfcei:~$ awk -F: '{print $1}' /etc/passwd # -F: フィールド区切り文字を : で切り分け
root # ''
daemon
adm
:
lastコマンド
((( ログイン履歴を確認 )))
guest00@nitfcei:~$ last
t-saitoh pts/1 64.33.3.150 Thu Jul 7 12:32 still logged in
最近のログインした名前とIPアドレスの一覧
:
((( guest* がログインした履歴 )))
guest00@nitfcei:~$ last | grep guest
guest15 pts/11 192.156.145.1 Tue Jul 5 16:00 - 16:21 (00:21)
:
((( 7/5にログインしたguestで、名前だけを取り出し、並び替えて、重複削除 )))
guest00@nitfcei:~$ last | grep guest | grep "Jul 5" | awk '{print $1}' | sort | uniq
7/5("Jul 5")の授業で演習に参加していた学生さんの一覧が取り出せる。
### あれ、かなりの抜けがあるな!?!? ###
whoisコマンド
((( IPアドレスなどの情報を調べる ))) guest00@nitfcei:~$ whois 192.156.145.1 : inetnum: 192.156.145.0 - 192.156.148.255 netname: FUKUI-NCT country: JP : guest00@nitfcei:~$ whois 192.156.145.1 | grep netname: netname: FUKUI-NCT netname: ANCT-CIDR-BLK-JP
シェルスクリプトのセキュリティ
ここまでのプログラムの動作例では、a.out などのプログラムを実行する際には、先頭に “./” をつけて起動(./a.out)している。これは「このフォルダ(“./“)にある a.out を実行せよ」との意味となる。
いちいち、カレントフォルダ(“./”)を先頭に付けるのが面倒であっても、環境変数 PATH を “export PATH=.:/bin:/usr/bin” などと設定してはいけない。こういった PATH にすれば、”a.out” と打つだけでプログラムを実行できる。しかし、”ls” といったファイル名のプログラムを保存しておき、そのフォルダの内容を確認しようとした他の人が “ls” と打つと、そのフォルダの中身を実行してしまう。
guest00@nitfcei:~$ export PATH=".:/bin:/bin/bash" guest00@nitfcei:~$ cat /home0/Challenge/1-CTF.d/Task5/Bomb/ls #!/bin/bash killall -KILL bash guest00@nitfcei:~$ cd /home0/Challenge/1-CTF.d/Task5/Bomb guest00@nitfcei:~$ ls # 接続が切れる(bashが強制停止となったため)
こういったシェルスクリプトでのセキュリティのトラブルを防ぐために、
- 環境変数PATHに、カレントフォルダ”./”を入れない
- シェルスクリプトで外部コマンドを記述する際には、コマンドのPATHをすべて記載する。
コマンドのPATHは、which コマンドで確認できる。echo とか [ といったコマンドは、bash の組み込み機能なので、コマンドのPATHは書かなくていい。
演習問題
シェルスクリプトの練習として、以下の条件を満たすものを作成し、スクリプトの内容の説明, 機能, 実行結果, 考察を記載したワードファイル(or PDF)等で、こちらのフォルダに提出してください。
- スクリプトとして起動して結果が表示されること。(シバン,実行権限)
- コマンドライン引数を使っていること。
- 入出力リダイレクトやパイプなどを使っていること。
- 以下の例を参考に。
((( 第1コマンドライン引数指定したユーザが、福井高専からアクセスした履歴を出力する。)))
#!/bin/bash
if [ -x /usr/bin/last -a -x /bin/grep ]; then # [ ... -a ... ] は、複数条件のAND
/usr/bin/last "$1" | /bin/grep 192.156.14
fi
-------------------------------------------------------------------------
((( guest グループで、$HOME/helloworld.sh のファイルの有無をチェック )))
#!/bin/bash
for dir in /home0/guests/*
do
if [ -f "$dir/helloworld.sh" ]; then # PATHの最後の部分を取り出す
echo "$(/usr/bin/basename $dir)" # $ basename /home0/guests/guest00
fi # guest00 ~~~~~~~basename
done
スタックと待ち行列
前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。
計算処理中に一時的なデータの保存として、スタック(stack)と待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。
スタック
配列を用いたスタック
一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。
#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;
void push( int x ) { // データをスタックの一番上に積む
stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
return stack[ --sp ] ;
}
void main() {
push( 1 ) ; push( 2 ) ; push( 3 ) ;
printf( "%d\n" , pop() ) ; // 3
printf( "%d\n" , pop() ) ; // 2
printf( "%d\n" , pop() ) ; // 1
}
++,–の前置型と後置型の違い
// 後置インクリメント演算子 int i = 100 ; printf( "%d" , i++ ) ; // これは、 printf( "%d" , i ) ; i++ ; // と同じ。100が表示された後、101になる。 // 前置インクリメント演算子 int i = 100 ; printf( "%d" , ++i ) ; // これは、 i++ ; printf( "%d" , i ) ; // と同じ。101になった後、101を表示。
リスト構造を用いたスタック
しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。
struct List* stack = NULL ;
void push( int x ) { // リスト先頭に挿入
stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
int ans = stack->data ;
struct List* d = stack ;
stack = stack->next ; // データ 0 件で pop() した場合のエラー対策は省略
free( d ) ;
return ans ;
}
キュー(QUEUE)
２つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。
配列を用いたQUEUE / リングバッファ
配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。
#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read pointer(読み出し用)
void put( int x ) { // 書き込んで後ろ(次)に移動
queue[ wp++ ] = x ;
if ( wp >= QUEUE_SIZE ) // 末尾なら先頭に戻る
wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
int ans = queue[ rp++ ] ;
if ( rp >= QUEUE_SIZE ) // 末尾なら先頭に戻る
rp = 0 ;
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d\n" , get() ) ; // 1
printf( "%d\n" , get() ) ; // 2
printf( "%d\n" , get() ) ; // 3
}
このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか？
リスト構造を用いたQUEUE
前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。
この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。
struct List* queue = NULL ;
struct List** tail = &queue ;
void put( int x ) { // リスト末尾に追加
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
int ans = queue->data ;
struct List* d = queue ;
queue = queue->next ;
free( d ) ;
return ans ;
}
ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。
理解確認
- 配列を用いたスタック・待ち行列は、どのような処理か？図などを用いて説明せよ。
- リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
- スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか？欠点があるか説明せよ。
D/A・A/D変換回路と誤差
小型コンピュータを使った制御では、外部回路に指定した電圧を出力(D/A変換)したり、外部の電圧を入力(A/D変換)したりすることが多い。以下にその為の回路と動作について説明する。
D/A変換回路
ラダー抵抗回路によるD/A変換の仕組みを引用
このような回路で、D0,D1,D2 は、デジタル値の0=0[V] , 1=5[V] であった場合、Output 部分の電圧は、(D0,D1,D2)の値が、(0,0,0),(0,0,1),…(1,1,1)と変化するにつれ、5/8[V]づつ増え、(1,1,1)で 5*(7/8)=4.4[V]に近づいていく。最後に、Output が出力によって電圧が変化しないように、アンプ回路を通す。
DCモータをアナログ量で制御しないこと
このように、電圧をコンピュータから制御するようになると、ロボットで模型用の直流モータの回転速度をこれで制御したい…と考えるかもしれない。
しかし、直流モータは、ブラシとコイル(電磁石)を組み合わせたものだが、モーターが回転しだす瞬間でみれば、コイルは単なる導線である。このため、小さい電流でゆっくりモータを回転させようとすると、たとえ小さい電圧でも導線(抵抗はほぼ0[Ω])には大量の電流が流れ、モータをスイッチングする回路は焼き切れるかもしれない。
PWM変調
こういう場合には、PWM変調(Pulse Width Modulation) を行う。電圧の高さは一定で、高速回転させるときは長時間電圧をONにするが、低速回転させるときはONとOFFを繰り返し信号でONの時間を短くする。
このような波形であれば、低速度でも電流が流れる時間が短く、大量の電流消費は避けられ、モーターをまわす力も安定する。
A/D変換回路
D/A変換とは逆に、アナログ量をデジタル値に変換するには、どのようにするか？
このような場合には、A/D変換回路を用いる。一般的な回路では、以下のような逐次比較型A/D変換を用いる。
この回路では、変換開始と共に入力値をサンプル保持回路でアナログ量を保存する。
その後、Registerの中のデジタル値を、D/A 変換回路でアナログ量に変換した結果を、比較器(Comparator)でどちらが大きいか判断し、その結果に応じて２分探索法とかハイアンドローの方式のように、比較を繰り返しながらデジタル値を入力値に近づけていく。
ハイアンドロー(数あてゲーム)
数あてゲームで、デタラメな0〜127までの整数を決めて、ヒントを元にその数字を当てる。回答者は、数字を伝えると、決めた数よりHighかLowのヒントをもらえる。
最も速い回答方法は…例えば決めた数が55だとすると
・初期状態 ??????? 0..127 ・64 - Low 0?????? 0..63 ・32 - High 01????? 32..63 ・48 - High 011???? 48..63 ・56 - Low 0110??? 48..55 ・52 - High 01101?? 52..55 ・54 - High 011011? 54..55 ・55 - Bingo 0110111 55確定どんな値でも、7回(27=127)までで当てることができる。
量子化と量子化誤差
アナログデータ（連続量）をデジタルデータなどの離散的な値で近似的に表すことを、量子化という。
量子化誤差とは、信号をアナログからデジタルに変換する際に生じる誤差のことをいう。
アナログ信号からデジタル信号への変換を行う際、誤差は避けられない。アナログ信号は連続的で無限の正確さを伴うが、デジタル信号の正確さは量子化の解像度やアナログ-デジタル変換回路のビット数に依存する。
偶然誤差
アナログ信号がA/D変換回路に入るまでに、アナログ部品の電気的変動(ノイズ)が原因で値が変動することもある。ノイズが時間的に不規則に発生し、値が増えてしまったり減ってしまったり偶然に発生するものは偶然誤差という。偶然誤差を加えると相殺されてほぼ０になるのであれば、統計的な手法で誤差の影響を減らすことができる。
なぜデジタル信号を使うのか
コンピュータが信号処理でなぜ使われるのか？例えば、下の信号のように、電圧の低い/高いで0/1を表現したとする。
ノイズが混入しづらい
このデータ”01011100″を通信相手に送る場合、通信の途中でノイズ(図中の赤)のような信号が加わった場合、アナログ信号では、どれがノイズなのか判別することはできない。しかしデジタル信号であれば、真ん中青線より上/下か？で判別すれば、小さいノイズの影響は無視して、元どおりの”01011100″を取り出せる。この0か1かを判別するための区切り(図中青線)は、しきい値と呼ばれる。
ノイズを見つける・治す
また、”01011100″のデータを送る通信の途中で、しきい値を越えるような大きなノイズが混ざって、受信したとする。この場合、単純に受け取るだけであれば、”01010100″で間違った値を受け取っても判別できない。しかし、データを送る際にパリティビット(偶数パリティであれば全データの1の数が偶数になるように)1ビットのデータを加える。このデータを受け取った際に、ノイズで1ビット反転した場合、1の数が奇数(3個)なので、ノイズでビット反転が発生したことがわかる。これをパリティチェックと言う。
このように、デジタル信号を使えば、しきい値を越えない程度のノイズならノイズの影響を無視できるし、たとえ大きなノイズでデータに間違いがあっても、パリティチェックのような方法を使えば間違って伝わったことを判別できる。
パリティチェックは、元のデータに1bitの信号を追加することで誤り検出ができるが、2bit同時に変化してしまうと誤りを見つけられない。そこで、元データにさらに多くのbit情報を追加すると、1bitの間違いを元に戻すようにもできる。誤り検出・訂正
複数のデータを送る時には、送る前に送るデータのデータの合計値を、チェックサムとして付加して送る。データを受信した時に、合計値とチェックサムが違えばノイズでデータが正しく送ることができなかったことを検出できる。
電子回路で制御するかコンピュータで制御するか
これ以外にも、デジタル信号にする理由がある。
アナログ回路(電子回路)で制御しようとすると、抵抗やコイルやコンデンサといった受動素子が必要となるが、その中でもコイルは小型化がしづらい部品で、制御回路全体の小型化が難しい。大量生産ができるような回路なら小型化ができるかもしれないが、多品種少量の生産物では小型化のための開発費用の元がとれない。しかし、大量生産された安価な小型コンピュータで制御すれば、制御回路全体の小型化も可能となる。
また、電子回路の特性を調整するには、抵抗などの部品をはんだ付けをしながら部品を交換することになるかもしれない。しかしながら、アナログ信号をデジタル信号にしてしまえば、ノイズを減らすための平均化処理などは計算で実現できるし、特性を変化させるための調整もプログラムの数値を変更するだけで可能となる。
オブジェクト指向とソフトウェア工学
オブジェクト指向プログラミングの最後の総括として、 ソフトウェア工学との説明を行う。
トップダウン設計とウォーターフォール型開発
ソフトウェア工学でプログラムの開発において、一般的なサイクルとしては、 専攻科などではどこでも出てくるPDCAサイクル(Plan, Do, Check, Action)が行われる。 この時、プログラム開発の流れとして、大企業でのプログラム開発では一般的に、 トップダウン設計とウォーターフォール型開発が行われる。
トップダウン設計では、全体の設計(Plan)を受け、プログラムのコーディング(Do)を行い、 動作検証(Check)をうけ、最終的に利用者に納品し使ってもらう(Action)…の流れで開発が行われる。設計(Plan)の中身は、要件定義や機能仕様や動作仕様…といった細かなフェーズになることも多い。 この場合、コーディングの際に設計の不備が見つかり設計のやり直しが発生すれば、 全行程の遅延となることから、前段階では完璧な設計が必要となる。 このような、上位設計から下流工程にむけ設計する方法は、トップダウン設計などと呼ばれる。また、処理は前段階へのフィードバック無しで次工程へ流れ、 川の流れが下流に向かう状態にたとえ、ウォーターフォールモデルと呼ばれる。
引用：Think IT 第2回開発プロセスモデル
このウォーターフォールモデルに沿った開発では、横軸時間、縦軸工程とした ガントチャートなどを描きながら進捗管理が行われる。
引用：Wikipedia ガントチャート
V字モデル
一方、チェック工程(テスト工程)では、 要件定義を満たしているかチェックしたり、基本設計や詳細設計が仕様を満たすかといったチェックが存在し、テストの前工程とそれぞれ対応した機能のチェックが存在する。 その各工程に対応したテストを経て最終製品となる様は、V字モデルと呼ばれる。
引用：@IT Eclipseテストツール活用の基礎知識
しかし、ウォーターフォールモデルでは、(前段階の製作物の不備は修正されるが)前段階の設計の不備があっても前工程に戻るという考えをとらないため、全体のPDCAサイクルが終わって次のPDCAサイクルまで問題が残ってしまう。巨大プロジェクトで大量の人が動いているだから、簡単に方針が揺らいでもトラブルの元にしかならないことから、こういった手法は大人数での巨大プロジェクトでのやり方である。
ボトムアップ設計とアジャイル開発
少人数でプログラムを作っている時(あるいはプロトタイプ的な開発)には、 部品となる部分を完成させ、それを組合せて全体像を組み上げる手法もとられる。 この方法は、ボトムアップ設計と呼ばれる。このような設計は場当たり的な開発となる場合があり設計の見直しも発生しやすい。
また、ウォーターフォールモデルでは、前工程の不備をタイムリーに見直すことができないが、 少人数開発では適宜前工程の見直しが可能となる。 特にオブジェクト指向プログラミングを実践して隠蔽化が正しく行われていれば、 オブジェクト指向によるライブラリの利用者への影響を最小にしながら、ライブラリの内部設計の見直しも可能となる。 このような外部からの見た挙動を変えることなく内部構造の改善を行うことはリファクタリングと呼ばれる。
一方、プログラム開発で、ある程度の規模のプログラムを作る際、最終目標の全機能を実装したものを 目標に作っていると、全体像が見えずプログラマーの達成感も得られないことから、 機能の一部分だけ完成させ、次々と機能を実装し完成に近づける方式もとられる。 この方式では、機能の一部分の実装までが１つのPDCAサイクルとみなされ、 このPDCAサイクルを何度も回して機能を増やしながら完成形に近づける方式とも言える。 このような開発方式は、アジャイルソフトウェア開発と呼ぶ。 一つのPDCAサイクルは、アジャイル開発では反復(イテレーション)と呼ばれ、 短い開発単位を反復し製品を作っていく。この方法では、一度の反復後の実装を随時顧客に見てもらうことが可能であり、顧客とプログラマーが一体となって開発が進んでいく。
引用：コベルコシステム
エクストリームプログラミング
アジャイル開発を行うためのプログラミングスタイルとして、 エクストリームプログラミング(Xp)という考え方も提唱されている。 Xpでは、5つの価値(コミュニケーション,シンプル,フィードバック,勇気,尊重)を基本とし、 開発のためのプラクティス(習慣,実践)として、 テスト駆動開発(コーディングでは最初に機能をテストするためのプログラムを書き、そのテストが通るようにプログラムを書くことで,こまめにテストしながら開発を行う)や、 ペアプログラミング(2人ペアで開発し、コーディングを行う人とそのチェックを行う人で役割分担をし、 一定期間毎にその役割を交代する)などの方式が取られることが多い。
リーン・ソフトウェア開発は、トヨタ生産方式を一般化したリーン生産方式をソフトウェア開発に導入したもの。ソフトウェアでよく言われる話として「完成した機能の64%は使われていない」という分析がある。これでは、開発に要する人件費の無駄遣いとみることもできる。そこで、品質の良いものを作る中で無駄の排除を目的とし、本当にその機能は必要かを疑いながら、優先順位をつけ実装し、その実装が使われているのか・有効に機能しているのかを評価ながら開発をすすことが重要であり、リーン生産方式がソフトウェア開発にも取り込まれていった。
伽藍(がらん)とバザール
これは、通常のソフトウェア開発の理論とは異なるが、重要な開発手法の概念なので「伽藍とバザール」を紹介する。
伽藍(がらん)とは、優美で壮大な寺院のことであり、その設計・開発は、優れた設計・優れた技術者により作られた完璧な実装を意味している。バザールは有象無象の人の集まりの中で作られていくものを意味している。
たとえば、伽藍方式の代表格である Microsoft の製品は、優秀なプロダクトだが、中身の設計情報などを普通の人は見ることはできない。このため潜在的なバグが見つかりにくいと言われている。
これに対しバザール方式の代表格の Linux は、インターネット上にソースコードが公開され、誰もがソースコードに触れプログラムを改良してもいい(オープンソース)。その中で、新しい便利な機能を追加しインターネットに公開されれば、良いコードは生き残り、悪いコードは自然淘汰されていく。
このオープンソースを支えているツールとしては、プログラムの変更履歴やバージョン管理を行う分散型バージョン管理システム git が有名であり、Linux のソフトウェア管理などで広く利用されている。。
オープンソースライセンス
バザール方式は、オープンソースライセンスにより成り立っていて、このライセンスが適用されていれば、改良した機能はインターネットに公開する義務を引き継ぐ。このライセンスの代表格が、GNU パブリックライセンス(GPL)であり、公開の義務の範囲により、BSD ライセンス、Apacheライセンスといった違いがある。
| コピーレフト型 | GNU ライセンス(GPL) | 改変したソースコードは公開義務, 組み合わせて利用で対応箇所の開示。 |
 |
| 準コピーレフト型 | LGPL, Mozilla Public License | 改変したソースコードは公開義務。 |  |
| 非コピーレフト型 | BSDライセンス, Apacheライセンス | ソースコードを改変しても必ずしもすべてを公開しなくてもいい。 |   |
GPLライセンスのソフトウェアを組み込んで製品を開発した場合に、ソースコード開示を行わないとGPL違反となる。大企業でこういったGPL違反が発生すると、大きな風評被害による損害をもたらす場合がある。
シェルスクリプト
前回の授業では、OSでのリダイレクト・パイプの概念とプロセスの概念について説明を行ってきた。これによりプログラムの実行結果を他のプログラムに渡すことができる。これらの機能を使うと、いくつかのプログラムを次々と実行させるなどの自動化をしたくなってくる。そこで、今回の授業では、OSとプログラムの間の情報を伝え合う基本機能の説明や、プログラムの起動をスクリプトとしてプログラム化するためのシェルスクリプト(shell script)について説明する。
環境変数
OSを利用していると、その利用者に応じた設定などを行いたい場合が多い。このような情報を管理する場合には、環境変数が使われる。環境変数はプロセス毎に管理され、プロセスが新しく子供のプロセス(子プロセス)を生成すると、環境変数は子プロセスに自動的に引き渡される。代表的な環境変数を以下に示す。
- HOME – ユーザがログインした際の起点となるディレクトリであり、/home/ユーザ名 となっているのが一般的。
シェルの中では”~” で代用できる。( “cd ~” で、最初のディレクトリに戻る ) - LC_ALL, LANG – ユーザが使う言語。OSからのメッセージなどを日本語で表示したい場合には、ja_JP.UTF-8 などを指定。
- TZ – ユーザの時差の情報(Time Zone) 日本であれば、”JST-9″ を設定するのが一般的。
日本標準時 “JST” で、グリニッジ標準時(GMT)との時差を表す “-9” の組み合わせ。 - PATH – ユーザがよく使うコマンドの保存されているディレクトリの一覧。/bin:/usr/bin の様にディレクトリ名を”:”区切りで書き並べる。
- LD_LIBRARY_PATH – 共有ライブラリの保存されているディレクトリの一覧。
環境変数と同じように、シェルの中で使われるものはシェル変数と呼ぶ。この変数は、子プロセスに引き渡されない。
環境変数を表示するには、env コマンド(環境変数を表示)や、set コマンド(環境変数やシェル変数を表示)を用いる。シェルの中で特定の環境変数を参照する場合には、$変数名 とする。echo コマンドで PATH を表示するなら、”echo $PATH” とすればいい。
guest00@nitfcei:~$ env SHELL=/bin/bash : guest00@nitfcei:~$ echo $PATH /bin:/usr/bin:/usr/local/bin
変数に値を設定する場合には、“変数名=値” の様に設定する。この変数を環境変数に反映させるには、export コマンドを用いるか、“export 変数名=値” を用いる。
((( 環境変数の設定 ))) guest00@nitfcei:~$ PATH=/bin:/usr/bin guest00@nitfcei:~$ echo $PATH guest00@nitfcei:~$ export PATH guest00@nitfcei:~$ export PATH=/bin:/usr/bin:/usr/local/bin ((( PATHの確認 ))) guest00@nitfcei:~$ which zsh # which はコマンドの場所を探してくれる /bin/zsh guest00@nitfcei:~$ export PATH=/usr/local/bin:/usr/bin:/bin guest00@nitfcei:~$ which zsh /usr/bin/zsh ((( LC_ALL,LANG の確認 ))) guest00@nitfcei:~$ export LC_ALL=C guest00@nitfcei:~$ man man (英語でマニュアルが表示される) guest00@nitfcei:~$ export LC_ALL=ja_JP.UTF-8 guest00@nitfcei:~$ man man (日本語でマニュアルが表示される) ((( TZタイムゾーンの確認 ))) guest00@nitfcei:~$ export TZ=GMT-0 guest00@nitfcei:~$ date 2022年 7月 4日 月曜日 05:23:23 GMT # イギリスの時間(GMT=グリニッジ標準時間)が表示された guest00@nitfcei:~$ export TZ=JST-9 guest00@nitfcei:~$ date # 日本時間(JST=日本標準時間)で表示された 2022年 7月 4日 月曜日 14:23:32 JST guest00@nitfcei:~$ TZ=GMT-0 date ; date # 環境変数を一時的に変更して date を実行 2022年 7月 4日 月曜日 05:23:23 GMT 2022年 7月 4日 月曜日 14:23:32 JST
プログラムとコマンドライン引数と環境変数
この後に説明するシェルスクリプトなどの機能を用いる場合は、自分のプログラムとのデータのやり取りにコマンドライン引数と環境変数を使う。また、プログラムの実行に失敗した時に別の処理を実行するためには、main関数の返り値を使うことができる。
コマンドライン引数
コマンドライン引数は、プログラムを起動する時の引数として書かれている情報であり、C言語でこの情報を用いる時には、main関数の引数”int main( int argc , char** argv ) …” により値をもらうことができ、以下のようなプログラムを記述することで受け取ることができる。
# 参考として Java の場合のコマンドライン引数の取得方法も示す。
((( argv.c )))
#include <stdio.h>
int main( int argc , char** argv ) {
for( int i = 0 ; i < argc ; i++ ) {
printf( "argv[%d] = %s\n" , i , argv[ i ] ) ;
}
return 0 ;
}
((( argv.c を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argv.c .
guest00@nitfcei:~$ gcc argv.c
guest00@nitfcei:~$ ./a.out 111 aaa 234 bcdef
argv[0] = ./a.out
argv[1] = 111
argv[2] = aaa
argv[3] = 234
argv[4] = bcdef
((( Argv.java )))
import java.util.* ;
public class Argv {
public static void main( String[] args ) throws Exception {
for( int i = 0 ; i < args.length ; i++ )
System.out.println( "args["+i+"] = "+args[i] ) ;
}
}
((( Argv.java を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/Argv.java .
guest00@nitfcei:~$ javac Argv.java
guest00@nitfcei:~$ java Argv 111 aaa 234 bcdef
args[0] = 111 # Java では コマンド名argv[0]は引数に含まれない
args[1] = aaa
args[2] = 234
args[3] = bcdef
注意点：コマンドライン引数の0番目には、プロセスを起動した時のプロセス名が入る。
環境変数の参照
C言語のmain関数は、コマンドライン引数のほかに環境変数も参照することができる。envpの情報は、getenv関数でも参照できる。
((( argvenvp.c )))
#include <stdio.h>
int main( int argc , char** argv , char** envp ) {
// コマンドライン引数argc,argvの処理
for( int i = 0 ; i < argc ; i++ ) {
printf( "argv[%d] = %s\n" , i , argv[ i ] ) ;
}
// 環境変数envpの処理
for( int i = 0 ; envp[i] != NULL ; i++ ) {
printf( "envp[%d] = %s\n" , i , envp[ i ] ) ;
}
return 0 ;
}
((( argvenvp.c を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argvenvp.c .
guest00@nitfcei:~$ gcc argvenvp.c
guest00@nitfcei:~$ ./a.out
argv[0] = ./a.out
envp[0] = SHELL=/bin/bash
:
プロセスの返す値
プログラムによっては、処理が上手くいかなかったことを検知して、別の処理を実行したいかもしれない。
こういう場合には、C言語であれば main の返り値に 0 以外の値で return させる。( exit関数を使ってもいい )
以下の例では、入力値の平均を出力するが、データ件数が0件であれば平均値を出力できない。こういう時に、”return 1 ;” のように値を返せば、シェル変数 $? (直前のコマンドの返り値) に return で返された値を参照できる。
((( average.c )))
#include <stdio.h>
int main() {
int count = 0 ;
int sum = 0 ;
char buff[ 1024 ] ;
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
int value ;
if ( sscanf( buff , "%d" , &value ) == 1 ) {
sum += value ;
count++ ;
}
}
if ( count == 0 ) {
// データ件数が0の場合は平均が計算できない。
fprintf( stderr , "No data\n" ) ;
// プログラムが失敗したことを返すには 0 以外の値を return する。
return 1 ; // exit( 1 ) ;
} else {
printf( "%lf\n" , (double)sum / (double)count ) ;
}
return 0 ;
}
((( average.c を動かしてみる )))
guest00@nitfcei:~$ gcc average.c
guest00@nitfcei:~$ ./a.out
12
14
^D # Ctrl-D で入力を終わらせる
13.00000
guest00@nitfcei:~$ echo $? # プロセスの実行結果の値を参照するためのシェル変数 $?
0
guest00@nitfcei:~$ ./a.out
^D # データを入力せずにすぐに終了させる。
No data
guest00@nitfcei:~$ echo $?
1
シェルスクリプト
今まで、コマンドラインで命令の入力をしてきたが、こういったキーボードと対話的処理を行うプログラムは shell (シェル) と呼ばれ、今回の演習では、/bin/bash を用いている。 shell は、キーボードとの対話的処理だけでなく、shell で入力するような処理をファイルに記録しておき、そのファイルに記載されている順に処理を実行することができる。
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/helloworld.sh . guest00@nitfcei:~$ cat helloworld.sh #!/bin/bash echo "Hello World" message="こんにちは" # シェル変数への代入 echo "Hello World = $message" # シェル変数の参照 guest00@nitfcei:~$ bash helloworld.sh # bash で helloworld.sh を実行する Hello World Hello World = こんにちは
シェルスクリプトの基本は、キー入力で実行するようなコマンドを書き並べればいい。
しかし、プログラムを実行する度に、bash ファイル名 と入力するのは面倒。こういう時には以下の2つの設定を行う。
- シェルスクリプトの先頭行に 実行させる shell の名前の前に “#!” をつける。
この行は、通称”シバン shebang (シェバン)“と呼ばれ、bashで実行させたいのなら”#!/bin/bash“、プログラミング言語 Perl で実行させたいのなら “#!/usr/bin/perl” とか、Python で実行させたいのなら、”#!/usr/bin/python” のようにすればいい。(今回のサンプルはすでに記入済み) - 保存したスクリプトに対して、実行権限を与える。
“ls -al “で “rw-r–r–” のようなファイルの書き込みパーミッションが表示されるが、通常ファイルの場合は、“x”の表示があると、プログラムとして実行可能となる。(フォルダであれば、rwxr-xr-x のように”x”の表示があると、フォルダの中に入ることができる)
((( 実効権限の設定 ))) guest00@nitfcei:~$ chmod 755 helloworld.sh guest00@nitfcei:~$ ./helloworld.sh Hello World Hello World = こんにちは
$HOME/.bashrc
シェルスクリプトは、Linux の環境設定を行うためのプログラム言語として使われている。
例えば、ユーザがログインする際には、そのユーザがどういった言語を使うのか(LC_LANG,LANG)や、どういったプログラムをよく使うのか(PATH,LD_LIBRARY_PATH)などは、そのユーザの好みの設定を行いたい。こういう時に、shell に bash を使っているのであれば、$HOME/.bashrc に、shell を使う際の自分好みの設定を記載すればいい。
((( $HOME/.bashrc の例 )))
#!/bin/bash
# PATHの設定
export PATH=/usr/local/bin:/usr/bin:/bin
# MacOS でインストールされているソフトで PATH を切り替える
if [ -d /opt/homebrew/bin ]; then # /opt/homebrew/bin のディレクトリがあるならば...
# HomeBrew
export PATH=/opt/homebrew/bin:$PATH
elif [ -d /opt/local/bin ]; then # /opt/local/bin のディレクトリがあるならば...
# MacPorts
export PATH="/opt/local/bin:$PATH"
fi
ユーザ固有の設定以外にも、OSが起動する時に、起動しておくべきプログラムの初期化作業などにもシェルスクリプトが使われている。
例えば、/etc/init.d/ フォルダには、Webサーバ(apache2)やsshサーバ(ssh) といったサーバを起動や停止をするための処理が、シェルスクリプトで記載してあり、OS 起動時に必要に応じてこれらのシェルスクリプトを使ってサーバソフトを起動する。(ただし最近は systemd が使われるようになってきた)
理解度確認小テスト
リストへの追加処理
最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。今回は、前回のリスト操作のプログラムの確認などと合わせ、リストへのデータの追加処理について説明する。
ループによるリスト操作・再帰によるリスト操作
ループによるリスト操作のプログラム例を以下に示す。
// リストの全要素を出力
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "¥n" ) ;
}
// リストの件数を返す
int count( struct List* p ) {
int c = 0 ;
for( ; p != NULL ; p = p->next )
c++ ;
return c ;
}
// リストの合計を返す
int sum( struct List* p ) {
int s = 0 ;
for( ; p != NULL ; p = p->next )
s += p->data ;
return s ;
}
// リストの最大値を返す
int max( struct List* p ) {
if ( p == NULL ) {
return 0 ;
} else {
int m = p->data ;
for( p = p->next ; p != NULL ; p = p->next )
if ( p->data > m )
m = p->data ;
return m ;
}
}
// リストの中から指定したkeyが含まれるか探す
int find( struct List* p , int key ) {
// 要素を見つけたら 1 、見つからなかったら 0 を返す
for( ; p != NULL ; p = p->next )
if ( p->data == key )
return 1 ;
return 0 ;
}
同じプログラムを再帰呼び出しで書いた場合。
// リストの全要素を再帰処理で出力
void print( struct List* p ) {
if ( p == NULL ) {
printf( "¥n" ) ;
} else {
printf( "%d " , p->data ) ;
print( p->next ) ;
}
}
// リストの件数を再帰処理でカウント
int count( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ;
}
// リストの合計を再帰処理で求める
int sum( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return p->data + sum( p->next ) ;
}
// リストの最大値を再帰処理で求める
int max( struct List* p ) {
if ( p == NULL ) {
return 0 ;
} else {
int tm = p->data ;
int rm = max( p->next ) ;
return tm > rm ? tm : rm ; // if ( tm > rm )
} // return tm ;
} // else
// return rm ;
// リストの中から指定した値 key を再帰処理で探す
int find( struct List* p , int key ) {
if ( p == NULL )
return 0 ; // 見つからなかった
else if ( p->data == key )
return 1 ; // 見つかった
else
return find( p->next , key ) ;
}
最も単純なリスト先頭への挿入
リスト構造を使うと、必要に応じてメモリを確保しながらデータをつなげることができるので、配列のように最初に最大データ件数を想定した入れ物を最初に作って保存するような処理をしなくて済む。
struct List {
int data ;
struct List* next ;
} ;
// 保存するリストの先頭
struct List* top = NULL ;
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
// ~~~~~~~~~(A) ~~~~~~~(B)
printf( "%d " , p->data ) ;
// ~~~~~(C) ~~~~~~~(D)
printf( "¥n" ) ;
}//~~~~~~~~~~~~~~(E)
int main() {
int x ;
while( scanf( "%d" , &x ) == 1 ) {
// ~~~~~~~~~~~~~~~~~~(F)
top = cons( x , top ) ;
} // ~~~~~~~~~~~~~~~(G)
print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(H)
return 0 ; // (生成したリストの廃棄処理は省略)
}
// (1) 入力で、11 , 22 を与えるとどうなる？ - 下図参照
// (2) 練習問題(A)～(H)の型は？
// (3) 入力で、11,22 の後に 33 を与えるとどうなる？
ここで示したコードは、新しい要素を先頭に挿入していく処理となる。このため、作られたリストは、与えられた要素順とは逆順となる。この方法は、リストを管理するポインタが1つで分かりやすい。
授業では、C言語のプログラムを示しているが、C++を使うと LIST 処理もシンプルに記述できるようになっている。参考資料として、C++で同様の処理を示す。テンプレートを使ったコンテナクラスを使うと、struct List {…} といった記述は不要で、std::forward_list<int> という型を使うだけで書けてしまう。
// C++ コンテナクラスで書くと...(auto を使うには C++11 以上) #include <iostream> #include <forward_list> #include <algorithm> int main() { std::forward_list<int> top ; int x ; while( std::cin >> x ) top.push_front( x ) ; for( auto i = top.cbegin() ; i != top.cend() ; ++i ) std::cout << *i << std::endl ; return 0 ; }
要素を末尾に追加して追加順序で保存
前に示した方法は、逆順になるので、追加要素が常に末尾に追加される方法を示す。
struct List* top = NULL ;
struct List** tail = &top ;
int main() {
int x ;
while( scanf( "%d" , &x ) == 1 ) {
// ~~~~~~~~~~~~~~~~~~~~~~~(A)
*tail = cons( x , NULL ) ;
tail = &((*tail)->next) ;
}//~~~~~~~~~~~~~~~~~~~~~~~(B) 下記の解説参照
print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(C)
return 0 ; // (生成したリストの廃棄処理は省略)
}
// (1) 入力で 11,22 を与えるとどうなる？ - 下図参照
// (2) 練習問題(A),(C)の型は？
// (3) 11,22の後に、さらに 33 を与えるとどうなる？
この方法は、次回にデータを追加する場所(末尾の目印のNULLが入っているデータの場所)を覚える方式である。ただし、リストへのポインタのポインタを使う方法なので、少しプログラムがわかりづらいかもしれない。
理解の確認のために、末尾のポインタを動かす部分の式を、型で解説すると以下のようになる。
途中でデータ挿入・データ削除
リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。
// 指定した途中の場所に要素を挿入
void insert( struct List*p , int data ) {
// p は要素を入れる前のポインタ
// data は追加する要素
// あえて、補助関数consを使わずに書いてみる
struct List* n ;
n = (struct List*)malloc( sizeof( struct List ) ) ;
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A)
if ( n != NULL ) {
n->data = data ;
// ~~~~(B)
n->next = p->next ;
// ~~~~~~~(C)
p->next = n ;
}
// consを使って書けば、簡単
// p->next = cons( data , p->next ) ;
}
int main() {
struct List* top = cons( 11 , cons( 22 , cons( 44 , NULL ) ) ) ;
// ↑
insert( top->next , 33 ) ; // ここに33を挿入したい
return 0 ; // (生成したリストの廃棄処理は省略)
}
// 指定した場所のデータを消す
void remove_after( struct List* p ) {
struct List* del = p->next ;
p->next = del->next ;
free( del ) ;
}
int main() {
struct List* top = cons( 11 , cons( 22 , cons( 33 , cons( 44 , NULL ) ) ) ) ;
remove_after( top->next ) ; // ↑
// これを消したい
return 0 ; // リストの廃棄処理は省略)
}
理解度確認
上記プログラムinsert() の中の、下線部(A),(B),(C)の型は何か答えよ。
レポート課題
以下に示すようなデータを扱うリスト構造を作り、そのリストを扱うプログラムを作成せよ。
( 出席番号 % 3 ) の番号の課題に取り組むこと。
- 緯度(latitude)経度(longitude)とその場所の都市名(city)
- 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
- 複素数(re,im)
このようなプログラムを作るのであれば、以下の例を参考に。
struct NameAgeList {
char name[ 20 ] ; // 名前
int age ; // 年齢
struct NameAgeList* next ; // 次のデータへのポインタ
} ;
struct NameAgeList* na_cons( char* nm, int ag,
struct NameAgeList*p )
{ struct NameAgeList* ans ;
ans = (struct NameAgeList*)malloc(
sizeof( struct NameAgeList ) ) ;
if ( ans != NULL ) {
strcpy( ans->name , nm ) ;
ans->age = ag ;
ans->next = p ;
}
return ans ;
}
int main() {
struct NameAgeList* top = NULL ;
struct NameAgeList* p ;
char buff[ 1024 ] ;
// 1行読み込みの繰り返し
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
char nm[ 100 ] ;
int ag ;
// 1行の中から名前と年齢があったら na_cons で挿入保存
if ( sscanf( buff , "%s%d" , nm , &ag ) == 2 ) {
top = na_cons( nm , ag , top ) ;
}
}
// 読み込んだデータを全部出力
for( p = top ; p != NULL ; p = p->next )
printf( "%s %d¥n" , p->name , p->age ) ;
return 0 ; // リストの廃棄処理は省略)
}
UMLと振る舞い図
前回の講義で説明した構造図に続いて、処理の流れを説明するための振る舞い図の説明。
講義の後半は、UML作成のレポートの課題時間とする。
振る舞い図
参考資料をもとに振る舞い図の説明を行う。
ユースケース図
ユーザなど外部からの要求に対する、システムの振る舞いを表現するための活用事例や機能を表す図がユースケース図。 システムを構築する際に、最初に記述するUMLであり、システムに対する処理要件の全体像や機能を理解するために記述する。 ユーザや外部のシステムは、アクターとよび人形の絵で示す。楕円でシステムに対する具体的な処理をユースケースとして楕円で記述する。 関連する複数のユースケースをまとめて、サブジェクトとして示す場合もある。
アクティビティ図
処理順序を記述するための図にはフローチャートがあるが、上から下に処理順序を記述するため、縦長の図になりやすい。また、四角枠の中に複雑なことを書けないので、UMLではアクティビティ図を用いる。
初期状態●から、終了状態◉までの手順を示すためのものがアクティビティ図。 フローチャートに無い表現として、複数の処理を並行処理する場合には、フォークノードで複数の処理を併記し、最終的に１つの処理になる部分をマージノードで示す。 通常の処理は、角丸の長方形で示し、条件分岐はひし形で示す。
ステートチャート図(状態遷移図)
ステートチャート図は、処理内部での状態遷移を示すための図。 １つの状態を長丸長方形で示し、初期状態●から終了状態◉までを結ぶ。 １つの状態から、なんらかの状態で他の状態に遷移する場合は、分岐条件となる契機(タイミング)とその条件、およびその効果(出力)を「契機[条件]/効果」で矢印に併記する。 複数の状態をグループ化して表す場合もある。
シーケンス図
複数のオブジェクトが相互にやり取りをしながら処理が進むようなもののタイミングを記述するためのものがシーケンス図。 上部の長方形にクラス/オブジェクトを示し、その下に縦軸にて時系列の処理の流れの線(Life Line)を描く。 オブジェクトがアクティブな状態は、縦長の長方形で示し、そのLife Line間を、やり取り(メッセージ)の線で相互に結ぶ。 メッセージは、相手側からの返答を待つような同期メッセージは、黒塗り三角矢印で示す。 返答を待たない非同期メッセージは矢印で示し、返答は破線で示す。
コミュニケーション図
クラスやオブジェクトの間の処理とその応答(相互作用)と関連の両方を表現する図。
応答を待つ同期メッセージは -▶︎、非同期メッセージは→で表す。複数のオブジェクト間のやりとりの相互作用を表現する。
タイミング図
タイミング図は、クラスやオブジェクトの時間と共に状態がどのように遷移するのかを表現する図。
状態変化の発生するタイミングや、時間的な遅れや時間的な制約を図で明記するために使われる。
IT専科・UML入門より引用
フィルタとプロセス管理
フィルタプログラム
パイプを使うと、標準入力からデータをもらい・標準出力に結果を出力するような簡単なプログラムを組み合わせて、様々な処理が簡単にできる。こういったプログラムは、フィルタと呼ぶ。
簡単な例として、入力をすべて大文字に変換するプログラム(toupper)、入力文字をすべて小文字に変換するプログラム(tolower)が、下記の例のように保存してあるので動作を確かめよ。
guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/toupper.c .
guest00@nitfcei:~$ gcc -o toupper toupper.c .
guest00@nitfcei:~$ cat toupper.c | ./toupper
#INCLUDE <STDIO.H>
#INCLUDE <CTYPE.H>
INT MAIN() {
INT C ;
WHILE( (C = GETCHAR()) != EOF )
PUTCHAR( TOUPPER( C ) ) ;
RETURN 0 ;
}
guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/tolower.c .
guest00@nitfcei:~$ gcc -o tolower tolower.c
guest00@nitfcei:~$ cat tolower.c | ./tolower
(((何が出力されるか答えよ)))
よく使われるフィルタのまとめ
| 文字パターンを含む行だけ出力 | grep 文字パターン |
| 文字パターンを含まない行を出力 文字パターンを正規表現でマッチングし該当行を出力 大文字小文字を区別しない |
grep -v 文字パターン grep -e 正規表現 grep -i 文字パターン |
| 入力文字数・単語数・行数をカウント(word counter) | wc |
| 入力行数をカウント | wc -l |
| データを昇順に並べる | sort |
| データを降順に並べる 先頭を数字と見なしてソート |
sort -r sort -g |
| 同じ行データが連続したら1つにまとめる | uniq |
| 同じ行が連続したら1つにまとめ、連続した数を出力 | uniq -c |
| 空白区切りで指定した場所(1番目)を抽出 | awk ‘{print$1;}’ |
| 入力の先頭複数行を表示(10行) | head |
| 入力の末尾複数行を表示(10行) | tail |
| 指定した行数だけ、先頭/末尾を表示 | head -行数 tail -行数 |
LOG解析
Linux は利用者に様々なサービスを提供するサーバで広く利用されている。しかし、幅広いサービス提供となると、中にはウィルス拡散や個人情報収集のための悪意のあるアクセスも増えてくる。
このためサーバでは、アクセスを受けた時の状況を記録し保存する。このような情報はアクセス履歴、ログと呼ぶ。
ログの中には、以下のような情報が混在することになるが、大量の 1. や 2. 目的のアクセスの中に、3. や 4. といったアクセスが混ざることになるが、これを見逃すとシステムに不正侵入を受ける可能性もある。
- 本来の利用者からのアクセス
- 検索システムの情報収集(クローラーからのアクセス)
- 不正な情報収集のためのアクセス
- システムの不備を探して不正侵入などを試みるアクセス
今回の演習では、電子情報の web サーバのとある1日のアクセス履歴ファイルを用い、パイプ機能を使い様々なフィルタを使い LOG解析の練習を行う。
アクセス履歴の解析
Webサーバのアクセス履歴が、/home0/Challenge/2.2-LOG.d/access.log に置いてある。このファイルで簡単な確認をしてみよう。
(( ファイルの場所に移動 )) $ cd /home0/Challenge/2.2-LOG.d/ (( .asp という文字を含む行を表示 )) $ grep .asp access.log
電子情報のWebサーバには、.asp (WindowsのWebサーバで動かすプログラムの拡張子) など存在しない。明らかに設定不備を探すための攻撃である。
これを見ると、grep で .asp を含む行が抜粋され、.asp の部分が強調されていることで、攻撃を簡単に確認できる。しかしこれは画面行数で10件程度が確認できるが、本当は何回攻撃を受けたのだろうか？この場合は、行数をカウントする”wc -l” を使えばいい。
(( アクセス回数を数える )) $ grep .asp access.log | wc -l 37
access.log の各項目の意味
電子情報のWebサーバの access.log に記録されている各項目の意味は以下の通り。
| 項目 | log項目 | 内容 |
|---|---|---|
| 1 | %h | リモートホスト。WebサーバにアクセスしてきたクライアントのIPアドレス |
| 2 | %l | リモートログ名。説明略。通常は “-“ |
| 3 | %u | ログインして操作するページでのユーザ名。通常は “-“ |
| 4 | %t | アクセスを受けた時刻 |
| 5 | %r | 読み込むページ。アクセス方法(GET/POSTなど)と、アクセスした場所。 |
| 6 | %>s | ステータスコード。(200成功,403閲覧禁止,404Not Found) |
| 7 | %b | 通信したデータのバイト数。 |
| 8 | %{Referer}i | Referer どのページからアクセスが発生したのか |
| 9 | %{User-Agent}i | User-Agent ブラウザ種別(どういったブラウザからアクセスされたのか) |
以下に、フィルタプログラムを活用して、色々な情報を探す例を示す。実際にコマンドを打って何が表示されるか確認しながら、フィルタプログラムの意味を調べながら、何をしているか考えよう。
.asp を使った攻撃を探す
(( .asp を試す最初の履歴を探す )) $ grep "\.asp" access.log | head -1 49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /Include/md5.asp HTTP/1.1" 404 64344 "https://www.ei.fukui-nct.ac.jp/Include/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)" (( 49.89.249.9 がどんなアクセスを試みているのか探す )) $ grep ^49.89.249.9 access.log | head 49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /Include/md5.asp HTTP/1.1" 404 64344 "https://www.ei.fukui-nct.ac.jp/Include/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)" 49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /inc/md5.asp HTTP/1.1" 404 61056 "https://www.ei.fukui-nct.ac.jp/inc/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)"
- ステータスコードが404は”Not Found”なので、読み出しに失敗している。
- IPアドレス検索で、49.89.249.9 がどこのコンピュータか調べよう。
攻撃の時間を確認
(( 49.89.249.9 がどんな時間にアクセスを試みているのか探す ))
$ grep ^49.89.249.9 access.log | awk '{print $4;}'
[20/Dec/2019:09:19:06
[20/Dec/2019:09:19:06
[20/Dec/2019:09:19:07
:
- 不正アクセスを試みている時間を調べると、そのアクセス元の09:00～17:00に攻撃していることがわかる場合がある。どういうこと?
ページの閲覧頻度を確認
(( /~t-saitoh/ 見たIPアドレスと頻度 ))
$ grep "/~t-saitoh/" access.log | awk '{print $1;}' | sort | uniq -c | sort -g -r | head
38 151.80.39.78
35 151.80.39.209
32 203.104.143.206
31 5.196.87.138
:
- grep – “/~t-saitoh/”のページをアクセスしているデータを抽出
- awk – 項目の先頭(IPアドレス)だけ抽出
- sort – IPアドレス順に並べる(同じIPアドレスならその数だけ重複した行になる)
- uniq – 重複している行数を数える
- sort -g -r – 先頭の重複数で大きい順にソート
- head – 先頭10行だけ抽出
(( /~t-saitoh/ 見たIPアドレスと頻度 )) (( t-saitoh のテスト問題のページを誰が見ているのか? )) $ grep "/~t-saitoh/exam/" access.log 5.196.87.156 - - [20/Dec/2019:06:36:02 +0900] "GET /~t-saitoh/exam/db2009/ex2009-5-1.pdf HTTP/1.1" 200 20152 "-" "Mozilla/5.0 (compatible; AhrefsBot/6.1; +http://ahrefs.com/robot/)" : (( クローラーのアクセスが多くてよくわからないので bot を含まない行を抽出 )) $ grep "/~t-saitoh/exam/" access.log | grep -v -i bot | lv 213.242.6.61 - - [20/Dec/2019:06:33:12 +0900] "GET /%7Et-saitoh/exam/ HTTP/1.0" 200 19117 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.87 Safari/537.36 OPR/54.0.2952.64 (Edition Yx)" 188.163.109.153 - - [20/Dec/2019:06:43:04 +0900] "GET /%7Et-saitoh/exam/ HTTP/1.0" 200 19117 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.170 Safari/537.36 OPR/53.0.2907.99" 188.163.109.153 - - [20/Dec/2019:06:43:05 +0900] "POST /cgi-bin/movabletype/mt-comments.cgi HTTP/1.0" 404 432 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.170 Safari/537.36 OPR/53.0.2907.99" 45.32.193.50 - - [20/Dec/2019:07:06:15 +0900] "GET /~t-saitoh/exam/apply-prog.html HTTP/1.0" 200 5317 "http://www.ei.fukui-nct.ac.jp/" "Mozilla/5.0 (Windows NT 5.2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/63.0.3239.132 Safari/537.36"
- この結果を見ると mt-comments.cgi というアクセスが見つかる。どうも コメントスパム(ブログのコメント欄に広告を勝手に書き込む迷惑行為)をしようとしている。
ネットワーク攻撃への対処
今回の access.log のアクセス履歴解析は、Webサーバへのアクセスへの基本的な対処となる。しかし、もっと違うネットワーク接続ではどのような対処を行うべきであろうか？
一般的には、
- サーバにネットワークアクセスの記録ソフトを使う(例ネットワークプロトコルアナライザーWireShark)
- ファイアウォールのアクセス履歴を解析
授業内レポート
- ここまでのLOG解析の例の１つについて、どういう考え方でフィルタを使っているのか、自分の言葉で説明せよ。
- LOG 解析のためのコマンドを考え、その実行結果を示し、それから何が判るか説明せよ。
(例) コメントスパムを何度も試す危ないアクセス元は〇〇である。
ジョブ管理
プログラムを実行している時、それがすごくメモリも使い計算時間もかかる処理の場合、条件を変化させながら結果が欲しい時、どのように実行すべきだろうか？1つの処理が1時間かかるとして、画面を見ながら1時間後に処理が終わったことを確認してプログラムを実行するのか？
簡単な方法としては、1つ目の処理(仮にプログラムAとする)を実行させたままで、新しくウィンドウを開いてそこで新しい条件でプログラムを並行処理すればいい(プログラムBとする)と考えるかもしれない。しかし、メモリを大量に使用する処理をいくつも並行処理させると、仮想メモリが使われるようになる。結果的にスワッピングが発生する分、プログラムAを実行させた後にプログラムBを実行するための時間以上に、時間がかかることになる。
ここで、プログラムを並行処理させるか、逐次処理させるといった、JOB(ジョブ)管理について説明を行う。
以下の説明で、複雑で時間のかかる処理を実行するとサーバの負担が高くなるので指定時間の処理待ちを行うための sleep 命令を使う。
逐次実行と並行実行
プログラムを連続して実行(処理Aの後に処理Bを実行する)場合には、セミコロン”;” で区切って A ; B のように処理を起動する。
guest00@nitfcei:~$ echo A A guest00@nitfcei:~$ echo A ; echo B A B
プログラムを並行して実行(処理Aと処理Bを並行処理)する場合には、アンド”&”で区切って A & B のように処理を起動する。
guest00@nitfcei:~$ sleep 5 & [1] 55 guest00@nitfcei:~$ echo A A [1]+ 終了 sleep 5 guest00@nitfcei:~$ sleep 2 & sleep 3 [1] 56 [1]+ 終了 sleep 2 guest00@nitfcei:~$ time ( sleep 1 ; sleep 1 ) # time コマンドは、コマンドの実行時間を測ってくれる。 real 0m2.007s user 0m0.005s sys 0m0.002s guest00@nitfcei:~$ time ( sleep 1 & sleep 1 ) real 0m1.002s user 0m0.003s sys 0m0.000s
fg, bg, jobs コマンド
プログラムを実行中に、処理(ジョブ)を一時停止したり、一時停止している処理を復帰させたりするときには、fg, bg, jobs コマンドを使う。
- 処理をしている時に、Ctrl-C を入力すると前面処理のプログラムは強制停止となる。
- 処理をしている時に、Ctrl-Z を入力すると前面処理のプログラムは一時停止状態になる。
- fg (フォアグラウンド) は、指定した処理を前面処理(キー入力を受け付ける処理)に変更する。
- bg (バックグラウンド) は、指定した処理を後面処理(キー入力が必要になったら待たされる処理)に変更する。
- jobs (ジョブ一覧) は、実行中や一時停止している処理(ジョブ)の一覧を表示する。
guest00@nitfcei:~$ sleep 10 # 途中で Ctrl-Z を入力する ^Z [1]+ 停止 sleep 10 guest00@nitfcei:~$ fg sleep 10 # 一時停止していた sleep 10 を実行再開 guest00@nitfcei:~$ sleep 3 ^Z [1]+ 停止 sleep 3 guest00@nitfcei:~$ sleep 4 ^Z [2]+ 停止 sleep 4 guest00@nitfcei:~$ jobs [1]- 停止 sleep 3 # [1],[2]というのはjob番号 [2]+ 停止 sleep 4 guest00@nitfcei:~$ fg %1 # ジョブ番号1 を前面処理にする sleep 3 guest00@nitfcei:~$ fg %2 # ジョブ番号2 を前面処理にする sleep 4
ps, kill コマンド
OS では、プログラムの処理単位は プロセス(process) と呼ぶ。OS はプロセスごとにメモリの実行範囲などの管理を行う。一連のプロセスを組み合わせて実行する単位を ジョブ(job) と呼ぶ。
複数のプロセスは間違ったメモリアクセスで他のプロセスが誤動作するようでは、安心して処理が実行できない。そこで、OS は、プロセスが他のプロセスのメモリをアクセスすると強制停止させるなどの保護をしてくれる。しかし、プロセスと他のプロセスが協調して処理を行うための情報交換のためにメモリを使うことは困難である。プロセス間で情報交換が必要であれば、パイプ機能やプロセス間共有メモリ機能を使う必要がある。
最近のOSでは、共通のメモリ空間で動き 並行動作する個々の処理は スレッド(thread) と呼び、その複数のスレッドをまとめたものがプロセスとなる。OS では、プロセスごとに番号が割り振られ、その番号を プロセスID(PID) と呼ぶ。実行中のプロセスを表示するには、ps コマンドを使う。
実行中のプロセスを停止する場合には、kill コマンドを用いる。停止するプログラムは、ジョブ番号(%1など) か プロセスID を指定する。
guest00@nitfcei:~$ sleep 3 ^Z [1]+ 停止 sleep 3 guest00@nitfcei:~$ sleep 4 ^Z [2]+ 停止 sleep 4 guest00@nitfcei:~$ jobs [1]- 停止 sleep 3 # [1],[2]というのはjob番号 [2]+ 停止 sleep 4 guest00@nitfcei:~$ ps w # プロセスの一覧(wを付けるとコマンドの引数も確認できる) PID TTY STAT TIME CMD 13 pts/0 Ss 00:00:00 -bash 84 pts/0 T 00:00:00 sleep 3 85 pts/0 T 00:00:00 sleep 4 86 pts/0 R 00:00:00 ps w guest00@nitfcei:~$ kill %1 [1]- Terminated sleep 3 guest00@nitfcei:~$ kill -KILL 85 [2]+ 強制終了 sleep 4 guest00@nitfcei:~$ ps ax # 他人を含めた全プロセスの一覧表示 PID TTY STAT TIME COMMAND 1 ? Ss 0:52 /sbin/init 2 ? S 0:00 [kthreadd] 3 ? I< 0:00 [rcu_gp] :
理解度確認
リスト処理
リスト構造
リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。
まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、１つ１つのデータをポインタでつなげる処理を示す。
#include <stdio.h>
#include <stdlib.h>
// List構造の宣言
struct List {
int data ; // データ保存部
struct List* next ; // 次のデータへのポインタ
} ;
int main() {
struct List* top ; // データの先頭
struct List* p ;
// (1)
top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 111 ;
// (2)
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 222 ;
// (3)
top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->next->data = 333 ;
top->next->next->next = NULL ; // 末尾データの目印
for( p = top ; p != NULL ; p = p->next ) {
printf( "%d¥n" , p->data ) ;
}
return 0 ;
}
このようなメモリーの中のポインタの指し示す番地のイメージを、具体的な番地の数字を書いてみると、以下のような図で表せる。先頭の111が入った部分が1000番地であったなら、topというポインタには1000番地が入っている。
NULLって何？
前回の授業で説明した、次の配列の添え字の番号を使う方式では、データの末尾を示すためには、-1 を使った。-1 は、配列の添え字で通常ありえない値であり、次のデータはないという目印とした。
同じように、C言語では、通常あり得ないポインタとして、0 番地を示す NULL が定義されている。NULLポインタの先を参照してはいけない。このリスト処理では、末尾を表す目印として使っている。
#define NULL 0
補助関数
上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。
struct List* cons( int x , struct List* n ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
int main() {
struct List* top ;
top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
:
return 0 ; // Listの開放free()は省略
}
補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP)※ というプログラム言語でのリスト(セル)を生成する関数が cons 。
typedefを使った書き方
List構造の宣言は、古い書き方では typedef を使うことも多い。typedef は、型宣言において新しい型の名前をつける命令。
// typedef の使い方 // typedef 型宣言 型名 ; typedef unsigned int uint32 ; // 符号なし32bit整数をシンプルに書きたい // ~~~~~~~~~~~~ uint32 x = 12345 ; typedef struct LIST { // 構造体のタグ名と新しくつける型名と重複できない int data ; // のでこの時点のタグ名は "LIST" としておく struct LIST* next ; } List ; List* cons( int x , List* n ) { // C++なら struct List { ... } ; と書く List* ans ; // だけでこういう表記が可能 ans = (List*)malloc( sizeof( List ) ) ; : ((略)) } int main() { List* top ; top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ; : ((略)) }最近のC言語(C++)では、構造体のタグ名がそのまま型名として使えるので、こういう書き方をする必要はなくなってきている。
// 最近のC++なら... struct List { public: int data ; List* next ; public: List( int x , List* n ) : data( x ) , next( n ) {} } ; int main() { List* top = new List( 111 , new List( 222 , new List( 333 , NULL ) ) ) ; : // Listの開放deleteは省略 }LISP※と関数型プログラミング言語
LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらいに遡る。最初は、人工知能※※(AI)のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式 , λ式)で表すことができ、プログラムは関数型に基づいて作られる。
関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しの関数で書けばいい…。
LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。
古いAI※※と最近のAIの違い
最近では、AI(Artificial Intelligence) という言葉が復活してきたが、LISP が開発された頃の AI と最近注目されている AI は、微妙に異なる点がある。
LISPが開発された頃の AI は、関数型のプログラム言語で論理的思考を表現することが目標であった。頭脳を左脳と右脳の違いで表現することが多いが、どちらかというとLISPの時代のAI「分析的で論理的に優れ、言語力や計算機能が高い」とされる左脳を作り出すことを目指していた。しかしながら、この時代では、漠然としたパターンを認識したりするような「感覚的、直感的な能力に優れ総合判断力を司る右脳」のような処理は苦手であった。
しかしながら、最近注目されている AI は、脳神経を真似たニューラルネットワークから発展した機械学習やディープラーニングという技法により今まで難しかった右脳の機能を実現することで、最近のAIでは左脳と右脳の機能を兼ね備えたものとなっている。
将棋のプログラミングで例えるなら、左脳(古いAI)に例えられるのが正確に先の手を読む機能であり、右脳に例えられる機能が大局観(全体の良し悪しを見極める判断能力)といえる。
簡単なリスト処理の例
先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。
// 全要素を表示する関数
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
int c = 0 ;
for( ; p != NULL ; p = p->next )
c++ ;
return c ;
}
int main() {
struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
print( top ) ;
printf( "%d¥n" , count( top ) ) ;
return 0 ;
}
リスト処理を自分で考えて作成
以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの平均値を返す
double mean( struct List* p ) {
// (111+444+333)/3=296.0
自分で考えよう
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
// find( top , 444 ) = 1 (先頭0番目)
// 見つからなかったら -1
自分で考えよう
}
再帰呼び出しでリスト処理
リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか？
// 全データを表示
void print( struct List* p ) {
if ( p == NULL ) {
printf( "¥n" ) ;
} else {
printf( "%d " , p->data ) ;
print( p->next ) ; // 末尾再帰
}
}
// データ数を返す関数
int count( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
// find( top , 444 ) = 1
// 見つかったら1 , 見つからなかったら 0
自分で考えよう
}
理解度確認
上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。
危ないURL
