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