第一工科大学陳研究室

4.Data Structure

データ構造とは

データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。

配列

配列（はいれつ）は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め，要素を区別します。配列によってまとめられた，一つひとつの変数を要素（ようそ）と呼びます。要素を区別するために添えた数字を添字（そえじ）と呼びます。

配列は大変シンプルで，コレクションクラスに比較すると必要とするメモリ量が少なく，アクセスが高速なことがメリットです。データを単純に格納して，順番に参照する程度の用途であれば，コレクションクラスに比較して配列のほうが有利です。

最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し，配列の添字を明記して要素に値を代入し，添字を指定して要素の値を呼び出します。

String names[] = {“Tim Bray”,        // 0番目の要素
“Brian Kernighan”, // 1番目の要素
“Jon Bentley”,     // 2番目の要素
“Karl Fogel”};     // 3番目の要素

for(int i = 0; i < names.length; ++i){
println(names[i]);
}

ランダムな整数データを500個もつデータファイルRandomData.txtを作成

int NUMBER_OF_RANDOM_DATA = 500;
int MIN_SIZE_OF_RANDOM_DATA = 1;
int MAX_SIZE_OF_RANDOM_DATA = 500;
String DATA_FILE_NAME = “RandomData.txt”;
int DIAMETER = 5;

void setup(){
//ランダムなデータの作成
ArrayList<Integer> nums = new ArrayList<Integer>();
for(int i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
nums.add((int)random(MIN_SIZE_OF_RANDOM_DATA,MAX_SIZE_OF_RANDOM_DATA));
}
//画面に出力してみる
size(500,500);
background(0,0,0);
stroke(255,0,0);
for(int i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
ellipse(i,nums.get(i),DIAMETER,DIAMETER);
}
//ファイルに出力
String[] data = new String[NUMBER_OF_RANDOM_DATA];
for(Integer i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
data[i] = nums.get(i).toString();
}
saveStrings(DATA_FILE_NAME,data);
}

このコードで作成したデータファイルRandomData.txtはスケッチフォルダGenerateRandomData内にあります。他のsketchで利用する場合は，そのsketchのスケッチフォルダにコピーしてください。

コレクション

配列は変数に添字と呼ばれる番号を振ることで要素を区別しています。場合によっては添字が不要であったり余計であったりします。

コレクション（collection）（時には，コンテナー（container）と呼ばれます）は，効率的なアクセスのために有用な方法で，オブジェクトを保持してまとめる入れ物です。

コレクション（リスト、セット）や マップ は、オブジェクトの集合を扱うための仕組みです。

カテゴリ	クラス	説明
List系	ArrayList	配列を扱います。
	LinkedList	配列を扱います。挿入・削除が高速です。
	Vector	配列を扱います。パフォーマンスが悪いため現在ではあまり推奨されない古いクラスです。
Set系	HashSet	値の重複を許さない順不同の要素集合を扱います。
Set系	TreeSet	値の重複を許さないソートされたの要素集合を扱います。
Map系	HashMap	キーと値の組からなる要素の集合を扱います。
Map系	TreeMap	キーと値の組からなる要素の集合を扱います。キーでソートされています。

【コレクションクラスの比較】
	Array List	Linked List	Hash Map	Tree Map	Hash Set	TreeSet
インタフェイス	List	List	Map	Map	Set	Set
要素の重複	○	○	×	×	×	×
null値の要素	○	○	○	×	○	×
自動ソート	×	×	×	○	×	○

まとめ

配列はシンプルで高速なアクセスが可能です。要素数が少なく，ごく単純な操作しか必要ない場合に活用すると良いでしょう。
コレクションは柔軟な取り扱いができるよう工夫された仕組みです。特に意味がなければ，配列ではなくコレクションを用いましょう。

参考：

3.Algorithms

アルゴリズムとは

アルゴリズム（英: algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法（さんぽう）」と訳されることもある。

基本的なアルゴリズム

順次
条件判定と分岐 (if, switch)
繰り返し (while, for)

順次

順次実行構造は，上に書かれた命令が先に実行され，下に書かれた命令が後に実行される構造のことです。なるべくこのようなシンプルで自然な構造になるようコードを書くべきです。

典型的な順次実行の例として，GSWPよりサンプルコードを引用します。

// Example 03-13 from "Getting Started with Processing" 
// by Reas & Fry. O'Reilly / Make 2010

size(480, 120);
smooth();
strokeWeight(12);
strokeJoin(ROUND);      // Round the stroke corners
rect(40, 25, 70, 70);
strokeJoin(BEVEL);      // Bevel the stroke corners
rect(140, 25, 70, 70);
strokeCap(SQUARE);      // Square the line endings
line(270, 25, 340, 95);
strokeCap(ROUND);       // Round the line endings
line(350, 25, 420, 95);

図5.2　Ex_03_13.pdeの実行結果

画面の設定から描画まで，上から下へ順に実行されます。

条件判定と分岐 (if, switch)

条件に従って実行するコードブロックを切り替える仕組みは大変便利です。図5.3はif文の流れ図です。論理式が成り立つ場合，つまり「真」ならば直下のコードブロックを実行し，論理式が成り立たなければ，つまり「偽」ならば流れは右へ分岐し，右側のコードブロックが実行されます。

図5.3　if文の流れ図

基本的に，条件分岐の流れ図では，論理式が成り立つ（すなわち真の）とき真下へ向かう流れ線をたどり，論理式が成り立たない（すなわち偽の）とき横へ向かう流れ線をたどります。流れ線に真や偽，TやFといった値が記されていない場合はそのように理解してください。

昼には太陽、夜には月が動くようなアニメーション

これを実現するためは、たとえば以下のようなプログラムを書く

 int scene;
 int x;
 float theta;
 void setup(){
  scene = 0;
  theta = 3.1;
  size(600,300);
 }
 void draw(){
  theta += 0.01;
  if(scene==0){
    background(100,100,200);
    noStroke();
    fill(250,250,250);
    ellipse(300*cos(theta)+300,300*sin(theta)+400,100,100);
    if(theta > 6.3){scene=1; theta=3.1;}
  }
  else {
    background(0);
    noStroke();
   fill(250,250,50);
   ellipse(300*cos(theta)+300,300*sin(theta)+400,100,100);
   if(theta > 6.3){scene=0; theta=3.1;}
 }
 }

ここでは、ふたつの場面のどちらであるかを表すために scene という変数を用意して、scene が0なら昼の場面、それ以外なら夜の場面を描くようにしている。実際にはscene は0か1である。

繰り返し (while, for)

同じような仕事を繰り返すことがあります。コンピュータは，繰り返しの仕事が得意です。人間なら早晩飽きて放り出してしまうことも，コンピュータは決して飽きません。

図5.4は繰り返しの基本形，while文の流れ図です。

図5.4　繰り返しの基本形，while文の流れ図

while文による繰り返し構造の流れ図は次のように読みます。

論理式（条件式とも呼びます）が成り立てば，すぐ下のコードブロックへ実行が移ります。
コードブロックの実行が終わると，論理式の直前に実行が戻ります。
論理式が成り立つ限り，コードブロックを繰り返し実行します。
論理式が成り立たない場合，実行は右側へ移り，コードブロックを実行せずwhile文の構造を終了します。

命令 for を使うと、同じ内容は以下のように書ける。

 int i;
 for(i=0; i<=90; i += 10){
  line(0,i,99,i);
 }

参考：

いろいろなソートアルゴリズム http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/
Interactive Data Structure Visualizations http://student.seas.gwu.edu/~idsv/idsv.html

2.Install Java env.

Javaのインストール

MacBookでのJavaのインストール方法

http://java.com/ja/download/help/mac_install.xml

MacにJavaをインストールするには、次の手順に従います。
jre-7u6-macosx-x64.dmgファイルをダウンロードします。ファイルをダウンロードする前に、使用許諾契約の内容を確認し、同意します。
.dmgファイルをダブルクリックして起動します
パッケージ・アイコンをダブルクリックし、インストール・ウィザードを起動します

結果確認

chen-no-MacBook-Air:~ chen$ java -version
java version “1.8.0_11”
Java(TM) SE Runtime Environment (build 1.8.0_11-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.11-b03, mixed mode)

Windows７でのJavaのインストール方法

http://java.com/ja/download/help/windows_manual_download.xml

手動ダウンロード・ページに移動します
「Windows Online」をクリックします
ダウンロードするファイルを実行するか保存するかを尋ねる「ファイルのダウンロード」ダイアログ・ボックスが表示されます
インストーラを実行するには、「実行」をクリックします。
ファイルを保存して後でインストールするには、「保存」をクリックします。
保存先として、ローカル・システムのフォルダを選択します。
ヒント: デスクトップなどのように、コンピュータ上のわかりやすい場所にファイルを保存してください。
保存したファイルをダブル・クリックし、インストールを開始します。
インストールが始まります。「Install (インストール)」ボタンをクリックして使用許諾契約の条項に同意し、インストールを続行します。

Javaアプリケーションのサンプル（HelloWorld）

Java の　Hello World

class Hello {
  public static void main(String[] args) {
    System.out.println("Hello World!");
  }
}

chen-no-MacBook-Air:Workshop chen$ vi Hello.java
chen-no-MacBook-Air:Workshop chen$ javac Hello.java
chen-no-MacBook-Air:Workshop chen$ java Hello
Hello World!
chen-no-MacBook-Air:Workshop chen$

ブラウザで実行できるサービス

例えばちょっと○○言語触ってみたいなーと思ったとき、
環境を作る手間を考えて辞めてしまうことは割と多い。

統合開発環境(IDE)みたいにインストールするだけで使えます！とかならまだしも、
手動で環境変数を設定したり設定ファイル編集したりしなければならないとなると･･･

そんなときに使えるのがこのIdeone。
http://ideone.com/

ユーザ登録をしなくても使うことができる。
しかしユーザ登録をした方が間違いなく便利なのでオススメ。

ユーザ名とパスワード、メールアドレスだけで登録できる。
「I have read and agree to the Ideone Terms of use.」にチェックをいれること。

Processingのインストール

ProcessingはJava言語の機能をより簡単に使えるよう工夫されており，また開発環境から実行環境までがワンセットになっています。初心者が学習する言語として最適です。作成したプログラムは単独で動く実行ファイルに簡単に変換できます。これも大変魅力的です。

ダウンロード

Processing の公式サイト（http://processing.org/）を開き，メニューから DOWNLOAD をクリックします．Linux ，Mac OSX，Windows，Windows (without Java) というメニューがありますので、自分のPCに合わせてダウンロードしてください。

Windows版であれば，ダウンロードしたファイルを展開するだけです。展開したフォルダに入っているProcessingのアイコンをダブルクリックすれば開発環境が立ち上がります。展開したフォルダをMy Documentsなどのお好みの場所へ置いてください。USB へのセットアップすれば、自分の Windows PC 以外でも USB メモリを挿せば Processing プログラミング環境が利用できます。

Mac OS X 版はさらに簡単です。ダウンロードしたファイルをダブルクリックすれば開発環境が立ち上がります。ダウンロードしたファイルはアプリケーションフォルダにドラッグ＆ドロップしておきましょう。

Processing のサンプル（HelloWorld）

プログラミング学習の第一歩は，Hello World という文字列を画面に表示するのが一般的ですが，Processing は視覚的な表現が得意，具体的には図形（グラフィック）描画が得意なので，最初の一歩も図形を描画することをしてみます．

では，入力エリアに次の文字列を入力してください．

line( 0, 0, 100, 100 );

入力が終わったら，入力エリアの上にあるボタンのうち，一番左にある音楽再生ボタンのような絵柄のボタンをクリックしてください．小さなウィンドウが表示され，直線が描かれていると思います．ここでは，このウィンドウを 実行ウィンドウ と呼ぶことにます．

ブラウザで実行できるサービス

OpenProcessing（英語）http://www.openprocessing.org
- 編集ページ → http://www.openprocessing.org/sketch/create
- 解説ページ → OpenProcessing の新機能 create new sketch を試してみた
アプリケーションをインストールしていなくても、ブラウザさえ立ち上げれば気楽に試すことができる。
OpenProcessing に公開すれば、他のユーザーの評価を受けたり、ブログパーツとして利用することもできる。

練習問題

  1. 画面に適当な大きさの正方形を描くプログラムを作れ
  2. 画面に「田の字」を描くプログラムを作れ

作ったプログラムはProcessing のメニューの File ⇒ save で保存する。プログラムの名前を変更するときは save asを使う。保存先のフォルダが上で作ったものになっているのを確認すること。

1.Introduction

プログラミング言語

コンピュータ上で動くプログラムには様々な目的のために，様々な動きをするものがあります．その動きによって，プログラムの書きやすい書き方が異なります．そのために，これまで様々なプログラム言語が考え出されてきました．

プログラム言語の分類

プログラム言語を書き方の種類で分類すると，手続き型言語，関数型言語，論理型言語，オブジェクト指向言語に分けられます．

手続き型言語は，命令文を実行する順に並べます．その順を変えるには繰り返し文や分岐文などの制御構造を利用します．手続き型言語には FORTRAN や COBOL，PASCAL，C などがあります．

関数型言語は，関数を定義することで動作を指示するもので，LISP や ML が代表的な例です．

論理型言語は，形式論理，数理論理に基づいたプログラム言語で，事実を定義することである問題を解決することができます．論理型言語には Prolog などがあります．

オブジェクト指向言語は，データとそのデータに対する操作をまとめたオブジェクトの性質を定義することで動作を指示します．オブジェクト指向言語には Smalltalk，C++, Objective-C，Java などがあります．

上記の高水準プログラム言語を実行するためには，アセンブリ言語で書かれたプログラムを実行するためにアセンブラで機械語に変換するように，機械語に変換しなければなりません．この変換作業を行うプログラムを言語処理系と呼びます．代表的な言語処理系にはコンパイラとインタプリタがあります．

コンパイラ

コンパイラは高水準言語を機械語に変換して出力する言語処理系です．実際にはコンパイラはアセンブラ言語までの変換を行います．その後アセンブラによって機械語への変換を行います．また，アセンブラが作成するのはオブジェクトプログラムと呼ぶもので，実際に実行するためには実行時ライブラリと結合する必要があります．この結合にはリンカを利用します．市販されているプログラム開発環境では，コンパイラ，アセンブラ，リンカを意識することなく利用できるようになっています．

インタプリタ

インタプリタは高水準プログラム言語で書かれたプログラムを順次解釈しながら実行していきます．コンパイラの場合，実行するときには機械語にすべて変換してから実行するため，実行速度が速くなるメリットがあります．一方，プログラムを作るたびにコンパイラを使って変換しなければならないという面倒もあります．

Javaとは

◆Sun が開発したプログラミング言語

Java は、1995年頃に Sun Microsystems 社によって発表されたプログラミング言語です。プログラミング言語には他に BASIC、COBOL、FORTLAN、LISP、C、C++、JavaScript、Perl、PHP、Ruby などがあります。

◆オブジェクト指向プログラミングが可能

Java は、オブジェクト指向 的なプログラミングが可能な言語です。オブジェクト指向とは継承機能を持つクラスに基づいてインスタンスを生成することで記述性を高める・・・と言っても説明しきれないので、どこか別の場所で詳しく説明します。オブジェクト指向プログラミング言語には他に、Smalltalk、C++、C# などがあります。

◆ 中間コードへのコンパイル言語

プログラミング言語は、プログラムを逐次解析しながら実行する インタープリタ型言語 と、あらかじめマシン語コードに変換しておく コンパイル型言語 に大別されます。Java は基本的にはコンパイル型言語ですが、CPU に依存したマシンコードではなく、CPU に依存しない 中間コード にコンパイルするのが特徴です。

Processingとは

Processingは比較的新しいプログラミング言語だ。どのくらい新しいといって、正式版が公開されたのが2008年11月のこと。

◆Java を単純化したプログラミング環境

Processing は Java という言語をベースとしたオープンソースのプログラミング言語です．プログラムのソースコードを入力する，実行する，デバッグするというプログラミングの一連の作業を行うための一つのソフトウェアとして動くものですので，プログラミング環境といった方がよいかもしれません．公式サイトでも environment という語を使っています．

The syntax isn’t alien, actually, Processing code is Java code, just hiding some syntax points unnecessary to start a quick sketch (wrapping in a class, declaring a static main function to create the object from the class and call it, etc.).

Processing は Windows でも Mac でも Linux でも利用できること，作ったプログラムを，どのような OS でも動作する Java アプレットやプログラミング環境なしでも実行可能な形式に変換できることも大きな特徴です．

簡単に記述できるのですが、文法はJavaやC言語などと同じような形になっているので、プログラミング言語のアルゴリズムの学習に最適となっています。

◆視聴的な表現を得意

Processing は、　画像やアニメーションを用いた視聴的な表現を得意としています．そのため，対象者の中にアーティストやデザイナ，建築家が含まれています．また，Processing を対象とした書籍も，「ビジュアライジング・データ ―Processingによる情報視覚化手法」，「Built with Processing デザイン/アートのためのプログラミング入門」，「Processing: Creative Coding and Computational Art」など，視覚表現に関連したものが多くなっています．

ProcessingはJavaを単純化し、グラフィック機能に特化した言語といえる。

学習環境

Gmail account : https://mail.google.com/
Google Plus (Community) : https://plus.google.com/
Google Keep (Memo) : https://keep.google.com/
Java on Win/Mac : http://java.com/ja/download/
Processing on Win/Mac : http://processing.org/

参考サイト

Algorithms and Data Structures

授業概要

　ソートとコレクションを中心にアルゴリズムとデータ構造に関する基本を学習する。
Java言語によるプログラミング技術の基本事項を習得する。
特にアルゴリズムとデータ構造の理解を中心に、講義および演習を行う。

授業の到達目標

・オブジェクト指向言語の概念を理解するとともに、Javaを用いて課題を解決するスキルを身につける。
・アプリケーションの開発に必要な概念を理解するとともに、Java言語を用いて実用的なWebアプリケーションの開発が行えるようになる。

事前・事後学習の内容

予習としてMyWasedaに掲載するレジュメの事前読了を求めることがあります。各回の予習には90分～120分かかると想定されます。

授業計画

1:	本講義の目的と進め方について説明する。最終的に作成するアプリケーションの実例を説明する。
2:	基本概念を理解する。Javaのインストールからコマンドライン実行の方法を学ぶ。
3:	基本的なアルゴリズムを学ぶ。
4:	基本的なデータ構造を学ぶ。
5:	探索アルゴリズムを学ぶ。
6:	スタックとキューを学ぶ。
7:	再帰的アルゴリズムを学ぶ。
8:	ソートを理解する。
9:	集合を学ぶ。
10:	文字列探索を学ぶ
11:	線形リストを学ぶ
12:	木構造を学ぶ
13:	Webアプリケーション作成に必要な概念を理解する
14:	RESTアーキテクチャとJSON オブジェクトを学ぶ
15:	Webアプリケーション作成（コーディング・テスト、デバッグ、仕上げ）

教科書

「明解 Javaによるアルゴリズムとデータ構造」柴田望洋 (著)ソフトバンククリエイティブ (2007/11/7)

参考文献

「明解Java　入門編」柴田望洋 (著)ソフトバンククリエイティブ(2007/8/8)
「Javaによるはじめてのアルゴリズム入門」（河西朝雄著、技術評論社、2001年）

成績評価方法

割合		評価基準
レポート:	80％	与えられた課題に対する、プログラム、プログラムの説明、考察をレポートに書いてください。レポートの内容で評価することになります。
平常点評価:	20％	授業および課題に対する取り組みを総合して評価します。

Reference(jp)

「明解 Javaによるアルゴリズムとデータ構造」柴田望洋 (著)ソフトバンククリエイティブ (2007/11/7)
「明解Java　入門編」柴田望洋 (著)ソフトバンククリエイティブ(2007/8/8)
- http://bohyoh.com/Java/
「Javaによるはじめてのアルゴリズム入門」（河西朝雄著、技術評論社、2001年）
「標準Javaプログラミングブック」（河西朝雄著、技術評論社、2001年）
とほほのJava入門 (http://www.tohoho-web.com/java/index.htm )

Reference

【参考文献（英語）】

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/ — Algorithms and Data Structures Research & Reference Material
https://www.cs.auckland.ac.nz/software/AlgAnim/ppt/ — Data Structures and Algorithms, PowerPoint slides
https://www.cs.auckland.ac.nz/software/AlgAnim/ds_ToC.html — Data Structures and Algorithms, Table of Contents
https://www.cs.auckland.ac.nz/software/AlgAnim/ppt/ — Data Structures and Algorithms , PowerPoint Slides, 1998 Lectures
http://xlinux.nist.gov/dads/ — Dictionary of Algorithms and Data Structures ( http://hissa.ncsl.nist.gov/~black/)
http://student.seas.gwu.edu/~idsv/idsv.html — Interactive visualisations グラフなどのデータ構造を視覚化して表示（Mozilla Firefoxでは動作しない）