ダイクストラ法の実装

データ構造とアルゴリズム
第11回リスト構造（１）
静岡大学工学部
安藤和敏
2011.06.24
目次
1. 変数とメモリの復習
2. 先週の復習
3. 課題8の解説
4. リスト構造
5. リストのポインタを用いた実装
6. 実習
コンピュータのメモリのイメージ
アドレス
内容
0
1
2
3
4
5
6
7
175
．
．
．
安藤
浜松
2004
．
．
．
変数とメモリ
int x;
と宣言することに
よって、xという名前
が付けられた4バイ
ト分のメモリ領域が
確保される。
確保されるバイト数
はその変数の型に
依存する。p.18の表
2.3を見よ。
アドレス
0
1
2
3
4
5:x:
6
7
内容
175
安藤
浜松
2004
．
．以降は、この確保されたメモ
と言う名前
．リ領域の内容をx．
．
．で参照できるようになる。
ポインタとメモリ（教科書p.143-144）
int x;
int *p=&x;
アドレス
内容
0
1:p:
2
3
4
5
6
7:x:
175
7
安藤
浜松
2004
ポインタ変数 pの
内容=7
xの宣言によっ
て確保されたメ
モリ領域
ポインタとメモリの関係の図示
int x;
int *p=&x;
アドレス
p:
x:
内容
以降では、前
ページのよう
な状況を図示
するために、
このような矢
線を用いて表
現する。
構造体ポインタとメモリ
struct COMPLEX a={1,-2};
struct COMPLEX *p=&a;
アドレス
0
1
2
3:p:
4
5:a:
7
8
内容
ポインタ変数 pの
内容=5
5
(real) 1
(img) -2
aの宣言によっ
て確保されたメ
モリ領域
構造体ポインタからのメンバの参照
struct COMPLEX a={1,-2};
struct COMPLEX *p=&a;
メモリの内容
p:
a:
(real) 1
(img) -2
構造体ポインタ
pを介してaのメ
ンバrealを参照
するときには、
p->real,
p->img
目次
1. 変数とメモリの復習
2. 先週の復習
3. 課題8の解説
4. リスト構造
5. リストのポインタを用いた実装
6. 実習
目次
1. 変数とメモリの復習
2. 先週の復習
3. 課題8の解説
4. リスト構造
5. リストのポインタを用いた実装
6. 実習
目次
1. 変数とメモリの復習
2. 先週の復習
3. 課題8の解説
4. リスト構造
5. リストのポインタを用いた実装
6. 実習
リストとは何か？
[10,8,4,23,95,6]
のように、ある決まった型の要素が順番に並べられた
ものをリストと呼ぶ。上の例は、整数のリストであるが
整数でなくても良い。例えば、
[浜松, 湖西, 磐田, 袋井]
もリストである。
リストの配列を用いた実装
リストは配列を用いて表現することもできる。例えば、
次のリスト
[10,8,4,23,95,6]
は、以下のようにデータが入っている整数型の配列
a によって表現できる。
a
0
10
1
8
2
4
3 4
23 95
5
6
6
リストの配列を用いた実装の欠点
例えば、以下のように配列で表現されたリストの先頭
に 2 を挿入するときに、どうしたらよいのか？
a
0
10
1
8
2
4
3 4
23 95
a
10
8
4
23 95
a
10
8
4
23
a
10
8
4
5
6
6
6
95 6
23 95
6
リストの配列を用いた実装の欠点
a
10
a
10
a
a
2
8
4 23 95
6
8
4 23 95
6
10 8
4 23 95
6
10 8
4 23 95
6
2 を a の先頭に挿入するためには、全ての要素を
右に一つずつ移動する必要がある！
目次
1. 変数とメモリの復習
2. 先週の復習
3. 課題8の解説
4. リスト構造
5. リストのポインタを用いた実装
6. 実習
リストのポインタを用いた実装
― リスト構造 ―
リスト構造と呼ばれるデータ構造を使えば、前のペー
ジで述べたような欠点は克服される。
リスト構造は、セルと呼ばれる構造体がポインタでつ
ながれたものである。
ポインタ
10
セル
8
23
4
95
6
セル
一つのセルは、データと次のセルへのポインタからな
る構造体である。
データ
root
10
先頭のセ
ルへのポイ
ンタ
次のセルへのポインタ
8
23
4
95
6
リスト構造のC言語による実装
（ソースコード list0.c の説明）
struct CELL {
int data;
struct CELL *next;
};
CELL
(data) (next)
構造体タグ CELL
の宣言。
構造体CELLは、
int 型 data と
構造体CELLへのポ
インタ next をメン
バとして持つ。
セルを作る（１）
struct CELL *cell1, *cell2, *cell3;
cell1 = (struct CELL *)
malloc(sizeof(struct CELL));
メモリの内容
cell3:
cell2:
cell1:
ポインタ変数
cell1, cell2,
cell3 のための
メモリ領域が確保
される。
セルを作る（２）そのアドレスは、適
切な型に変換（キャ
struct CELL *cell1, *cell2,スト）されなければ
*cell3;
cell1 = (struct
(struct CELL
COMPLEX
ならない。
*) *)
malloc(sizeof(struct
COMPLEX));
malloc(sizeof(struct
CELL))
メモリの内容
cell1:
(data)
(next)
mallocによって確
保されたメモリ領域。
sizeof(struct
CELL)バイト。
mallocはこのメモリ
のアドレスを返す。
セルを作る（3）
struct CELL *cell1,*cell2,*cell3;
a =
cell1
= (struct CELL *)
malloc(sizeof(struct CELL));
メモリの内容
ポインタ変数 cell1
にmallocによって確
保されたメモリのアドレ
スが代入される。
cell1:
(data)
(next)
それ以降は、ここの内
容はポインタ cell1
を介して参照できる。
cell1->data,
cell1->next で。
セルを作る（4）
struct CELL *cell1,*cell2,*cell3;
cell1 =(struct CELL *)
malloc(sizeof(struct CELL));
cell1->data = 10;
cell1->next = NULL;
cell1:
(data)
(next)
10
NULL
セルを作る（4）
struct CELL *cell1,*cell2,*cell3;
cell1 =(struct CELL *)
malloc(sizeof(struct CELL));
cell1->data = 10;
cell1->next = NULL;
以降では、この様に簡
略化した図を用いて説
明をする。
cell1:
(data)
(next)
10
NULL cell1
(data) (next)
10 NULL
セルを作る (cell2, cell3)
(data) (next)
cell1
10 NULL
(data) (next)
cell2
8
NULL
(data) (next)
cell3
4
NULL
同様にして、セ
ルへのポインタ
cell2 と
cell3 は左図
のようなセルを
指し示すように
なる。
セルをつなげる (1)
(data) (next)
cell1
root
10 NULL
root = cell1;
cell1->next=cell2;
cell2->next=cell3;
(data) (next)
cell2
8
NULL
(data) (next)
cell3
4
NULL
cell1の指し示すセル構
造体のアドレスをrootに
代入する。
セルをつなげる (2)
(data) (next)
cell1
root
10 NULL
root = cell1;
cell1->next=cell2;
cell2->next=cell3;
(data) (next)
cell2
8
NULL
(data) (next)
cell3
4
NULL
cell2の指し示すセル構造
体のアドレスを
cell1->nextに代入する。
セルをつなげる (3)
(data) (next)
cell1
root
10
root = cell1;
cell1->next=cell2;
cell2->next=cell3;
(data) (next)
cell2
8
NULL
(data) (next)
cell3
4
NULL
cell3の指し示すセル構造
体のアドレスを
cell2->nextに代入する。
目次
1. 変数とメモリの復習
2. 先週の復習
3. 課題8の解説
4. リスト構造
5. リストのポインタを用いた実装
6. 実習

Download Report