データ構造とアルゴリズム 第11回 リスト構造（１）

Presentation on theme: "データ構造とアルゴリズム 第11回 リスト構造（１）"— Presentation transcript:

1 データ構造とアルゴリズム 第11回 リスト構造（１）
データ構造とアルゴリズム 第11回　リスト構造（１） 静岡大学工学部 安藤 和敏

2 目次 変数とメモリの復習 先週の復習 課題8の解説 リスト構造 リストのポインタを用いた実装 実習

3 コンピュータのメモリのイメージ アドレス 内容 175 1 2 安藤 3 4 浜松 5 6 2004 7 ．．． ．．．

4 変数とメモリ ．．． ．．． アドレス 内容 int x;
175 と宣言することによって、xという名前が付けられた4バイト分のメモリ領域が確保される。 1 2 安藤 3 4 浜松 5:x: 6 2004 7 確保されるバイト数はその変数の型に依存する。p.18の表2.3を見よ。 以降は、この確保されたメモリ領域の内容をx と言う名前で参照できるようになる。 ．．． ．．．

5 ポインタとメモリ（教科書p.143-144） int x; int *p=&x; ポインタ変数 pの内容=7 アドレス 内容
175 1:p: 7 2 安藤 3 4 浜松 xの宣言によって確保されたメモリ領域 5 6 2004 7:x:

6 以降では、前ページのような状況を図示するために、このような矢線を用いて表現する。
ポインタとメモリの関係の図示 int x; int *p=&x; 以降では、前ページのような状況を図示するために、このような矢線を用いて表現する。 アドレス 内容 p: x:

7 構造体ポインタとメモリ struct COMPLEX a={1,-2}; struct COMPLEX *p=&a; アドレス 内容
1 2 3:p: 5 4 (real) 1 5:a: aの宣言によって確保されたメモリ領域 (img) -2 7 8

8 構造体ポインタpを介してaのメンバrealを参照するときには、p->real,
構造体ポインタからのメンバの参照 struct COMPLEX a={1,-2}; struct COMPLEX *p=&a; メモリの内容 構造体ポインタpを介してaのメンバrealを参照するときには、p->real, p->img p: (real) 1 a: (img) -2

9 目次 変数とメモリの復習 先週の復習 課題8の解説 リスト構造 リストのポインタを用いた実装 実習

10 目次 変数とメモリの復習 先週の復習 課題8の解説 リスト構造 リストのポインタを用いた実装 実習

11 目次 変数とメモリの復習 先週の復習 課題8の解説 リスト構造 リストのポインタを用いた実装 実習

12 リストとは何か？ [10,8,4,23,95,6] [浜松, 湖西, 磐田, 袋井]
のように、ある決まった型の要素が順番に並べられたものをリストと呼ぶ。上の例は、整数のリストであるが整数でなくても良い。例えば、 [浜松, 湖西, 磐田, 袋井] もリストである。

13 リストの配列を用いた実装 リストは配列を用いて表現することもできる。例えば、次のリスト [10,8,4,23,95,6] は、以下のようにデータが入っている整数型の配列 a によって表現できる。 10 8 4 23 95 6 a 1 2 3 5

14 リストの配列を用いた実装の欠点 例えば、以下のように配列で表現されたリストの先頭に 2 を挿入するときに、どうしたらよいのか？ 10 8 4 23 95 6 a 1 2 3 5 10 8 4 23 95 6 a 10 8 4 23 95 6 a 10 8 4 23 95 6 a

15 リストの配列を用いた実装の欠点 10 8 4 23 95 6 a 10 8 4 23 95 6 a 10 8 4 23 95 6 a 10 8 4 23 95 6 a 2 2 を a の先頭に挿入するためには、全ての要素を右に一つずつ移動する必要がある！

16 目次 変数とメモリの復習 先週の復習 課題8の解説 リスト構造 リストのポインタを用いた実装 実習

17 リストのポインタを用いた実装 ― リスト構造 ―
リストのポインタを用いた実装 ― リスト構造 ― リスト構造と呼ばれるデータ構造を使えば、前のページで述べたような欠点は克服される。 リスト構造は、セルと呼ばれる構造体がポインタでつながれたものである。 ポインタ 10 8 4 セル 23 95 6

18 セル 10 8 4 23 95 6 一つのセルは、データと次のセルへのポインタからなる構造体である。 データ 次のセルへのポインタ root
先頭のセルへのポインタ 23 95 6

19 リスト構造のC言語による実装 （ソースコード list0.c の説明）
構造体タグ CELL　の宣言。 struct CELL { int data; struct CELL *next; }; CELL 構造体CELLは、int 型　data と構造体CELLへのポインタ next をメンバとして持つ。 (data) (next)

20 セルを作る（１） struct CELL *cell1, *cell2, *cell3; cell1 = (struct CELL *)
malloc(sizeof(struct CELL)); メモリの内容 ポインタ変数 cell1, cell2, cell3 のためのメモリ領域が確保される。 cell3: cell2: cell1:

21 セルを作る（２） struct CELL *cell1, *cell2, *cell3;
そのアドレスは、適切な型に変換（キャスト）されなければならない。 struct CELL *cell1, *cell2, *cell3; cell1 = (struct COMPLEX *) malloc(sizeof(struct COMPLEX)); (struct CELL *) malloc(sizeof(struct CELL)) メモリの内容 mallocによって確保されたメモリ領域。sizeof(struct CELL)バイト。mallocはこのメモリのアドレスを返す。 cell1: (data) (next)

22 それ以降は、ここの内容はポインタ cell1 を介して参照できる。
セルを作る（3） struct CELL *cell1,*cell2,*cell3; a = (struct CELL *) malloc(sizeof(struct CELL)); cell1 = メモリの内容 ポインタ変数 cell1 にmallocによって確保されたメモリのアドレスが代入される。 cell1: それ以降は、ここの内容はポインタ cell1 を介して参照できる。 cell1->data, cell1->next で。 (data) (next)

23 セルを作る（4） struct CELL *cell1,*cell2,*cell3; cell1 =(struct CELL *)
malloc(sizeof(struct CELL)); cell1->data = 10; cell1->next = NULL; cell1: (data) 10 (next) NULL

24 以降では、この様に簡略化した図を用いて説明をする。
セルを作る（4） struct CELL *cell1,*cell2,*cell3; cell1 =(struct CELL *) malloc(sizeof(struct CELL)); cell1->data = 10; cell1->next = NULL; 以降では、この様に簡略化した図を用いて説明をする。 cell1: (data) 10 cell1 (data) (next) 10 NULL (next) NULL

25 同様にして、セルへのポインタ cell2 と cell3 は左図のようなセルを指し示すようになる。
(data) (next) 10 NULL 同様にして、セルへのポインタ cell2 と cell3 は左図のようなセルを指し示すようになる。 cell2 (data) (next) 8 NULL cell3 (data) (next) 4 NULL

26 cell1の指し示すセル構造体のアドレスをrootに代入する。
セルをつなげる (1) root = cell1; cell1->next=cell2; cell2->next=cell3; (data) (next) cell1 10 NULL root (data) (next) cell2 8 NULL cell1の指し示すセル構造体のアドレスをrootに代入する。 (data) (next) cell3 4 NULL

27 cell2の指し示すセル構造体のアドレスを
セルをつなげる (2) root = cell1; cell1->next=cell2; cell2->next=cell3; (data) (next) cell1 10 NULL root (data) (next) cell2 8 NULL cell2の指し示すセル構造体のアドレスを cell1->nextに代入する。 (data) (next) cell3 4 NULL

28 cell3の指し示すセル構造体のアドレスを
セルをつなげる (3) root = cell1; cell1->next=cell2; cell2->next=cell3; (data) (next) cell1 10 root (data) (next) cell2 8 NULL cell3の指し示すセル構造体のアドレスを cell2->nextに代入する。 (data) (next) cell3 4 NULL

29 目次 変数とメモリの復習 先週の復習 課題8の解説 リスト構造 リストのポインタを用いた実装 実習