解説#74 連結リスト
0 likes229 views
C言語の連結リストについて５０分ほど話しました。連結リストは重宝するデータ構造です。ポインタが本領を発揮します。 ? 連結リストとは？ ? 連結リストの基本的性質（配列と比較して） ? 挿入１：リストの途中で要素を挿入 ? 挿入２：リストの先頭に要素を挿入 ? 削除１：リストの途中の要素を削除 ? 削除２：リストの先頭の要素を削除 ?（発展）挿入３：境界条件用に改良した挿入
![連結リストとは？
struct CELL {
struct CELL *next;
int v;
};
2 5 12 -4
変数header
? 例えば、[2, 5, 12, -4]という数字のリストを扱いたいとする
? リストを実現するデータ構造には、配列と連結リストの２つがある
? 連結リストはポインタによって連結されたセルとして表現される
2 a[0]
5
12
-4
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
int a[10]
整数(int) ポインタ(*) NULL
配列
連結リスト](https://image.slidesharecdn.com/ppt-74-220113130229/85/74-3-320.jpg)
![連結リストの基本的性質（配列と比較して）
? 配列はシーケンシャルアクセス
? 連結リストはランダムアクセス
例えば、３番目の要素を参照したい場合、
配列→a[3]と一回で済む
連結リスト→３回リストを辿らないといけない
? 挿入削除は連結リストの方が簡単
配列は、挿入?削除した地点から
後ろにある要素全てをずらさないと
いけない
連結リストは、ポインタを書き換える
だけで済む
アクセス挿入 削除
配列 O(1) O(n) O(n)
連結リスト O(n) O(1) O(1)
O(n) > O(1)
連結リストはアクセスは苦手だが
挿入?削除は得意。](https://image.slidesharecdn.com/ppt-74-220113130229/85/74-4-320.jpg)
![本日扱う連結リスト
2 5 12 -8
x
0x100
x->next
0x200
p
0x800
struct CELL {
int value;
};
メモリアドレス
変数
struct CELL *next;
? 連結リストはポインタによって連結されたセルとして
表現される
? 扱うリストは、[2,5,12,-8]の数字の並び](https://image.slidesharecdn.com/ppt-74-220113130229/85/74-6-320.jpg)
![2 5 12 ４
x
0x100
x->next
0x200
p
0x800
2 5 12 ４
x
0x100
x->next
0x200
p
0x800
0x800 0x200
x->next
処理結果[2,5,12] -> [2,4,5,12]
①
②
x1 x2](https://image.slidesharecdn.com/ppt-74-220113130229/85/74-14-320.jpg)
![処理結果 [2,5,12] -> [1,2,5,12]
2 5 12
header
y
0x010
2 5 12 1
header p
0x100
x
0x001
x
0x001
0x001
0x100
y
0x010 ②
①
0x001
x1](https://image.slidesharecdn.com/ppt-74-220113130229/85/74-20-320.jpg)
Ad
More Related Content
What's hot (20)
More from Ruo Ando (20)
Ad
解説#74 連結リスト
- 2. 本日の概要 ? 連結リストとは？ ? 連結リストの基本的性質（配列と比較して） ? 挿入１：リストの途中で要素を挿入 ? 挿入２：リストの先頭に要素を挿入 ? 削除１：リストの途中の要素を削除 ? 削除２：リストの先頭の要素を削除 ? （発展）挿入３：境界条件用に改良した挿入
- 3. 連結リストとは？ struct CELL { struct CELL *next; int v; }; 2 5 12 -4 変数header ? 例えば、[2, 5, 12, -4]という数字のリストを扱いたいとする ? リストを実現するデータ構造には、配列と連結リストの２つがある ? 連結リストはポインタによって連結されたセルとして表現される 2 a[0] 5 12 -4 a[1] a[2] a[3] a[4] a[5] a[6] a[7] int a[10] 整数(int) ポインタ(*) NULL 配列 連結リスト
- 4. 連結リストの基本的性質（配列と比較して） ? 配列はシーケンシャルアクセス ? 連結リストはランダムアクセス 例えば、３番目の要素を参照したい場合、 配列→a[3]と一回で済む 連結リスト→３回リストを辿らないといけない ? 挿入削除は連結リストの方が簡単 配列は、挿入?削除した地点から 後ろにある要素全てをずらさないと いけない 連結リストは、ポインタを書き換える だけで済む アクセス挿入 削除 配列 O(1) O(n) O(n) 連結リスト O(n) O(1) O(1) O(n) > O(1) 連結リストはアクセスは苦手だが 挿入?削除は得意。
- 5. 本日説明する連結リストの処理 ? 挿入１：リストの途中で要素を挿入 ? 挿入２：リストの先頭に要素を挿入 ? 削除：リストの途中の要素を削除 ? 削除：リストの先頭の要素を削除 ? 挿入３：境界条件用に改良した挿入 ＊境界条件：リストの先頭と末尾、空リストを扱う場合
- 6. 本日扱う連結リスト 2 5 12 -8 x 0x100 x->next 0x200 p 0x800 struct CELL { int value; }; メモリアドレス 変数 struct CELL *next; ? 連結リストはポインタによって連結されたセルとして 表現される ? 扱うリストは、[2,5,12,-8]の数字の並び
- 7. 挿入１：リストの途中に要素を 挿入 2 ４ ５ 12 x p
- 8. struct CELL *p; if((p = malloc(sizeof(struct CELL))) == NULL){ fatal_error(“エラー：メモリが足りない”) p->next = x->next; x->next = p; リストの途中に要素を追加 2 5 12 2 ４ ５ 12 x x p p
- 9. ポイント p->next = x->next; x->next = p; 左辺と右辺で意味が違う
- 10. 復習：変数とアドレス 0x100 0x200 0x800 x y z ? 箱の名前が変数(x, y, z) ? 箱の場所がアドレス（0x100, 0x200, 0x800) ? 箱の中身が実際の値 (2, 5, 12) ２ ５ １２
- 11. 復習: 変数 = 実際の値 X = Y X(左辺）: 変数（〇) Y(右辺）: 実際の値（メモリのアドレス ?） 2 5 12 x 0x100 x->next 0x200 p 0x800 メモリアドレス 0x800 p 12 0x200 0x800番地にある箱pにアド レス(0x200)の値が入る。
- 12. ①: p->next = x->next 2 5 12 ４ x 0x100 x->next 0x200 p 0x800 【左辺】 ｐ->next 0x200 ｐ->next 2 5 12 ４ x 0x100 x->next 0x200 p 0x800 x->next（右辺）：箱の中身 0x200 【右辺】 x->next 0x200 ｐ->next x1 x2
- 13. ②: x->next = p; 2 5 12 ４ x 0x100 x->next 0x200 p 0x800 【左辺】ｘ->next 0x800 x->next 2 5 12 ４ x 0x100 x->next 0x200 p 0x800 x->next（左辺）：箱 0x800 0x200 x->next 【右辺】 p 0x800 x1 x2
- 14. 2 5 12 ４ x 0x100 x->next 0x200 p 0x800 2 5 12 ４ x 0x100 x->next 0x200 p 0x800 0x800 0x200 x->next 処理結果[2,5,12] -> [2,4,5,12] ① ② x1 x2
- 15. 挿入２：リストの先頭に要素を 挿入 2 5 12 1 header p 0x100 x 0x001 0x100 y 0x010 ② ① 0x001
- 16. 連結リストの挿入① リストの先頭に要素を追加 struct CELL *header, *p;” if((p = malloc(sizeof(struct CELL))) == NULL){ fatal_error(“エラー：メモリが足りない”) p->next = header; header = p; 2 5 12 1 header y 0x010 p 0x100 x 0x001 0x001 2 5 12 1 header 0x100 0x001 y 0x010 p 0x100 x 0x001
- 17. ポイント p->next = header; header = p; headerの値が書き換わる
- 18. ①: p->next = header 2 5 12 1 0x001 p header y z 2 5 12 1 p x 0x001 z p 0x100 p 0x100 x 0x001 header 0x100 y 0x010 y 0x010 0x001 0x001
- 19. ②: header = p; 2 5 12 ４ 0x001 p header y z 2 5 12 ４ 0x001 p x z p 0x100 p 0x100 x 0x001 0x001 header 0x100 y 0x010 y 0x010
- 20. 処理結果 [2,5,12] -> [1,2,5,12] 2 5 12 header y 0x010 2 5 12 1 header p 0x100 x 0x001 x 0x001 0x001 0x100 y 0x010 ② ① 0x001 x1
- 22. リストの途中の要素を削除 struct CELL *p; if(x->next == NULL){ エラー：直後のセルがない } p = x->next; x->next = p->next; free(p); 2 ５ 12 x 0x100 0x200 0x200 0x300 0x300 2 ５ 12 0x300 0x300 x 0x100 0x200 0x300
- 23. ポイント ?p = x->next; ?x->next = p->next; x->nextの値が書き換わる
- 24. p = x->nextを実行すると。。 2 ５ 12 x 0x100 0x200 0x200 0x300 0x300 p 2 ５ 12 x 0x100 0x200 0x200 0x300 0x300 p 0x200 0x800 0x800 x1
- 25. ポイント： p = x->nextの実行後の、p->nextの値は？ 0x100 0x800 0x200 x->next = 0x300 0x300 p = 0x200 x->next = 0x200 int = 4 int = 5 p->next は 0x300 を指すようになる
- 26. x->next = p->next; 2 ５ 12 x 0x100 0x300 0x300 0x200 p 0x800 0x200 2 ５ 12 x 0x100 0x300 0x300 0x200 p 0x800 0x300 0x200 0x200
- 27. 処理結果 2 ５ 12 x 0x100 0x200 0x200 0x300 0x300 2 ５ 12 x 0x100 0x300 0x300 0x200 p 0x800 0x300 0x200 struct CELL *p; if(x->next == NULL){ エラー：直後のセルがない } p = x->next; x->next = p->next; free(p); free free
- 29. やりたいこと リストの先頭の要素を削除 struct CELL *p; if(head == NULL){ エラー：リストが空 } p = head; head = p->next; free(p); 2 ５ 12 x 0x100 x->next 0x200 head 0x100 0x000 2 ５ 12 x 0x100 x->next 0x200 head 0x200 0x000
- 30. ポイント ?p = head; ?head = p->next; headの値が書き換わる
- 31. p = head; 2 ５ 12 x 0x100 x->next 0x200 struct CELL *p; if(head == NULL){ エラー：リストが空 } p = head; head = p->next; free(p); head 0x100 0x000 2 ５ 12 x 0x100 x->next 0x200 p 0x800 0x100 head 0x100 0x000
- 32. ポイント： p = headの実行後の、p->nextの値は？ 0x100 0x800 0x200 x->next = 0x300 0x300 p = 0x100 x->next = 0x200 int = 4 int = 5 p->next は 0x200 を指すようになる
- 33. head = p->next 2 ５ 12 x 0x100 x->next 0x200 struct CELL *p; if(head == NULL){ エラー：リストが空 } p = head; head = p->next; free(p); head 0x100 0x000 2 ５ 12 x 0x100 x->next 0x200 p 0x800 0x100 head 0x200 0x000 x2
- 34. 処理結果 2 ５ 12 x 0x100 x->next 0x200 struct CELL *p; if(head == NULL){ エラー：リストが空 } p = head; head = p->next; free(p); head 0x100 0x000 2 ５ 12 x 0x100 x->next 0x200 p 0x800 0x100 head 0x200 0x000 free free
- 36. 境界条件とは？ ? リストの先頭の処理 ? リストの末尾の処理 ? リストが空の時の処理 境界条件でないものとは？ ? リストの途中の処理 改良： すべての場合を 同じコードで 処理できるようにする
- 37. struct CELL { struct CELL *next; int value; } header; insert(int a) { struct CELL *p, *q, *new; p= header.next; q = &header; while(p != NULL && a > p->value) { q = p; p = p->next; } if((new = malloc(sizeof(struct CELL))) = NULL) fatal_error(メモリがたりない） new->next = p; new->value = a; q->next = new; } p, qをセット(初期化） 挿入(insert)する場所を 探す newをリストに挿入
- 38. 連結リストの操作：初期化後 struct CELL { struct CELL *next; int value; } header; insert(int a) { struct CELL *p, *q, *new; p = header.next; q = &header: while(p != NULL && a > p->value) { q = p; p = p->next; } } - 2 5 7 12 q p header 始めのセルは連結リスト自身を表すための ダミーで、次のセルへのポインタはあるが、 値は入らない。
- 39. 連結リストの操作：a=4(途中） - 2 5 7 12 q p 4 new if((new = malloc(sizeof(struct CELL))) = NULL) fatal_error(メモリがたりない） ① new->next = p; ② new->value = a; ③ q->next = new; ① ③ ② struct CELL { struct CELL *next; int value; } header; 境界条件ではない
- 40. 連結リストの操作：a = 1（先頭） - 2 5 7 12 q p 1 new if((new = malloc(sizeof(struct CELL))) = NULL) fatal_error(メモリがたりない） ① new->next = p; ② new->value = a; ③ q->next = new; ① ③ ② struct CELL { struct CELL *next; int value; } header; 境界条件１
- 41. 連結リストの操作：a=15(末尾） - 2 5 7 12 q p = NULL 15 new if((new = malloc(sizeof(struct CELL))) = NULL) fatal_error(メモリがたりない） ① new->next = p; ② new->value = a; ③ q->next = new; ③ ② ① struct CELL { struct CELL *next; int value; } header; 境界条件２
- 42. 連結リストの操作：空リストに２を挿入 - q p＝NULL - 2 q p=NULL new if((new = malloc(sizeof(struct CELL))) = NULL) fatal_error(メモリがたりない） ① new->next = p; ② new->value = a; ③ q->next = new; ② ③ ① struct CELL { struct CELL *next; int value; } header; 境界条件３
- 43. 本日のまとめ ? 連結リストとは？ ? 連結リストの基本的性質（配列と比較して） ? 挿入１：リストの途中で要素を挿入 ? 挿入２：リストの先頭に要素を挿入 ? 削除１：リストの途中の要素を削除 ? 削除２：リストの先頭の要素を削除 ? （発展）挿入３：境界条件用に改良した挿入