◇下へ・上へ ○配列 添字つき変数 同じ型の変数をメモリ内の連続した場所に並べたもの 番号で順に取り扱える。個々の変数を配列要素と呼ぶ。 ( 添字 subscript ) 配列の宣言 int a[10]; 10個の整数変数を並べた配列 C では a[0]からa[9]が扱える (Pascal では a[1] から a[10]) double b[101]; 101個の double 変数を並べた配列
◇下へ・上へ これまでは、テキストの Pascal に合わせて、 配列の要素 0 を使わないでいた。 (C言語での添字の使い方)
◇下へ・上へ 2次元配列 添字が二つある配列 C や Pascal では、「配列の配列」と考える。 int a[3][2]; 整数2個の配列を三つ並べたもの (メモリ中の順番 a[0][0] a[0][1] a[1][0] a[1][1] a[2][0] a[2][1])
◇下へ・上へ 構造体 異なる(かもしれない)型のデータをメモリ内の連続 した場所に並べてある。要素に名前をつけて指定する。 C では struct ( Pascal では record ) 構造体の宣言 struct タグ名 { 型名1 メンバー名1; 型名2 メンバー名2; ... 型名3 メンバー名3; }; 構造体変数の宣言; struct タグ名 変数名1,変数名2; 構造体配列変数の宣言; struct タグ名 配列名1[大きさ]; ◇下へ・上へ 使い方 これまでの 変数の代わりに 構造体変数名のあとにピリオド「.」で区切って メンバー名をつける。 「構造体変数名.メンバー名」
◇下へ・上へ 例1 学生記録用構造体の宣言例 struct gakusei{ int id; /* 学籍番号 */ char name[100]; /* 名前100 文字分(英字換算) */ double shiryoku_r, shiryoku_l; /* 視力(右と左) */ }; 学生記録用配列の宣言例 struct gakusei students[200];
◇下へ・上へ 例2 2次元平面内の点(平面ベクトル) struct point2d { double x, y; }; 三角形 struct triangle { struct point2d a, b, c; }
◇下へ・上へ 例3 複素数 C では、複素数を直接に扱うことはできないので、 構造体を利用して表現する場合が多い。 複素数構造体宣言例 struct complex { double re, im; }; /* re を実部 imを虚部とする */ complex はプログラム作成者が、任意につけた名前であり、 したがって、実際の意味づけはプログラム作成者が行なう。 このように定義したからといって、複素数の演算が行なえる わけではない。 複素数構造体変数の宣言例 struct complex z1, z2, z3, zi; (複素数の演算プログラム)
◇下へ・上へ ○テキスト 6章(ただし、データ構造についてのみ)
データ構造 データ単独ではなくデータとデータの関係の表現
○スタック stack 入れた逆順に取り出す First In Last Out 基本操作 Push データを入れる Pop データを取り出す ○キュー queue 待ち行列 First In First Out FIFO 順番は維持 基本操作 リングバッファ( 入れる 出す ) 使用例 ウインドウシステム(X端末)のキー入力、マウス入力など Unix のプリンタ制御 マルチタスクでの仕事の切換え
◇下へ・上へ ○リスト 説明 「いもづる」式 ある要素が次の要素の記憶場所を保持することにより 一連の要素をメモリ中の不連続な位置に格納する。 特徴 挿入 / 削除 が容易 「n番目」を調べるに手間がかかる struct node { double data; int next;};
○リストのプログラミング例
( 双方向リスト:前の要素位置も保持することで、両方向にたどれる
struct node { double data; int next, prev;}; )
◇下へ・上へ ○ツリー 木が枝分れするように複数の方向に分岐しているリスト 枝分れが二つ 2進木 binary tree 例 lisp ( emacs mule の内部で使われている ) 数式の表現(解析) モールス符号の解読 データ圧縮に用いられる可変長符号の表現
◇下へ・上へ ○演習・レポート課題(解答) 1. 配列の要素の操作についての以下のプログラムを作れ。 double a[10], b[10]; 1) 配列 a の全要素を 配列 b にコピーする。 2) 配列 a の 0 から 8 の要素の内容を同じ配列 a の 1 から 9 の要素に それぞれコピーする。 注意：手順をうまく考えないと全部同じになる 2. 次に示すプログラムについて以下の課題を行なえ。 a) このプログラムを実行し、リスト構造のデータの順番を表示せよ。 b) data メンバーの値が昇順に表示されるように、プログラムの 「データの代入」の root および、各 next メンバーの代入部分の データのみを直接変えよ。 (プログラムを実行して確認する。) c) リストを順にたどって data メンバーの総和を求めるプログラム を作り実行せよ。 ◇下へ・上へ #include <stdio.h> #define N 100 main() { struct node{ double data; int next; }; struct node node[N];/* 構造体タグ名と配列名はこの例のように、*/ int root; /* 同じでも良いし、異なっていてもよい */ int p; /* ◇一覧へ・上へ */ /* データの代入 */ root=3; node[0].data=5.8409 ; node[0].next=2; node[1].data=3.90478 ; node[1].next=8; node[2].data=6.91004 ; node[2].next=9; node[3].data=8.40485 ; node[3].next=5; node[4].data=8.57378 ; node[4].next=7; node[5].data=3.18693 ; node[5].next=0; node[6].data=6.04144 ; node[6].next=1; node[7].data=8.46476 ; node[7].next=-1; node[8].data=2.98526 ; node[8].next=4; node[9].data=1.63546 ; node[9].next=6; p=root; while( p != -1 ){ printf("%g\n", node[p].data ); p=node[p].next; } exit(1); }