データ構造とアルゴリズム

データ構造とアルゴリズム
第3回
配列，構造体，ポインタ
～データ構造について学ぶための基礎～
1
前回の解答
問題１．次のうち、計算量が一番大きいものはどれか
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)
2
得点分布
設問２不正解
0729：
17 18 20 31 37 39
67 81
062914 052908
設問１不正解
0729： 14 17 20
正解者の割合
100
設問３不正解
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
設問１
設問２
設問３
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の場合は添字が必
ず０から始まる！
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
１名分のデータをま
とめて管理できると
便利だな
４名分のデータの集合
をどう表わそう？
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型
４名分のデータを
まとめて扱える！
14
配列の短所

データの数をあらかじめ宣言する必要がある
int a[3];

データを格納するための領域を自由に追加したり、不
要になったら領域を開放したい… どうする？
⇒ ポインタを利用
15
ポインタ（pointer）とは



変数を指し示すためのデータ型
他のデータへの参照を示す（他のデータがあ
る場所の番地が格納される）
ポインタ型がある言語

C, PASCAL
cf.)
 ポインタ型がない言語

BASIC, FORTRAN
16
ポインタ
メモリ空間
アドレス
８０番地 :
ptr
１０４番地 :
n
「ptrはnを指している」
とは？
ポインタ型変数ptr
int型変数n
17
ポインタとアドレス
メモリ空間
アドレス
８０番地 :
１０４番地
１０４番地 :
５０
変数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番地 :
５０
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
ポインタ図示の例


データ構造を図示するときは，ポインタは矢印を使っ
て表現される
データ構造として見る場合は，ポインタがどのデータ
を指しているかが重要（ポインタに入っているアドレ
ス値そのものは意識しなくて良い）
ポインタｐｔｒ
整数型変数
ポインタｔｍｐ
構造体（ﾚｺｰﾄﾞ型変数）
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


*pｔｒ ;
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(ナル，０番地)
を代入
ptr
１００
？
？
28
データの代入
(*ptr).data = 100;
(*ptr).next = NULL;


*ptr.dataと書くと，*(ptr.data)と解
釈されるので注意する.
（）の書忘れを防ぐため，
->演算子（アロー演算子）を用い
て
ptr -> data = 100；
と書いても良い．
ptrの指すもののメンバーdataに100を代入
ptrの指すもののメンバーnextにNULL(ナル，０番地)
を代入
NULLは斜線で表わされる
ことが多い
ptr
１００
？
？
29
メモリの解放
ｆree(ptr);

ptrが指しているメモリ領域を解放し，システムに返す
ptr
１００
30
メモリリーク


プログラムの実行中に確保したメモリ領域が解放さ
れないこと
メモリリークすると、メモリ領域中の使用できる部分が
減る
そっちを指すのは、僕を解
放してからにしてよ～
ptr
100
malloc
31
ポインタを用いたデータ構造の実現例

リスト (list) p.26～



要素を順番に並べたもの
配列による実現
ポインタによる実現
しりとり
りんご
ごじら

詳細は次週
らっぱ
ぱそこん
32
まとめ

配列とは

構造体とは

ポインタとは
33
本日の問題

問題以下の４個のメンバーから構成される構造体を
定義せよ。タグ名をIMAGEとする。
・整数値の番号 n
・ローマ字タイトル name
・実数値の平均輝度 avL
・次のIMAGE型構造体へのポインタ next
34

Download Report