データが登録済みかどうかを判定する処理を作るために、登録された値を配列に次々と値を追加保存する場合、どのようにプログラムを記述するだろうか？

配列にデータを追加

次々と与えられた値を保存していくのであれば、Java であれば下記のようなコードが一般的であろう。
でも、ArrayList とはどのようにデータを覚えているのだろうか? なぜ 宣言は ArrayList<Integer> array であって ArrayList<int> array で宣言するとエラーが出るのであろうか?

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // ArrayList は連続アドレス空間に保存してくれる可変長配列
        //   ランダムアクセスをする場合に向いている
        ArrayList<Integer> array = new ArrayList<Integer>() ;
        array.add( 11 ) ;
        array.add( 2 ) ;
        array.add( 333 ) ;
        
        for( Integer i : array ) {
            System.out.println( i ) ;
        }
    }
}

このような ArrayList のようなデータ構造の仕組みを考えるために、最も単純な配列でプログラムを作ってみる。

末尾に追加

import java.util.*;

public class Main {
    static int[] array = new int[ 10 ] ;
    static int   size  = 0 ;

    public static void add( int x ) {
        array[ size ] = x ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        add( 11 ) ;
        add( 2 ) ;
        add( 333 ) ;
        
        for( int i = 0 ; i < size ; i++ )
            System.out.println( array[i] ) ;
    }
}

同じ処理をC言語で書いてみる。

#include <stdio.h>

int array[ 10 ] ;
int size = 0 ;

void add( int x ) {          // if ( size < array.length ) ... の判定が必要かも
    array[ size ] = x ;
    size++ ;
}

int main() {
    add( 11 ) ;
    add( 2 ) ;
    add( 333 ) ;

    for( int i = 0 ; i < size ; i++ )
        printf( "%d\n" , array[ i ] ) ;
    return 0 ;
}

しかし、このプログラムでは、最初に宣言した要素数10個を越えてデータを保存できないし、配列溢れさせないためには要素数の上限チェックも必要となるだろう。

昇順に並べながら途中に要素を追加

前述のプログラムでは、配列の末尾の場所を size で覚えておき、末尾にデータを追加していた。でも、配列に保存されている値の中から目的の値が含まれているか検索したいのであれば、配列に要素を昇順に保存しておいて2分探索法を使うのが一般的であろう。では、前述のプログラムを昇順で保存するにはどうすべきか？

最も簡単な方法で書くのであれば、下記のようなコードになるかもしれない。

public static void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) { // ここは2分探索で書けば O( log N ) にできるかも
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )   // 途中に挿入は、コレじゃダメ?
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- ) // 途中にデータを入れるために要素を１つ後ろに移動
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) {
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- )
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

このプログラムでは、for( i … ) の処理でデータを挿入すべき場所を見つけ、for( int j … ) の繰り返しでデータを1つ後ろにずらしてから要素を加えている。

for( i … ) の処理は、このプログラムでは O( N ) となっているが、2分探索法を用いれば O( log N ) に改善ができるかもしれない。しかし、for( int j… ) の処理は、データを1つ後ろにずらす必要があるため O( N ) の処理が必要となる。

ここで、途中にデータを追加する処理の効率を改善することを考える。

リスト構造の導入

以下のデータ構造では、配列にデータと次のデータの場所を覚えることで、一見デタラメな順序に保存されているようにみえるが、next[] に次の値の保存されている場所が入っている。

import java.util.*;

public class Main {           //    0    1    2    3    4    5
    static int[] data = new int[] { 11 , 55 , 22 , 44 , 33 , 0 , 0 , 0 , 0 , 0 } ;
    static int[] next = new int[] { 2  , -1 , 4  , 1  , 3  , 0 , 0 , 0 , 0 , 0 } ;
    static int   size = 5 ;
    static int   top = 0 ;

    static void insert( int n , int x ) {
        data[ size ] = x ;
        next[ size ] = next[ n ] ;
        next[ n ] = size ;
        size++ ;
    }
    
    public static void main(String[] args) throws Exception {
        for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
            System.out.println( data[ idx ] ) ;
        insert( 2 , 25 ) ;
        for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
            System.out.println( data[ idx ] ) ;
    }
}

#include <stdio.h>

int  data[ 10 ] = { 11 , 55 , 22 , 44 , 33 , 0 , 0 , 0 , 0 , 0 } ;
int  next[ 10 ] = { 2  , -1 , 4  , 1  , 3  , 0 , 0 , 0 , 0 , 0 } ;
int  size = 5 ;
int  top  = 0 ;

void insert( int n , int x ) {
    data[ size ] = x ;
    next[ size ] = next[ n ] ;
    next[ n ] = size ;
    size++ ;
}

int main() {
    for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
        printf( "%d\n" , data[ idx ] ) ;
    insert( 2 , 25 ) ;
    for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
        printf( "%d\n" , data[ idx ] ) ;
    return 0 ;
}

このようなデータ構造であれば、データ自体は末尾に保存しているが、次の値が入っている場所を修正することで途中にデータを挿入することができる。この方法であれば、途中にデータを入れる場合でもデータを後ろにずらすような処理が不要であり、O(1)で途中にデータを挿入できる。

このプログラムでは、配列の当初の長さを超えてデータを格納することはできない。

リスト構造 ListNode

前述の data と 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 ) ;
    }
}

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int       data ;
    ListNode* next ;
} ;

ListNode* newListNode( int d , ListNode* nx ) {
    ListNode* _this = new ListNode() ;
    if ( _this != NULL ) {
        _this->data = d ;
        _this->next = nx ;
    }
    return _this ;
}

int main() {
    ListNode* top = newListNode( 11 , newListNode( 22 , newListNode( 33 , NULL ) ) ) ;
    for( ListNode* p = top ; p != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    top->next = newListNode( 15 , top->next ) ;
    for( ListNode* p = top ; p != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    return 0 ;
}

Javaのジェネリクス

Javaのジェネリクス(C++のテンプレート)を使って書いてみた。ジェネリクスは、クラスやメソッドにおいて、特定の型を指定することなく動作するコードを記述することができる機能。これにより、型安全性を保ちながら、コードの再利用性と柔軟性を向上させることがでる。

import java.util.*;

class ListNode<T> {
    T           data ;
    ListNode<T> next ;
    
    ListNode( T d , ListNode<T> n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        // var 宣言は型推論で、右辺のデータ型を自動的に選択してくれる。
        // itop は整数型のリスト
        var itop = new ListNode<Integer>( 11 , new ListNode<Integer>( 22 , new ListNode<Integer>( 33 , null ) ) ) ;
        // new List<int>( 11 , ... ) と書くと、<>の中は reference しか使えないと言われる。
        for( var p = itop ; p != null ; p = p.next )
            System.out.println( p.data ) ;

        // stop は文字列型のリスト
        var stop = new ListNode<String>( "aa" , new ListNode<String>( "bb" , new ListNode<String>( "cc" , null ) ) ) ; 
        for( var p = stop ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

前述のプログラムをJavaのジェネリッククラスで記述

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // LinkedList は上記のリスト構造で保存される。
        //    途中に要素の追加削除を行ったり、シーケンシャルアクセスに向いたデータ構造
        var top = new LinkedList<Integer>() ;
        top.add( 11 ) ;
        top.add( 22 ) ;
        top.add( 33 ) ;
        for( int i : top )            // 11 22 33
            System.out.println( i ) ;
        top.add( 1 , 15 ) ;
        for( int i : top )            // 11 15 22 33
            System.out.println( i ) ;
    }
}

クラスの宣言とコンストラクタ・メソッド

import java.util.*;

// クラス宣言
class Person {
    // データ構造
    String name ;
    int    age ;

    // コンストラクタ(データ構造を初期化する関数)
    Person( String n , int x ) {
        this.name = n ;    // this は対象となるデータそのものを指す
        this.age  = x ;    // 対象が明言されていれば、this は省略可能
    }
    // データを扱うメソッド
    void print() {                 // データを表示
        System.out.println( this.name + "," + this.age ) ;
    }
    boolean sameAge( Person x ) {  // 同じ年齢か判断するメソッド
        return this.age == x.age ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {

        Person tsaitoh = new Person( "Tohru Saitoh" ,  59 ) ;
        Person tomoko  = new Person( "Tomoko Saitoh" , 48 ) ;

        tsaitoh.print() ;  // Tohru Saitoh, 59
        tomoko.print() ;   // Tomoko Saitoh,48

        if ( tsaitoh.sameAge( tomoko ) ) {
            // sameAge( Person x ) では、
            // this = tsaitoh , x = tomoko となって呼び出される
            System.out.println( "同じ年齢ですよ" ) ;
        }
        Person[] family = new Person[ 2 ] ;
        family[0] = tsaitoh ;
        family[1] = tomoko ;
        for( int i = 0 ; i < 2 ; i++ )
            family[ i ].print() ;
    }
}こ

このプログラムのデータ構造は下記のような状態。

情報構造論の前期中間までのレポートとして、自分の理解力に応じて下記課題の1つを選んで回答せよ。ポインタや文字列操作の練習を目的とするため、言語はC言語,C++にて行うこと。

1. 入力の中の特定文字列ABCを、別の文字列DEFGに変換して出力したい。ABCやDEFGの文字列は最初に与える。
   最初の2行で、変換元ABCと変換後DEFGで与えられ、その後に複数行の入力が続くものとする。
   • 変換元,変換後の文字列は、空白を含まない50文字以内の文字。複数行の入力は10文字以内、1行は200文字以内とする。
   • 入力例と変換例

   orange (変換元) apple (変換後) I like an orange. He likes a pineapple.

   ⇒

   I like an apple. He likes a pineapple.

2.  URLが複数行入力として与えられる。最初にすべての入力行を配列に格納した後、URLの中のドメイン名部分は大文字小文字の区別がないので、ドメイン名部分だけ小文字に修正し、その結果を表示せよ。
   • URLは10行以内、URLの1行は200文字以内とする。
   • 変換例
     • http://HOGE.jp/FUGA.html → http://hoge.jp/FUGA.html
     • https://www.Google.co.jp/search?q=FOO+BAR
       → https://www.google.co.jp/search?q=FOO+BAR

   ---

3. プログラムのソースコードが入力として与えられる。最初にすべての入力行を配列に格納した後、プログラム中のキーワード(int, char, if, while, など)だけを大文字に変換して出力するプログラムを作成せよ。(難易度高いので注意)
   • プログラムは10行以内。1行は200文字以内とする。
   • 変換例
     • int a = 123 ; → INT a = 123 ;
     • for( int form = 0 ; form < 10 ; form++ ) printf( “int = %d\n” , form ) ; // if
       → FOR( INT form = 0 ; form < 10 ; form++ ) printf( “int = %d\n” , form ) ; // if
       • formはキーワードではない。
       • “int…”は、C言語の文字列内なのでキーワードではない。(オプション)
       • /*…*/ , // のコメント内の if はキーワードではない。(オプション)

レポートには、下記の点を記載してあること。

• プログラムリスト
• 説明(コメントや解説)
• 動作検証とその結果
• 考察(自分のプログラムの問題点)

C言語での文字列処理に便利な標準関数<string.h>

• strlen( str ) : 文字列の長さを数える。文字列末尾文字NUL ‘\0’ までの文字数
• strcpy( dest , src ) : 文字列をコピー。
• strcmp( s1 , s2 ) : 文字列を比較(辞書順で s1<s2 なら負の値, s1=s2 なら0, s1>s2 なら正の値を返す)
• strncmp( s1 , s2 , n ) : 文字列を指定した長さ n までで比較。

文字判定に便利な標準関数<ctype.h>

• isalpha( c ) : 文字 c が英字(A-Z or a-z)、isdigit( c ) : 文字 c が数字(0-9)

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