第3回 配列，構造体，ポインタ ～ データ構造について学ぶための基礎～

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

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

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

3 配列（array） の集合 各要素はメモリ上に同じサイズで連続して格納される ことで，要素にランダムにアクセス可能 100： 170
　　　　　　　　　の集合 各要素はメモリ上に同じサイズで連続して格納される 　　　　　　　　　　　　　ことで，要素にランダムにアクセス可能 メモリ　 アドレス　 100： 170 data[0] 104： 160 data[1] 108： 158 data[2] 173 data[3]

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

5 配列を扱うときの注意点 C言語による配列の宣言例 double height[MAX]; int data[4]; 100： 170
メモリ　 C アドレス　 100： 170 data[0] 104： 160 data[1] 108： 158 data[2] 112： 173 data[3]

6 各部の計算量は？ O(n) O(n) O(n2)
int printData(int n, int data[]) /* dataの要素数はnとする */ { int i, j; for (i=0; i<n; i++) printf(“%d\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) O(n2)

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

8 構造体（Structure） (C言語) name height ※「構造体」はC言語特有の呼び名．
※一般には，「レコード構造（record structure）」と呼ばれる． 　　cf.) PASCAL → レコード型 name height

9 構造体宣言の例 name height 変数st1 name height 変数st2 struct STUDENT {
char name[10]; int height; 　　 } st1, st2 ; name height 変数st1 name height 変数st2

10 メンバーの参照 （構造体型の変数の名前）.（メンバー名）で表わせる st1.name = aoki; st1.height = 177;
メンバーの参照　　　　　 （構造体型の変数の名前）.（メンバー名）で表わせる st1.name = aoki; st1.height = 177; st2.name = oda; st2.height = 158; name height 変数st1 a o k i 177 STUDENT型 name height 変数st2 o d a 158

11 構造体の配列 struct STUDENT { char name[10]; int height; } ;
struct STUDENT stData[4]; 　　 stData[0] 青木 177 小田 158 金子 167 佐藤 174 STUDENT型 stData[1] stData[2] stData[3]

12 配列の短所 データを格納するための領域を自由に追加したり、不要になったら領域を開放したい…　どうする？ ⇒　 int a[3];

13 ポインタ（pointer）とは　　 ポインタ型がある言語 C, PASCAL cf.) ポインタ型がない言語 BASIC, FORTRAN

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

15 ポインタとアドレス メモリ空間 アドレス ８０番地 : １０４番地 ポインタ型変数ptr １０４番地 : ５０ int型変数n

16 ポインタ型変数宣言の例 int n; ← nはint型の変数 int *ptr; ← n = 50; ptr = ＆n;
ポインタ型変数宣言の例　 int n; 　 int *ptr; 　 n = 50; ptr = ＆n; ←　nはint型の変数 ←　 ポインタであることを表わす記号 データが格納されているアドレスを 取り出す演算子

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

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

19 参考) 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; }

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

21 プログラム例 #include <stdio.h> #include <stdlib.h>
/* 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; }

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

23 変数の定義 ？ ptr struct ITEM *pｔｒ ;
struct ITEM型構造体変数のアドレスを入れる箱（ポインタ変数ptr）を用意 ptr ？

24 メモリ領域の確保 ？ ptr ptr = (struct ITEM*)malloc(sizeof(struct ITEM));
　　　　　　　　　　　　　　　　　　　　　　　　　　　　（メモリ領域）を確保． ptr ？

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

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

27 メモリの解放 ｆree(ptr); ptr １００

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

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

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

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