1 データ構造とアルゴリズム 第 3 回 配列，構造体，ポインタ ～ データ構造について学ぶための基礎～

Presentation on theme: "1 データ構造とアルゴリズム 第 3 回 配列，構造体，ポインタ ～ データ構造について学ぶための基礎～"— Presentation transcript:

1 1 データ構造とアルゴリズム 第 3 回 配列，構造体，ポインタ ～ データ構造について学ぶための基礎～

2 2 前回の解答 問題１．次のうち、計算量が一番大きいものはどれ か O(1), O(n), O(n 2 ), O(n log n) 問題２．計算量が一番小さいものはどれか O(log n), O(n 3 ), O(n log n), O(n) 問題３．計算量の大きいものから順に並べなさい O(n 3 ), O(nlogn), O(n), O(logn), O(1)

3 3 得点分布 0729 ： 14 17 20 0729 ： 14 16 17 20 27 31 33 34 39 49 56 72 73 81 0729 ： 17 18 20 31 37 39 67 81 062906 062957 062914 052908 設問３不正解 設問２不正解 設問１不正解

4 4 講義資料 http://www.ced.is.utsunomiya-u.ac.jp/lecture/2008/ds/ 但し虫食い版 できるだけ火曜日夕方までに用意したいと思っているが、 水曜日未明になることも予想される。 水曜日 2 コマよりちょっと早めに来て確認し、印刷して、 授業中に書き込むのを勧める

5 5 配列（ array ） 同じ型の要素の集合 各要素はメモリ上に同じサイズで連続して格納さ れる 添え字 ( インデクス ) を指定することで，要素にラ ンダムにアクセス可能 170 160 158 173 data[0] data[1] data[2] data[3] 個々のセルに整数型の 要素が格納されている． 100 ： 104 ： 108 ： アドレス メモリ

6 6 ランダムアクセス (random access) 使いたいデータにすぐアクセスできること CD プレーヤは聴きたい曲にランダムアクセス可能 cf) カセットテープは聴きたい曲を前から順に探す必要が ある ⇒シーケンシャルアクセス (sequential access) 例） 170 160 158 173 data[0] data[1] data[2] data[3] アドレス メモリ 100 ： 104 ： 108 ： 112 ： y = data[2];

7 7 ランダムアクセス (random access) 使いたいデータにすぐアクセスできること CD プレーヤは聴きたい曲にランダムアクセス可能 cf) カセットテープは聴きたい曲を前から順に探す必要が ある ⇒シーケンシャルアクセス (sequential access) 例） 170 160 158 173 data[0] data[1] data[2] data[3] アドレス メモリ 配列名 添字 （インデクス， index ） 100 ： 104 ： 108 ： 112 ： y = data[2];

8 8 配列を扱うときの注意点 C 言語による配列の宣言例 doubleheight[MAX]; intdata[4]; 170 160 158 173 アドレス data[0] data[1] data[2] data[3] C C の場合は添字が必 ず０から始まる！ 100 ： 104 ： 108 ： 112 ： メモリ

9 9 各部の計算量は？ int printData(int n, int data[]) /* data の要素数は n とする */ { int i, j; for (i=0; i<n; i++) printf(“%d\n”, i); for (i=0; i<n; i++) printf(“%d \n”, data[i]); for (j=0; j<n; j++){ for (i=0; i<n; i++){ printf(“i*j は %d \n”, i*j); } return 0; } O(n) O(n 2 ) O(n)+O(n)+O(n 2 ) → O(n 2 )

10 10 異なる型のデータをまとめて扱うに は？ 配列は同じ型のデータの集まり 文字列と数値など，異なる型のデータをまとめる にはどうしたらよいだろうか？ 名前は文字列で 表現しよう 身長は整数型？ 実数型？ ４名分のデータの集 合をどう表わそう？ １名分のデータを まとめて管理でき ると便利だな 青木 177 小田 158 金子 167 佐藤 174

11 11 構造体（ Structure ） (C 言語 ) さまざまな型をもつデータをまとめた もの ※「構造体」は C 言語特有の呼び名． ※一般には，「レコード構造（ record structure ）」と呼ばれる． cf.) PASCAL → レコード型 nam e heigh t メンバー 文字型配列 整数型

12 12 構造体宣言の例 struct STUDENT { char name[10]; int height; } st1, st2 ; 構造体タグ ｛｝内で定義する構造体の名 前 メンバー (member) STUDENT 型の変数の定義 STUDENT 型 nam e heigh t nam e heigh t 変数 st1 変数 st2

13 13 メンバーの参照 ※ （構造体型の変数の名前）. （メンバー名）で表 わせる st1.name = aoki; st1.height = 177; st2.name = oda; st2.height = 158; STUDENT 型 177 a o k i 158 o d a 変数 st1 変数 st2 ドット演算子（. 演算子，.operator ） nam e heigh t nam e heigh t

14 14 同じ型の構造体を並べて配列を作ることができ る struct STUDENT { char name[10]; int height; } ; struct STUDENT stData[4]; STUDENT 型構造体の 配列 構造体の配列 青木 177 小田 158 金子 167 佐藤 174 stData[0] stData[1] stData[2] stData[3] STUDENT 型 ４名分のデータ をまとめて扱え る！

15 15 配列の短所 データの数をあらかじめ宣言する必要がある データを格納するための領域を自由に追加したり、 不要になったら領域を開放したい … どうする？ ⇒ ポインタを利用 int a[3];

16 16 ポインタ（ pointer ）とは 変数を指し示すためのデータ型 他のデータへの参照を示す（他のデータが ある場所の番地が格納される） ポインタ型がある言語 C, PASCAL cf.) ポインタ型がない言語 BASIC, FORTRAN

17 17 ポインタ ポインタ型変数 ptr アドレス n １０４番地 : メモリ空 間 ptr ８０番地 : 「 ptr は n を指している 」 とは？ int 型変数 n

18 18 ポインタとアドレス アドレス ５０ １０４番地 : メモリ空 間 １０４番地 ８０番地 : 変数 n のデータが入っ ているメモリ上のア ドレスが格納される ポインタ型変数 ptr int 型変数 n

19 19 ポインタ型変数宣言の例 int n; int *ptr; n = 50; ptr = ＆ n; アドレス演算子 （単項 & 演算子， &operator ） データが格納されているアドレスを 取り出す演算子 ← n は int 型の変数 ← ptr は int 型の変数を指すポインタ変数 ポインタであることを表わす記号 （ “ アスタリスク ” という）

20 20 ポインタ型変数宣言の例 int n; int *ptr; n = 50; ptr = ＆ n; ptr n 104 番地 :80 番地 : 50 104 番地 :80 番地 : 104 番地 50 104 番地 :80 番地 :

21 21 参考）間接演算子 int n; int *ptr; n = 50; ptr = ＆ n; printf(“ptr が指しているものの中身は %d” ， *ptr); ptr 104 番地 : 104 番地 間接演算子 （ indirect operator ） ptr が n を指すとき， *ptr は n の別名（エイリアス）となる n ５０ 先ほどの＊とは意味 が異なるので注意

22 22 参考 ) C 言語におけるポインタの使い 方 データ構造としてのポイン タ 参照渡しのためのポインタ 配列参照のためのポインタ void exsample1 (int a, int b, int *sum, int * diff) { *sum = a + b; *diff = a - b; } int a[5]; int i; for (i = 0; i < 5; i++) { a[i] = a[i] + 3; } int a[5]; int *p; for (p = a; p < a+5; p++) { *p = *p + 3; }

23 23 ポインタ図示の例 ポインタ ｐｔｒ 整数型変数 ポインタ ｔ ｍｐ 構造体 （ﾚｺｰﾄﾞ型変数） データ構造を図示するときは，ポインタは矢印を 使って表現される データ構造として見る場合は，ポインタがどのデ ータを指しているかが重要 （ポインタに入って いるアドレス値そのものは意識しなくて良い）

24 24 プログラム例 #include /*------------ ITEM 型構造体の型定義 ------------*/ struct ITEM { int data; /* 整数値 */ struct ITEM *next; /* 次の ITEM 型構造体へのポインタ */ }; /*------------ メイン部 ------------------------*/ int main(void) { struct ITEM *ptr; /* ITEM 型構造体へのポインタ変数．変数名は ptr */ ptr = (struct ITEM*)malloc(sizeof(struct ITEM)); /* メモリ確保 */ (*ptr).data = 100; (*ptr).next = NULL; free(ptr); /* メモリ解放 */ return 0; }

25 25 解説 ITEM 型構造体の型定義 struct ITEM { int data; struct ITEM *next; } ; ITEM 型構造体は， int 型のデータが入る箱と ITEM 型構造体へのポインタが入る箱から成る int 型の箱の名前（メンバー名）は data ポインタ型の箱の名前は next ITEM 型 int 型 ポインタ型 data next

26 26 変数の定義 struct ITEM *p ｔｒ ; struct ITEM 型構造体変数のアドレス を入れる箱（ポインタ変数 ptr ）を用 意 この時点では，箱の中身は不定 ？ ptr

27 27 メモリ領域の確保 ptr = (struct ITEM*)malloc(sizeof(struct ITEM)); struct ITEM 型構造体変数を入れるための箱 （メモリ領域）を確保． 箱のサイズは ITEM 型構造体の大きさ． その箱のアドレスを ptr に入れる. ptr ？？

28 28 データの代入 (*ptr).data = 100; (*ptr).next = NULL; ptr の指すもののメンバー data に 100 を代入 ptr の指すもののメンバー next に NULL( ナル，０ 番地 ) を代入 ptr ？？ １００ *ptr.data と書くと， *(ptr.data) と解釈されるので注意する. （）の書忘れを防ぐため， -> 演算子（アロー演算子）を 用いて ptr -> data = 100 ； と書いても良い．

29 29 データの代入 (*ptr).data = 100; (*ptr).next = NULL; ptr の指すもののメンバー data に 100 を代入 ptr の指すもののメンバー next に NULL( ナル，０ 番地 ) を代入 ptr ？？ １００ NULL は斜線で表わされ ることが多い *ptr.data と書くと， *(ptr.data) と解釈されるので注意する. （）の書忘れを防ぐため， -> 演算子（アロー演算子）を 用いて ptr -> data = 100 ； と書いても良い．

30 30 メモリの解放 ｆ ree(ptr); ptr が指しているメモリ領域を解放し，システムに 返す ptr １００

31 31 メモリリーク プログラムの実行中に確保したメモリ領域が解放 されないこと メモリリークすると、メモリ領域中の使用できる 部分が減る ptr 100 そっちを指すのは、僕 を解放してからにして よ～ malloc

32 32 ポインタを用いたデータ構造の実現 例 リスト (list) p.26 ～ 要素を順番に並べたもの 配列による実現 ポインタによる実現 詳細は次週 しりとり りんご ごじら らっぱ ぱそこん

33 33 まとめ 配列とは 構造体とは ポインタとは

34 34 本日の問題 問題 以下の４個のメンバーから構成される構造 体を定義せよ。タグ名を IMAGE とする。 ・整数値の番号 n ・ローマ字タイトル name ・実数値の平均輝度 avL ・次の IMAGE 型構造体へのポインタ next