情報処理・演習II --

情報処理・演習ＩＩ
--- 第7回: 構造体へのポインタ --情報科学科
井口幸洋
[email protected]
2015/10/1
情報処理・演習ＩＩ
1
構造体を指すポインタの宣言と使用法
変数 p と q は,struct complex型
struct complex {
を指す. つまり, struct complex型
double re, im;
が入っているアドレスを入れる為
};
の変数.
struct complex *p, *q;
p
q
100番地
144.5
100
200番地
200
2015/10/1
re
re
76.5
情報処理・演習ＩＩ
im
3.14
im
43.2
2
？？？
p = q; を行うとどうなりますか？
実行前
p
q
100番地
144.5
100
200番地
200
2015/10/1
re
re
76.5
情報処理・演習ＩＩ
im
3.14
im
43.2
3
答え
p = q;
/* q の値200をpに入れるのだから p の値は200に
なる. これは, p が q と同じ所を指し示しているこ
とを表している */
p
q
100番地
144.5
200
200番地
200
2015/10/1
re
re
76.5
情報処理・演習ＩＩ
im
実行後
3.14
im
43.2
4
？？？
*p = *q; を行うとどうなりますか？
実行前
p
q
100番地
144.5
100
200番地
200
2015/10/1
re
re
76.5
情報処理・演習ＩＩ
im
3.14
im
43.2
5
答え
*p = *q;
/* q が指し示している内容を p が指し示している所
に代入するという意味である. 構造体丸ごとのコピー
が行われる. */
p
q
100番地
76.5
100
200番地
200
2015/10/1
re
re
76.5
情報処理・演習ＩＩ
im
実行後
43.2
im
43.2
6
？？？
• qが指し示すreal partを,pが指し示すreal partに,
qが指し示すimaginary partの符号を反転したも
のを, pが指し示すimaginary partに代入したい.
• どう書けば良いか？
実行前
im
100番地 re
p 100
144.5
3.14
q
200番地
200
2015/10/1
re
76.5
情報処理・演習ＩＩ
im
43.2
7
？？？
• qが指し示すreal partを,pが指し示すreal partに,
• qが指し示すimaginary partの符号を反転したも
のを, pが指し示すimaginary partに代入したい.
• どう書けば良いか？
実行後
im
100番地 re
p 100
76.5
-43.2
q
200番地
200
2015/10/1
re
76.5
情報処理・演習ＩＩ
im
43.2
8
答え
(*p).re = (*q).re;
(*p).im = -(*q).im;
注意： *p.re と書くと *(p.re) というように解釈されてしまう！
p
q
100番地
76.5
100
200番地
200
2015/10/1
re
re
76.5
情報処理・演習ＩＩ
im
実行後
-43.2
im
43.2
9
答え（矢印演算子を使った書き方：推
奨）
(*p).re = (*q).re;
(*p).im = -(*q).im;
p -> re = q -> re;
p -> im = -(q -> im);
2015/10/1
情報処理・演習ＩＩ
10
自己参照構造体
• 今日のポイント！
• 構造体の中に同じ構造体を指すポインタをメン
バーの一つとして持たせた構造体を言う.
• これを使うとリスト構造, ツリー構造などの有
用なデータ構造（データを覚える構造：これが優
れたものであると効率アップが望める.）を作れる.
2015/10/1
情報処理・演習ＩＩ
11
リスト構造とは
• 次のようなときに威力を発揮！
– 1万人のデータが入っている名簿.
– 会員番号順のデータ.
– 配列で実現可能だが，次のような場合ちょっとこまる．
• 退会する人のデータ削除：削除するデータの後ろのデータを一つづつ
前に詰める操作が必要．×印をつける方法もある．
• データを途中に追加：それ以後のデータを１つづつずらさなければなら
ない．例えば5番目に新しいデータを挿入する時、それ以後の９９９６
人分のデータを1個づつずらす必要あり．
• 配列を最初に2万人分用意したとする．2万人以上にデータが増えたら
使えない．プログラムを書き換える必要あり．
2015/10/1
情報処理・演習ＩＩ
12
リスト構造を使ったデータの集まりの実現
• 一連のデータ 2, 3, 5, 7 をリスト構造で表現．
番地が入る
head
50
300
5
50
2
100
100
3
2015/10/1
300
情報処理・演習ＩＩ
200
200
7
0
0は終了
を示す．
NULL．
13
リスト構造をC言語で実現
• 一つのセルを表すデータを構造体で表せばよい．
• セルには，格納したいデータと次のデータの格
納アドレスを記憶させればよい．
head
50
300
5
50
2
100
100
3
2015/10/1
200
200
7
0
300
情報処理・演習ＩＩ
14
リスト構造をC言語で実現
struct cell {
int value;
struct cell *next;
};
2015/10/1
情報処理・演習ＩＩ
5
200
15
リストの走査
• リストを先頭
から順に調べ
る操作
head
50
50
2
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
p
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
print_list(head);
200
200
0
7
16
リストの走査実行例(1)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p
50
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
17
リストの走査実行例(2)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p 100
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
18
リストの走査実行例(3)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p 100
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
19
リストの走査実行例(4)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p 300
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
20
リストの走査実行例(5)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p 300
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
21
リストの走査実行例(6)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p 200
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
22
リストの走査実行例(7)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p 200
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
23
リストの走査実行例(8)
struct cell *head;
...
print_list(head);
head
50
50
p
0
終了を表す
2
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
24
リストの走査実行例(9)
void print_list(struct cell *p)
{
while (p != NULL) {
printf("%3d ", p -> value);
p = p -> next;
}
printf("\n");
}
struct cell *head;
...
print_list(head);
head
50
p
0
50
2
100
100
3
2015/10/1
whileの条件にあてはまらないのでループを
抜ける。
300
5
300
情報処理・演習ＩＩ
200
200
7
0
25
??? list内に5があるか探す．
関数が返す値を答えなさい．
struct cell *head;
...
search_list(5, head);
head
50
50
2
void search_list(int x, struct cell *p)
{
while (p != NULL) {
if (x == p -> value)
return(p);
p = p -> next;
}
return(NULL);
}
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
26
リストの生成：値を読み込みリストに付
け加える．0なら停止．
void make_list(void)
{
struct cell *p; int x;
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
}
2015/10/1
情報処理・演習ＩＩ
27
動的なメモリの確保
• 配列は静的（static)にメモリを確保
– コンパイル時に大きさがきまってしまう
• 動的(dynamic)なメモリ確保
– 実行時に必要に応じてメモリを確保
– OSに対してメモリ確保を依頼
2015/10/1
情報処理・演習ＩＩ
28
動的なメモリの確保
• sizeof(型名）は，その型を格納するために必要
なメモリサイズ(単位はbyte)を返す
• malloc(サイズ）は，指定サイズ分のメモリを確
保し，その先頭番地（ポインタ）を返す．確保でき
なかった時はNULLを返す．
• p=(struct cell *)malloc(sizeof(struct cell));
右辺先頭の(struct cell *)はキャストといい指定された型
に強制的に型変換させる構文．
2015/10/1
情報処理・演習ＩＩ
29
？？？このプログラムを実行すると入力の逆順にリストが
作成される．その様子を箱を描いてわかりやすく説明せよ
void make_list(void)
{
struct cell *p; int x;
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
}
2015/10/1
情報処理・演習ＩＩ
30
？？？解答（１）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
head ＮＵＬＬ
2015/10/1
情報処理・演習ＩＩ
31
？？？解答（２）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
head ＮＵＬＬ
2015/10/1
２を入力
情報処理・演習ＩＩ
x
2
32
？？？解答（３）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
head ＮＵＬＬ
ｐ
50
x
2
50
2015/10/1
情報処理・演習ＩＩ
33
？？？解答（４）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
head ＮＵＬＬ
ｐ
50
x
2
50
２
2015/10/1
情報処理・演習ＩＩ
34
？？？解答（５）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
head NULL
ｐ
50
x
2
50
２
2015/10/1
NULL
情報処理・演習ＩＩ
35
？？？解答（６）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
ｐ
head ５０
50
x
2
50
２
2015/10/1
NULL
つづきを必ずやってみること！
情報処理・演習ＩＩ
36
？？？解答（１）
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
ｐ
head ＮＵＬＬ
２を入力
50
2
2015/10/1
100
情報処理・演習ＩＩ
37
課題１
• リストを先頭
から順に調べ
て和を求める
head
50
50
2
100
100
3
2015/10/1
int sum_list(struct cell *p)
{
sum = 0;
while (p != NULL) {
データを足しこむ；
p = p -> next;
}
合計を返す;
}
300
5
300
情報処理・演習ＩＩ
200
200
7
0
38
課題２以下のプログラムでは入力と逆順のリストができる。
正順にリストを作成するnew_make_listを作れ．
void make_list(struct cell *head)
{
struct cell *p; int x;
head = NULL;
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
p -> value = x;
p -> next = head;
head = p;
}
}
2015/10/1
情報処理・演習ＩＩ
39
課題２ヒント
void new_make_list(struct cell *head)
{
struct cell *p, *tail; int x;
/* dummy 挿入 */
head=(struct cell *)malloc(sizeof(struct cell));
if(head==NULL){
printf("Can't allocate memory.\n");exit(1);
}
head->next = NULL;
tail = head;
head
2015/10/1
tail
50
50
NULL
50
情報処理・演習ＩＩ
40
課題２ヒント
for (;;) {
scanf("%d", &x);
if (x == 0) break;
p=(struct cell *)malloc(sizeof(struct cell));
if(p==NULL){
printf("Can't allocate memory.\n");
exit(1);
}
p -> value = x;
箱をかいて図で理解し、
p -> next =
;
それからコーディングする
tail ->
=
;
こと！
tail =
;
}
/* ここにdummy削除を書く */
return(head);
2015/10/1
41
情報処理・演習ＩＩ
}
課題３ xを見つけてそのあとにyを挿入
search_listを改良すれば簡単に書ける．ノーヒント．
箱をかいて図で理解し、
それからコーディングする
こと！
2015/10/1
情報処理・演習ＩＩ
42
課題４リストを逆順にする
p
head
50
q
100
r
300
50
50
2
100
100
3
2015/10/1
300
5
300
情報処理・演習ＩＩ
200
200
7
0
43
課題４リストを逆順にする
p
head
q
100
r
300
50
50
2
50
NULL
100
3
2015/10/1
head -> next = NULL;
q->next = p;
300
5
50
情報処理・演習ＩＩ
200
200
7
0
44
課題４リストを逆順にする
p
head
100
q
300
r
200
50
50
2
NULL
100
3
2015/10/1
300
5
50
情報処理・演習ＩＩ
200
200
7
0
45
課題４リストを逆順にする
p
head
100
q
300
r
200
50
50
q->next = p;をやるとどうなりますか？
2
NULL
100
3
2015/10/1
300
5
50
情報処理・演習ＩＩ
200
200
7
0
46
リスト構造を使った名簿の操作（削除）
• 後藤さんがやめたので名簿から削除．
head
削除
50
50
飯田 100
300
後藤 200
200
吉澤
0
100
石川 300
2015/10/1
情報処理・演習ＩＩ
47
リスト構造を使った名簿の操作（削除）
• 後藤さんがやめたので名簿から削除．
head
50
50
飯田 100
300
後藤 200
100
石川 200
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
石川さんからの
矢印を書換える
だけでよい．
48
リスト構造を使った名簿の操作（削除）
• 後藤さんがやめたので名簿から削除．
head
ここの部分はそのままでも構わないが、
メモリの無駄にはなる．解決策は後述．
50
50
飯田 100
300
後藤 200
100
石川 200
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
石川さんからの
矢印を書換える
だけでよい．
49
リスト構造を使った名簿の操作（挿入）
• 高橋さんが加入したので名簿に挿入．
head
50
200
吉澤
50
0
飯田 100
100
石川 200
2015/10/1
情報処理・演習ＩＩ
石川さんからの
矢印を書換える
だけでよい．
50
リスト構造を使った名簿の操作（挿入）
• 高橋さんのデータを入れる場所を確保．
head
50
50
500
高橋
---
200
吉澤
0
飯田 100
100
石川 200
2015/10/1
情報処理・演習ＩＩ
石川さんからの
矢印を書換える
だけでよい．
51
リスト構造を使った名簿
• 会員が飯田，石川，後藤，吉澤のあるクラブがあ
る．これをリスト構造で示す．
50
飯田 100
300
後藤 200
100
石川 300
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
0は終了
を示す．
NULL．
52
文字列のメモリ管理(解決法）
• 何行もある文章を扱うプログラム
– 一つの大きな配列に、詰め込む.
– 一つの行の区切りは０をいれる.
– 行の始まりを示す配列 line[]を用意.
line[i] には i 行目が格納される番地を入れる.
line[0] = 320; line[1] = 325; line[2] = 329;
'a' 'b' 'c' 'd' 0 'p' 'q' 'r' 0 'x' 'y' 'z' 0
320
2015/10/1
324
328
情報処理・演習ＩＩ
332
336
53
文章を格納するプログラム(1)
char buffer[10000]; /* 10000文字格納
*/
char *line[500]; /* 500行まで扱う */
int lc; /* line counter */
int cc; /* character counter */
int ch; /* 一文字入力用 */
lc = 0;
cc = 0;
2015/10/1
情報処理・演習ＩＩ
54
文章を格納するプログラム(2)
for(;;){ /* 行の繰り返し */
ch = getchar();
if (ch == EOF) break; /* End Of File検出 */
if (lc >= 500) {
printf("Too many lines.\n");
exit(1);
}
line[lc] = &buffer[cc]; /* lc行目の先頭番地 */
lc++;
2015/10/1
情報処理・演習ＩＩ
55
文章を格納するプログラム(3)
for(;;){ /* 文字の繰り返し */
if (ch == '\n') break; /* 改行検出 */
if (cc >= 9999) {
printf("Too many characters.\n");
exit(2);
}
buffer[cc++] = ch;
ch = getchar();
}
buffer[cc++] = 0;
}
2015/10/1
情報処理・演習ＩＩ
56
リスト構造を使った名簿の実現
• 会員が飯田，石川，後藤，吉澤のあるクラブがあ
る．これをリスト構造で示す．
head
50
50
飯田 100
300
後藤 200
100
石川 300
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
0は終了
を示す．
NULL．
57
リスト構造をC言語で実現
head
50
50
飯田 100
300
後藤 200
100
石川 300
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
0は終了
を示す．
NULL．
58
リスト構造を使った名簿の操作（削除）
• 後藤さんがやめたので名簿から削除．
head
削除
50
50
飯田 100
300
後藤 200
200
吉澤
0
100
石川 300
2015/10/1
情報処理・演習ＩＩ
59
リスト構造を使った名簿の操作（削除）
• 後藤さんがやめたので名簿から削除．
head
50
50
飯田 100
300
後藤 200
100
石川 200
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
石川さんからの
矢印を書換える
だけでよい．
60
リスト構造を使った名簿の操作（削除）
• 後藤さんがやめたので名簿から削除．
head
ここの部分はそのままでも構わないが、
メモリの無駄にはなる．解決策は後述．
50
50
飯田 100
300
後藤 200
100
石川 200
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
石川さんからの
矢印を書換える
だけでよい．
61
リスト構造を使った名簿の操作（挿入）
• 高橋さんが加入したので名簿に挿入．
head
50
200
吉澤
50
0
飯田 100
100
石川 200
2015/10/1
情報処理・演習ＩＩ
石川さんからの
矢印を書換える
だけでよい．
62
リスト構造を使った名簿の操作（挿入）
• 高橋さんのデータを入れる場所を確保．
head
50
50
500
高橋
---
200
吉澤
0
飯田 100
100
石川 200
2015/10/1
情報処理・演習ＩＩ
石川さんからの
矢印を書換える
だけでよい．
63
リスト構造を使った名簿
• 会員が飯田，石川，後藤，吉澤のあるクラブがあ
る．これをリスト構造で示す．
50
飯田 100
300
後藤 200
100
石川 300
2015/10/1
情報処理・演習ＩＩ
200
吉澤
0
0は終了
を示す．
NULL．
64

Download Report