コンピュータ基礎演習ースタックー

コンピュータ基礎演習
ー探索、整列ー
岩井儀雄
[email protected]
線形探索と二分探索

線形探索法(linear search)
データを最初から順番に探索する
例）{2, 4, 5, 8, 9, 11, 6, 7, 15, 20} から15を探す
最初の要素から始めて９回目→計算量O(n)


二分探索法(binary search)

データをあらかじめソートしておき，中央の要素から検
索する．
二分探索(binary search)

{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す
１回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20}
二分探索(binary search)

{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す
２回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20}
二分探索(binary search)

{2, 4, 5, 6, 7, 8, 9, 11, 15, 20} から15を探す
３回目
{2, 4, 5, 6, 7, 8, 9, 11, 15, 20}
探索回数
計算量
３回
log2(n)
O(log n)
整列(sort)

内部整列(internal sort)


主記憶上で行う整列
外部整列(external sort)

外部記憶装置（テープ等）上で行う
整列アルゴリズムの優劣→比較回数と交換回数の大小
安定な整列(stable sort)

同じ値を持つデータ間の順序関係が整
列の前後で保たれている
例）整列前： 7 9 5A 4 8 5B 2
整列後： 2 4 5A 5B 7 8 9 （安定）
整列後： 2 4 5B 5A 7 8 9 （不安定）
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
整列前 20 6 55 74 3 45 13 87 46 30
１回目
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 87 30 46
入替
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 87 30 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 30 87 46
入替
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 30 87 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 45 13 30 87 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 13 45 30 87 46
入替
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20 6 55 74 3 13 45 30 87 46
比較
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
１回目 20
20
20
20
3
6 55 74 3 13
6 55
3 74 13
6
3 55 74 13
3
6 55 74 13
20 6 55 74 13
45
45
45
45
45
30
30
30
30
30
87
87
87
87
87
46
46
46
46
46
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
２回目 3 20 6 55 74 13 45 30 87 46
46 87
30 46
30 45
13 30
13 74
13 55
6 13
6 20
単純な整列（バブルソート）

配列の後ろから先頭に向かって走査し，もし隣り合う二つ
の要素の大小関係が逆であったら入れ替える
２回目
３回目
４回目
５回目
６回目
７回目
８回目
９回目
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
20
13
13
13
13
13
13
13
13
20
20
20
20
20
20
20
55
30
30
30
30
30
30
30
74
55
45
45
45
45
45
45
30
74
55
46
46
46
46
46
45
45
74
55
55
55
55
55
46
46
46
74
74
74
74
74
87
87
87
87
87
87
87
87
バブルソート（疑似コード）
for (i←0..n-1)
for (j←n-1..i)
if !(a[j-1] ≦ a[j])
swap(a[j-1],a[j])
右辺値の交換
整列アルゴリズムが満たす事後条件
 < j]  a[i]  a[ j]
i,j[i
計算量は O(n2)
バブルソート（Ｃ言語）
for (i←0..n-1)
for (j←n-1..i)
if !(a[j-1] ≦ a[j])
swap(a[j-1],a[j])
void bubble_sort(int a[],int n) {
int I,j,t;
for (int I=0; I<n-1; ++I)
for (int j=n-1; j>I; --j)
if (a[j-1] > a[j]) {
t = a[j]; a[j] = a[j-1]; a[j-1] = t;
}
swap(a[j-1],a[j])に相当する
}
単純な整列（選択ソート）

未整列部分から最小の要素を選び出し，それを未整
列部分の先頭と入れ替える
  a[1] 
a[0]
整列済
 a[i –1]  a[i] 
a[n –1]
未整列部分
未整列部分から最小値を取り出し
続けると下記の条件を満たす
整列アルゴリズムが満たす事後条件
 < j]  a[i]  a[ j]
i,j[i
選択ソート
整列前 20
１回目
6
55
入替
74
3
45
13
87
46
30
選択ソート
整列前 20
１回目 3
6
6
55
55
74
74
3
20
45
45
13
13
87
87
46
46
30
30
選択ソート
整列前 20
１回目 3
２回目 3
6
6
6
55 74
3 45 13 87 46 30
55 74 20 45 13 87 46 30
55 74 20 45 13 87 46 30
入替
選択ソート
整列前 20
１回目 3
２回目 3
３回目 3
４回目 3
５回目 3
６回目 3
７回目 3
８回目 3
９回目 3
6 55
6 55
6 55
6 13
6 13
6 13
6 13
6 13
6 13
6 13
74
74
74
74
20
20
20
20
20
20
3
20
20
20
74
30
30
30
30
30
45
45
45
45
45
45
45
45
45
45
13
13
13
55
55
55
55
46
46
46
87
87
87
87
87
87
87
87
55
55
46
46
46
46
46
46
46
55
87
74
30
30
30
30
30
74
74
74
74
87
選択ソート（疑似コード）
for (i←0..n-2)
lowest←argmin(a[j])
i<j<n
swap(a[i],a[lowest])
選択ソート（Ｃ言語）
void selection_sort(int a[],int n) {
int i,j,t,lowest,lowval;
for (i = 0; i<n-1; ++i) {
argminの計算部分
lowest = i; lowval = a[i];
for (j = i+1; j < n; ++j)
if (a[j] < lowval) {
lowval = a[j]; lowest = j;
}
t = a[I]; a[I] = a[lowest]; a[lowest] = t;
}
}
選択ソートの計算量


ループ n 回，argmin の計算量 O(n)
選択ソートの計算量は O(n2)
単純な整列（挿入ソート）

配列の一部分が整列済みの時に，残りの要素
を一つずつ整列済みの中に挿入する
整列前 20 6 55
１回目 6 20 55
２回目 6 20 55
３回目 6 20 55
４回目 3 6 20
５回目 3 6 20
６回目 3 6 13
７回目 3 6 13
８回目 3 6 13
９回目 3 6 13
74
74
74
74
55
45
20
20
20
20
3
3
3
3
74
55
45
45
45
30
45
45
45
45
45
74
55
55
46
45
13
13
13
13
13
13
74
74
55
46
87
87
87
87
87
87
87
87
74
55
46
46
46
46
46
46
46
46
87
74
30
30
30
30
30
30
30
30
30
87
挿入ソート（疑似コード）
for (i←0..n-1)
j←i
while (! (a[j-1] ≦ a[j]) )
swap( a[j-1], a[j] )
j←j-1
計算量：外側ループ O(n)
内側ループ O(n)
合計： O(n2)
コンピュータ基礎演習
ー計算量ー
岩井儀雄
[email protected]
計算量(complexity)

時間計算量(time complexity)


空間計算量(space complexity)



アルゴリズムがデータに対してどれくらい時間がかかるか
を示す
アルゴリズムがデータに対してどれくらい記憶領域を必要
とするかを示す
時間計算量と空間計算量はトレードオフの関係にあ
ることが多い
計算機にとって記憶資源は潤沢にあるので，通常時
間計算量の方が重きを置かれることが多い
オーダー記法Ｏ

計算量T(n)の上界値を評価するとき，
O(f(n))という記法を用い，オーダーf(n) と
読む．

c,n 0 c > 0, n  n 0  T(n)  cf (n)
ある正定数cとn0が存在して，n0以上のnに対して，
常に T(n) ≦cf(n) が成立するという意味
n0の役割は有限個の例外を許すことにある．
オーダー記法Ω

計算量の下界値のオーダーを表すには，
記法Ωを用いる．T(n)=Ω(f(n))とは，

cn T(n)  cf (n)
計算量とオーダ表記の関係
計算量の上界O
計算量
実際の計算量
有限個の
例外はOK
計算量の下界Ω
n0
n
オーダーの演算

T1 = O( f (n)), T2 = O(g(n))
T1 + T2 = O(max( f (n),g(n)))
T1  T2 = O( f (n) g(n))
例） T1 = O(n 2), T2 = O(n 3)
T1 + T2 = O(n 3)
T1  T2 = O(n 5)
最悪計算量と平均計算量


同じアルゴリズムでも入力するデータに応じ
て計算量が変化する．そこで，客観的に測定
し評価する必要がある．
最悪計算量 worst case complexity


全ての入力パターンに対して最大の計算量を要す
るものに基づいて定める
平均計算量 average complexity

全ての入力パターンとその入力の生起確率に基づ
いて計算量の平均を求める
コンピュータ基礎演習
ー再帰ー
岩井儀雄
[email protected]
再帰

再帰的(recursive)な構造とは，自分自身
(n次)を定義するのに，自分自身より1次
低い集合(n-1次)を用い，さらにその部
分集合は，より低次の部分集合を用い
て定義するということを繰り返す構造．
このような構造を一般的に再帰
(recursion)と呼ぶ．
再帰

数学ではいろいろな概念を再帰的に定
義している．
例）数列
a 1,a 2,
a1 = 1
an = an – 1 + 2n – 1
再帰呼び出し

関数の中で自分自身を関数として呼び
出すこと
例）数列
a 1,a 2,
a1 = 1
an = an – 1 + 2n – 1
int A(int n) {
if (n == 1) return 1; /* 再帰呼び出しの停止条件 */
else return A(n-1)+2*n-1;
}
再帰呼び出し例

階乗(n!)の計算プログラム
f0 = 1
fn = n  fn – 1
#include <stdio.h>
int factorial(int n) {
if (n == 0) return 1;
else return n*factorial(n-1);
}
int main() {
int n;
for (n=0; n<10; ++n)
printf( “ %2d! = %d\n”, n, factorial(n) );
return 0;
}
階乗(n!)の計算実行例
0!
1!
2!
3!
4!
5!
6!
7!
8!
9!
=
=
=
=
=
=
=
=
=
=
1
1
2
6
24
120
720
5040
40320
362880
実行：PowerBook G4, MacOS X 10.2.5, gcc 3.1
10!
11!
12!
13!
14!
15!
16!
17!
18!
19!
=
=
=
=
=
=
=
=
=
=
3628800
39916800
479001600
1932053504
1278945280
2004310016
2004189184
-288522240
-898433024
109641728
演算結果が正しくない
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 3555687428096000
18! = 64023737057280000
19! = ？
intが32ビットなら，正の数は
231 = 2147483648までしか表現できない
演習課題

フィボナッチ数列を再帰を用いて求める
f1 = f2 = 1
fn = fn – 1 + fn – 2
#include <stdio.h>
int fibonacci(int n) {
if (n == 1 || n == 2) return 1;
else return fibonacci(n-1)+fibonacci(n-2);
}
int main() {
int n;
for (n=0; n<20; ++n)
printf( “ %2d! = %d\n”, n, fibonacci(n) );
return 0;
}
コンピュータ基礎演習
ーリスト構造ー
岩井儀雄
[email protected]
ADT Stack (スタック)



データの集まり
一番上の要素しか操作できない
イメージ的には物を上に積んだ状態
スタックに可能な操作
・一番上の要素の値を見る(top)
・一番上の要素を取り除く(pop)
・上に要素を積む(push)
・スタックが空？(isEmpty)
・スタックの要素数(size)
ADT Queue(待ち行列）



データの集まり
要素の挿入，削除が端でしかできない
イメージ的には人の待ち行列
待ち行列の先頭
ADT Stack, ADT Queue の実装

前回は配列を使って実装した
今回はリスト構造を使って実装する

→まずはリスト構造について

リスト構造



連結リスト
循環リスト
双方向リスト
連結リスト(Linked list)




データの集まり
データが一覧表（リスト）のように連なっている構造
連なりの表現には効率のため，ポインタが用いられることが多い
もちろん，配列とインデックスでも実装できる（リスト容量が制限）
データ
データ
データ
DATA[0]
DATA[1]
DATA[2]
…
DATA[N]
データ
未使用
データ
…
データ
IDX[0]
IDX[1]
IDX[2]
…
IDX[N]
2
-1
N
…
EOD
連結リストの操作









要素の挿入 (insert)
要素の削除 (erase)
リストの連結（concatenate）
リストの分断 (split)
要素の探索 (find)
空リストの生成 (create)
要素数 (size)
先頭要素を見る (front)
最後尾要素を見る(tail)
連結リストの操作

要素の挿入 (insert)

指定された要素の次の位置に要素を挿入する
B
A
C
D
連結リストの操作

要素の挿入 (insert)

指定された要素の次の位置に要素を挿入する
B
A
C
D
連結リストの操作

要素の削除 (erase)

指定された要素を削除する
B
A
C
D
連結リストの操作

要素の削除 (erase)

指定された要素を削除する
B
A
D
連結リストの操作

リストの連結 (concatenate)

B
A
指定された要素の次の位置にリストを連結する
D
E
F
連結リストの操作

リストの連結 (concatenate)

B
A
指定された要素の次の位置にリストを連結する
D
E
F
連結リストの操作

リストの分断 (split)

B
A
指定された要素の次の位置からリストを分断する
D
E
F
連結リストの操作

リストの分断 (split)

B
A
指定された要素の次の位置からリストを分断する
D
E
F
連結リストの操作

要素の探索 (find)

指定された値を持つ要素の位置を返す
B
A
B
D
連結リストの操作

要素の探索 (find)

指定された値を持つ要素の位置を返す
B
A
B
D
連結リストの操作

空リストの生成 (create)


要素のないリスト
なぜ必要か？
要素をすべて削除したり，分断で空になったりする


どう表す？
ヘッダを付加して表現
ヘッダのみの場合は空リストとして扱う


header
A
B
D
連結リストの操作

空リストの生成 (create)


要素のないリスト
なぜ必要か？
要素をすべて削除したり，分断で空になったりする


どう表す？
ヘッダを付加して表現
ヘッダのみの場合は空リストとして扱う


header
A
B
D
構造体とポインタを用いた
連結リストの実装

構造体を利用する利点


データと次のデータへのポインタが同時に管理できる
ポインタを利用する利点



ヒープ領域を利用して動的にメモリを使用できる
固定のサイズに依存しない
要素の位置指定に利用できる
struct CELL {
struct CELL *next; /* 次のデータへのポインタ */
DATATYPE data;
/* 格納されるデータ */
};
構造体とポインタを用いた
連結リストの実装

空リストの生成 (create)

ヘッダを作成して初期化する
struct CELL myList; /* List を表すヘッダ変数 */
myList.next = NULL; /* 空を示す */
myList.data = 0; /* header の data は使用されないが，
一応 int 型として話を進める */
リストの生成はよく使う＆要素の生成にも利用できる
ので関数にする
構造体とポインタを用いた
連結リストの実装

空リスト(要素)の生成 (create)


ヘッダを作成して初期化する
作成したヘッダをポインタとして返す
struct CELL *create(DATATYPE data) {
struct CELL *p = (struct CELL*)malloc(sizeof(struct CELL));
p->next = NULL;
p->data = data;
struct CELL の格納領域を
return p;
ヒープ領域に確保する
}
空リスト（要素）生成の
実装（Ｃ言語）
struct CELL *create(DATATYPE data) {
struct CELL *p = (struct CELL*)malloc(sizeof(struct CELL));
p->next = NULL;
p->data = data;
struct CELL の格納領域を
return p;
ヒープ領域に確保する
}
間違ったコーディング例）
struct CELL *create(DATATYPE data) {
struct CELL p; /* 局所変数 */
p.next = NULL;
p.data = data;
return &p;
/* 関数からでた途端に局所変数は有効でなくなる */
}
要素挿入の実装

指定された要素の次の位置に挿入する


要素の指定にはポインタを利用する
挿入する要素もポインタで指定する
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
pos->next = val;
}
pos
val
B
A
C
要素挿入の実装

指定された要素の次の位置に挿入する


要素の指定にはポインタを利用する
挿入する要素もポインタで指定する
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
pos->next = val;
}
pos
val
B
A
C
要素挿入の実装

指定された要素の次の位置に挿入する


要素の指定にはポインタを利用する
挿入する要素もポインタで指定する
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
pos->next = val;
}
pos
val
B
A
C
要素削除の実装

指定された要素の次を削除する


要素の指定にはポインタを利用する
削除された要素のポインタを返す
struct CELL *erase( struct CELL *pos ) {
struct CELL *p = pos->next;
if (p != NULL) { pos->next = p->next; p->next = NULL; }
return p;
}
pos
B
A
C
要素削除の実装

指定された要素の次を削除する


要素の指定にはポインタを利用する
削除された要素のポインタを返す
struct CELL *erase( struct CELL *pos ) {
struct CELL *p = pos->next;
if (p != NULL) { pos->next = p->next; p->next = NULL; }
return p;
}
pos
p
B
A
C
要素削除の実装

指定された要素の次を削除する


要素の指定にはポインタを利用する
削除された要素のポインタを返す
struct CELL *erase( struct CELL *pos ) {
struct CELL *p = pos->next;
if (p != NULL) { pos->next = p->next; p->next = NULL; }
return p;
}
pos
p
B
A
C
最後尾要素を見る(tail)

リストの最後尾を返す
header
A
B
tail の実装

リストの最後尾を返す
struct CELL *tail( struct CELL *pos ) {
while (pos->next != NULL) pos = pos->next;
return pos;
}
pos
header
A
B
tail の実装

リストの最後尾を返す
struct CELL *tail( struct CELL *pos ) {
while (pos->next != NULL) pos = pos->next;
return pos;
}
pos
header
A
B
tail の実装

リストの最後尾を返す
struct CELL *tail( struct CELL *pos ) {
while (pos->next != NULL) pos = pos->next;
return pos;
}
pos
header
A
B
tail の実装

リストの最後尾を返す
struct CELL *tail( struct CELL *pos ) {
while (pos->next != NULL) pos = pos->next;
return pos;
}
header
A
B
リスト連結の実装


二つのリストのヘッダを渡す
連結されたヘッダを返す
struct CELL *concatenate( struct CELL *L1, struct CELL *L2 );
header
A
C
B
D
リスト連結の実装


二つのリストのヘッダを渡す
連結されたヘッダを返す
struct CELL *concatenate( struct CELL *L1, struct CELL *L2 ) {
struct CELL *p = tail( L1 );
insert( p, L2->next ); L2->next = NULL;
return L1;
};
header
L1
A
L2
C
B
D
リスト連結の実装


二つのリストのヘッダを渡す
連結されたヘッダを返す
struct CELL *concatenate( struct CELL *L1, struct CELL *L2 ) {
struct CELL *p = tail( L1 );
insert( p, L2->next ); L2->next = NULL;
return L1;
p
};
header
L1
A
L2
C
B
D
リスト連結の実装


二つのリストのヘッダを渡す
連結されたヘッダを返す
struct CELL *concatenate( struct CELL *L1, struct CELL *L2 ) {
struct CELL *p = tail( L1 );
insert( p, L2->next ); L2->next = NULL;
return L1;
p
};
header
L1
A
L2
C
B
D
リスト連結の実装


二つのリストのヘッダを渡す
連結されたヘッダを返す
struct CELL *concatenate( struct CELL *L1, struct CELL *L2 ) {
struct CELL *p = tail( L1 );
insert( p, L2->next ); L2->next = NULL;
return L1;
p
};
header
L1
A
L2
C
B
D
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val );
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
p
header
A
B
C
要素探索の実装



要素を比較し等価な要素を探索
最初に見つかった要素の位置を返す
なければ NULL を返す
struct CELL *find( struct CELL *p, DATATYPE val ) {
p = p->next;
while (p != NULL)
if (isEqual(p.data, val)) return p; else p = p->next;
return p;
}
header
A
B
C
p
等価判定関数 isEqual の実装

等価判定




二つのデータが等しいかどうか
演算子=は基本データ型にしか利用できない
DATATYPE の中身で等価判定関数は異なる
（実装，設計により異なる）
等価とはどういうことか定義が必要
int isEqual(DATATYPE d1, DATATYPE d2);
d1 と d2 が等価ならば !0
そうでないならば 0 を返す
循環リスト
連結リスト linked list
header
A
B
C
B
C
循環リスト circular list
header
A
後ろに移動し続ければ，先頭に戻れる
循環リストの特徴と目的



環状に並んだデータ構造を表現
要素を結び合わせるポインタをたどれ
ば，循環リストに含まれる全要素を順
番に処理できる
厳密には「最初」と「最後」の要素と
いうものは存在しない
循環リストの操作

要素の挿入・削除


連結リストの場合と同様
要素の追跡(trace)


基本的に連結リストと同様
最後尾がNULLでは判定できないので工夫
が必要→追跡を開始した要素に到達したら
終了
要素追跡の実装例
struct CELL *p, *ptr; /* 追跡用のポインタ変数 */
if (ptr != NULL) { /* 追跡開始点 ptr */
p = ptr;
/* 追跡開始点を作業用変数 p にコピー */
do {
/* p が指すセルの処理 */
p = p->next;
} while (p != ptr); /* 開始点まで戻ってきたら終了 */
}
変数 ptr が NULL なら，この循環リストは空（要素なし）なので何もしない．
リストが空でないなら，セルを順番にたどって処理する
Do .. While 形式によりループ末尾で終了条件を判断する

Download Report