この回の要点
• C言語における変数
– プリミティブ型とポインタの違い – 参照型における実体オブジェクトへの参照• リストとは？
• 配列によるリスト
– 配列の利点と欠点 – C言語による配列の実現 – 配列の代入と複製の違いデータ構造
• アルゴリズム＋データ構造＝プログラム
– アルゴリズム・・・データをどのように加工するか
– データ構造・・・データをどのように表現するか
• アルゴリズムと、データ構造とは、互いに密接に関
係している
– プログラムを書くとき、アルゴリズムとデータ構造とを同時
に考えていく必要がある
– 並べ替えアルゴリズムの場合
• データの移動がほとんどないアルゴリズム・・・配列による表現 • データの削除・挿入が頻繁にあるアルゴリズム・・・リンクリストに よる表現– どちらでも可能であるが、効率が問題
変数
• 変数（variables）とは
– プログラム中で、値が変化するデータを格納する箱 – １つの箱に、１つのデータを格納できる – 箱にはいろいろな大きさがある（型、Type）• 変数には名前をつける＝
変数名
（識別子）
123 3.141592 “Hello World” (100,120) PersonalData x = pi = str = pt = p = 箱 箱にはいろいろな データが入っている 変数名C言語の基本型（プリミティブ）
種類 型 長 signed unsigned 型なし void ー ー ー 文字型 char 8 -128 ~ 127 0 ~ 255 整数型 short 16 -32768 ~ 32767 0 ~ 65535 int 32 -2147483648 ~ 2147483647 0 ~ 4294967295 long 32 -2147483648 ~ 2147483647 0 ~ 4294967295 long long 64 -9223372036854775808 ~ 9223372036854775807 0 ~ 18446744073709551615 浮動小 数点型 float 32 最小の正の数1.175494351e-38 最大値3.402823466e+38 double 64 最小の正の数2.2250738585072014e-308 最大値1.7976931348623158e+308 ILP32（一般的な32ビット環境）での例ポインタ型
• メモリへの参照を示す • 参照するメモリのアドレスが格納されている • 変数名の前に＊（アスタリスク）を付けた型 – int *ip; – double *dp; （＊は変数名ではない） 4バイト 8バイト 参照 参照 アドレス幅 メモリ メモリ 123 3.14 ip dpプリミティブとポインタ
123 3.141592 123 “Hello World” 構造体 int x = double pi = int *ip = char *str = MyData *dp = 参照 実体への参照 実体 （オブジェクト） 実体（値） 参照 参照 プリミティブ ポインタ変数への代入
• プリミティブ
int x=123; double pi=3.141592; MyPoint pt={3,4};• ポインタ
int *ip=&x; double *dp=πconst char *str=“Hello World”;
int *data=(int*)malloc(100*sizeof(int)); MyPoint *pt1=(MyPoint*)malloc(sizeof(MyPoint)); プリミティブには直接数値を代入 プリミティブのアドレスを代入 malloc() を使用 free()でメモリを解放すること！ 構造体の初期化
構造体
• いくつかのデータをまとめた型
– キーワード
struct
で定義する
– タグ名
を付ける
– 内部に複数の異なる型の変数を持つ
– 構造体の宣言の形
struct タグ名 { データ型 メンバー名 データ型 メンバー名 ・・・ };– 変数の宣言
struct タグ名 変数名;– メンバーへのアクセス（.か->を使用）
変数.メンバー名 ポインタ変数->メンバー名構造体の例１
#include <stdio.h> struct MyPoint { int x; int y; }; int main(void){ struct MyPoint pt1; struct MyPoint pt2={ 3,4 };struct MyPoint *pt3=&pt2;
printf(“(%d,%d)¥n”,pt1.x,pt1.y); printf(“(%d,%d)¥n”,pt2.x,pt2.y); printf(“(%d,%d)¥n”,pt3->x,pt3->y); } 構造体タグの宣言 構造体タグを使って 変数を宣言 初期化
構造体の例２
#include <stdio.h> typedef struct { int x; int y; } MyPoint; int main(void){ MyPoint pt1; MyPoint pt2={ 3,4 }; MyPoint *pt3=&pt2; printf("(%d,%d)¥n",pt1.x,pt1.y); printf("(%d,%d)¥n",pt2.x,pt2.y); printf("(%d,%d)¥n",pt3->x,pt3->y); } 構造体型の定義 構造体型を使って 変数を宣言 typedefを使った場合 タグ名は省略抽象データ型とリスト（list）
• 抽象データ型とは
– データが持つ性質＋データに行える操作
– 「クラス」として表現される
– 中にどんなデータが入るかは関知しない
• リストとは
– 一般には、一覧表、目録、名簿
– 要素を順番に並べた構造を表す総称
• データを一列に並べたもの→線形リスト • リスト x の k 番目の要素→ x[k] とすると、 • それの1つ前→ x[k-1] • それの1つ後→ x[k+1] • 先頭の要素→ x[1] • 末尾の要素→ x[n] （n個の場合） 番号によって 要素にアクセス可能 （ただし、C言語の配 列の添字は0から始 まるので注意）抽象データ型としてのリスト
• リストのメンバ変数
– そのリストに格納されているデータ• リストが持つべきメソッド
– k番目の要素の内容を読む・書く – k番目の要素の前に要素を挿入する – k番目の要素の後に要素を挿入する – k番目の要素を削除する – 特定のキーを持つ要素を取り出す – 複数のリストを1つにまとめる – 1つのリストを複数のリストに分割する – リストを複製する – リストの要素数を得る – ・・・• すべのメソッドを効率よく実現するリストは困難
– 必要に応じて、どのメソッドを重視するかで、データ構造が決まる配列（array）
• リストの実現の一種
• たくさんの箱を一列に並べた構造
– 箱の数（配列の大きさ）は固定
• 配列を作るときに決める • あとから変更はできない– 箱には番号（添え字）がつけられる
• 0,1,2,・・・,N－1（JavaやCの場合）– 番号を使って、中のデータにアクセス可能
• たくさんのデータを１つの名前（配列名）で管理できる • 多くのデータを扱うプログラムで有効• 多次元配列
– 配列の添え字が２つ以上
0 1 2 3 N－1配列の利点と欠点
• 利点
– 箱の番号を利用してデータに直接アクセスできる＝
O(1)
– データだけから構成され、無駄なメモリが不要
• 欠点
– サイズが固定
– 途中に要素を挿入、削除する際、前後のデータを移動さ
せる必要がある＝
O(N)
0 1 2 3 ・・・ N-1 挿入 後ろにずらす 削除 前にずらすC言語の配列１
• C言語の配列は連続するメモリ領域（＝ポインタ）
• 変数名に[ ]をつけて宣言する
int a[10]; // 10個の箱を持つ配列変数a int b[5]={1,2,3,4,5}; // 初期化 int c[]={1,2,3}; // 初期化すればサイズは不要
• 配列要素へのアクセス
a[0]=3; a[9]=123;• ２次元配列
int x[3][4]; // ３行４列の２次元行列 int y[][2]={{1,2},{3,4},{5,6}}; // ３行２列 （実際には２次元配列も１次元として確保されている）• 注意
– C言語の配列のインデックスはチェックされない – 初期化しなければ、何が入ってるかは不定C言語の配列２
• ポインタとしての配列
int *a=(int*)malloc(10*sizeof(int)); // 10個の配列 MyPoint *pt=(MyPoint*)malloc(5*sizeof(MyPoint)); // 5個のMyPointの配列• 配列へのアクセス
– 前ページの配列同様、[]でアクセスできる ? ? ? ? ? a[0] a[1] a[2] a[3] a[9] MyPoint pt[0] 参照 a pt 参照 配列 変数 配列 変数 MyPoint pt[1] MyPoint pt[2] MyPoint pt[3] MyPoint pt[4]ポインタの配列
• MyPointクラスの
ポインタの配列
MyPoint **pt=(MyPoint**)malloc(5*sizeof(MyPoint*)); pt[1]=(MyPoint*)malloc(sizeof(MyPoint)) // 実体 pt[3]=(MyPoint*)malloc(sizeof(MyPoint)); pt[4]=(MyPoint*)malloc(sizeof(MyPoint)); 参照 pt ? 参照 ? 参照 参照 pt[0] pt[1] pt[2] pt[3] pt[4] (x,y) (x,y) (x,y) 実体 （ヒープメモリ） 配列自体 の参照 MyPoint 型の参照 ２段階の参照別なメモリ
配列の代入と複製
• 配列の
代入
– 参照だけが代入され、その先は同じもの• 配列の
複製（コピー）
– 配列の先は別々なオブジェクトとなる 参照 int a[5] 5 14 3 8 4 a[0] a[1] a[2] a[3] a[4] 参照 int *b 5 14 3 8 4 c[0] c[1] c[2] c[3] c[4]b=a
memcpy(c,a,sizeof(a)); 参照 int c[5]代入と複製の違い
• 代入と複製の違いを確認する
– 配列 a を { 5,14,3,8,4 } で初期化 – a を配列 b に代入 – a を配列 c に複製 – a と b , c を表示 – a の2番目 a[1] の 14 を 99 に変更 – a と b , c を表示• 結果
– 代入・・・b[1] は 99 に変わる – 複製・・・c[1] は 14 のままArrayTest.c
1. #include <stdio.h> 2. #include <stdlib.h> 3. #include <memory.h> 4.
5. void printArray(char c,int *a,int s){ 6. printf("%c: ",c); 7. int i; 8. for(i=0;i<s;i++) 9. printf("%d ",a[i]); 10. printf("¥n"); 11. } 12. 13. int main(void){ 14. int a[5]={5,14,3,8,4}; 15. int *b=a; 16. int c[5]; 17. memcpy(c,a,sizeof(a)); 18. a[1]=99; 19. printArray('a',a,5); 20. printArray('b',b,5); 21. printArray('c',c,5); 22. }
$ gcc –o ArrayTest ArrayTest.c $ ./ArrayTest.exe a: 5 99 3 8 4 b: 5 99 3 8 4 c: 5 14 3 8 4 $ 実行結果：
プログラムの作成方法
• 実際のプログラム
– ヘッダファイルと実装ファイルに分けて作る
• ヘッダファイル（.h）
– データ型（クラス）の宣言
– データ操作（関数）のプロトタイプ宣言
• 実装ファイル（.cc）
– 関数の具体的なコード
– 拡張子.ccで書くことで、コンパイラがソースコードをC++として
扱うようになる
– C++言語はC言語の拡張
– この講義ではC言語の機能だけを用いるが、C++として扱って
おくと後々便利（かもしれない）
– ということで、以下ではコンパイラとして
g++
を用いる
ヘッダファイル
• ソースファイルを分割する手段
• 拡張子 .h
• #include文で読み込む
– プリプロセッサによる作業
– 標準ヘッダ <stdio.h>
– 自作ヘッダ “hogehoge.h”
• 目的
– 複数のソースで共通して使う場合
– 定義を書く場合
– プロトタイプ宣言
– 関数の実体を書いてはいけない
• リンクエラーになる場合がある.cc
.h
.h
.h
.o
コンパイル #includeコンパイルとリンク
• コンパイル
– .hと.ccから.oを作る
– 共通で使える.oを使う場合
– 規模が大きい場合
• リンク
– .oから.exeを作る
• コンパイル＆リンク
– .hと.ccから直接.exeを作る
– 規模が小さい場合はこれでもよい
.o
.o
.o
.exe
リンク$ g++ –o test1 test1.cc $ ./test1
成績型Seiseki
• 小学生の1回の試験の成績
– 名前と国語、算数、理科、社会の点数
– 成績の生成と表示ができる
メンバー
const char* name 名前
int kokugo 国語の点数
int sansuu 算数の点数
int rika 理科の点数
int shakai 社会の点数
関数
Seiseki* makeSeiseki(const char*,int,int,int,int) 成績の生成 void print(Seiseki*) 成績の表示 void free(Seiseki*) 成績の解放
Seiseki.h
1. #ifndef __Seiseki__h 2. #define __Seiseki__h 3. #include <stdio.h> 4. #include <stdlib.h> 5. 6. // データ型宣言 7. typedef struct { 8. const char *name; 9. int kokugo; 10. int sansuu; 11. int rika; 12. int shakai; 13. } Seiseki; 14. 15. // プロトタイプ宣言16. Seiseki* makeSeiseki(const char*,int,int,int,int); 17. void print(Seiseki*);
18. void free(Seiseki*); 19.
20. #endif // __Seiseki__h
Seiseki.cc
1. #include "Seiseki.h"
2.
3. // 成績の生成（コンストラクタ）
4. Seiseki* makeSeiseki(const char *n,int k,int m,int r,int h){ 5. Seiseki *s=(Seiseki*)malloc(sizeof(Seiseki)); 6. s->name=n; 7. s->kokugo=k; 8. s->sansuu=m; 9. s->rika=r; 10. s->shakai=h; 11. return s; 12. } 13. 14. // 成績の表示 15. void print(Seiseki *s){ 16. printf(“%s 国%d 算%d 理%d 社%d¥n", 17. s->name,s->kokugo,s->sansuu,s->rika,s->shakai); 18. } 19. 20. // 成績の解放 21. void free(Seiseki *s){ 22. free((void*)s); 23. } ヘッダファイルの読み込み Seiseki型のメモリを確保し、 中にデータを入れて、返す
TestSeiseki.cc
1. #include "Seiseki.h" 2. 3. int main(){ 4. Seiseki *s[3]; 5. s[0]=makeSeiseki("山田太郎",78,55,80,88); 6. s[1]=makeSeiseki("佐藤花子",90,80,85,87); 7. s[2]=makeSeiseki("中村裕次郎",40,62,72,21); 8. 9. for(int i=0;i<3;i++) 10. print(s[i]); 11. 12. for(int i=0;i<3;i++) 13. free(s[i]); 14. } s s[0] s[1] s[2] “山田太郎” 78 55 80 88 “佐藤花子” 90 80 85 87 “中村裕次郎” 40 62 72 21データ構造の形
• XXXという型を作る場合：
• XXX.h
– 型宣言
– プロトタイプ宣言
• XXX.cc
– 関数の実装
• AAA.ccで使う場合
– g++ -o AAA AAA.cc XXX.cc
データ構造の形
1. #ifndef __XXX__h 2. #define __XXX__h 3. #include <stdio.h> 4. #include <stdlib.h> 5. 6. // データ型宣言 7. typedef struct { 8. int xx,yy; 9. } XXX; 10. 11. // プロトタイプ宣言12. XXX* makeXXX(int x,int y); 13. void print(XXX*); 14. void free(XXX*); 15. 16. #endif // __XXX__h 1. #include “XXX.h" 2. 3. // XXXの生成（コンストラクタ）
4. XXX* makeXXX(int x,int y){
5. XXX *s=(XXX*)malloc(sizeof(XXX)); 6. // ... 7. return s; 8. } 9. 10. // XXXの表示 11. void print(XXX *s){ 12. // ... 13. } 14. 15. // XXXの解放 16. void free(XXX *s){ 17. free((void*)s); 18. } “XXX.h” “XXX.cc”
