1
Cプログラミング演習
第９回 ポインタとリンクドリストデータ
構造
2
今まで説明してきた変数
#include "stdafx.h"
#include <math.h>
#pragma warning(disable:4996)
int _tmain()
{
double x;
double y;
char buf[256];
int i;
double start_x;
double step_x;
FILE* fp;
printf( "start_x =" );
fgets( buf, 256, stdin );
sscanf_s( buf, "%lf\n", &start_x );
printf( "step_x =" );
fgets( buf, 256, stdin );
sscanf_s( buf, "%lf\n", &step_x );
fp = fopen( "d:\\data.csv", "w" );
for( i = 0; i < 20; i++ ) {
x = start_x + ( i * step_x );
y = sin( x );
printf( "x= %f, y= %f\n", x, y );
fprintf( fp, "x=, %f, y=, %f\n", x,
y );
}
fprintf( stderr, "file z:\\data.csv
created\n" );
fclose( fp );
return 0;
}
プログラムが使う
メモリ空間
メイン関数の
実行時に
自動的に確保
3
今日の内容
#include "stdafx.h"
#include <math.h>
int _tmain()
{
new ・・・
}
プログラムが使う
メモリ空間
new を使い
必要な分を確保
new の実行によりメモリアドレス
が得られる
4
今日の内容
#include "stdafx.h"
#include <math.h>
int _tmain()
{
new ・・・
delete ・・・
}
プログラムが使う
メモリ空間
new を使い
必要な分を確保
不要になったら delete を実行
するのがルール
5
プログラムが使う
メモリ空間
例えば，new を１０回実行すると・・・
メモリエリアが
１０回確保される
プログラミングテクニック
確保して得られた１０個のメモリアドレス
を，メモリの「どこに」，「どうやって」
格納しておくのか？
6
リストの模式図
データ部分とポインタ部分で１単位を構成
する（これをリストセルと呼ぶ）
NULL
ポインタ
部分
（＝次のリストセル
のメモリアドレス）
データ
部分
リストセル
リストの末端を表す
メモリ中では
[00 00 00 00] という
値をとる
7
リストの基本操作の例
•リストの生成 (new_list)
•リストの追加 (insert_list)
•リストの削除 (delete_list)
•リストの探索 (find_list)
生成前 何も無い 生成後 NULL サイズ１
のリスト
生成前 長さ k のリスト
（k≧0）
生成後 長さ k+1 のリスト
（先頭に追加）
生成前 長さ k のリスト
（k≧1）
生成後 長さ k-1 のリスト
（ある特定要素値を
持つものを削除）
リスト内から，ある特定要素値を持つものを探索
8
再帰的構造体：リストの定義の
例
struct data_list {
int data;
struct data_list *next;
};
data next
int 型のデータ メモリアドレス
9
リストの生成を行う関数
struct data_list *new_list(int x)
{
struct data_list *c = new(struct data_list);
c->data = x;
c->next = NULL;
return c;
}
メモリエリア
を確保
確保したメモリエリアの
アドレスが c にセットされる
プログラムが使う
メモリ空間
data next
c に入っているメモリアドレスを使い，
構造体にアクセス
data にx の値を，
next にNULL をセット
10
リストの追加を行う関数
void insert_list(struct data_list *p, int x)
{
struct data_list *c = new(struct data_list);
c->data = p->data;
c->next = p->next;
p->data = x;
p->next = c;
}要素の追加
NULL
ｘの値 NULL
新しく作ったセル
11
プログラム例
12 345 67 89 NULL
下記のような，サイズ４のリストを作るプログラム
12
89
new_list(89)
NULL
このメモリアドレス = a
13
67
insert_list(a, 67)
このメモリアドレス = a
89
NULL
14
345
insert_list(a, 345)
このメモリアドレス = a
67 89
NULL
15
12
insert_list(a, 12)
このメモリアドレス = a
345 67 89
NULL
16
#include "stdafx.h"
#include <math.h>
struct data_list {
int data;
struct data_list *next;
};
struct data_list *new_list(int x)
{struct data_list *c = new(struct data_list);
c->data = x;
c->next = NULL;
return c;
}
void insert_list(struct data_list *p, int x)
{struct data_list *c = new(struct data_list);
c->data = p->data;
c->next = p->next;
p->data = x;
p->next = c;
}
int _tmain()
{int ch;
struct data_list *a;
a = new_list( 89 );
insert_list( a, 67 );
insert_list( a, 345 );
insert_list( a, 12 );
printf( "Enter キーを1,2回押してください. プログラムを終了します\n");
ch = getchar();
ch = getchar();
return 0;
}
17
実際のメモリの中身
12 345 67 89 NULL
12, ポインタ
89, NULL
67, ポインタ
345, ポインタ
16進数表示であることに注意
18
構造体リストの長所
•動的メモリ管理(new)により、必要な分
だけのメモリを、好きなときに得られ
る。
→セル数の制限を気にしなくてよい
•削除したセルの再利用も簡単化できる。
→ごみ集めの自動化が可能
19
例題１．リストの要素の表示
•リストの個々の要素をたどり，要素値
を順に表示するプログラム
20
リストの表示を行う関数
void print_list(struct data_list *p)
{
struct data_list *x;
if ( p == NULL ) {
return;
}
printf( "%d", p->data );
x = p->next;
while( x != NULL ) {
printf( ", %d", x->data );
x = x-> next;
}
printf( "\n" );
}
21
#include "stdafx.h"
#include <math.h>
struct data_list {
int data;
struct data_list *next;
};
void print_list(struct data_list *p)
{struct data_list *x;
if ( p == NULL ) {
return;
}
printf( "%d", p->data );
x = p->next;
while( x != NULL ) {
printf( ", %d", x->data );
x = x-> next;
}
printf( "\n" );
}
struct data_list *new_list(int x)
{struct data_list *c = new(struct data_list);
c->data = x;
c->next = NULL;
return c;
}
void insert_list(struct data_list *p, int x)
{struct data_list *c = new(struct data_list);
c->data = p->data;
c->next = p->next;
p->data = x;
p->next = c;
}
int _tmain()
{int ch;
struct data_list *a;
a = new_list( 89 );
insert_list( a, 67 );
insert_list( a, 345 );
insert_list( a, 12 );
print_list( a );
printf( "Enter キーを1,2回押してください. プログラムを終了します\n");
ch = getchar();
ch = getchar();
return 0;
}
22
実行結果の例
23
例題２．リストの探索
•リストの個々の要素をたどり，要素に
よる探索を行うプログラム
24
リストの探索
12 345 67 89 NULL
find_list(67)
25
リストの探索
12 345 67 89 NULL
find_list(67)
26
リストの探索
12 345 67 89 NULL
find_list(67)
見付かった
27
リストの探索を行う関数
int find_list(struct data_list *p, int data )
{
struct data_list *x;
x = p;
while( x != NULL ) {
if ( x->data == data ) {
return 1;
}
x = x-> next;
}
return 0;;
}
28
#include "stdafx.h"
#include <math.h>
struct data_list {
int data;
struct data_list *next;
};
#include "stdafx.h"
int find_list(struct data_list *p, int data )
{struct data_list *x;
x = p;
while( x != NULL ) {
if ( x->data == data ) {
return 1;
}
x = x-> next;
}
return 0;;
}
struct data_list *new_list(int x)
{struct data_list *c = new(struct data_list);
c->data = x;
c->next = NULL;
return c;
}
void insert_list(struct data_list *p, int x)
{struct data_list *c = new(struct data_list);
c->data = p->data;
c->next = p->next;
p->data = x;
p->next = c;
}
int _tmain()
{int ch;
struct data_list *a;
a = new_list( 89 );
insert_list( a, 67 );
insert_list( a, 345 );
insert_list( a, 12 );
if ( find_list( a, 65 ) ) {
printf( "65はリスト中にある\n" );
};
if ( find_list( a, 67 ) ) {
printf( "67はリスト中にある\n" );
};
printf( "Enter キーを1,2回押してください. プログラムを終了します\n");
ch = getchar();
ch = getchar();
return 0;
}
29
例題３．リストの削除
•リストの個々の要素をたどり，要素の
削除を行うプログラム
30
リストの削除
12 345 67 89 NULL
delete_list(67)
31
リストの削除
12 345 67 89 NULL
delete_list(67)
32
リストの削除
12 345 67 89 NULL
delete_list(67)
y x
33
リストの削除
12 345 89 NULL
delete_list(67)
y
34
リストの削除
12 345 89 NULL
delete_list(67)
y
35
リストの削除を行う関数
void delete_list(struct data_list **p, int data )
{struct data_list *x;
struct data_list *y;
x = *p;
y = NULL;
while( x != NULL ) {
if ( x->data == data ) {
if ( y != NULL ) {
y->next = x->next;
delete( x );
break;
}
else {
(*p) = x->next;
delete( x );
break;
}
}
y = x;
x = x-> next;
}
return;
}
36
#include "stdafx.h"
#include <math.h>
struct data_list {
int data;
struct data_list *next;
};
void delete_list(struct data_list **p, int data )
{struct data_list *x;
struct data_list *y;
x = *p;
y = NULL;
while( x != NULL ) {
if ( x->data == data ) {
if ( y != NULL ) {
y->next = x->next;
delete( x );
break;
}
else {
(*p) = x->next;
delete( x );
break;
}
}
y = x;
x = x-> next;
}
return;
}
void print_list(struct data_list *p)
{struct data_list *x;
if ( p == NULL ) {
return;
}
printf( "%d", p->data );
x = p->next;
while( x != NULL ) {
printf( ", %d", x->data );
x = x-> next;
}
printf( "\n" );
}
struct data_list *new_list(int x)
{struct data_list *c = new(struct data_list);
c->data = x;
c->next = NULL;
return c;
}
void insert_list(struct data_list *p, int x)
{struct data_list *c = new(struct data_list);
c->data = p->data;
c->next = p->next;
p->data = x;
p->next = c;
}
int _tmain()
{int ch;
struct data_list *a;
a = new_list( 89 );
insert_list( a, 67 );
insert_list( a, 345 );
insert_list( a, 12 );
print_list( a );
delete_list( &a, 67 );
print_list( a );
printf( "Enter キーを1,2回押してください. プログラムを終了します\n");
ch = getchar();
ch = getchar();
return 0;
}
37
再帰的構造体を用いた実装法
•データとポインタをメンバとする構造
体を定義する。
•リストの末端はNULL（空ポインタ）
•先頭の要素セルをおさえるためのポイ
ンタ変数を使う（例題１，例題２，例
題３でのメイン関数内での変数 a）
–最後尾の要素セルをおさえるためのポイン
タ変数が役立つ場合もある（次回授業での
リストの併合のケース）
•必要に応じて途中のセルをおさえるた
めのポインタ変数を適宜用意
38
リストの長さを求める関数
39
lengthの実行状況
12 345 67 89 NULL
最初
x
40
12 345 67 89 NULL
x
41
12 345 67 89 NULL
x
42
12 345 67 89 NULL
x
43
12 345 67 89 NULL
結果：４
