Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

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

2 2 前回の解答 問題1.次のうち、計算量が一番大きいものはどれ か O(1), O(n), O(n 2 ), O(n log n) 問題2.計算量が一番小さいものはどれか O(log n), O(n 3 ), O(n log n), O(n) 問題3.計算量の大きいものから順に並べなさい 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 設問3不正解 設問2不正解 設問1不正解

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 の場合は添字が必 ず0から始まる! 100 : 104 : 108 : 112 : メモリ

9 9 各部の計算量は? int printData(int n, int data[]) /* data の要素数は n とする */ { int i, j; for (i=0; i { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slidesplayer.net/39/11010342/slides/slide_9.jpg", "name": "9 各部の計算量は? int printData(int n, int data[]) /* data の要素数は n とする */ { int i, j; for (i=0; i

10 10 異なる型のデータをまとめて扱うに は? 配列は同じ型のデータの集まり 文字列と数値など,異なる型のデータをまとめる にはどうしたらよいだろうか? 名前は文字列で 表現しよう 身長は整数型? 実数型? 4名分のデータの集 合をどう表わそう? 1名分のデータを まとめて管理でき ると便利だな 青木 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 型 4名分のデータ をまとめて扱え る!

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

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

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

18 18 ポインタとアドレス アドレス 50 104番地 : メモリ空 間 104番地 80番地 : 変数 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 50 先ほどの*とは意味 が異なるので注意

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 ポインタ図示の例 ポインタ ptr 整数型変数 ポインタ t mp 構造体 (レコード型変数) データ構造を図示するときは,ポインタは矢印を 使って表現される データ構造として見る場合は,ポインタがどのデ ータを指しているかが重要 (ポインタに入って いるアドレス値そのものは意識しなくて良い)

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 tr ; 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( ナル,0 番地 ) を代入 ptr ?? 100 *ptr.data と書くと, *(ptr.data) と解釈されるので注意する. ()の書忘れを防ぐため, -> 演算子(アロー演算子)を 用いて ptr -> data = 100 ; と書いても良い.

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

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

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

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

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

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


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

Similar presentations


Ads by Google