ホーム » スタッフ » 斉藤徹 » 講義録 (ページ 2)

講義録」カテゴリーアーカイブ

2025年7月
 12345
6789101112
13141516171819
20212223242526
2728293031  

検索・リンク

リスト処理のレポート課題(前期期末)

プログラムは書いて・動かして・間違って・直す が重要ということで、以下に前期期末試験前までに取り組むレポート課題をしめす。

レポート課題(プログラム例)

Java を用いて、後に示すデータ処理をするためのリスト構造を定義し、与えられたデータを追加していく処理を作成せよ。

課題の説明用に、複素数のリスト構造を定義し、指定した絶対値以下の複素数を抜き出す関数をつくった例を示す。

import java.util.* ;

class ComplexListNode {
   double          re ;
   double          im ;
   ComplexListNode next ;
   ComplexListNode( double r , double i , ComplexListNode n ) {
       this.re = r ;
       this.im = i ;
       this.next = n ;
   }
} ;

public class Main {
    // 先頭からデータを挿入する方式
    static ComplexListNode top = null ;
    // 全リストを表示する処理
    static void print( ComplexListNode p ) {
        for( ; p != null ; p = p.next ) {
            System.out.println( "(" + p.re + ")+j(" + p.im + ")" ) ;
        }
    }
    // top に要素を追加する処理(先頭に入れる)
    static void add( double r , double i ) {
        top = new ComplexListNode( r , i , top ) ;
    }
    // 特定のデータを対象にした処理の例
    static ComplexListNode filter_lessthan( ComplexListNode p , double v_abs ) {
        ComplexListNode ans = null ;
        for( ; p != null ; p = p.next ) {
            if ( Math.sqrt( p.re * p.re + p.im * p.im ) <= v_abs )
                ans = new ComplexListNode( p.re , p.im , ans ) ;
        }
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        add( 1.0 , 2.0 ) ;
        add( -1.0 , -1.0 ) ;
        add( 2.0 , -1.0 ) ;
        add( 1.0 , 0 ) ;
        print( top ) ;
        
        ComplexListNode less_than_2 = filter_lessthan( top , 2 ) ;
        System.out.println( "less than 2" ) ;
        print( less_than_2 ) ;
    }
}

((( 実行結果の例 )))
(1.0)+j(0.0)
(2.0)+j(-1.0)
(-1.0)+j(-1.0)
(1.0)+j(2.0)
less than 2
(-1.0)+j(-1.0)
(1.0)+j(0.0)

レポート内容

上記のプログラムをまねて、以下のレポート課題を作成すること。テーマは ((出席番号-1)%3+1) を選択すること。

  1. 年号のデータが、年号の名称と年号の始まりの年月日がYYYYMMDD形式で
    • “Meiji”,18681023
    • “Taisho”,19120730
    • “Showa”,19261225
    • “Heisei”,19890108
    • “Reiwa”,20190501

    の様に与えられる。このデータ構造を覚えるリスト構造を作成せよ。また ListNode のデータで、西暦の日付のリストが seireki_list = new ListNode( 19650207, new ListNode( 20030903 , null ) ) ; のように与えられたら、そのデータを和暦で表示するプログラムを作成せよ。 (参考2023年前期期末)

  2. 市町村名,月,日,最高気温,最低気温のデータが、
    • “fukui”,8月,4日,27.6℃,22.3℃
    • “fukui”,8月,5日,31.5℃,23.3℃
    • “fukui”,8月,7日,34.7℃,25.9℃
    • “obama”,8月,6日,34.2℃,23.9℃

    の様に与えられる。このデータ構造で覚えるリスト構造を作成せよ。また、この中から真夏日(最高気温が30℃以上)でかつ熱帯夜(最低気温が25℃以上)の日のリストを抽出し表示するプログラムを作成せよ。(参考2022年前期期末)

  3. ホスト名と、IPアドレス(0~255までの8bitの値✕4個で与えるものとする)のデータ構造で、
    • “www.fukui-nct.ac.jp”,104,215,54,205
    • “perrine.tsaitoh.net”,192,168,11,2
    • “dns.fukui-nct.ac.jp”,10,10,21,51
    • “dns.google.com”,8,8,8,8

    の様に与えられる。このデータ構造をリスト構造で覚えるプログラムを作成せよ。また、この中からプライベートアドレスのリストを抽出し表示するプログラムを作成せよ。プライベートアドレスは 10.x.x.x, 172.16~31.x.x,192.168.x.x とする。(参考2019年前期期末)

プログラムを作るにあたり、リスト構造には add( 与えられたデータ… ) のように呼び出してリストに追加すること。この時、生成されるリストが、登録の逆順になるか(先頭に挿入)、登録順(末尾に追加)になるかは、自分の理解度に応じて選択すること。抽出する処理を書く場合も登録順序どおりにするかは自分の理解度に応じて選べばよい。

また、理解度に自信がある人は、add() などの処理を「オブジェクト指向」のように記述する方法を検討すること。
あくまで、リスト構造の理解を目的とするため、ArrayList<型> , LinkedList<型> のようなクラスは使わないこと。(ただし考察にて記述性の対比の対象として使うのはOK。複素数の場合の LinkedList を使った例を以下に示す。)

import java.util.* ;
import java.util.stream.Collectors ;

class Complex {
   double re ;
   double im ;
   Complex( double r , double i ) {
       this.re = r ;
       this.im = i ;
   }
   public double abs() {
       return Math.sqrt( re * re + im * im ) ;
   }
   @Override
   public String toString() {
       return "(" + re + ")+j(" + im + ")" ;
   }
} ;

public class Main {
    public static LinkedList<Complex> top = new LinkedList<Complex>() ;

    // 絶対値が指定した値以下の要素だけを集める関数
    public static LinkedList<Complex> filter_lessthan(
                            LinkedList<Complex> list , double v_abs ) {
        var ans = new LinkedList() ;
        for( var c : list ) {
            if ( Math.sqrt( c.re * c.re + c.im * c.im ) <= v_abs )
                ans.add( c ) ;
        }
        return ans ;
    }
    public static void main( String[] args ) throws Exception {
        // リストに複素数を追加
        top.add( new Complex(  1.0 ,  2.0 ) ) ;
        top.add( new Complex( -1.0 , -1.0 ) ) ;
        top.add( new Complex(  2.0 , -1.0 ) ) ;
        top.add( new Complex(  1.0 ,  0   ) ) ;
        
        for( var c : top ) {
            System.out.println( c ) ;
        }
        System.out.println( "---" ) ;
        // static な関数でフィルタリング
        for( var c : filter_lessthan( top , 2.0 ) ) {
            System.out.println( c ) ;
        }
        /* Stream API を使ってフィルタリング
        for( var c : top.stream()                    // LinkedList を Stream に変換
                     .filter( c->c.abs() < 2.0 )     // filter条件をラムダ式で渡す
                     .collect( Collectors.toList() ) // Collectorsで結果を集める
            ) {
            System.out.println( c ) ;
        }
        */
    }
}

リダイレクトとパイプ

Linux/unixを使う上で、キーボードでコマンドを入力しているが、こういうコマンドの管理を行うプログラムshell と呼ぶ。shell には、色々なものがある(sh, csh, bash, zsh)が、広く使われている bash( born-again shell )について説明する。最初に、コマンドの入出力を組み合わせるために重要となるリダイレクトとパイプについて説明する。

標準入出力とリダイレクト

出力リダイレクト

C言語のプログラミングで、プログラムの実行結果をレポートに張り付ける時はどのように行っているだろうか?多くの人は、実行画面を PrintScreen でキャプチャした画像を張り付けているかもしれない。しかし、数十行にわたる結果であれば何度もキャプチャが必要となる。
そこで、今日の最初はリダイレクト機能について説明する。

“gcc ファイル.c” は、C言語のプログラムをコンパイルし、a.out という実行ファイルを生成する。”./a.out” にてプログラムを実行する。実行する命令に、“> ファイル名” と書くと、通常の出力画面(標準出力) をファイル名に記録してくれる。これを出力リダイレクトと呼ぶ。また、“>> ファイル名” と書くと、既存ファイルの後ろに追記してくれる。

guest00@nitfcei:~$ cat helloworld.c
#include <stdio.h>
int main() {
    printf( "Hello World\n" ) ;
    return 0 ;
}

guest00@nitfcei:~$ gcc helloworld.c
guest00@nitfcei:~$ ./a.out
Hello World

guest00@nitfcei:~$ ./a.out > helloworld.txt

guest00@nitfcei:~$ cat helloworld.txt
Hello World

guest00@nitfcei:~$ ./a.out >> helloworld.txt

guest00@nitfcei:~$ cat helloworld.txt 
Hello World
Hello World 

入力リダイレクト

次に、1行に名前と3教科の点数が書いてある複数行に渡るデータの各人の平均点を求めるプログラムを考える。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-each-low.c .
guest00@nitfcei:~$ cat avg-each-low.c
#include <stdio.h>
// ((input))           ((output))
// saitoh  43  54 82   saitoh 59.67
// tomoko  89 100 32   tomoko 73.67
// mitsuki 79  68 93   mitsuki 80.00
int main() {
   char name[ 100 ] ;
   int point[ 3 ] ;
   while( scanf( "%s%d%d%d" ,
                 name , &point[0] , &point[1] , &point[2] ) == 4 ) {
      double sum = 0.0 ;
      for( int i = 0 ; i < 3 ; i++ )
         sum += point[i] ;
      printf( "%s %6.2f\n" , name , sum / 3.0 ) ;
   }
   return 0 ;
}

guest00@nitfcei:~$ gcc avg-each-low.c
guest00@nitfcei:~$ ./a.out
saitoh 43  54 82    入力
saitoh 59.67        出力
tomoko 89 100 32    入力
tomoko 73.67        出力
^D             ← Ctrl-D を押すとファイル入力を終了

しかし、プログラムの書き方を間違えてプログラムを修正していると、動作確認のたびに何度も同じデータを入力するかもしれないが、面倒ではないだろうか?

プログラムを実行する時に、“< ファイル名” をつけると、通常はキーボードから入力する所を、ファイルからの入力に切り替えて実行することができる。このようなscanf()を使う時のようなプログラムの入力を標準入力といい、それをファイルに切り替えることを入力リダイレクトと呼ぶ。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/name-point3.txt .

guest00@nitfcei:~$ cat name-point3.txt
saitoh  43  54 82
tomoko  89 100 32
mitsuki 79  68 93 

guest00@nitfcei:~$ ./a.out < name-point3.txt
saitoh  59.67
tomoko  73.67
mitsuki 80.00

この入力リダイレクトと出力リダイレクトを合わせて使うこともできる。

guest00@nitfcei:~$ ./a.out < name-point3.txt > name-avg.txt

guest00@nitfcei:~$ cat name-avg.txt
saitoh  59.67
tomoko  73.67
mitsuki 80.00

パイプ

先の名前と3教科のプログラムの結果から、全員の平均点をも計算したい場合、どのようなプログラムを作るだろうか?C言語だけの知識なら、各人の行のデータを計算するループの中に、全員の合計と人数を求めるプログラムを書いて、最後に平均点を出力するだろう。

一方で、複数人の名前と平均点のデータから平均点を求めるプログラムを書いて、前述のプログラムの実行結果を使う人もいるだろう。

以下の例では、“gcc -o avg-each-row avg-each-row.c” で、avg-each-row という実行ファイル、“gcc -o avg-all avg-all.c” で、avg-all という実行ファイルを生成し、avg-each-row で入力リダイレクト・出力リダイレクトを使って、name-avg.txt を作り、avg-all を入力リダイレクトで、最終結果を表示している。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-all.c .
guest00@nitfcei:~$ cat avg-all.c
#include <stdio.h>
// ((input))      ((output))
// saitoh  59.67  73.11
// tomoko  73.67
// mitsuki 80.00
int main() {
   char name[ 100 ] ;
   double point ;
   double sum = 0 ;
   int count = 0 ;
   while( scanf( "%s%lf" , name , &point ) == 2 ) {
      sum += point ;
      count++ ;
   }
   printf( "%6.2f\n" , sum / (double)count ) ;
   return 0 ;
}

guest00@nitfcei:~$ gcc -o avg-each-low avg-each-low.c
guest00@nitfcei:~$ gcc -o avg-all avg-all.c

guest00@nitfcei:~$ ./avg-each-low < name-point3.txt > name-avg.txt

guest00@nitfcei:~$ ./avg-all < name-avg.txt
71.11

しかし、いちいち入出力の結果を name-avg.txt を作るのは面倒である。であれば、以下の様なイメージで処理をすれば答えが求まる。

name-point3.txt(avg-each-row)name-avg.txt(avg-all)結果

これは、パイプ機能を使って以下の様に動かすことができる。

guest00@nitfcei:~$ ./avg-each-low < name-point3.txt | ./avg-all
71.11

guest00@nitfcei:~$ cat name-point3.txt | ./avg-each-low | ./avg-all
71.11

プログラムを実行する時に、“A | B” ように書くと、プログラムA の標準出力結果を、プログラムB の標準入力に接続させて、2つのプログラムを実行できる。このような機能を、パイプと呼ぶ。上記例の2つめ “cat… | ./avg-each-low | ./avg-all” では3つのプログラムをパイプでつないでいる。


リダイレクトのまとめ

 

入力リダイレクト(標準入力) 実行コマンド < 入力ファイル
出力リダイレクト(標準出力) 実行コマンド > 出力ファイル
 出力リダイレクト(標準出力の追記) 実行コマンド >> 出力ファイル
 標準エラー出力のリダイレクト 実行コマンド 2> 出力ファイル
パイプ
コマンドAの標準出力をコマンドBの標準入力に接続
コマンドA | コマンドB

標準エラー出力,/dev/null, /dev/zero デバイス

パイプやリダイレクトを使っていると、出力をファイルに保存する場合、途中で異常を伝える目的で出力メッセージを出力するものが見逃すかもしれない。こういった際に、計算結果などを出力する標準出力(stdout)とは別に標準エラー出力(stderr)がある。ファイルを使う際には、デバイスを区別するためのデバイス番号(ファイルディスクリプタ)を使う。この際に、標準入力(stdin) = 0, 標準出力(stdout) = 1, 標準エラー出力(stderr) = 2 という番号を使うことになっている。

#include <stdio.h>
int main() {
   int x , y ;
   scanf( "%d%d" , &x , &y ) ;
   if ( y == 0 )
      fprintf( stderr , "zero divide\n" ) ;
   else
      printf( "%f\n" , (double)x / (double)y ) ;
}

Unix のシステムでは、特殊なデバイスとして、/dev/null, /dev/zero というのがある。

/dev/null は、入力リダイレクトに使うと ファイルサイズ 0 byte のデータが得られるし、出力リダイレクトに使うと 書き込んだデータは捨てられる。 /dev/zero は、入力リダイレクトに使うと、’\0′ のデータを延々と取り出すことができ、ファイルをゼロで埋めるなどの用途で使う。

/dev/null の使い方の例としては、例えば標準エラー出力が不要なときは、コマンドラインで以下のようにすれば、標準エラー出力(デバイス番号2番)の内容を捨てることができる。

$ command 2> /dev/null

C言語のコンパイルまとめ

 

C言語のコンパイル(実行ファイルはa.out) gcc ソースファイル
 実行ファイル名を指定してコンパイル gcc -o 実行ファイル ソースファイル

 

理解度確認

Windows における PRN デバイス, AUX デバイス

/dev/null といった特殊デバイスの一例として、昔の Windows では PRN デバイス、AUX デバイスというのがあった。

C:< command > PRN

昔の文字印刷しかできないプリンタが普通だったころは、PRN という特殊デバイスがあって、このデバイスにリダイレクトをすれば、出力をプリンタに出力することができた。同じように AUX というデバイスは、通信ポートにつながっていて ” command > AUX ” と入力すれば、通信先にデータを送ることができた。最近のプリンタや通信デバイスはもっと複雑になっているためにこういった機能は使えなくなっているが、このデバイス名の名残りで、Windows では PRN とか AUX という名前のファイルを作ることはできない。

UMLの概要

巨大なプロジェクトでプログラムを作成する場合、設計の考え方を図で示すことは、直感的な理解となるため重要であり、このために UML がある。以下にその考え方と記述方法を説明していく。

プログラムの考え方の説明

今まで、プログラムを人に説明する場合には、初心者向けの方式としてフローチャートを使うのが一般的であろう。しかし、フローチャートは四角の枠の中に説明を書ききれないことがあり、使い勝手が悪い。他には、PAD と呼ばれる記述法もある。この方法は、一連の処理を表す縦棒の横に、処理を表す旗を並べるようなイメージで記載する。

しかし、これらの記法は、手順を記載するためのものであり、オブジェクト指向ではデータ構造の理解も重要でありデータ構造を説明するための図が必要となってきた。

個人的な経験では、企業にてプログラムを作っていた頃(1990年頃)、UML などの考え方は普及していなかった。処理を説明するためのフローチャートでも、通信関係のプログラムでは、送信側と受信側の相互関係を説明する場合、フローチャートでは相互のタイミングなどの説明は困難であった。また、通信では、リトライ・タイムアウトといった状態も発生するが、その場合だと状態遷移図なども併記する必要があり、フローチャートの限界を感じていた。

また、データ構造については、オブジェクト指向も普及前であればデータ要素の一覧表が中心であった。プログラム書式(コーディングスタイル)などの統一もされていないので、同じチーム内で誤解などを解消するための意思統一が重要であった。

ドキュメントを残す技術

学生のみなさんは、プログラムの説明の文書はどのように残しているだろうか?

私が仕事をしていた頃は、プログラムと別にドキュメントをワープロで残そうとすると、プログラム変更に合わせて編集することが難しく、プログラムとドキュメントの乖離が発生する。このため、プログラムの中にコメントの形で残すことが重要であった。特にデータ構造の説明は、ヘッダファイルの中に大量のコメントで残すことが多かった。

企業であれば、関数宣言の前には、コーディングスタイルとして決められた書式のコメントで、引数や返り値などを明記することが求められるのが一般的。

文芸的プログラミング TeX

TeX(LaTeX)を改発した Knuth は、文芸的プログラミングとして、プログラム中にドキュメントを併記するための WEB(注記:Internetの意味のWebではない) を同時に開発している。このシステムでは、プログラムとドキュメントを併記したソースプログラムから、ドキュメントを取り出すプログラムと、ソースコードを取り出すプログラムがあり、情報の一体性を高めている。

手っ取り早くドキュメント Markdown

最近では、プログラムのエディタで Markdown という、マークアップ言語でドキュメントを残す場合も多いだろう。これであれば、プレーンテキストで書いたドキュメントを、HTMLLaTeXといったWeb形式・論文形式といったドキュメントに変換も容易である。

このような方法で、ドキュメントとプログラムの乖離を防ぐことが重要となる。

github では、ドキュメントとして README.md といったファイル名で Markdown によるドキュメントを残すのが一般的。


UML記法が生まれるまで

巨大なプロジェクトでプログラムを作る場合、対象となるシステムを表現する場合、オブジェクト指向分析(Object Oriented Analysis)オブジェクト指向設計(Object Oriented Design)とよばれるソフトウェア開発方法が重要となる。(総称して OOAD – Object Oriented Analysis and Design)

これらの開発方法をとる場合、(1)自分自身で考えを整理したり(2)グループで設計を検討したり(3)ユーザに仕様を説明したりといった作業が行われる。この時に、自分自身あるいはチームメンバーあるいはクライアントに直感的に図を用いて説明する。この時の図の書き方を標準化したものが UML であり、(a)処理の流れを説明するための振る舞い図(フローチャートやPAD)と、(b)データ構造を説明するための構造図を用いる。

UMLは、ランボーによるOMT(Object Modeling Technique どちらかというとOOA(Object Oriented Anarisys)中心)と、 ヤコブソンによるオブジェクト指向ソフトウェア工学(OOSE/Object Oriented Software Engineering)を元に1990年頃に 発生し、ブーチのBooch法(どちらかというとOOD(Object Oriented Design)中心)の考えをまとめ、 UML(Unified Modeling Language)としてでてきた。

UMLでよく使われる図を列記すると、以下の物が挙げられる。

  • 構造図
    • クラス図
    • コンポーネント図
    • 配置図
    • オブジェクト図
    • パッケージ図
  • 振る舞い図
    • アクティビティ図
    • ユースケース図
    • ステートチャート図(状態遷移図)
    • 相互作用図
    • シーケンス図
    • コミュニケーション図(コラボレーション図)

その他の関連雑談のためのリンク

 

Webプログラミングとセキュリティ

ここまでの授業では、Webを使った情報公開で使われる、HTML , JavaScirpt , PHP , SQL などの解説を行ってきたが、これらを組み合わせたシステムを構築する場合には、セキュリティについても配慮が必要である。

今回は、初心者向けの情報セキュリティの講習で使われるCTFという競技の練習問題をつかって、ここまで説明してきた Web の仕組みを使ったセキュリティの問題について解説を行う。

派生や集約と多重継承

派生や継承について、一通りの説明が終わったので、データ構造(クラスの構造)の定義の方法にも様々な考え方があり、どのように実装すべきかの問題点を考えるための説明を行う。その中で特殊な継承の問題についても解説する。

動物・鳥類・哺乳類クラス

派生継承を使うと、親子関係のあるデータ構造をうまく表現できることを、ここまでの授業で示してきた。

しかしながら、以下に述べるような例では、問題が発生する。

// 動物クラス
class Animal {
private:
  char name[ 10 ] ;
public:
  Animal( const char s[] ) {
    strcpy( name , s ) ;
  }
  const char* get_name() const { return name ; }
  virtual void move() = 0 ;
  virtual void birth() = 0 ;
} ;

// 鳥類クラス
class Bird : public Animal {
public:
  Bird( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s fry.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay egg.\n" , get_name() ) ;
  }
} ;

// 哺乳類クラス
class Mammal : public Animal {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s walk.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay baby.\n" , get_name() ) ;
  }
} ;

int main() {
  Bird chiken( "piyo" ) ;
  chiken.move() ;
  chiken.birth() ;
  Mammal cat( "tama" ) ;
  cat.move() ;
  cat.birth() ;
  return 0 ;
}

ここで、カモノハシを作るのであれば、どうすれば良いだろうか?

鳥類・哺乳類とは別にカモノハシを作る(いちばん無難な方法)

class SeaBream : public Animal {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s walk.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay egg.\n" , get_name() ) ;
  }
} ;

この例では、簡単な処理だが、move() の中身が複雑であれば、改めて move() を宣言するのではなく、継承するだけの書き方ができないだろうか?

多重継承を使う方法(ダイヤモンド型継承が発生する)

C++ には、複数のクラスから、派生する多重継承という機能がある。であれば、鳥類と哺乳類から進化したのだから、以下のように書きたい。

// 多重継承 鳥(Bird)と哺乳類(Mammal) から SeaBeam を作る
class SeaBream : public Bird , public Mammal {
   //
} ;

しかし、カモノハシに move() を呼び出すと、鳥類の move() と哺乳類の move() のどちらを動かすか曖昧になる。

また「派生」は、基底クラスと派生クラスの両方のデータを持つデータ構造を作る。このため、単純に多重継承を行うと、カモノハシのクラスでは、派生クラスは親クラスのデータ領域と、派生クラスのデータ領域を持つため、鳥類の name[] と、哺乳類の name[] を二つ持つことになる。多重継承による”ダイヤモンド型継承”の問題

足と羽のクラスを作る場合(本来は多重継承で実装すべきではない)

以下に、足と羽のクラスを作ったうえで、多重継承を行うプログラム例を示す。

しかし、この例では、相変わらずカモノハシのクラスを多重継承で実装すると、ダイヤモンド型継承の問題が残る。

class Animal {
private:
  char name[ 10 ] ;
public:
  Animal( const char s[] ) {
    strcpy( name , s ) ;
  }
  const char* get_name() const { return name ; }
  virtual void move() = 0 ;
} ;
// 羽
class Wing {
public:
   const char* move_method() { return "fly" ; }
} ;
// 
class Leg {
public:
   const char* move_method() { return "walk" ; }
} ;
class Bird : public Animal , public Wind {
public:
  Bird( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s %s.\n" , get_name() , move_method() ) ;
  }
} ;
class Mammal : public Animal , public Leg {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s %s.\n" , get_name() , move_method() ) ;
  }
} ;

継承を使うべきか、部品として持つべきか

ただし、ここで述べた方式は、UML による設計の際に改めて説明を行うが、is-a , has-a の関係でいうなら、

  • Bird is a Animal. – 鳥は動物である。
    • “Bird has a Animal” はおかしい。
    • 鳥は、動物から派生させるのが正しい。
  • Bird has a Wing. – 鳥は羽をもつ。
    • “Bird is a Wing” はおかしい。
    • 鳥は、羽を部品として持つべき。

であることから、Wing は 継承で実装するのではなく、集約もしくはコンポジションのような部品として実装すべきである。

このカモノハシ問題をどうしても多重継承で実装したいのなら、C++では、以下のような方法で、ダイヤモンド型の継承問題を解決できる。

class Animal {
private:
   char name[ 10 ] ;
public:
   Animal( const char s[] ) {
      strcpy( name , s ) ;
   }
   const char* get_name() const { return name ; }
   virtual void move() = 0 ;
   virtual void birth() = 0 ;
} ;

// 鳥類クラス
class Bird : public virtual Animal {
public:
   Bird( const char s[] ) : Animal( s ) {}
   virtual void move() {
      printf( "%s fry.\n" , get_name() ) ;
   }
   virtual void birth() {
      printf( "%s lay egg.\n" , get_name() ) ;
   }
} ;

// 哺乳類クラス
class Mammal : public virtual Animal {
public:
   Mammal( const char s[] ) : Animal( s ) {}
   virtual void move() {
      printf( "%s walk.\n" , get_name() ) ;
   }
   virtual void birth() {
      printf( "%s lay baby.\n" , get_name() ) ;
   }
} ;

class SeaBream : public virtual Bird , virtual Mammal {
public:
   SeaBream( const char s[] ) : Animal( s ) {}
   void move() {
      Mammal::move() ;
   }
   void birth() {
      Bird::birth() ;
   }
} ;

ただし、多重継承は親クラスの情報と、メソッドを継承する。この場合、通常だと name[] を二つ持つことになるので、問題が発生する。そこで、親クラスの継承に virtual を指定することで、ダイヤモンド型継承の 2つの属性をうまく処理してくれるようになる。

しかし、多重継承は処理の曖昧さや効率の悪さもあることから、採用されていないオブジェクト指向言語も多い。特に Java は、多重継承を使えない。その代わりに interface という機能が使えるようになっている。

多重継承を使える CLOS や Python では、適用するメソッドやインスタンス変数の曖昧さについては親クラスへの優先度を明確にできる機能がある。曖昧さの問題を避けるのであればクラス限定子”::”を使うべきである。

Javaでリスト構造

テスト前のリスト導入の復習

前回のリスト構造の導入では、配列のデータに次のデータの入っている番号を添えることで途中にデータを挿入できるデータ構造の説明をした。

また、それをクラスを用いたプログラムを示した。

ヒープメモリとは

Javaでは、すべてのオブジェクトはヒープメモリに保存する。

ヒープメモリとは、一時的なデータの保管場所であり、new 演算子でデータを保存する場所を確保する。

Javaでは、分かり難いのでC言語で説明を行う。malloc() は、指定されたバイト数のメモリをヒープ領域に確保する命令。malloc() に失敗すると、NULL が返ってくる。また、使い終わったら malloc() の領域は free() 命令で返却が必要となる。

((( 配列をヒープメモリで確保 )))
#include <stdio.h>
#include <stdlib.h>

int main() {
   int a[ 5 ] = { 1 , 2 , 3 , 4 , 5 } ;
   int* b ;
   if ( (b = (int*)malloc( sizeof( int ) * 5 )) != NULL ) {
      for( int i = 0 ; i < 5 ; i++ )
         b[ i ] = i + 1 ;
      free( b ) ;    // malloc() で確保したメモリ領域は返却が必要
   }
   return 0 ;
}

((( オブジェクトをヒープメモリに確保 )))
struct Complex {
   double re ;
   double im ;
} ;
int main() {
   struct Complex* c ;
   if ( (c = (struct Complex*)malloc( sizeof( struct Complex ) )) != NULL ) {
      c->re = 1.23 ;
      c->im = 2.34 ;
      free( c ) ;
      return 0 ;
   } else {
      printf( "No heap memory\n" ) ;
      return 1 ;
   }
}

((( 上記C言語をJavaで書くと )))
class Complex {
   double re ;
   double im ;
   Complex( double r , double i ) {
      this.re = r ;
      this.im = i ;
   }
}

public class Main {
   public static void main( String[] args ) {
      try {
         Complex c = new Complex( 1.23 , 2.34 ) ;
                    // Javaではヒープメモリが確保に失敗したら、
                    // OutOfMemoryErrorの例外が発生する。

         c = null ; // free()はJavaでは不要
                    // nullを代入してもいい。
      } catch( OutOfMemoryError e ) {
         System.out.println( "No heap memory" ) ;
         System.exit( 1 ) ;
      }
   }
}

リスト構造 ListNode

前述の data と next で次々とデータを続けて保存する方法を、next の部分を次のデータへの参照を用いるように、リスト構造(連結リスト)を定義する。

import java.util.*;

class ListNode {
    int      data ;   // データ部分
    ListNode next ;   // 次のデータへの参照
    // コンストラクタ
    ListNode( int d , ListNode nx ) {
        this.data = d ;
        this.next = nx ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
        // 途中にデータを入れる
        top.next = new ListNode( 15 , top.next ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

リスト操作

リスト構造に慣れるために簡単な練習をしてみよう。リスト構造のデータに対するメソッドをいくつか作ってみよう。print() や sum() を参考に、データ数を求める count() , 最大値を求める max() , データを検索する find() を完成させてみよう。

class ListNode {
    (略)
} ;

public class Main {
    static void print( ListNode p ) {   // リストを表示
        for( ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }

    static int sum( ListNode p ) {      // リストの合計を求める
        int s = 0 ;
        for( ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }

    static int count( ListNode p ) {    // データ件数を数える

    }

    static int max( ListNode p ) {      // データの最大値を求める

    }

    static boolean find( ListNode p , int key ) { // データ列の中から特定のデータを探す
                                                  //   見つかったら true , 見つからなければ false
    }
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        print( top ) ;
        System.out.println( "合計:" + sum( top ) ) ;
        System.out.println( "件数:" + count( top ) ) ;
        System.out.println( "最大:" + max( top ) ) ;
        System.out.println( "検索:" + (find( top , 22 )
                                       ? "みつかった" : "みつからない" ) ) ;
    }
}

オブジェクト指向っぽく書いてみる

前述のプログラムでは、print( top ) のように使う static な関数としてプログラムを書いていた。しかし、オブジェクト指向であれば、オブジェクトに対するメソッドだと top.print() のように書きたい。この場合だと、以下のように書くかもしれない。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
    int sum() {    // リストの合計を求める
        int  s = 0 ;
        for( ListNode p = this ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = null ;
        list_empty.print() ;  // 実行時エラー java.lang.NullPointerException ぬるぽ!
    }
}

しかし、データ件数 0件 に対してメソッドを呼び出せない。

ListNode と List というクラスで書いてみる

ひとつの方法として、リストの先頭だけのデータ構造を宣言する方法もある。

class ListNode {
    int   data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

class List {
    ListNode top ;
    List( ListNode p ) {
        this.top = p ;
    }
    void print() {
        for( ListNode p = top ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        List list = new List( new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ) ;
        list.print() ;
        
        List list_empty = new List( null ) ;
        list_empty.print() ;
    }
}

しかし、List と ListNode の2つのデータの型でプログラムを書くのは面倒くさい。

授業ではシンプルに説明したいので、今後はこの方法は極力避けていく。

先頭にダミーデータを入れる

複数のクラス宣言するぐらいなら、リストデータの先頭は必ずダミーにしておく方法もあるだろう。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this.next ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode list = new ListNode( -1 , null ) ;
        list.next = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = new ListNode( -1 , null ) ;
        list_empty.print() ;
    }
}

以降、必要に応じて、先頭にダミーを入れる手法も取り混ぜながらプログラムを書くこととする。

入力データをリストに追加

入力しながらデータをリストに格納する処理を考えてみる。

リストでデータを追加保存するのであれば、一番簡単なプログラムは、以下のように先頭にデータを入れていく方法だろう。

class ListNode {
    (略)
    void print() {
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data ) ;
        System.out.println() ;
    }
} ;
    
public class Main {
    public static void main(String[] args) throws Exception {
        int[] inputs = { 11 , 22 , 33 } ;
        ListNode top = null ;

        for( int datum : inputs )
            top = new ListNode( datum , top ) ;
        top.print() ;
    }
}

でもこの方法だと、先頭にデータを入れていくため、保存されたデータは逆順になってしまう。

末尾にデータを入れる

逆順になるのを避けるのであれば、データを末尾に追加する方法があるだろう。ただし初期状態でデータが0件だと処理が書きづらいので、先頭にダミーを入れておく方法で書いてみる。

public class Main {
    public static void main(String[] args) throws Exception {
        int[] test_data = { 11 , 22 , 33 } ;

        ListNode top = new ListNode( -1 , null ) ; // ダミー
        ListNode tail = top ;
        for( int x : test_data ) {
            tail.next = new ListNode( x , null ) ;
            tail = tail.next ;
        }
        top.print() ; // -1   11  22  33
    }                 // ダミー
}

バックエンドと所有権の設定

前回の講義でファイルのパーミッション(読み書き権限)について確認したが、バックエンドプログラミングで必要となるファイルの所有権の設定を通して、演習を行う。これに合わせ、サーバ上のファイルの編集作業なども体験する。

サーバ上のファイルの編集

以前のバックエンドのプログラムの演習ではサーバの設定などの体験もできていないため、フロントエンドの処理でサーバ上に送られたデータは、最終的な書き込み処理は行っていなかった。今回は、サーバ上でデータをサーバ上のバックエンドプログラムの PHP ファイルを修正し、データが書き込めるようにプログラムの修正を行う。

サーバ上のファイルを編集するには、色々な方法がある。

サーバ上のエディタで直接編集
unix のシステムで直接ファイルを編集するのであれば、vimemacs を利用するのが一般的であろう。これらのエディタはリモートサーバにsshなどでログインしている時は、端末ソフトの文字表示機能だけで動作し、GUI 機能を使わない。vim や emacs は、古くから使われ、Windows で動く vim emacs もある。
システム管理者権限で編集する必要があるファイルの場合は、以下に紹介するような方法は煩雑であり、サーバ上で直接編集も知っておくべき。
プログラムをローカルPCで編集しアップロード(今回はコレ)
前回の演習では、リモートサーバに接続する際には ssh コマンドを用いたが、ssh にはファイル転送のための scp コマンドも用意されている。
scp コマンドは、通常の cp 命令 ( cp コピー元 コピー先 ) を ssh のプロトコルでリモートする機能を拡張したものであり、リモートのコンピュータをコピー元やコピー先として指定する場合は、 ユーザ名@リモートホスト:ファイル場所 と記載する。
# remotehostのファイル helloworld.c をローカルホストのカレントディレクトリ.にダウンロード
C:\Users\tsaitoh> scp tsaitoh@remotehost:helloworld.c .  
# ローカルホストの foobar.php を remotehostの/home/tsaitoh/public_html/ フォルダにアップロード
C:\Users\tsaitoh> scp foobar.php tsaitoh@remotehost:/home/tsaitoh/public_html/
VSCode でリモートファイルを編集
最近のエディタでは、前述のローカルPCで編集しアップロードといった作業を、自動的に行う機能が利用できる。emacs の tramp-mode や、VS Code の Remote ssh プラグインなどがこれにあたる。利用する演習用のサーバが高機能であれば、vscode + remote-ssh が一番便利と思われるが、remote-ssh はサーバで大きな node.js を動かすため、サーバ負担が大きいので今回はこの方式は使わない。

Webアプリと所有権の問題

PHPで書かれたバックエンドでのプログラムにおいて、Webサーバは www-data(uid),www-data(groupid) というユーザ権限で動作している。そして、webサーバと連動して動く PHP のプログラムも www-data の権限で動作する。一方で、通常ユーザが開発しているプログラムが置かれる $HOME/public_html フォルダは、何もしなければそのユーザのものである。このため、PHP のプログラムがユーザのフォルダ内にアクセスする際には、www-data に対してのアクセス権限が必要となる。

Windows ユーザが Web プログラミングの体験をする際には、XAMPP などのパッケージを利用することも多いだろう。しかし XAMPP などは、中身のWebサーバ(apache), DBサーバ(MySQL)などすべてがインストールしたユーザ権限で動いたりするため、所有権の設定の知識が無くても簡単に利用することができる(あるいはユーザ自身が管理者権限を持っているため設定が無くてもアクセス権問題が発生しない)。このため Linux 環境での Web プログラミングに移行する際に、ユーザ権限の設定を忘れ、プログラムが動かず戸惑うことも多い。

今回の演習では、管理者権限で動いている自分のパソコンの中のXAMPPを使わず、複数のユーザで動いている演習用サーバを用いる。

データベースサーバの場合

また、データの保存でデータベースを利用する場合、Oracle や MySQL といった、ネットワーク型のデータベースでは、Webサーバとは別にデータベースのサーバプログラムが動作している。ネットワーク型のデータベースでは、様々なユーザ・アプリケーションがデータの読み書きを行うため、SQL の create user 命令でユーザを割り当てgrant 命令でユーザのデータへのアクセス権限を指定する。

Webアプリは、データベースのサーバに接続する際には、ユーザ名とパスワードが必要となる。

簡易データベースSQLiteの場合

簡単なデータベースシステムの SQLite は、PHP の SQLite プラグインを経由してディレクトリ内のファイルにアクセスする。このため、データベースファイルやデータベースのファイルが置かれているフォルダへのアクセス権限が必要となる。今回の演習用サーバでは、ゲストアカウントは www-data グループに所属しているので、データベースファイルやフォルダに対し、www-data グループへの書き込み権限を与える。

chown , chgrp , chmod コマンド

ファイル所有者やグループを変更する場合には、chown (change owner) 命令や chgrp (change group) 命令を使用する。ただし、chown はシステム管理者権限(root)でなければ使えない。chgrp も自分が所有してかつ変更後のグループに加入していなければ使えない。

chown ユーザID ファイル
 例: $ chown tsaitoh helloworld.c
chgrp グループID ファイル
 例: $ chgrp www-data public_html

ファイルに対するパーミッション(利用権限)を変更するには、chmod (change mode) 命令を用いる。
chmod 命令では、読み書きの権限は2進数3桁の組み合わせで扱う。読書可 “rw-“ = 6, 読出可 = “r–“ = 4 , ディレクトリの読み書き可 “rwx” = 7 など。ファイルには、所有者,グループ,その他の3つに分けて、読み書きの権限を割り当てる。2進数3桁=8進数1桁で表現できることから、一般的なファイルの “rw-,r–,r–“ は、8進数3桁 で 644 , ディレクトリなら “rwx,r-x,r-x”755 といった値で表現する。

chmod 権限 ファイル
 例: $ chmod 664 helloworld.c
       $ ls -al
       -rw-rw-r-- tsaitoh ei        123 5月20 12:34 helloworld.c
       $ chmod 775 public_html
       drwxrwxr-x tsaitoh www-data 4096 5月20 12:34 public_html
  8進数表現を使わない場合
       $ chmod u+w,g+w helloworld.c
               ユーザ(u)への書き込み権限,グループ(g)への書き込み権限の追加(+)
       $ chmod g-w,o-rw helloworld.c
               グループ(g)書き込み権限を消す、その他(o)の読み書き権限を消す(-)
       $ chmod u=rw,g=r,o=r helloworld.c
               ユーザ(u)への読み書き,グループ(g),その他(o)への読み出し権限を設定(=)

演習内容

前回の演習と同じ方法でサーバにログインし、サーバ上で直接ファイル編集をしてみよう。

C:\Users\tsaitoh> ssh -P 443 guest00@nitfcei.mydns.jp
$ ls -al
-rw-r--r-- 1 guest00 root 76 Mar 8 12:06 helloworld.c
$ vi helloworld.c
もしくは
$ emacs helloworld.c
vim の使い方
挿入 iテキストESC
削除 x
ファイルの保存 :w
エディタの修了 ZZ
emacs の使い方
ファイルの保存 Ctrl-X Ctrl-S
エディタの修了 Ctrl-X Ctrl-C

GitHubから演習ファイルを複製

GitHub は、複数の開発者が共同でプログラムを開発するための環境で、プログラムの情報共有などに広く使われている。ファイルは、git コマンドで複製や更新ができる。

(( public_html の中に演習用ファイルを github からダウンロード ))
$ cd ~/public_html
public_html$ git clone https://github.com/tohrusaitoh/recp.git
public_html/recp$ cd recp/
public_html/recp$ ls -al
-rw-r--r-- 1 t-saitoh home 870 11月 10 2021 Makefile
-rw-r--r-- 1 t-saitoh home 1152 10月 8 2021 README.md
 :

サーバ上のファイルをパソコンにコピーして編集

(( サーバ上のファイル sampleI.php (sample-アイ.php) をダウンロード ))
C:\Users\tsaitoh> scp -P 443 guest00@nitfcei.mydns.jp:public_html/recp/sampleI.php .

VSCode などのエディタで編集

(( 編集した sampleI.php をサーバにアップロード ))
C:\Users\tsaitoh> scp -P 443 sampleI.php guest00@nitfcei.mydns.jp:public_html/recp/

Webサーバで書き込みができるように設定

(( public_html のデータベースファイル shopping.db を書き込み可能にする ))
$ chgrp www-data ~guest00/public_html/recp/shopping.db
$ chmod g+w ~guest00/public_html/recp/shopping.db

(( public_html/recp フォルダを書き込み可能にする ))
$ chgrp www-data ~guest00/public_html/recp
$ chmod g+w ~guest00/public_html/recp

バックエンドプログラムを実行してみる

パソコンのブラウザで、http://nitfcei.mydns.jp/~guest00/recp/sampleI.php を開く。

 

書き込み結果を確認してみる

(( データベースファイル shopping.db の書込み結果を確認 ))
$ cd ~guest00/public_html/recp
public_html/recp$ sqlite3 shopping.db
SQLite version 3.31.1 2020-01-27 19:55:54
Enter ".help" for usage hints.
sqlite> select * from BUYLIST ;
1010|10001|2021-11-05|1
1020|10001|2021-11-05|2
1022|10001|2021-11-05|3
  :
sqlite> [Ctrl-D] コントロールDで sqlite3 を抜ける
public_html/recp$

テスト返却と追加説明

前期中間試験の返却に伴い、補足説明。

C言語,Javaにおける文の定義

テストの時に、下記のようなプログラムで piyo() は、for の範囲?みたいな質問があったので、補足説明

for( ... ; ... ; ... )
   if ( ... )
      foo = bar ;
   else {
      baz() ;
      hoge() ;
   }
piyo() ;

C言語やJavaにおける文の定義は、以下の通り

文 ::= 式 ;    // 単文
     | ;       // 空文
     | { 文 文 ... }        // 複文
     | for( .. ; .. ; .. ) 文   // 制御構文
     | do 文 while( 式 ) ;
     | if ( 式 ) 文 [ else 文 ]
     ;

こういった文の範囲の誤解を避けるためのものが、インデント。

正しいインデントをつける習慣が重要。

Javaにおけるクラスとデータ構造のイメージ

この後のリスト構造の説明でもオブジェクトがどのように保存されるかを理解するのは重要なので、オブジェクトの説明。

Java では、class 宣言されたデータ構造は、ヒープメモリと呼ばれるデータ領域に保存されている。

class A {
   int data ;
   A( int value ) {
      this.data = value ;
   }
} ;

public class Main {
   public static void main( String[] args ) {
      A a = new A( 123 ) ;
   }
}

ここで、new 演算子は、指定されたオブジェクトをヒープメモリ上に確保する。そして、そのデータの入っている領域アドレスを、インスタンスの変数 a に代入している。

テストで出題した例であれば、

class IdNameAge {
   int    id ;
   String name ;
   Age    age ;
   IdNameAge( int i , String n , int a ) {
      this.id   = i ;
      this.name = n ;
      this.age  = a ;
   }
} ;

IdNameAge[] = people = {
   new IdNameAge( 1001 , "saitoh" ,  60 ) ,
   new IdNameAge( 1002 , "tomoko" ,  49 ) ,
   new IdNameAge( 1003 , "mitsuki" , 26 ) ,
} ;

Integer 型も、整数データを記憶するけど、オブジェクト型である。

ただし、Integer 型を常にヒープメモリに保存するのは、効率が悪いので、-128~127までの値ではIntegerオブジェクトは内部でキャッシュされる。Integer y = 123 ; 書いてはいるけど本来であれば、Integer y = new Integer( 123 ) ;  と書く必要があった。しかしJava5以降に、オートボクシングと呼ばれる機能があるため Integer y = 123 のように書けるし、こう書く方が推奨されている。

public class Main {
    public static void main(String[] args) {
        // Your code here!
        Integer sx = 123 ;
        Integer sy = 123 ;
        System.out.println( sx == sy ) ; // true
        Integer fx = 12345 ;
        Integer fy = 12345 ;
        System.out.println( fx == fy ) ; // false
    }
}

プログラム言語(C言語)の基礎

学際科目の情報制御基礎において、学科間でプログラミングの初歩の理解差があるので、簡単なC言語プログラミングの基礎の説明。

Hello World

“Hello World”と表示するだけのC言語プログラムは以下のようになる。

// コメントの書き方1              // "//"で始まる行は、プログラムの説明(コメント)
/* コメントの書き方2 */           // "/*"から"*/"で囲まれる範囲もコメント
#include <stdio.h>             // #で始まる行はプリプロセッサ行
                               // stdio.h には、入出力関数の説明が書いてある
int main() {                   // 一連の処理の塊を関数と呼ぶ。
                               // C言語では main() 関数を最初に実行する。
   printf( "Hello World\n" ) ; // printf() は、以下の物を表示する関数。
                               // "\n"は、文字を出力して改行するための特殊文字
   return 0 ;                  // main() 関数が、正常終了したことを意味する
}                              // 0 を返り値として返す。

#include <…>“のプリプロセッサ行は、最初のうちは解りにくいので、「これを書かないとダメ…」と思っていればいい。

#include <stdio.h> は、別ファイル(ヘッダファイル) stdio.h に記載されているプログラムリストを読み込む機能。
stdio.h には、printf() や scanf() などの基本的な関数や定数などの情報が記載されている。

C言語の基本的な命令(文)は、”;”で終わる。(単文)
複数の処理をまとめる場合には、”{“から”}”の中に、複数の文を書き並べる。(複文)

関数とは、複数の処理をひとまとめにした、処理の「かたまり」と思えばいい。

関数の型 関数名( 仮引数 ... ) {
   処理1 ... ;
   処理2 ... ;
}

printf() の 文字列中の”\n”(あるいは”¥n”)は、改行を意味する。
「\:バックスラッシュ」は、日本語環境では「¥:円記号」で入力・表示することが多い。

Paiza.io で動かしてみよう

C言語を本格的に使いたいなら、Microsoft Visual Studio などをインストールして使う方が便利だが、情報制御基礎で説明する程度のプログラムなら、Paiza.io が便利。ブラウザの画面で簡単にプログラムの動作を確認することができる。https://paiza.io/jaにアクセスして、上述の Hello World を動かしてみよう。

変数と代入

#include <stdio.h>
#include <math.h>            // 数学関数を使う 平方根 sqrt() を使っている
int main() {
   // 変数の宣言
   int    i ;                // 符号付き32bit変数 i の宣言
   int    a = 123 , j ;      // a を 123 で初期化 , j も整数型
   float  x ;                // 単精度実数の x を宣言
   double y = 1.234 , z ;    // 倍精度実数の y を宣言し 1.234 で初期化,
                             // z も倍精度実数
   // 変数への代入
   i = 1 ;                   // i に 1 を代入
   i = 12 + 2 * a ;          // 12+2*a を代入 a は123なので、
                             //   iには、258 が入る。
   x = sqrt( 2.0 ) ;         // x に 2.0 の平方根(1.4142)を代入
   z = y * 2.0 + x * 3.0 ;   // y*2+x*3をzに代入

   // 変数の内容の表示
   printf( "%d\n" , i ) ;    // 整数型(%d)で、    i の値を表示
   printf( "%f\n" , x ) ;    // 単精度実数(%f) で、x の値を表示
   printf( "%lf\n" , z ) ;   // 倍精度実数(%lf)で、z の値を表示

   printf( "iの値は%d,xの値は%lfです。\n" , i , x ) ;

   return 0 ;                // 正常終了 0 を返す
}

変数(計算結果を格納する入れ物)を使う場合は、変数を宣言する。
変数名には、何が入っているのか理解しやすいように、名前をつければいい。(英字で始まり、英数字が続くもの,_が入ってもいい)

変数に値を記憶する時は、”変数名=式 ;”の様に書くと、代入演算子”=” の右辺を計算し、その計算結果が左辺の変数に保存される。

変数の内容を表示する時には、printf() の文字列の中に、%d,%f,%lf などの表示したい式の型に応じたものを書いておく。%d=int型 , %f=float型 , %lf=double型
式の値が、その %.. の部分に書き込まれて、出力される。

繰り返しの制御命令

最も基礎的な繰り返し命令として、for() 文を説明。

#include <stdio.h>
int main() {
   int i ;
   for( i = 1 ; i <= 10 ; i++ ) {     // iを1から10まで変化させる。
      printf( "%d %d\n" , i , i*i ) ; // i と iの二乗を表示
   }
   return 0 ;
}

for文の意味を説明するために、対応するフローチャートを示す。

先のプログラムをフローチャートで示し、その命令の実行順序と、その変数の変化を下図に示す。

練習問題1

簡単なプログラミングの練習として、前回講義の練習問題をC言語で書いてみよう。

  • 電気電子工学科,電子情報工学科の学生は、出席番号が奇数は処理C,偶数は処理Dについて回答せよ。
  • それ以外の学科の学生は、出席番号が奇数は処理A,偶数は処理Bの結果について回答せよ。
  • 自分が考えたプログラムは、前述の Paiza.io や、自分のパソコンのC言語環境で入力し、動作結果も確認せよ。

制御構文とフローチャート

構文の入れ子

文と複文

C言語の文法で、{,} は複数の処理を連続して実行し、複文とよばれる。複数ので文を構成する。

これに対して、a = 123 ; といったセミコロンで終わる「処理 ;」は単文といい、1つの式で文となる。

制御構文のif文は、「if ( 条件 ) 文」で文となる。このため条件が満たされたときに実行する文が単文であれば、{,} は不要である。条件が満たされない場合の処理も記述するときには、「if ( 条件 ) 文 else 文」を使う。

// if文
if ( 条件 ) {
   a = 123 ;
}
if ( 条件 )
   a = 123 ; // 単文なら中括弧は不要

// if-then-else
if ( x >= 60 ) {
   printf( "合格点\n" ) ;
} else {
   printf( "不合格点\n" ) ;
}

同じように、「while(条件) 文」、「for(A,B,C) 文」、「do 文 while(条件) ;」も、それぞれ文を構成する。
{,} の複文は、{ 文 文 文… } のように、一連の文を実行し、それを1つの文として扱うための機能である。

// while 文
i = 0 ;
while( i < 10 ) {
   printf( "%d\n" , i ) ;
   i++ ;
}

// for 文
for( i = 0 ; i < 10 ; i++ ) {
   printf( "%d\n" , i ) ;
}

// do-while 文
i = 0 ;
do {
   printf( "%d\n" , i ) ;
   i++ ;
} while( i < 10 ) ;

練習問題2

プログラムの制御構造の確認として、以下の3つ(No.1,No.2,No.3)の問題から、
M科,C科,B科の学生は((自分の出席番号+1) % 2)+1 の問題、E科,EI科の学生は、((自分の出席番号+1) % 3)+1について、プログラムのフローチャートを描き、その処理がどのように進むのか答えよ。

レポートには、以下の点を記載すること。

  • フローチャート
  • 実行順序と変数の変化がわかる内容
  • (できれば、実際にプログラムを動かし、正しいことを検証すること)
// No.1 ---------------------------------------------------------
#include <stdio.h>
int main() {
   int i , j ;
   for( i = 1 ; i <= 4 ; i++ ) {
      if ( i % 2 == 0 ) {  // i%2 は2で割った余り,i%2==0ならば偶数のとき
         for( j = 1 ; j <= 2 ; j++ )
            printf( "%d %d\n" , i , j ) ;
      }
   }
   return 0 ;
}
// No.2 ---------------------------------------------------------
#include <stdio.h>
int main() {
   int x = 10 , y = 7 , s = 0 ;
   while( x > 0 ) {
      if ( x % 2 != 0 )
         s = s + y ;
      y = y * 2 ;
      x = x / 2 ;  // 注意: xは整数型      
   }
   printf( "%d\n" , s ) ;
   return 0 ;
}

// No.3 ---------------------------------------------------------
#include <stdio.h>
int a[ 6 ] = { 2 , 3 , 5 , 8 , 13 , 21 } ; 
int main() {
   int left = 0 , right = 6 , mid ;
   int key = 13 ;
   while( right - left > 0 ) {
      mid = (left + right) / 2 ; // 整数型で計算
      printf( "%d\n" , a[ mid ] ) ;
      if ( a[ mid ] == key )
         break ;
      else if ( a[ mid ] > key )
         right = mid ;
      else
         left = mid + 1 ;
   }
   return 0 ;
}

抽象クラス(純粋仮想基底クラス)

前回説明した仮想関数では、基底クラスから派生させたクラスを作り、そのデータが混在してもクラスに応じた関数(仮想関数)を呼び出すことができる。

この仮想関数の機能を逆手にとったプログラムの記述方法として、抽象クラス(純粋仮想基底クラス)がある。その使い方を説明する。

JavaのGUIにおける派生の使い方

先週の講義では、派生を使ったプログラミングは、GUI で使われていることを紹介したが、例として Java のプログラミングスタイルを少し紹介する。

例えば、Java で アプレット(ブラウザの中で動かすJavaプログラム)を作る場合の、最小のサンプルプログラムは、以下のようになる。

import java.applet.Applet; // C言語でいうところの、Applet 関連の処理を include
import java.awt.Graphics;

public class App1 extends Applet {  // Applet クラスから、App1 クラスを派生
    public void paint(Graphics g) { // 画面にApp1を表示する必要がある時に呼び出される。
        g.drawString("Hello World." , 100 , 100);
    }
}

この例では、ブラウザのGUIを管理する Applet クラスから、App1 というクラスを派生(extendsキーワード)し、App1 固有の処理として、paint() メソッドを定義している。GUI のプログラミングでは、本来ならマウスが押された場合の処理などを記述する必要があるが、このプログラムでは paint() 以外何も書かれていない。これはマウス処理などは、基底クラスのAppletのマウス処理が継承されるので、省略してもうまく動くようになっている。paint() メソッドは、このApp1クラスの中で、継承されたメソッドでなく自分で新たに定義している。

このように、派生クラスの継承機能を使うことで、雑多な処理を基底クラスですべて書くようにすれば、同じようなデータ型が出てくる場合プログラムを書く手間を減らすことができる。

抽象クラス(純粋仮想基底クラス)

抽象クラス(純粋仮想基底クラス)とは、見かけ上はデータを何も持たないクラスであり、本来なら意味がないデータ構造となってしまう。しかし、派生クラスで要素となるデータと仮想関数で機能を与えることで、基底クラスという共通部分から便利な活用ができる。(実際には、型を区別するための型情報を持っている)

例えば、C言語であれば一つの配列に、整数、文字列、実数といった異なる型のデータを記憶させることは本来ならできない。しかし、以下のような処理を記載すれば、可能となる。

C言語では、1つの記憶域を共有するために共用体(union)を使うが、C++では仮想関数が使えるようになり、型の管理をプログラマーが行う必要のある「面倒で危険な」共用体を使う必要はなくなった。

// 純粋仮想基底クラス
class Object {
public:
   virtual void print() const = 0 ;
   // 中身の無い純粋基底クラスで、
   // 仮想関数を記述しない時の書き方。
} ;

// 整数データの派生クラス
class IntObject : public Object {
private:
   int data ;
public:
   IntObject( int x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%d\n" , data ) ;
   }
} ;

// 文字列の派生クラス
class StringObject : public Object {
private:
   char data[ 100 ] ;
public:
   StringObject( const char* s ) {
      strcpy( data , s ) ;
   }
   virtual void print() const {
      printf( "%s\n" , data ) ;
   }
} ;

// 実数の派生クラス
class DoubleObject : public Object {
private:
   double data ;
public:
   DoubleObject( double x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%lf\n" , data ) ;
   }
} ;

// 動作確認
int main() {
   Object* data[3] = {
      new IntObject( 123 ) ,
      new StringObject( "abc" ) ,
      new DoubleObject( 1.23 ) ,
   } ;
   for( int i = 0 ; i < 3 ; i++ ) { // 123
      data[i]->print() ;            // abc
   }                                // 1.23 と表示
   return 0 ;
} ;

このプログラムでは、純粋仮想基底クラスObjectから、整数IntObject, 文字列StringObject, 実数DoubleObject を派生させ、そのデータを new により生成し、Objectの配列に保存している。

仮想関数を使うと、Object型の中に自動的に型情報が保存されるようになる。一般的な実装では、各派生クラス用の仮想関数のポインタテーブル(vtable)へのポインタが使われる。

Javaなどのオブジェクト指向言語では、全てのクラス階層のスーパークラスとして、Object を持つように作られている。

様々な型に適用できるプログラム

次に、抽象クラス(純粋仮想基底クラス)の特徴を応用したプログラムの作り方を説明する。

例えば、以下のような最大選択法で配列を並び替えるプログラムがあったとする。

int a[5] = { 11, 55, 22, 44, 33 } ;

void my_sort( int array[] , int size ) {
   for( int i = 0 ; i < size - 1 ; i++ ) {
      int max = i ;
      for( int j = i + 1 ; j < size ; j++ ) {
         if ( array[j] > array[max] )
            max = j ;
      }
      int tmp = array[i] ;
      array[i] = array[max] ;
      array[max] = tmp ;
   }
}
int main() {
   my_sort( a , 5 ) ;
}

しかし、この整数を並び替えるプログラムがあっても、文字列の並び替えや、実数の並び替えがしたい場合には、改めて文字列用並び替えの関数を作らなければいけない。しかも、ほとんどが同じような処理で、改めて指定された型のためのプログラムを作るのは面倒である。

C言語のデータの並び替えを行う、qsort() では、関数ポインタを用いることで、様々なデータの並び替えができる。しかし、1件あたりのデータサイズや、データ実体へのポインタを正しく理解する必要がある。これを間違えると、メモリエラーなどが簡単に発生することから、オブジェクト指向の抽象クラスを用いた方が、型として安全なプログラムが記述できる。

#include <stdio.h>
#include <stdlib.h>
int a[ 4 ] = { 11, 33, 22, 44 } ;
double b[ 3 ] = { 1.23 , 5.55 , 0.11 } ;
// 並び替えを行いたいデータ専用の比較関数を作る。
// a>bなら+1, a=bなら0, a<bなら-1を返す関数
int cmp_int( int* pa , int* pb ) { // int型用コールバック関数
   return *pa - *pb ;
}
int cmp_double( double* pa , double* pb ) { // double型用コールバック関数
   if ( *pa == *pb )
      return 0 ;
   else if ( *pa > *pb )
      return 1 ;
   else
      return -1 ;
}
int main() {                                   // C言語の怖さ
   qsort( a , 4 , sizeof( int ) ,              //   このあたりの引数を書き間違えると
          (int(*)(void*,void*)) cmp_int ) ;    //   とんでもない目にあう。
   qsort( b , 3 , sizeof( double ) ,           // "void*は、型を明記しないポインタ型"
          (int(*)(void*,void*)) cmp_double ) ; //   の意味。
} 

このように、自分が作っておいた関数のポインタを、関数に渡して呼び出してもらう方法は、コールバックと呼ぶ。
JavaScript などの言語では、こういったコールバックを使ったコーディングがよく使われる。

// コールバック関数 f を呼び出す関数
function exec_callback( var f ) {
   f() ;
}
// コールバックされる関数 foo()
function foo() {
   console.log( "foo()" ) ;
}
// foo() を実行する。
exec_callback( foo ) ;
// 無名関数を実行する。
exec_callback( function() {
                  console.log( "anonymous" ) ;
               } ) ;

任意のデータを並び替え

class Object {
public:
   virtual void print() const = 0 ;
   virtual int  cmp( Object* ) = 0 ;
} ;

// 整数データの派生クラス
class IntObject : public Object {
private:
   int data ;
public:
   IntObject( int x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%d\n" , data ) ;
   }
   virtual int cmp( Object* p ) {
      int pdata = ((IntObject*)p)->data ;  // 本当はこのキャストが危険
      return data - pdata ;                //  ↓安全な実装したいなら↓
   }                                       // IntObject* pi = dynamic_cast<IntObject*>(p) ;
} ;                                        // return pi != NULL ? data - pi->data : 0 ;

// 文字列の派生クラス
class StringObject : public Object {
private:
   char data[ 100 ] ;
public:
   StringObject( const char* s ) {
      strcpy( data , s ) ;
   }
   virtual void print() const {
      printf( "%s\n" , data ) ;
   }
   virtual int cmp( Object* p ) {
      char* pdata = ((StringObject*)p)->data ;
      return strcmp( data , pdata ) ; // 文字列比較関数
   }
} ;

// 実数の派生クラス
class DoubleObject : public Object {
private:
   double data ;
public:
   DoubleObject( double x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%lf\n" , data ) ;
   }
   virtual int cmp( Object* p ) {
      double pdata = ((DoubleObject*)p)->data ;
      if ( data == pdata )
         return 0 ;
      else if ( data > pdata )
         return 1 ;
      else
         return -1 ;
   }
} ;

// Objectからの派生クラスでcmp()メソッドを
//   持ってさえいれば、どんな型でもソートができる。
void my_sort( Object* array[] , int size ) {
   for( int i = 0 ; i < size - 1 ; i++ ) {
      int max = i ;
      for( int j = i + 1 ; j < size ; j++ ) {
         if ( array[j]->cmp( array[max] ) > 0 ) // 仮想関数により適切な
            max = j ;                           //  比較メソッドが呼び出される。
      }
      Object* tmp = array[i] ;
      array[i] = array[max] ;
      array[max] = tmp ;
   }
}
// 動作確認
int main() {
   Object* idata[3] = {
      new IntObject( 11 ) ,
      new IntObject( 33 ) ,
      new IntObject( 22 ) ,
   } ;
   Object* sdata[3] = {
      new StringObject( "abc" ) ,
      new StringObject( "defghi" ) ,
      new StringObject( "c" ) ,
   } ;
   my_sort( idata , 3 ) ; // 整数のソート
   for( int i = 0 ; i < 3 ; i++ )
      idata[i]->print() ;
   my_sort( sdata , 3 ) ; // 文字列のソート
   for( int i = 0 ; i < 3 ; i++ )
      sdata[i]->print() ;
   return 0 ;
} ;

このような方式でプログラムを作っておけば、新しいデータ構造がでてきてもソートのプログラムを作らなくても、比較専用の関数 cmp() を書くだけで良い。このような抽象クラスをデータを入れる入れ物として使う手法は「コンテナクラス」(あるいはコレクション)と呼ぶ。JavaにおけるList(ArrayList, LinkedList), Set, Map, Deque など(コレクションフレームワーク)は、Java.lang.Object から派生した物として扱うことで、面倒なデータ構造のプログラミングを簡潔に記述することができるようになっている。

ただし、この並び替えの例では、Object* を IntObject* に強制的に型変換している。

また、このプログラムでは、データを保管するために new でポインタを保管し、データの比較をするために仮想関数の呼び出しを行うことから、メモリの使用効率も処理効率でもあまりよくない

こういう場合、最近の C++ ではテンプレート機能が使われる。

template <typename T>
void my_sort( T a[] , int size ) {
  for( int i = 0 ; i < size - 1 ; i++ ) {
    int max = i ;
    for( int j = i + 1 ; j < size ; j++ ) { if ( a[j] > a[max] )
        max = j ;
    }
    T  tmp = a[i] ;
    a[i] = a[max] ;
    a[max] = tmp ;
  }
}

int main() {
  int idata[ 5 ] = { 3, 4, 5 , 1 , 2 } ;
  double fdata[ 4 ] = { 1.23 , 0.1 , 3.4 , 5.6 } ;

  // typename T = int で int::mysort() が作られる
  my_sort<int>( idata , 5 ) ;
  for( int i = 0 ; i < 5 ; i++ )
    printf( "%d " , idata[i] ) ;
  printf( "\n" ) ;

  // typename T = double で double::mysort() が作られる
  my_sort<double>( fdata , 4 ) ;
  for( int i = 0 ; i < 4 ; i++ )
    printf( "%lf " , fdata[i] ) ;
  printf( "\n" ) ;
  return 0 ;
}

C++のテンプレート機能は、my_sort( int[] , int ) で呼び出されると、typename T = int で、整数型用の my_sort() の処理が自動的に作られる。同じく、my_sort( double[] , int ) で呼び出されると、typename = double で 実数型用の my_sort() が作られる。

テンプレート機能では、各型用のコードが自動的に複数生成されるという意味では、出来上がったコードがコンパクトという訳ではない。C++では、STL(標準テンプレートライブラリ:Standard Template Library)による、コンテナ, イテレータ(反復子), アルゴリズム, 関数オブジェクトにより、様々なデータ構造を簡単に扱うことができる。

#include <vector>
#include <stdio.h>

int main(void) {
    std::vector<int> vec{ 1, 2, 3 } ;  // STLによる整数のvector

    for( int i = 0 ; i < vec.size() ; i++ )
        cout << vec[i] ;
    cout << endl ;

    // 反復子による繰り返し処理 auto は型推論による反復子の宣言
    for( auto it = vec.begin() ; it != vec.end() ; it++ )
        cout << *it ;      // it は std::vector<int>::iterator 型
    cout << endl ;

    // もっとシンプルな書き方 (C++11で導入された範囲ベース for ループ)
    for( auto &num : vec ) // auto は型推論による変数宣言 vec が int なので num は int& 型になる 
        cout << num ;      // イテレータ反復子による繰り返しの処理
    cout << endl ;
    return 0;
}

仮想関数レポート課題

ここで示したプログラムを参考に、独自のデータ(例えば、複素数のデータや名前と誕生日といったデータ)について、my_sort() などで並び替えるプログラムを作成せよ。並び替える時の順序も、各自て定義すればいい。(複素数なら絶対値順とか、名前と誕生日なら、誕生日順とか)

レポートの提出先はこちら

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー