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

前回の問題 問題 以下の４個のメンバーから構成される構造体を定義せよ。型名をIMAGEとする。 ・整数値の番号 n ・ローマ字タイトル　name　 ・実数値の平均輝度　avL ・次のIMAGE型構造体へのポインタ　next

前回の問題の解答 struct IMAGE{ int n; 正答率＝41％ char name[20]; double avL; struct IMAGE *next; }; 正答率＝41％ 簡単すぎるかと反省してたので、ちょっとビックリでガッカリ 文字数を指定して文字列にする！ 多かった間違い 第１位　char name; 　⇒　char name[20]; 第２位　セミコロン無し

前回の復習 配列 構造体 ポインタ data[0] 170 data[1] 160 data[2] 158 STUDENT name height 変数st1 １００

復習のつづき ＊ ← この記号の名前は「アスタリスク」。使われている状況によって意味が異なるので注意。 ＊　←　この記号の名前は「アスタリスク」。使われている状況によって意味が異なるので注意。 int *a; のように書かれていたら、 　「aはint型の変数を指せるポインタだよ」 　という意味。ポインタ型の変数を宣言。 n = *a; のように書かれていたら、 　「 n に a が指しているものの中身を代入するよ」 　という意味。このときの*は間接演算子。

init = (struct cell *) malloc(sizeof(struct cell)); これは何でしょう？　　 void： 「空の」とか 「法的拘束力のない」 “valid”の反対語 void関数：「空の」戻り値 　　　　　⇒　戻り値を返さない関数 struct cell *init; struct cell * void * init = (struct cell *) malloc(sizeof(struct cell)); これは“キャスト”（型変換）と呼ばれる操作 void型のポインタをstruct cell型のポインタに型変換している

本日の内容 リスト 抽象データ型としてのリスト 配列によるリストの実現 連結リストによるリストの実現

基本的な抽象データ型 リスト（List） リストの特殊なケース スタック（Stack） キュー（Queue, 待ち行列） D C B A ３つとも情報関連の資格試験に頻出する．重要なのでよく理解しておくこと． A B C D

リストの数学的表現 （p.26～） a0,a1, a2, …, ai-1, ai, ai+1, … , an-1 リスト： 一定の型の要素を０個以上一列に並べたもの． 線形リスト(linear list)と呼ぶこともある． ai ： i 番目の位置にある要素 n　： 要素数．リストの長さ． n = 0のとき空リストという a0,a1, a2, …, ai-1, ai, ai+1, … , an-1 最初の要素 aiの直前の要素 aiの直後の要素 最後の要素

抽象データ型としてのリスト 抽象データ型：　データ構造＋操作 リスト 操作 新要素の挿入 要素を 並べたもの 要素の削除 リストを空にする

表記法についての説明 x p L n L ： リスト p ：位置を表わす変数 ｘ ：挿入したいデータ a0 a1 … ai-1 ai … ｘ　　　　：挿入したいデータ 要素の型はすべて同じであればよい． 教科書ではelememttype型としている． x p a0 a1 … ai-1 ai … an-1 L n

代表的なリスト操作 INSERT(x, p, L) 新要素の挿入 DELETE(p, L) 要素の削除 LOCATE(x, L)　要素ｘの位置を探す RETRIEVE(p, L)　位置pにある要素を返す FIND(i, L)　　　　i番目の要素を返す TOP(L)、LAST(L)　先頭、末尾の位置を返す NEXT(p, L)、PREVIOUS(p, L)　pの直前、直後の位置を返す CREATE（L)　新規に空リストLを作成する

INSERT(x, p, L) p ｘ p リストLの位置pの次に要素xを挿入 E L A B C D F G H B D C L E F

DELETE(p, L) p p リストLの位置pの次の要素（もし存在すれば）を削除 L A B C D E F G H B D C L E

LOCATE(x, L) ｘ 要素ｘがL中に存在すれば、その位置を返す D L A B C D F G H この位置が返る 配列のインデクスなら[3] ポインタならば、ここを指すポインタ

RETRIEVE(p, L)　　　　　 位置pのセルの内容を返す p L A B C D F G H ‘ F ’が返る

FIND(i, L) ‘ C ’が返る i = 3のときは？ L の i 番目のセルの内容を返す（ただし、i は1から始まるものとする） L A B C D F G H ‘ C ’が返る

TOP(L) と LAST(L) TOP( L ) LAST( L ) TOP(L) L の最初の位置を返す LAST(L) L の最後の位置を返す TOP( L ) LAST( L ) A B C D F G H L

NEXT(p,L)とPREVIOUS(p,L) PREVIOUS(p, L) 位置pの前のセルの位置を返す p A B C D F G H L PREVIOUS(p, L ) NEXT(p, L )

CREATE(L) CREATE(L) 空リスト L を準備し、その先頭の位置を返す 空リストの先頭の位置が返る L

Insert，Deleteの実現方法の例を説明する リストの実現（実装） すべての操作が常に必要になるとは限らない すべての操作を効率よく実行できるデータ構造の実現は困難 ⇒プログラムの実装の際には，必要な操作を，効率よく実行できるデータ構造を採用する リストの実現に使用できるデータ構造 配列 連結リスト（linked list） ポインタを用いてデータ間の関係を表現したデータ構造 Insert，Deleteの実現方法の例を説明する

配列によるリストの実現

配列によるリストの実現 例） int a[MAXLENGTH]; a[0] a[1] リスト MAXLENGTH 個 last 空 5 配列の大きさ（定数） 10 リスト MAXLENGTH 個 last 22 最後の要素の位置を記録 空 a[MAXLENGTH-1]

Insert(x, p, L) 位置pの後ろの要素を一つずつずらし，新しい要素のための場所を空けてから，要素を入れる p p [0] [0] A x p p [0] B [0] B [1] 2 last L [1] A ③ last L ① [2] L [2] 2 [3] 3 ② [3] [4] [4] [5] [5]

Delete(p, L) 削除する要素の後の要素を一つずつ前へずらし，すき間を埋める [0] p [0] p [1] [1] 3 last X [1] X 3 last ① [2] E [2] T I ② E [3] I [3] I 4 last [4] T [4] T 4 [5] [5]

配列で実現する場合の注意点 [0] p [1] last 2 [2] [3] [4] [5] [6] E I T 要素を挿入できる範囲は [0]～[last+1] [5] [6] lastがMAXLENGTH – 1の場合，リストは満杯 （これ以上，要素を挿入できない）

ポインタ(連結リスト) によるリストの実現

mallocの復習 malloc(n); メモリ上に n バイトの領域を確保し、その先頭アドレスを返す 普通、n　にはsizeof演算子を使って求めた領域の大きさを記述する

mallocの使用例 ？ ptr struct ITEM{ int element; struct ITEM *next; }; ptr = (struct ITEM*)malloc(sizeof(struct ITEM)); メモリ空間上に、ITEM構造体が入る大きさの領域を確保して、その領域の先頭アドレスをptrに代入。 mallocはポインタ(アドレス)を返す関数。型の整合性が取れるようにキャスト(型変換)してから代入する。 ptr ？

メモリ空間上のイメージ 番地 内容 ptrが格納されている場所 00000000 FF1F0204 mallocするのか。 それじゃ、ここがstruct ITEMの分確保できるから、ここをつかうぞ。 00000004番地を使うことをptrにメモしておこう。 00000004 00000008 0000000C 0CFFFF1A 00000010 FF001121 00000004 ptrが格納されている場所 00000128

値を返すとは？(2週目のスライド再掲) ある関数を呼び出して計算した値を、呼び出し元の変数に代入すること。 関数 float triangle(int L, int H){ 　　return L*H/2.0； } 関数triangle を呼び出す メインプログラム S = triangle(5, 7); (5*7/2.0=17.5) 計算結果を 関数の呼び出し元に返す (Sに17.5が代入される)

ポインタを返すとは？ ある関数を呼び出した結果得られたアドレスを、呼び出し元のポインタ変数に代入すること。 関数 メインプログラム struct cell* LAST (struct cell* init){ リストの末尾の位置を探す; 　　return 末尾へのポインタ； } 関数LAST君、末尾のセルは どこか調べてね メインプログラム pt = LAST(init); 末尾のセルは 0104番地にありますよ pt にアドレス 0104が 代入される

復習 ドット演算子 . struct SAMPLE{ int width; int height; }; int main(void) { 復習　ドット演算子　.　　　 struct SAMPLE{ int width; int height; }; int main(void) { struct SAMPLE data1; data1.width = 50; … return 0; } data1 width 50 height 構造体のメンバにアクセスするときは、ドット演算子を使って、メンバ名を指定する。

復習 間接演算子 ＊ int main(void) { 5 int a=5, b; int *pt; pt = &a; b = *pt; … 復習　　間接演算子 ＊　　　　 int main(void) { int a=5, b; int *pt; pt = &a; b = *pt; … return 0; } a 5 pt b 5 ptの指している先の中身にアクセスするときは間接演算子を使う

構造体へのポインタのときは？ int main(void) { struct SAMPLE data1; data1.width (*pt).width pt->width int main(void) { struct SAMPLE data1; struct SAMPLE *pt; pt = &data1; (*pt).width = 50; … return 0; } pt data1.width 50 data1.height これを簡単に書くために アロー演算子－＞を使用 　　　　　pt -> width = 50;

ポインタによるリストの実現 ポインタによってリストのデータ構造を表現したものを連結リスト（リンクトリスト，linked list）と呼ぶ 「要素」と「次のセルを指すポインタ」で構成される連結リストは，特に，単方向リスト，一方向リストなどと呼ばれる init ここではポインタのみになっているが、実装を簡単にするため、ヘッダも完全なセルにすることもある． a0 a1 a2 an-1

例）整数のリスト（単方向リスト版） 型定義 struct CELL { int element; struct CELL *next; }; init CELL型 要素（element）と 次のセルを指すポインタからなる a0 a1 a2 an-1

挿入する位置の一つ前を指している点に注意 Insert(x, p, L) pが指すセルの次に，新しいセルを挿入する init 挿入する位置の一つ前を指している点に注意 p A B C x

r = (struct CELL *)malloc(sizeof(struct CELL)); Insert(x, p, L)の実現(1) 重要！！ 教科書p.30のソースと よく見比べて理解すること init p A B C ｒ r = (struct CELL *)malloc(sizeof(struct CELL)); ①

Insert(x, p, L)の実現(2) リストの途中への挿入の場合 init q = p -> next;　 ② p A B C ｒ

Insert(x, p, L)の実現(3) リストの途中への挿入の場合 init p q ③ p -> next = r; ｒ A B C ③ p -> next = r;　 ｒ

Insert(x, p, L)の実現(4) init p q A B C ｒ x r->element = x; ④

Insert(x, p, L)の実現(5) init p q A B C ｒ x ⑤ r->next = q;

先頭へのInsert ②、③が異なる p （先頭への挿入のときpはNULL） ② q = init; init ③ init = r ; ｒ A B C ③ init = r ; ｒ

② p->next = q->next; Delete(p, L) pが指すセルの次のセルを削除する init ① q = p->next; p ③ free(q); A B B C D ② p->next = q->next;

双方向リスト 「要素」と「次のセルを指すポインタ」， 「前のセルを指すポインタ」で構成される連結リストは，双方向リストと呼ばれる 双方向リスト　　　　 「要素」と「次のセルを指すポインタ」， 「前のセルを指すポインタ」で構成される連結リストは，双方向リストと呼ばれる 長所：リストを前方にも後方にもたどれる 短所：前のセルを指すポインタが必要になる 　　　　　単方向リストと比べ，操作が複雑になる ap-1 ap ap+1

例）整数のリスト（双方向リスト版） 型定義 struct CELL { int element; struct CELL *next; 前の要素を指す ポインタが増えた 型定義 struct CELL { int element; struct CELL *next; struct CELL *previous; }; ap-1 ap ap+1

計算量の比較 p [0] last [1] init p 2 [2] [3] [4] [5] [6] データ構造 計算量の比較　　　　　　 データ構造 INSERT, DELETE FIND, LAST, PREVIOUS 配列 要素数に比例O (n) 一定時間O (1) 単方向リスト 2 last T E I [0] [1] [2] [3] [4] [5] [6] p E I p T init

メモリの使用効率に関する比較 init p p [0] last [1] 2 [2] [3] [4] [5] [6] データ構造 メモリの使用効率に関する比較　 データ構造 リストの最大長 余分に必要になるメモリ 配列 固定 MAXLENGTH - 実際の長さ 単方向リスト 可変 ポインタ用の空間 E I p T init 2 last T E I [0] [1] [2] [3] [4] [5] [6] p データが 入っていない ポインタ用の空間

データ構造とアルゴリズム 2008年度前期　出席カード 5月14日　学籍番号　　　　　　氏名　　　　　　　 の様に連結されている時、下の番地表での連結を矢印で示せ。 一つのセルは連続した２つの番地に入っているとする。 ROOT 0091 0093 0094 009D 0000 0100 0091 0106 009C 0104 009D 0000 内容 番地 00FF 0101 0102 0103 0105 0093 0108 010E 009A 010C 009B 0102 内容 番地 0106 0107 0109 010A 010B 010D 0095 010A 0096 0112 0098 0114 0099 0000 内容 番地 010E 010F 0110 0111 0113 0115 ROOT