第３回 配列とリスト

Transcription

1 リストと配列 Algorithms and Data Structures on C

2 この回の要点 C 言語における変数 プリミティブ型とポインタの違い 参照型における実体オブジェクトへの参照 リストとは? 配列によるリスト 配列の利点と欠点 C 言語による配列の実現 配列の代入と複製の違い

3 データ構造 アルゴリズム + データ構造 = プログラム アルゴリズム データをどのように加工するか データ構造 データをどのように表現するか アルゴリズムと データ構造とは 互いに密接に関係している プログラムを書くとき アルゴリズムとデータ構造とを同時に考えていく必要がある 並べ替えアルゴリズムの場合 データの移動がほとんどないアルゴリズム 配列による表現 データの削除 挿入が頻繁にあるアルゴリズム リンクリストによる表現 どちらでも可能であるが 効率が問題

4 変数 変数 (variables) とは プログラム中で 値が変化するデータを格納する箱 1 つの箱に 1 つのデータを格納できる 箱にはいろいろな大きさがある ( 型 Type) 変数には名前をつける = 変数名 ( 識別子 ) x = 123 箱 変数名 pi = str = pt = p = Hello World (100,120) PersonalData 箱にはいろいろなデータが入っている

5 C 言語の基本型 ( プリミティブ ) 種類型長 signed unsigned 型なし void ーーー 文字型 char ~ ~ 255 整数型 浮動小数点型 short ~ ~ int ~ long ~ long long ~ float 32 double 64 最小の正の数 e-38 最大値 e+38 0 ~ ~ ~ 最小の正の数 e-308 最大値 e+308 ILP32( 一般的な 32 ビット環境 ) での例

6 ポインタ型 メモリへの参照を示す 参照するメモリのアドレスが格納されている 変数名の前に *( アスタリスク ) を付けた型 int *ip; double *dp; (* は変数名ではない ) アドレス幅 ip 参照 バイト dp 参照 バイト メモリ メモリ

7 プリミティブとポインタ プリミティブ int x = 実体 ( 値 ) 123 実体 ( オブジェクト ) double pi = int *ip = char *str = MyData *dp = ポインタ 参照参照参照実体への参照 Hello World 構造体

8 変数への代入 プリミティブ int x=123; double pi= ; 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() でメモリを解放すること!

9 構造体 いくつかのデータをまとめた型 キーワード struct で定義する タグ名を付ける 内部に複数の異なる型の変数を持つ 構造体の宣言の形 struct タグ名 { データ型メンバー名データ型メンバー名 }; 変数の宣言 struct タグ名変数名 ; メンバーへのアクセス (. か -> を使用 ) 変数. メンバー名ポインタ変数 -> メンバー名

10 構造体の例 1 #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);

11 構造体の例 2 #include <stdio.h> typedef struct { int x; int y; } MyPoint; タグ名は省略 構造体型の定義 typedef を使った場合 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);

12 抽象データ型とリスト (list) 抽象データ型とは データが持つ性質 + データに行える操作 クラス として表現される 中にどんなデータが入るかは関知しない リストとは 一般には 一覧表 目録 名簿 要素を順番に並べた構造を表す総称 データを一列に並べたもの 線形リスト リスト x の k 番目の要素 x[k] とすると それの 1 つ前 x[k-1] それの 1 つ後 x[k+1] 先頭の要素 x[1] 末尾の要素 x[n] (n 個の場合 ) 番号によって要素にアクセス可能 ( ただし C 言語の配列の添字は 0 から始まるので注意 )

13 抽象データ型としてのリスト リストのメンバ変数 そのリストに格納されているデータ リストが持つべきメソッド k 番目の要素の内容を読む 書く k 番目の要素の前に要素を挿入する k 番目の要素の後に要素を挿入する k 番目の要素を削除する 特定のキーを持つ要素を取り出す 複数のリストを 1 つにまとめる 1 つのリストを複数のリストに分割する リストを複製する リストの要素数を得る すべのメソッドを効率よく実現するリストは困難 必要に応じて どのメソッドを重視するかで データ構造が決まる

14 配列 (array) リストの実現の一種 1 たくさんの箱を一列に並べた構造 2 箱の数 ( 配列の大きさ ) は固定 3 配列を作るときに決める あとから変更はできない 箱には番号 ( 添え字 ) がつけられる N-1 0,1,2,,N-1(JavaやCの場合) 番号を使って 中のデータにアクセス可能 たくさんのデータを1つの名前 ( 配列名 ) で管理できる 多くのデータを扱うプログラムで有効 多次元配列 配列の添え字が2つ以上 0

15 配列の利点と欠点 利点 箱の番号を利用してデータに直接アクセスできる =O(1) データだけから構成され 無駄なメモリが不要 欠点 サイズが固定 途中に要素を挿入 削除する際 前後のデータを移動させる必要がある =O(N) 削除 N-1 挿入 後ろにずらす 前にずらす

16 C 言語の配列 1 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; 2 次元配列 int x[3][4]; // 3 行 4 列の2 次元行列 int y[][2]={{1,2},{3,4},{5,6}}; // 3 行 2 列 ( 実際には2 次元配列も1 次元として確保されている ) 注意 C 言語の配列のインデックスはチェックされない 初期化しなければ 何が入ってるかは不定

17 C 言語の配列 2 ポインタとしての配列 int *a=(int*)malloc(10*sizeof(int)); // 10 個の配列 MyPoint *pt=(mypoint*)malloc(5*sizeof(mypoint)); // 5 個の MyPoint の配列 配列へのアクセス 前ページの配列同様 [] でアクセスできる a 参照 配列変数 a[0] a[1] a[2] a[3]???? pt 参照 配列変数 pt[0] pt[1] pt[2] pt[3] MyPoint MyPoint MyPoint MyPoint a[9]? pt[4] MyPoint

18 ポインタの配列 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] 参照 (x,y) 実体 ( ヒープメモリ ) 配列自体の参照 pt[2] pt[3] pt[4] 2 段階の参照? 参照 参照 MyPoint 型の参照 (x,y) (x,y)

19 配列の代入と複製 配列の代入 参照だけが代入され その先は同じもの 配列の複製 ( コピー ) 配列の先は別々なオブジェクトとなる int a[5] 参照 a[0] a[1] a[2] a[3] a[4] b=a memcpy(c,a,sizeof(a)); int *b 参照 c[0] c[1] 5 14 int c[5] 参照 c[2] c[3] c[4] 別なメモリ

20 代入と複製の違い 代入と複製の違いを確認する 配列 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 のまま

21 ArrayTest.c 1. #include <stdio.h> 2. #include <stdlib.h> 3. #include <memory.h> 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. } 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: b: c: $

22 プログラムの作成方法 実際のプログラム ヘッダファイルと実装ファイルに分けて作る ヘッダファイル (.h) データ型 ( クラス ) の宣言 データ操作 ( 関数 ) のプロトタイプ宣言 実装ファイル (.cc) 関数の具体的なコード 拡張子.cc で書くことで コンパイラがソースコードを C++ として扱うようになる C++ 言語は C 言語の拡張 この講義では C 言語の機能だけを用いるが C++ として扱っておくと後々便利 ( かもしれない ) ということで 以下ではコンパイラとして g++ を用いる

23 ヘッダファイル ソースファイルを分割する手段 拡張子.h #include 文で読み込む プリプロセッサによる作業 標準ヘッダ <stdio.h> 自作ヘッダ hogehoge.h 目的 複数のソースで共通して使う場合 定義を書く場合 プロトタイプ宣言 関数の実体を書いてはいけない リンクエラーになる場合がある.h.h.h.cc.o #include コンパイル

24 コンパイルとリンク コンパイル.h と.cc から.o を作る 共通で使える.o を使う場合 規模が大きい場合 リンク.o から.exe を作る コンパイル & リンク.h と.cc から直接.exe を作る 規模が小さい場合はこれでもよい.o.o.o.exe リンク 具体例 : $ g++ o test1 test1.cc $./test1

25 成績型 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*) 成績の解放

26 Seiseki.h 1. #ifndef Seiseki h 2. #define Seiseki h 3. #include <stdio.h> ヘッダファイルの重複読み込みを回避 4. #include <stdlib.h> // データ型宣言 7. typedef struct { 8. const char *name; 9. int kokugo; 10. int sansuu; 11. int rika; 12. int shakai; 13. } Seiseki; // プロトタイプ宣言 16. Seiseki* makeseiseki(const char*,int,int,int,int); 17. void print(seiseki*); 18. void free(seiseki*); #endif // Seiseki h

27 Seiseki.cc 1. #include "Seiseki.h" // 成績の生成 ( コンストラクタ ) 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. } // 成績の表示 15. void print(seiseki *s){ 16. printf( %s 国 %d 算 %d 理 %d 社 %d n", Seiseki 型のメモリを確保し 中にデータを入れて 返す ヘッダファイルの読み込み 17. s->name,s->kokugo,s->sansuu,s->rika,s->shakai); 18. } // 成績の解放 21. void free(seiseki *s){ 22. free((void*)s); 23. }

28 TestSeiseki.cc 1. #include "Seiseki.h" 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); for(int i=0;i<3;i++) 10. print(s[i]); for(int i=0;i<3;i++) 13. free(s[i]); 14. } s s[0] s[1] s[2] 中村裕次郎 山田太郎 佐藤花子

29 データ構造の形 XXX という型を作る場合 : XXX.h 型宣言 プロトタイプ宣言 XXX.cc 関数の実装 AAA.cc で使う場合 g++ -o AAA AAA.cc XXX.cc

30 データ構造の形 XXX.h 1. #ifndef XXX h 2. #define XXX h 3. #include <stdio.h> 4. #include <stdlib.h> // データ型宣言 7. typedef struct { 8. int xx,yy; 9. } XXX; // プロトタイプ宣言 12. XXX* makexxx(int x,int y); 13. void print(xxx*); 14. void free(xxx*); #endif // XXX h XXX.cc 1. #include XXX.h" // XXXの生成 ( コンストラクタ ) 4. XXX* makexxx(int x,int y){ 5. XXX *s=(xxx*)malloc(sizeof(xxx)); 6. // return s; 8. } // XXXの表示 11. void print(xxx *s){ 12. // } // XXXの解放 16. void free(xxx *s){ 17. free((void*)s); 18. }

31 課題 TestSeiseki.cc をコンパイルして実行し 実行結果を示せ 次のページの TestSeiseki2.cc は ポインタ配列の代わりに二重ポインタをつかって 同じプログラムを書きなおしたものである このコードの不足分を埋めて完成させ 完成したコードと実行結果を示せ 作成方法 : ワードで作成し 実行結果は図として貼り付けること ファイル名は scxxxxxx-al docx 提出方法 : メールで渕田まで送付すること メールの本文中にも学籍番号を氏名を明記すること 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 厳守! 期限 :2018 年 10 月 21 日 ( 日 ) 24:00

32 TestSeiseki2.cc 1. #include "Seiseki.h" int main(){ ここを変えた 4. Seiseki **s; 5. /* ここにs 用のメモリを確保するコードを追加する */ 6. s[0]=makeseiseki(" 山田太郎 ",78,55,80,88); 7. s[1]=makeseiseki(" 佐藤花子 ",90,80,85,87); 8. s[2]=makeseiseki(" 中村裕次郎 ",40,62,72,21); for(int i=0;i<3;i++) 11. printseiseki(s[i]); for(int i=0;i<3;i++) 14. freeseiseki(s[i]); 15. /* ここにs 用のメモリを開放するコードを追加する */ 16. }

33 リストと配列 終了