リスト （list）
一定の型の要素を，０個以上，一列に，順序付けて並べたデ タ構造．
データ構造．
線形リスト（linear list），列，並び（sequence）
リストの例：
例
学籍番号の並び
509004650900235090004

5090032

リストの操作（リストの抽象データ型）：
リストの操作（リストの抽象デタ型）：
初期化，要素の追加，参照（ｎ番目），削除，探索（指定された値を探す），
前
前の要素，後の要素，先頭要素，最終要素．
素 後素
素
終 素
リスト結合・分割・複製・要素数

algorithm@sis１次元配列によるリストの実現
添字で参照
リストの大きさがｎのとき：参照は計算量Ｏ（１）．
特定されている位置への追加 削除は特定されている位置への追加，削除は，ｎ／２ ～ Ｏ（ｎ）．
追加 削除要素に続く要素を追加，削除要素に続く要素を，移動させる．
探索は
探索は，ｎ／２／２ ～ Ｏ（ｎ）．
Ｏ（ ）0| data-0

1| data-1

2| data-2

3| ddata-3
t 3

n - 2 | data-x
n - 1 | data-y|algorithm@sis連結リスト （linked list） によるリストの実現
セル：

リスト要素のデータと，次のセルの所在場所を収めるデータ構造．
要素のデータ｜

次のセルの場所所在場所を指定することで，次のセルをつなぎ，リストとする.
リストとする
46 |

23 |

04 |

35| /

algorithm@sis

構造体 （structure）
複数のデ タをまとめ，１つの変数のように扱う．
複数のデータをまとめ，１つの変数のように扱う．
struct personali t id;int
int lang;
int math;};{

int main( ) {struct personal/* メンバ：学籍番号
メンバ 学籍番号 *//* メンバ：国語の成績 *//* メンバ：数学の成績 */ken;

ken.id = 5101; ken.lang = 90;
printf (" %d, %d ¥n",
ken idken.id,ken.lang + ken.math);/* 構造体変数の宣言 */ken.math = 95;/* メンバへの代入 *//* 学籍番号の表示 *//* 国語，数学の計 */}algorithm@sis

ポインタ （pointer）：
メモリ上にあるデ タのアドレスとデ タの大きさを持つ．
メモリ上にあるデータのアドレスとデータの大きさを持つ．
整数型変数とポインタの例

構造体変数とポインタの例

int main ( ) {int k;/* int 変数 k */int *p;p;/* ポインタ変数/p */k = 3;
p = &k;/* アドレス演算 *///int main ( ) {struct personal
struct personal

ken;
*q;
q;

ken.id = 5101;
ken.lang = 90;
ken.math = 95;
q = &ken;printf("%d, %d, %d ¥n",kk,*p,/* 間接参照 */*p + 2);

printf ("%d, %d ¥n",ken.id,ken lang + ken
ken.lang
ken.math);math);
printf ("%d, %d ¥n",q->id,q->lang
q>lang + q->math);q >math);}}algorithm@sis構造体によるセルの実現１
struct list_elm0 {
int
id;
struct list_elm0
list elm0 *next;
};
リスト：
リスト
構造体変数：

46ａ23ｂ/* 要素データ *//* 次のセルの場所 */04ｃ35
ｄａ（46，ｂへのポインタ）→ ｂ（23，ｃへのポインタ）→ ｃ（04，ｄへのポインタ）（04 ｄへのポインタ）→ ｄ（35，end ）先頭セル lst
|

46 |

23 |

04 |

35| /

46 |

23 |

04 |

35| /
algorithm@sis

#include <stdio.h>
struct list_elm0 {
intid;
struct list_elm0};

4623
432

*next;

int main(void) {struct list_elm0 lst;
struct list_elm0 a, b, c, d;struct list_elm0
list elm0 x;

x = lst;while (1) {if (x.next == NULL)
br k;
break;
x = *x.next;printf ("%d ¥n", x.id);}

lst.next = &a;a id = 46;
a.ida next = &b;a.nextb.id = 23;b.next = &c;c.id = 04;
c.next = &d;d id = 32
d.id32;
dd.next= NULL
NULL;}

algorithm@sis

構造体によるセルの実現２（混在した型のデータ）
学籍番号： 46
2304
32
・・・
名前：
Beth John Mick Kate
structlist_elm1 {
intid;
char
name[21];struct list_elm1*next;};
キーと，キーに対応つけたデータの組を要素とした
リスト → 連想リスト （association list）
学籍簿： id をキーとして，対応する名前を探索．
lst|46 |23 |04 |32| /---

algorithm@sis構造体単純変数での実現

b.id = 23;
strcpy(b.name, "John");bb.nextt = &&c;;#include <stdio.h>#include <string.h>
struct list_elm1 {
intid;
char
name[21];struct list_elm1};

c.id = 04;
strcpy(c.name,t("MiMickk"););
c.next = &d;d.id
did = 32
32;
strcpy(d.name, "Kate");d.next = NULL;*next;

int main(void){
struct list_elm1
lst, a, b, c, d, x;

46 Bethx = lst;
23 Johnwhile (1) {4 Mickif ((x.next == NULL)
32 Katebreak;x = *x.next;("%s ¥n","printf ("%dx.id, x.name);}

lst.next = &a;a.id = 46;
strcpy(a.name,py(, "Beth");)a.next = &b;}
algorithm@sisセルによる連結リスト操作の計算量
追加，削除：

特定されている位置の後ろへの追加，削除は，Ｏ（１）．
ポインタの書き換えですむ．

参照 探索：
参照，探索：

ｎ／２ ～ Ｏ（ｎ）
← 位置の特定するためには，参照，探索が必要．

リスト結合，リスト分割：
長さ，位置のポインタが特定されていれば，ポがばＯ（１）．
リスト複製，リスト要素数：

Ｏ（ｎ）．

algorithm@sis

循環リスト （circular list）
最終要素の指す先が，先頭要素，または，リストの頭．
双方向リスト（doubly-linked list： 双方向連結リスト）
次の要素へのポインタとともに，直前の要素へのポインタを持つ．
structlist_elm2 {
intid;
char
name[21];struct list_elm2
struct list_elm2}* previous;* next;

特定位置の，前後の，追加，削除が，Ｏ（１）で可能．

algorithm@sis