データ構造とアルゴリズム
第3回
配列,構造体,ポインタ
~ データ構造について学ぶための基礎~
1
前回の解答
問題1.次のうち、計算量が一番大きいものはどれか
O(1), O(n), O(n2), O(n log n)
問題2.計算量が一番小さいものはどれか
O(log n), O(n3), O(n log n), O(n)
問題3.計算量の大きいものから順に並べなさい
O(n3), O(nlogn), O(n) , O(logn), O(1)
2
得点分布
設問2不正解
0729:
17 18 20 31 37 39
67 81
062914 052908
設問1不正解
0729: 14 17 20
正解者の割合
100
設問3不正解
0729:
14 16 17 20 27 31 33
34 39 49 56 72 73 81
90
80
70
062906 062957
60
50
正解者の割合
40
30
20
10
0
設問1
設問2
設問3
3
講義資料
http://www.ced.is.utsunomiya-u.ac.jp/lecture/2008/ds/
但し虫食い版
できるだけ火曜日夕方までに用意したいと思っているが、
水曜日未明になることも予想される。
水曜日2コマよりちょっと早めに来て確認し、印刷して、
授業中に書き込むのを勧める
4
配列(array)



同じ型の要素の集合
各要素はメモリ上に同じサイズで連続して格納される
添え字(インデクス)を指定することで,要素にランダ
ムにアクセス可能
アドレス
メモリ
100:
170
data[0]
104:
160
data[1]
108:
158
data[2]
173
data[3]
個々のセルに整数型の
要素が格納されている.
5
ランダムアクセス(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]
例)
6
ランダムアクセス(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]
添字
(インデクス,
index)
7
配列を扱うときの注意点

C言語による配列の宣言例
double
height[MAX];
int
data[4];
アドレス
メモリ
C
100:
170
data[0]
104:
160
data[1]
108:
158
data[2]
112:
173
data[3]
Cの場合は添字が必
ず0から始まる!
8
各部の計算量は?
int printData(int n, int data[]) /* dataの要素数はnとする */
{
int i, j;
for (i=0; i<n; i++)
printf(“%d\n”, i);
O(n)
for (i=0; i<n; i++)
printf(“%d \n”, data[i]);
O(n)
for (j=0; j<n; j++){
for (i=0; i<n; i++){
printf(“i*jは %d \n”, i*j);
}
}
O(n2)
return 0;
}
O(n)+O(n)+O(n2) → O(n2)
9
異なる型のデータをまとめて扱うには?


配列は同じ型のデータの集まり
文字列と数値など,異なる型のデータをまとめるには
どうしたらよいだろうか?
名前は文字列で
表現しよう
青木
小田
金子
佐藤
身長は整数型?
実数型?
177
158
167
174
1名分のデータをま
とめて管理できると
便利だな
4名分のデータの集合
をどう表わそう?
10
構造体(Structure) (C言語)

さまざまな型をもつデータをまとめたもの
※「構造体」はC言語特有の呼び名.
※一般には,「レコード構造(record structure)」と
呼ばれる.
cf.) PASCAL → レコード型
メンバー
文字型配列
整数型
name
height
11
構造体宣言の例
構造体タグ
{}内で定義する構造体の名前
struct STUDENT {
char name[10];
int height;
} st1, st2 ;
メンバー(member)
STUDENT型の変数の定義
変数st1
変数st2
name
name
height
height
STUDENT型
12
メンバーの参照

※
(構造体型の変数の名前).(メンバー名)で表わせる
st1.name = aoki;
st1.height = 177;
st2.name = oda;
st2.height = 158;
ドット演算子(.演算子, .operator)
変数st1
変数st2
name
ao k i
name
od a
height
177
height
158
STUDENT型
13
構造体の配列

同じ型の構造体を並べて配列を作ることができる
struct STUDENT {
char name[10];
int height;
};
struct STUDENT stData[4];
STUDENT型構造体の配列
stData[0]
stData[1]
stData[2]
stData[3]
青木
小田
金子
177
158
167
佐藤
174
STUDENT型
4名分のデータを
まとめて扱える!
14
配列の短所

データの数をあらかじめ宣言する必要がある
int a[3];

データを格納するための領域を自由に追加したり、不
要になったら領域を開放したい… どうする?
⇒ ポインタを利用
15
ポインタ(pointer)とは



変数を指し示すためのデータ型
他のデータへの参照を示す(他のデータがあ
る場所の番地が格納される)
ポインタ型がある言語

C, PASCAL
cf.)
 ポインタ型がない言語

BASIC, FORTRAN
16
ポインタ
メモリ空間
アドレス
80番地 :
ptr
104番地 :
n
「ptrはnを指している」
とは?
ポインタ型変数ptr
int型変数n
17
ポインタとアドレス
メモリ空間
アドレス
80番地 :
104番地
104番地 :
50
変数nのデータが入っ
ているメモリ上のアドレ
スが格納される
ポインタ型変数ptr
int型変数n
18
ポインタ型変数宣言の例
int n;
int *ptr;
n = 50;
ptr = &n;
← nはint型の変数
← ptrは int型の変数を指すポインタ変数
ポインタであることを表わす記号
(“アスタリスク”という)
アドレス演算子
(単項&演算子, &operator)
データが格納されているアドレスを
取り出す演算子
19
ポインタ型変数宣言の例
n
ptr
int n;
int *ptr;
80番地 :
104番地 :
n = 50;
ptr = &n;
80番地 :
104番地 :
50
80番地 : 104番地 104番地 :
50
20
参考)間接演算子
int n;
int *ptr;
先ほどの*とは意味
が異なるので注意
n = 50;
ptr = &n;
printf(“ptrが指しているものの中身は %d”, *ptr);
間接演算子(indirect operator)
ptrがnを指すとき,*ptrはnの別名(エイリアス)となる
ptr
104番地
n
104番地 :
50
21
参考) C言語におけるポインタの使い方

データ構造としてのポインタ

参照渡しのためのポインタ
void exsample1 (int a, int b, int *sum, int * diff)
{
*sum = a + b;
*diff = a - b;
}

配列参照のためのポインタ
int a[5];
int i;
int a[5];
int *p;
for (i = 0; i < 5; i++) {
a[i] = a[i] + 3;
}
for (p = a; p < a+5; p++) {
*p = *p + 3;
}
22
ポインタ図示の例


データ構造を図示するときは,ポインタは矢印を使っ
て表現される
データ構造として見る場合は,ポインタがどのデータ
を指しているかが重要 (ポインタに入っているアドレ
ス値そのものは意識しなくて良い)
ポインタ ptr
整数型変数
ポインタ tmp
構造体 (レコード型変数)
23
プログラム例
#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;
}
24
解説
ITEM型構造体の型定義
struct ITEM {
int
data;
struct ITEM *next;
};



ITEM型
int型
ポインタ型
data
next
ITEM型構造体は,int型のデータが入る箱とITEM
型構造体へのポインタが入る箱から成る
int型の箱の名前(メンバー名)はdata
ポインタ型の箱の名前はnext
25
変数の定義
struct ITEM


*ptr ;
struct ITEM型構造体変数のアドレスを
入れる箱(ポインタ変数ptr)を用意
この時点では,箱の中身は不定
ptr
?
26
メモリ領域の確保
ptr = (struct ITEM*)malloc(sizeof(struct ITEM));



struct ITEM型構造体変数を入れるための箱(
メモリ領域)を確保.
箱のサイズはITEM型構造体の大きさ.
その箱のアドレスをptrに入れる.
ptr
?
?
27
データの代入
(*ptr).data = 100;
(*ptr).next = NULL;


*ptr.dataと書くと,*(ptr.data)と解
釈されるので注意する.
()の書忘れを防ぐため,
->演算子(アロー演算子)を用い
て
ptr -> data = 100;
と書いても良い.
ptrの指すもののメンバーdataに100を代入
ptrの指すもののメンバーnextにNULL(ナル,0番地)
を代入
ptr
100
?
?
28
データの代入
(*ptr).data = 100;
(*ptr).next = NULL;


*ptr.dataと書くと,*(ptr.data)と解
釈されるので注意する.
()の書忘れを防ぐため,
->演算子(アロー演算子)を用い
て
ptr -> data = 100;
と書いても良い.
ptrの指すもののメンバーdataに100を代入
ptrの指すもののメンバーnextにNULL(ナル,0番地)
を代入
NULLは斜線で表わされる
ことが多い
ptr
100
?
?
29
メモリの解放
free(ptr);

ptrが指しているメモリ領域を解放し,システムに返す
ptr
100
30
メモリリーク


プログラムの実行中に確保したメモリ領域が解放さ
れないこと
メモリリークすると、メモリ領域中の使用できる部分が
減る
そっちを指すのは、僕を解
放してからにしてよ~
ptr
100
malloc
31
ポインタを用いたデータ構造の実現例

リスト (list) p.26~



要素を順番に並べたもの
配列による実現
ポインタによる実現
しりとり
りんご
ごじら

詳細は次週
らっぱ
ぱそこん
32
まとめ

配列とは

構造体とは

ポインタとは
33
本日の問題

問題 以下の4個のメンバーから構成される構造体を
定義せよ。タグ名をIMAGEとする。
・整数値の番号 n
・ローマ字タイトル name
・実数値の平均輝度 avL
・次のIMAGE型構造体へのポインタ next
34
ダウンロード

PPT for 20080507完全版