• 動的メモリ確保（new/delete）とポインタを用いた連結リ
ストの実装方法の習得。
• 【学習内容の構成】
1. 動的メモリ管理：newによるメモリ確保とdeleteによる
解放
2. リストセルの構造：データ部分とポインタ部分（次セル
のアドレス）で構成される再帰的構造体
3. リストの基本操作：生成（new_list）、追加
（insert_list）、表示（print_list）、探索（find_list）、削
除（delete_list）
4. ポインタの活用：先頭セルを保持するポインタ変数によ
るリスト全体の管理
• 前提：C言語の基本文法、構造体、ポインタの基礎知識
• 意義：配列サイズの制限を超えた柔軟なデータ構造の設計
能力
2
•3
今まで説明してきた変数
#include "stdio.h"
#include <math.h>
#pragma warning(disable:4996)
int main()
{
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;
}
プログラムが使う
メモリ空間
メイン関数の
実行時に
自動的に確保
•4
今日の内容
#include "stdio.h"
#include <math.h>
int main()
{
new ・・・
}
プログラムが使う
メモリ空間
new を使い
必要な分を確保
new の実行によりメモリアドレス
が得られる
•5
今日の内容
#include "stdio.h"
#include <math.h>
int main()
{
new ・・・
delete ・・・
}
プログラムが使う
メモリ空間
new を使い
必要な分を確保
不要になったら delete を実行
するのがルール
•6
プログラムが使う
メモリ空間
例えば，new を１０回実行すると・・・
メモリエリアが
１０回確保される
プログラミングテクニック
確保して得られた１０個のメモリアドレス
を，メモリの「どこに」，「どうやって」
格納しておくのか？
リストの模式図
•7
データ部分とポインタ部分で１単位を構成する
（これをリストセルと呼ぶ）
NULL
ポインタ
部分
（＝次のリストセル
のメモリアドレス）
データ
部分
リストセル
リストの末端を表
す
メモリ中では
[00 00 00 00] という
値をとる
リストの基本操作の例
• リストの生成 (new_list)
• リストの追加 (insert_list)
• リストの削除 (delete_list)
• リストの探索 (find_list)
•8
生成前
何も無い
生成後
NULL
サイズ１
のリスト
生成前
長さ k のリスト
（k≧0）
生成後
長さ k+1 のリスト
（先頭に追加）
生成前
長さ k のリスト
（k≧1）
生成後
長さ k-1 のリスト
（ある特定要素値を
持つものを削除）
リスト内から，ある特定要素値を持つものを探索
再帰的構造体：リストの定義の例
data next
•9
struct data_list {
int data;
struct data_list *next;
};
int 型のデータ
メモリアドレス
リストの生成を行う関数
•10
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 をセット
リストの追加を行う関数
•11
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
新しく作ったセル
プログラム例
•12
12 345 67 89 NULL
下記のような，サイズ４のリストを作るプログラム
•13
89
new_list(89)
NULL
このメモリアドレス = a
•14
67
insert_list(a, 67)
このメモリアドレス = a
89
NULL
•15
345
insert_list(a, 345)
このメモリアドレス = a
67
89
NULL
•16
12
insert_list(a, 12)
このメモリアドレス = a
345
67 89
NULL
•17
#include "stdio.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 main()
{
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;
}
•18
実際のメモリの中身
12 345 67 89 NULL
12, ポインタ
89, NULL
67, ポインタ
345, ポインタ
16進数表示であることに注意
構造体リストの長所
• 動的メモリ管理(new)により、必要な分だけのメモ
リを、好きなときに得られる。
→セル数の制限を気にしなくてよい
• 削除したセルの再利用も簡単化できる。
→ごみ集めの自動化が可能
•19
例題１．リストの要素の表示
• リストの個々の要素をたどり，要素値を順に表示
するプログラム
•20
リストの表示を行う関数
•21
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" );
}
•22
#include "stdio.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 main()
{
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;
}
•23
実行結果の例
例題２．リストの探索
• リストの個々の要素をたどり，要素による探索を
行うプログラム
•24
リストの探索
•25
12 345 67 89 NULL
find_list(67)
リストの探索
•26
12 345 67 89 NULL
find_list(67)
リストの探索
•27
12 345 67 89 NULL
find_list(67)
見付かった
リストの探索を行う関数
•28
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;;
}
•29
#include "stdio.h"
#include <math.h>
struct data_list {
int data;
struct data_list *next;
};
#include "stdio.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 main()
{
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;
}
例題３．リストの削除
• リストの個々の要素をたどり，要素の削除を行う
プログラム
•30
リストの削除
•31
12 345 67 89 NULL
delete_list(67)
リストの削除
•32
12 345 67 89 NULL
delete_list(67)
リストの削除
•33
12 345 67 89 NULL
delete_list(67)
y x
リストの削除
•34
12 345 89 NULL
delete_list(67)
y
リストの削除
•35
12 345 89 NULL
delete_list(67)
y
リストの削除を行う関数
•36
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;
}
•37
#include "stdio.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 main()
{
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;
}
再帰的構造体を用いた実装法
• データとポインタをメンバとする構造体を定義す
る。
• リストの末端はNULL（空ポインタ）
• 先頭の要素セルをおさえるためのポインタ変数を
使う（例題１，例題２，例題３でのメイン関数内
での変数 a ）
• 最後尾の要素セルをおさえるためのポインタ変数が役
立つ場合もある（次回授業でのリストの併合のケー
ス）
• 必要に応じて途中のセルをおさえるためのポイン
タ変数を適宜用意
•38
実習
• リストの長さを求める関数を作成しなさい
39
lengthの実行状況
•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
x
•44
12 345 67 89 NULL
結果：４
