集約関数と副問い合わせ
特殊な条件演算子
WHERE 節の中で使える特殊な条件演算子を紹介する。
... AND ... WHERE S.業者番号 <= 100 AND S.業者番号 >= 200 ; ... OR ... WHERE S.業者番号 >= 100 OR S.業者番号 <= 200 ; NOT ... WHERE NOT S.業者番号 >= 100 ; ... IN ... WHERE S.業者番号 IN ( 'S1' , 'S4' ) ; ... BETWEEN A AND B WHERE S.優良度 BETWEEN 50 AND 100 ; ... LIKE ... WHERE S.業者名 LIKE 'A_C社' ; _ は任意の1文字 ABC社 ADC社 WHERE S.業者名 LIKE 'A%社' ; % は任意の0~N文字 A社, AA社 ABC社 ... IS NULL WHERE S.業者名 IS NULL WHERE S.業者名 IS NOT NULL
集約関数
集約関数は、SQL の SELECT の射影部分で使える関数で、出力対象となった項目に対して、COUNT(),SUM(),AVG()といった計算を行うもの。
COUNT() - 項目の数 SUM() - 項目の合計 AVG() - 項目の平均 MAX() - 項目の最大値 MIN() - 項目の最低値 SELECT COUNT(S.業者番号) FROM S WHERE S.優良度 > 20 ;
- 実験環境で集約関数(学内のみ)
集合計算
複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。
... UNION ... 集合和 ... EXPECT ... 集合差 ... INTERSECT ... 集合積 SELECT S.業者名 FROM S WHERE S.所在 = '福井' UNION SELECT S.業者名 FROM S WHERE S.所在 = '東京'
- 実験環境で集合計算(学内のみ)
SQLの副問い合せ
前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。
SELECT S.業者名, S.所在 FROM S WHERE S.業者番号 IN ( SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = 'G2' AND SG.在庫量 >= 200 ) ;
- 実験環境で副問い合わせ(学内のみ)
まず、『◯ IN { … }』 の比較演算子は、◯が{…}の中に含まれていれば真となる。また、SQLの中の (…) の中が副問い合わせである。
この SQL では、副問い合わせの内部には、テーブル S に関係する要素が含まれない。この場合、副問い合わせ(商品番号がG2で在庫量が200以上)は先に実行される。
{(S1,G2,200),(S2,G2,400),(S3,G2,200),(S4,G2,200)}が該当し、その業者番号の{S1,S2,S3,S4}が副問い合わせの結果となる。最終的に SELECT … FROM S WHERE S.業者番号 IN {‘S1′,’S2′,’S3′,’S4’} を実行する。
相関副問い合わせ
SELECT G.商品名, G.色, G.価格 FROM G WHERE 'S4' IN ( SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = G.商品番号 ) ;
- 実験環境で相関副問い合わせ(学内のみ)
この副問い合わせでは、内部に G.商品番号 が含まれており、単純に()内を先に実行することはできない。こういった副問い合わせは、相関副問い合わせと呼ばれる。
処理は、Gのそれぞれの要素毎に、副問い合わせを実行し、その結果を使って WHERE節の判定を行う。WHERE節の選択で残った結果について、射影で商品名,色,価格が抽出される。
// 概念の説明用に、C言語風とSQL風を混在して記載する for( int i = 0 ; i < sizeofarray( G ) ; i++ ) { SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = G[i].商品番号 を実行 if ( WHERE 'S4' IN 副query の結果が真なら ) { printf( ... ) ; } } // 全てのG 副queryの結果 WHERE 射影 // G1 -> {S1,S2} // G2 -> {S1,S2,S3,S4} -> ◯ -> (ノート,青,170) // G3 -> {S1} // G4 -> {S1,S4} -> ◯ -> (消しゴム,白,50) // G5 -> {S1,S4} -> ◯ -> (筆箱,青,300) // G6 -> {S1}
演習課題
SQLの実験環境を使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。
さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。
考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。
AVLと2分ヒープ
前回、2分探索木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。
2分探索木へのデータ追加と不均一な木の成長
先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。
しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか?
- 86, 53, 11 – 降順のデータ
- 12, 24, 42 – 昇順のデータ
この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。
AVL木
このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで検索回数を改善できる。例えば、以下のような木では、赤の左側に偏っている。
このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)
この様に、左右の枝の大きさが不均一な場所を見つけ、右回転や左回転を行う処理を繰り返すことで、段数が均一な2分探索木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。
理解確認
- 木の根からの段数を求める関数 tree_depth() を作成せよ。
例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。
// 木の段数を数える関数 _____ tree_depth( _______________ p ) { if ( p == NULL ) { return _____ ; } else { int d_L = ______________ ; int d_R = ______________ ; if ( d_L > d_R ) return _____ ; else return _____ : } } // pをつなぎ替え上部を返り値で返す。 struct Tree*rot_right( struct Tree* p ) { struct Tree* pl = p->left ; struct Tree* pr = pl->right ; pl->right = p ; p->left = = pr ; return pl ; } int main() { printf( "%d¥n" , tree_depth( top ) ) ; top = rot_right( top ) ; return 0 ; }
2分ヒープ(binary heap)
2分探索木では、1つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。
これらの問題の解決法の1つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝は 2×i+1 番目、右の枝は 2×i+2 番目であることが判る。
このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、O(log(N))で挿入が可能となる。
int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ; // 2分ヒープを表示 void print_heap( int array[] , int idx , int size ) { if ( idx < size ) { // 左の枝を表示 print_heap( array , 2*idx + 1 , size ) ; // 真ん中の枝を表示 printf( "%d " , array[ idx ] ) ; // 右の枝を表示 print_heap( array , 2*idx + 2 , size ) ; } } // 2分ヒープから key を検索 int find_heap( int array[] , int idx , int size , int key ) { while( idx < size ) { if ( array[ idx ] == key ) return idx ; // 見つかったら配列の番号を返す else if ( array[ idx ] _____ key ) // 何が入るか考えよう idx = ________________ ; else idx = ________________ ; } return -1 ; // 見つからなかったら、-1 を返す } int main() { print_heap( a , 0 , 7 ) ; if ( find_heap( a , 0 , 7 , 65 ) >= 0 ) printf( "Find!!¥n" ) ; return 0 ; }
SQLの基本
先週の、関係データベースの導入説明を終えて、実際のSQLの説明。
SQLの命令
SQL で使われる命令は、以下のものに分類される。((参考資料))
- データ定義言語 – CREATE, DROP, ALTER 等
- データ操作言語 – INSERT, UPDATE, DELETE, SELECT 等
- データ制御言語 – GRANT, REVOKE 等 (その他トランザクション制御命令など)
create user
データベースを扱う際の create user 文は、DDL(Data Definition Language)で行う。
CREATE USER ユーザ名 IDENTIFIED BY "パスワード"
grant
テーブルに対する権限を与える命令。
GRANT システム権限 TO ユーザ名 データベースシステム全体に関わる権限をユーザに与える。 (例) GRANT execute ON admin.my_package TO saitoh GRANT オブジェクト権限 ON オブジェクト名 TO ユーザ名 作られたテーブルなどのオブジェクトに関する権限を与える。 (例) GRANT select,update,delete,insert ON admin.my_table TO saitoh REVOKE オブジェクト権限 ON オブジェクト名 TO ユーザ名 オブジェクトへの権限を剥奪する。
ただし、後に示す実験環境では、データベースのシステムにSQLiteを用いている。SQLite はネットワーク対応型のデータベースではないため、データベースをアクセスするユーザや権限の概念が存在しない。
create table
実際にテーブルを宣言する命令。構造体の宣言みたいなものと捉えると分かりやすい。
CREATE TABLE テーブル名 ( 要素名1 型 , 要素名2 型 ... ) ; PRIMARY KEY 制約 1つの属性でのキーの場合、型の後ろに"PRIMARY KEY"をつける、 複数属性でキーとなる場合は、要素列の最後に PRIMARY KEY(要素名,...) をつける。 これによりKEYに指定した物は、重複した値を格納できない。 型には、以下の様なものがある。(Oracle) CHAR( size) : 固定長文字列 / NCHAR国際文字 VARCHAR2( size ) : 可変長文字列 / NVARCHAR2... NUMBER(桁) :指定 桁数を扱える数 BINARY_FLOAT / BINARY_DOUBLE : 浮動小数点(float / double) DATE : 日付(年月日時分秒) SQLiteでの型 INTEGER : int型 REAL : float/double型 TEXT : 可変長文字列型 BLOB : 大きいバイナリデータ DROP TABLE テーブル名 テーブルを削除する命令
insert,update,delete
指定したテーブルに新しいデータを登録,更新,削除する命令
INSERT INTO テーブル名 ( 要素名,... ) VALUES ( 値,... ) ; 要素に対応する値をそれぞれ代入する。 UPDATE テーブル名 SET 要素名=値 WHERE 条件 指定した条件の列の値を更新する。 DELETE FROM テーブル名 WHERE 条件 指定した条件の列を削除する。
select
データ問い合わせは、select文を用いる、 select文は、(1)必要なカラムを指定する射影、(2)指定条件にあうレコードを指定する選択、 (3)複数のテーブルの直積を処理する結合から構成される。
SELECT 射影 FROM 結合 WHERE 選択 (例) SELECT S.業者番号 FROM S WHERE S.優良度 > 30 ;
理解確認
- キー・プライマリキー・外部キーについて説明せよ。
- 上記説明中の、科目テーブルにふさわしい create table 文を示せ。
- select文における、射影,結合,選択について説明せよ。
SQLの演習環境の使い方
下記URLにアクセスすると、認証画面が表示されるので、情報処理センターのユーザIDとパスワードで、Login する。
以下のような画面が表示されるので、最初に”データベースリセット”を押すこと。
以降、登録済みの処理を実行する場合は、左上のプルダウンメニューから、処理を選んで”バッチ処理実行”を行う。
画面下に、実行された結果が表示される。
教科書内の基本演習のデータを利用したい場合は、”0_Create_DB” , “1_Insert_Data”を実行する。
自分で処理を実行したい場合には、中段のSQLコマンドの欄に、命令を記載する。”create table”や”insert”といった結果を伴わない命令の場合は、”EXEC”を実行。”select” などの実行結果がある場合は、”QUERY”を実行すること。
SQLの基礎
ここまで述べたようにデータベースでは記録されているデータの読み書きは、SQL で行われ、射影・結合・選択を表す処理で構成されることを示した。SQL の機能を理解するために、同じ処理を C 言語で書いたらどうなるのかを示す。
((( 元のSQL ))) SELECT S.業者番号 -- 必要とされるデータを抽出する射影 -- FROM S -- 複数のテーブルを組合せる結合 -- WHERE S.優良度 >= 20 ; -- 対象となるデータを選び出す選択 -- ((( SQLをC言語で書いたら ))) // 配列の個数を求める #define 文 #define sizeofarray(ARY) (sizeof(ARY) / sizeof(ARY[0])) // C言語なら... S のデータを構造体宣言で書いてみる。 struct Table_S { char 業者番号[ 6 ] ; // 当然、C言語では要素名を char 業者名[ 22 ] ; // 漢字で宣言はできない。 int 優良度 ; char 所在[ 16 ] ; } S[] = { { "S1" , "ABC社" , 20 , "福井" } , : } ; // SELECT...をC言語で書いた場合の命令のイメージ // 結合 for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // 選択 if ( S[i].優良度 >= 20 ) // 射影 printf( "%d¥n" , S[i].業者番号 ) ; }
Sは、テーブル名であり、文脈上対象テーブルが明らかな場合、フィールド名の前の テーブルは省略可能である。
SELECT 業者番号 FROM S WHERE 優良度 >= 20 ;
WHERE 節で記述できる条件式では、= , <>(not equal) , < , > , <= , >= の比較演算子が使える。
# これ以外の演算機能は、次週にて紹介予定。
直積と結合処理
ここで、SQLの最も便利な機能は、直積による結合処理。複数の表を組み合わせる処理。単純な表形式の関係データベースで、複雑なデータを表現できる基本機能となっている。
SELECT SG.商品番号 , S.所在 FROM S , SG WHERE SG.業者番号 = S.業者番号
- 実験環境で直積と結合処理(学内のみ)
上記の様に FROM 節に複数のテーブルを書くと、それぞれのテーブルの直積(要素の全ての組み合わせ)を生成する処理が行われる。この機能が結合となる。しかし、これだけでは意味がないので、通常は外部キーが一致するレコードでのみ処理を行うように、WHERE SG.業者番号 = S.業者番号 のような選択を記載する。最後に、結果として欲しいデータを抽出する射影を記載する。
SELECTの結合処理と処理内容
selectでの選択,結合,射影の処理(select 射影 from 結合 where 選択)を理解するために、同じ処理をC言語で書いたらどうなるかを示す。
// C言語なら struct Table_S { char 業者番号[ 6 ] ; char 業者名[ 22 ] ; int 優良度 ; char 所在[ 16 ] ; } S[] = { { "S1" , "ABC社" , 20 , "福井" } , : } ; struct Table_SG { char 業者番号[ 6 ] ; char 商品番号[ 6 ] ; int 在庫量 ; } = SG[] { { "S1" , "G1" , 300 } , : } ; // FROM S for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // FROM SG for( int j = 0 ; j < sizeofarray( SG ) ; j++ ) { // WHERE S.業者番号 = SG.業者番号 if ( strcmp( S[i].業者番号 , SG[j].業者番号 ) == 0 ) { // SELECT SG.商品番号 , S.所在 printf( "%s %s¥n" , SG[j].商品番号 , S[i].所在 ) ; } } }
(1) i,jの2重forループが、FROM節の結合に相当し、(2) ループ内のif文がWHERE節の選択に相当し、(3) printfの表示内容が射影に相当している。
射影の処理では、データの一部分を抽出することから、1件の抽出レコードが同じになることもある。この際の重複したデータを1つにまとめる場合には、DISTINCT を指定する。
SELECT DISTINCT SG.商品番号, S.所在 FROM S, SG WHERE SG.業者番号 = S.業者番号 ;
- 実験環境で結合/重複削除(学内のみ)
上記のプログラムでは、データの検索は単純 for ループで記載しているが、内部で HASH などが使われていると、昇順に処理が行われない場合も多い。出力されるデータの順序を指定したい場合には、ORDER BY … ASC (or DESC) を用いる
SELECT SG.商品番号, S.所在 FROM S, SG WHERE SG.業者番号 = S.業者番号 ORDER BY S.所在 ASC ; -- ASC:昇順 , DESC:降順 --
- 実験環境で結合/並び替え(学内のみ)
表型のデータと串刺し
FROM に記載する直積のための結合では、2つ以上のテーブルを指定しても良い。
SELECT S.業者名, G.商品名, SG.在庫量 FROM S, G, SG WHERE S.業者番号 = SG.業者番号 -- 外部キー業者番号の対応付け -- AND SG.商品番号 = G.商品番号 -- 外部キー商品番号の対応付け -- // 上記の処理をC言語で書いたら struct Table_G { char 商品番号[ 6 ] ; char 商品名[ 22 ] ; char 色[ 4 ] ; int 価格 ; char 所在[ 12 ] ; } = G[] = { { "G1" , "赤鉛筆" , "青" , 120 , "福井" } , : } ; // [結合] S,G,SGのすべての組み合わせ // FROM S -- 結合 for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // FROM G -- 結合 for( int j = 0 ; j < sizeofarray( G ) ; j++ ) { // FROM SG -- 結合 for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) { // [選択] 条件でレコードを選び出す // WHERE S.業者番号 = SG.業者番号 // AND SG.商品番号 = G.商品番号 if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 && strcmp( SG[k].商品番号 , G[j].商品番号 ) == 0 ) { // [射影] 使用するフィールドを出力 printf( "%s %s %d\n" , S[i].業者名 , G[j].商品名 , SG[k].在庫量 ) ; } } } }
- 実験環境で結合/3つのTABLEの串刺し(学内のみ)
ここで結合と選択で実行している内容は、外部キーである業者番号を S から探す、商品番号を G から探している。この、外部キー対応しているものを探すという視点で、上記 C 言語のプログラムを書き換えると、以下のように表せる。
// FROM SG for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) { // 外部キー SG.業者番号に対応するものを S から探す for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 ) { // 外部キー SG.商品番号に対応するものを G から探す for( int j = 0 ; j < sizeofarray( G ) ; j++ ) { if ( strcmp(SG[k].商品番号,G[j].商品番号) == 0 ) { printf( "%s %s %d\n" , S[i].業者名,G[j].商品名,SG[k].在庫量 ) ; } } } } }
このような、複数の表の実体と関係を対応付けた検索を、データベースの専門の人は「データを串刺しにする」という言い方をすることも多い。
また、SQL では、このようなイメージの繰り返し処理を、数行で分かりやすく記述できている。このプログラム例では、キーに対応するものを単純 for ループで説明しているが、SQL ではプライマリキーなら、B木やハッシュなどを用いた効率の良い検索が自動的に行われる。このため、SQLを扱う応用プログラマは、SQLの結合の処理方法は通常はあまり考えなくて良い。
batchとnohup
学校の CUDA サーバを自宅より使う学生より、「接続が Broken Pipeで切れるのどうすれば?」との質問があった。
原因は ssh で操作が何もない状態が続くと、セキュリティのために接続が切られるため。んで、.ssh/ssh_config でセッションの最大時間を延ばす設定あたりを説明したけど、「計算どのぐらいかかるの?」と聞くと「20時間かな…」。# さすが CUDA を使う卒研。
ssh のセッション延長の設定で20時間とかしちゃうと、ネットワークトラブルで通信が途中で切れたときに、サーバ側で「まだこの ssh 通信中だよね…」というプロセスが生き残る可能性があるので、あまり勧められる方法ではない。
こういう時には、処理を継続したままで、ログアウトするテクニックが必要。
通常は処理を起動して、ログアウトすると親プロセスにあたる sh が死ぬので、子プロセスが死んでしまう。
# このプロセスの原則があるから、Linux サーバで「訳の変わらんプロセスがあったら、『親を殺せ!!』が基本。」
プロセス確認の基本
((( 通常のプロセス全表示 ))) $ ps ax ((( 指定したコマンドのプロセス情報表示 ))) $ ps ax | grep コマンド名など ((( プロセスの起動引数を全部表示 ))) $ ps axl ((( 負荷の高い順にプロセス一覧を表示 ))) $ top ((( 指定したプロセスを停止 ))) $ kill -KILL プロセス番号
プロセスのバックグラウンド起動
((( プロセスをバックグラウンド起動 ))) $ コマンド... & # &がバックグラウンド起動の意味 ((( プロセスをバックグラウンドに変更 ))) $ コマンド... # フォアグランドでプロセスが動き出す ^Z (Ctrl-Z) # プロセスを一時停止 $ fg # 停止中のプロセスを再びフォアグラウンドで再起動 $ bg # 停止中のプロセスをバックグラウンドで再起動 $ jobs # 起動中の job を表示
上記で説明したコマンドは、login した shell の子プロセスになるため、たとえバックグラウンドで起動して「裏で動いている…プロセス」といえども、logout すると親プロセスが死ぬので、一緒に子プロセスも死んでしまう。
このため、起動するプロセスの親をシステムに代替わりしてもらって起動する nohup コマンドが使われる。
((( プロセスを No Hugup コマンドで起動 ))) $ nohup コマンド & # 出力はファイル保存される。 $ nohup コマンド > file.out & # 明示的にリダイレクトで表示保存先を指定 $ tail file.out # 保存しているファイルの末尾を表示
ただし nohup コマンドだと、プロセスが終了したかどうかわからない。こういう時は、batch コマンドが便利。ただし、batch コマンドはインストールされていない処理系が多い。(メールの設定が必要だから)
((( at パッケージのインストール ))) $ sudo apt-get install at # at(指定時間コマンド起動) # batch(バッチ処理起動) ((( batchの使い方 ))) $ batch at> コマンド at> ^D $ echo "コマンド" | batch
ただし batch は PATH が /bin/sh だけで起動するので、”python ほげ.py” とかで起動しても動かない場合あり。”/usr/bin/python ほげ.py” とかPATHを明記して起動するか、PATH=/usr/local/bin:/usr/bin:/bin なりの設定する処理を明記しないと動かない場合があるので要注意。
batch は、処理の出力結果はメールで送られてくる。結果を残すのなら、出力リダイレクトをしておく方がいい。
高専プロコン2021入賞
先日開催された、第32回秋田大会(2021). 「集え!未来創造への限りなき想い」において、電子情報工学科では、課題2作品、自由2作品、競技1チームにて応募し、6月に行われた書類審査にて、下記の3チームが本戦に参加し、2作品が入賞となりました。
- 自由部門 : 特別賞(ベスト3+企業賞:トヨタシステムズ賞)
- 「お地蔵様といっしょ -保育士のための園児見守りサポートシステム-」
- 開発,横山,加藤,北,飯島(電子情報4年),村田(指導教員)
- 課題部門 : 敢闘賞(+企業賞:さくらインターネット賞)
- 「マジメン-マジのイクメンパパになるための育児ⅤR教材アプリ-」
- 髙山,三木(電子情報4年),小松(指導教員)
- 競技部門 : 敗者復活戦にて敗退
- 小川,村中(電子情報4年),斉藤(指導教員)
2分探索木の処理とデータ追加処理
前回の授業では、当初予定に加え、この後に示すデータの追加処理の説明を行った。その代わり、簡単な2分木の演習が抜けていたので少し演習を追加。
2分木の簡単な処理
int count( struct Tree* p ) { if ( p == NULL ) return 0 ; else return 1 + count( p->left ) + count( p->right ) ; } int sum( struct Tree* p ) { // データ合計 if ( p == NULL ) return 0 ; else return p->data + sum( p->left ) + sum( p->right ) } int max( struct Tree* p ) { // 最大値 if ( p == NULL ) { return 0 ; // データ件数=0のとき0が最大値でいいのかなぁ? } else { while( p->right != NULL ) p = p->right ; return p->data ; } } int depth( struct Tree* p ) { // 木の深さ if ( p == NULL ) { return 0 ; } else { int d_l = depth( p->left ) ; int d_r = depth( p->right ) ; if ( d_l > d_r ) return d_l + 1 ; else return d_r + 1 ; } } int main() { struct Tree* top = ..... ; printf( "%d\n" , count( top ) ) ; // 木全体のデータ件数 printf( "%d\n" , sum( top ) ) ; // 木全体のデータ合計 printf( "%d\n" , depth( top ) ) ; // 木全体の最大段数 return 0 ; }
2分探索木にデータを追加
前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。
struct Tree* top = NULL ; // 2分探索木にデータを追加する処理 void entry( int d ) { struct Tree** tail = &top ; while( *tail != NULL ) { if ( (*tail)->data == d ) // 同じデータが見つかった break ; else if ( (*tail)->data > d ) tail = &( (*tail)->left ) ; // 左の枝に進む else tail = &( (*tail)->right ) ; // 右の枝に進む } if ( (*tail) == NULL ) *tail = tcons( d , NULL , NULL ) ; } int main() { char buff[ 100 ] ; int x ; while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) if ( sscanf( buff , "%d" , &x ) != 1 ) break ; entry( x ) ; return 0 ; }
このプログラムでは、struct Tree** tail というポインタへのポインタ型を用いている。tail が指し示す部分をイメージするための図を以下に示す。
理解確認
- 関数entry() の14行目の if 判定を行う理由を説明せよ。
- 同じく、8行目の tail = &( (*tail)->left ) の式の各部分の型について説明せよ。
- sscanf() の返り値を 1 と比較している理由を説明せよ。
- entry() でデータを格納する処理時間のオーダを説明せよ。
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... void entry( struct Tree* top , int d ) { struct Tree** tail = &top ; while( *tail != NULL ) { : // 上記の entry() と同じとする } void main() { // 追加対象の top は局所変数 struct Tree* top = NULL ; char buff[ 100 ] ; int x ; while( fgets(buff,sizeof(buff),stdin) != NULL ) { if ( sscanf( buff , "%d" , &x ) != 1 ) break ; entry( top , x ) ; } }上記のプログラム↑は動かない。なぜ?
このヒントは、このページ末尾に示す。
演習課題
以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。
- 名前(name)と電話番号(phone)
- 名前(name)と誕生日(year,mon,day)
- 名前(name)とメールアドレス(mail)
プログラムは以下の機能を持つこと。
- 1行1件でデータを入力し、2分木に追加できること。
- 全データを昇順(or降順)で表示できること。
- 検索条件を入力し、目的のデータを探せること。
レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。考察のネタが無い人は、このページの理解確認の内容について記述しても良い。
// プログラムのおおまかな全体像の例 struct Tree { // // この部分を考えて // 以下の例は、名前と電話番号を想定 } ; struct Tree* top = NULL ; void tree_entry( char n[] , char ph[] ) { // n:名前,ph:電話番号 を追加 } void tree_print( struct Tree* p ) { // 全データを表示 } struct Tree* tree_search_by_name( char n[] ) { // n:名前でデータを探す } int main() { char name[ 20 ] , phone[ 20 ] ; char buff[ 1000 ] ; struct Tree* p ; // データを登録する処理(空行を入力するまで繰り返し) while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { if ( sscanf( buff , "%s%s" , name , phone ) != 2 ) break ; // 入力で、2つの文字列が無い場合はループを抜ける tree_entry( name , phone ) ; } // 全データの表示 tree_print( top ) ; // データをさがす while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { if ( sscanf( buff , "%s" , name ) != 1 ) break ; // 入力で、1つの文字列が無い場合はループを抜ける if ( (p = tree_search_by_name( name )) == NULL ) printf( "見つからない¥n" ) ; else printf( "%s %s¥n" , p->name , p->phone ) ; } return 0 ; }
動かないプログラムのヒント
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... // ちなみに、こう書くと動く // Tree*を返すように変更 struct Tree* entry( struct Tree* top , int d ) { : // 最初の entry と同じ : return top ; } void main() { // 追加対象のポインタ struct Tree* top = NULL ; while( ... ) { : // entry() の返り値を top に代入 top = entry( top , x ) ; } }
fgets()とsscanf()による入力の解説
前述のプログラムの入力では、fgets() と sscanf() による処理を記載した。この関数の組み合わせが初見の人も多いと思うので解説。
// scanf() で苦手なこと -------------------------// // scanf() のダメな点 // (1) 何も入力しなかったら...という判定が難しい。 // (2) 間違えて、abc みたいに文字を入力したら、 // scanf()では以後の入力ができない。(入力関数に詳しければ別だけどさ) int x ; while( scanf( "%d" , &x ) == 1 ) { entry( x ) ; } // scanf() で危険なこと -------------------------// // 以下の入力プログラムに対して、10文字以上を入力すると危険。 // バッファオーバーフローが発生する。 char name[ 10 ] ; scanf( "%s" , name ) ; // 安全な入力 fgets() ---------------------------// // fgets() は、行末文字"¥n"まで配列 buff[]に読み込む。 // ただし、sizeof(buuf) 文字より長い場合は、途中まで。 char buff[ 100 ] ; while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { // buff を使う処理 } // 文字列からデータを抜き出す sscanf() -------------// // sscanf は、文字列の中から、データを抜き出せる。 // 入力が文字列であることを除き、scanf() と同じ。 char str[] = "123 abcde" ; int x ; char y[10] ; sscanf( str , "%d%s" , &x , y ) ; // x=123 , y="abcde" となる。 // sscanf() の返り値は、2 (2個のフィールドを抜き出せた) // ただし、Microsoft Visual Studio では、以下のように関数名を読み替えること。 // scanf( ... ) → scanf_s( ... ) // fscanf( ... ) → fscanf_s( ... ) // sscanf( ... ) → sscanf_s( ... )
理解確認
- 標準入力からの1行入力関数 gets() 関数が危険な理由を説明せよ。
深さ優先探索と幅優先探索
2分探索木の説明で、深さ優先探索、幅優先探索の話をしたので、補足説明。
幅優先探索(breadth-first search)は、待ち行列を使って実装可能なことを示すサンプルコード。待ち行列は授業で説明したFIFOでは、データ件数0になる際の処理を手抜きで説明しているため、C++ の deque で記述。
深さ優先探索(deep-first search)は、スタックを使って実装可能なことを示すために、あえて再帰呼び出しを使わずに記述してみた。
#include <deque> #include <algorithm> int main() { std::deque<struct Tree*> deq ; struct Tree* p ; // 幅優先探索(FIFOを使って) deq.push_front( top ) ; while( !deq.empty() ) { // 待ち行列の最初を取り出す p = deq.front() ; deq.pop_front() ; if ( p != NULL ) { printf( "%d\n" , p->data ) ; // 待ち行列に枝葉を追加 deq.push_back( p->left ) ; deq.push_back( p->right ) ; } } // 深さ優先探索(再帰呼び出しを使わずstack/LIFOで実装) p = top ; for( ;; ) { // 分岐をpushしながら左下にまっしぐら while( p != NULL ) { deq.push_front( p ) ; p = p->left ; } if ( deq.empty() ) break ; // pushしておいた分岐点をpopして繰り返し p = deq.front() ; deq.pop_front() ; printf( "%d\n" , p->data ) ; p = p->right ; } return 0 ; }