配列（array）

• 配列とはオブジェクトの並びをいう
• その要素（成分）が何番目か？というインデックス（添字）を用いて、 どのデータにも直接アクセス（参照）できる
• インデックスの範囲（配列の大きさ）に注意する必要がある
  
• リスト（list）や集合（set）を表現することができる
  • リスト（list）$q=[\,x_1,x_2,\dots,x_n\,]$ は任意の要素の一連
  • 集合（set）$s=\{x_1,x_2,\dots,x_n\}$ は異なる要素の集まり

• データ構造に対する基本的な操作には以下のものがある
  • アクセス（Access）
    特定（インデックスで指定、先頭、末尾）の要素を参照する
  • 挿入（Insert）
    新たなデータを特定の場所（インデックスで指定、先頭、末尾など）に挿入する
  • 探索（Find, Search）
    指定されたデータを探索する
  • 削除（Delete）
    指定されたデータや特定（インデックスで指定、先頭、末尾）の要素を削除する

Ｃの配列（array）

• Ｃの配列のインデックスは０から始まる
  
• 固定長である：扱うデータ数の上限で宣言しておかなければならない！

  /* 配列の宣言
  	型 配列名[要素数]; */
  
  	int	x[10];
  
  /* 配列の参照：配列名[インデックス]
  	配列名[0], 配列名[1], 配列名[2], ..., 配列名[要素数-1]; */
  
  	x[0], x[1], x[2], ..., x[9];
  

配列（unordered array）

/* 配列データ */
	int data[15] = { 123, 106, 777, 580, 216, 136, 800, 351, 103, 197 };
/* データの個数 */
	int datanum = 10;

　準備

　挿入（Insert）

• 新たなデータを最後に挿入する(⇒図)
  データの数を覚えていれば、挿入は速い！
  ●データを最後に挿入する（例えば、当初の配列の大きさを越えて挿入できない場合は-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int insert( int n );
  
• 新たなデータを最初に挿入する（その２）(⇒図)
  データを１個ずつ後にずらしてから...だから遅い！
  ●データを最初に挿入する（例えば、当初の配列の大きさを越えて挿入できない場合は-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int inserth( int n );
  

　探索（Search）

• 指定されたデータを検索する
  
• 最初から順番に調べて行き、最悪の場合は、全てのデータを調べる必要がある
  この方法を線形探索（linear search）と呼ぶ。(⇒図)
  ●データを検索する（例えば、見つかったらそのインデックスを返し、見つからなければ-1を返す）関数を作成し、キー入力したデータを検索してみよう
  int search( int n );
  

　削除（Delete）

• 指定されたデータを削除する
  削除して空いた場所をどうする！？
  • 最後のデータを移動する(⇒図)
  • 後のデータを１個ずつずらす(⇒図)
  ●与えられたインデックスのデータを削除する関数を作成し、キー入力したデータを検索して削除してみよう
  void delete( int i );
  

　最小値（Minimum）／最大値（Maximum）

• 最小値／最大値を求める
  最初のデータを仮の最小値／最大値とし、順番に調べて行き、
  それより小さい／大きいデータがあれば、仮の値を更新し、最後まで調べる
  ●最小値（例えば、見つかったらそのインデックスを返す、見つからなければ-1を返す）関数を作成し、最小値を表示してみよう
  int minimum();
  ●最大値（例えば、見つかったらそのインデックスを返す、見つからなければ-1を返す）関数を作成し、最大値を表示してみよう
  int maximum();
  

順序配列（ordered array）

• 順序配列（ordered array）とは、ある基準（キーという）で順に並んでいる配列である
  ソート済み配列とも呼ばれる

/* 配列データ */
	int data[15] = { 106, 123, 136, 197, 216, 229, 351, 580, 700, 777 };
/* データの個数 */
	int datanum = 10;

　挿入（Insert）

• 新たなデータを順序を守って挿入する
  その場所以降にあったデータは１個ずつずらす(⇒図)
  ●データを挿入する（例えば、当初の配列の大きさを越えて挿入できない場合は-1を返す）関数を作成し、キー入力したデータを挿入してみよう
  int insert( int n );
  

　探索（Search）

• 指定されたデータを検索する
  未ソート配列よりも探索は高速！
  ●順番に並んでいることを利用して、データを検索する（例えば、見つかったらそのインデックスを返し、見つからなければ-1を返す）関数を作成し、キー入力したデータを検索してみよう
  int search( int n );
  
• データを２分し、中央データとの大小判定により、探索データが属している半分を見極め、
  その半分のデータをさらに２分して探し、これを繰り返す。
  この方法を二分探索（binary search）と呼ぶ。(⇒図)

　削除（Delete）

• 指定されたデータを削除する
  その場所以降にあったデータは１個ずつずらす(⇒図)
  ●与えられたインデックスのデータを削除する関数を作成し、キー入力したデータを検索して削除してみよう
  void delete( int i );
  

　最小値（Minimum）／最大値（Maximum）

• 最小値／最大値を求める
  最初or最後のデータ！
  ●最小値（例えば、見つかったらそのインデックスを返す、見つからなければ-1を返す）関数を作成し、最小値を表示してみよう
  int minimum();
  ●最大値（例えば、見つかったらそのインデックスを返す、見つからなければ-1を返す）関数を作成し、最大値を表示してみよう
  int maximum();