データ構造とアルゴリズム 第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]; 第２位　セミコロン無し

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

基本的な抽象データ型 （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 ： n　： n = 0 a0,a1, a2, …, ai-1, ai, ai+1, … , an-1 最初の要素 最後の要素

抽象データ型としてのリスト 抽象データ型：　 リスト 操作 要素を 並べたもの

表記法についての説明 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 ｘ E L A B C D F G H p L A B C D

DELETE(p, L) 　　　　　　　　　　 p L A B C D E F G H p B D C L E F G A H

LOCATE(x, L)　　　　　　　 ｘ D L A B C D F G H 配列のインデクスなら[3] ポインタならば、ここを指すポインタ

RETRIEVE(p, L)　　　　　 p L A B C D F G H

FIND(i, L)　　　　　　　　 i = 3のときは？ L A B C D F G H

TOP(L)　と　LAST(L)　　　　　　 TOP(L) LAST(L) A B C D F G H L

NEXT(p,L)とPREVIOUS(p,L) A B C D F G H L

CREATE(L) CREATE(L) 空リストの先頭の位置が返る L

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

配列によるリストの実現 例） int a[MAXLENGTH]; a[0] a[1] リスト MAXLENGTH 個 last 空 5 10 22 空 a[MAXLENGTH-1]

Insert(x, p, L) p p [0] [0] [1] 2 last [1] ③ last ① [2] [2] 2 [3] 3 ② 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 ① [2] [2] ② [3] [3] 4 last [4] X [1] X 3 last ① [2] E [2] E T I ② [3] I [3] I 4 last [4] T [4] T 4 [5] [5]

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

mallocの復習 malloc(n); メモリ上に 普通、n　には

mallocの使用例 ？ ptr struct ITEM{ int element; struct ITEM *next; }; ptr = (struct ITEM*)malloc(sizeof(struct ITEM)); メモリ空間上に、 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； } を呼び出す メインプログラム S = triangle(5, 7); (5*7/2.0=17.5) 計算結果を 関数の呼び出し元に返す (Sに17.5が代入される)

ポインタを返すとは？ 関数 メインプログラム pt = LAST(init); 関数LAST君、末尾のセルは どこか調べてね 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

構造体へのポインタのときは？ 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 data1.height

ポインタによるリストの実現 init a0 a1 a2 an-1 ここではポインタのみになっているが、実装を簡単にするため、ヘッダも完全なセルにすることもある． a0 a1 a2 an-1

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

Insert(x, p, L) init p A B C x

Insert(x, p, L)の実現(1) 重要！！ 教科書p.30のソースと よく見比べて理解すること init p A B C

Insert(x, p, L)の実現(2) リストの途中への挿入の場合 init p A B C ｒ

Insert(x, p, L)の実現(3) リストの途中への挿入の場合 init p q A B C ｒ

Insert(x, p, L)の実現(4) init p q A B C ｒ

Insert(x, p, L)の実現(5) init p q A B C ｒ x

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

Delete(p, L) init p ③ free(q); A B B C D

双方向リスト 「要素」と「次のセルを指すポインタ」， 「前のセルを指すポインタ」で構成される連結リストは， ap-1 ap ap+1 長所： 双方向リスト　　　　 「要素」と「次のセルを指すポインタ」， 「前のセルを指すポインタ」で構成される連結リストは， 長所： 短所：　 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 配列 単方向リスト 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] データ構造 メモリの使用効率に関する比較　 データ構造 リストの最大長 余分に必要になるメモリ 配列 単方向リスト E I p T init 2 last T E I [0] [1] [2] [3] [4] [5] [6] p データが 入っていない ポインタ用の空間

本日の問題 の様に連結されている時、下の番地表での連結を矢印で示せ。 一つのセルは連続した２つの番地に入っているとする。 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