アルゴリズムとデータ構造 補足資料11-3 「線形リストのオペレータ」

Presentation on theme: "アルゴリズムとデータ構造 補足資料11-3 「線形リストのオペレータ」"— Presentation transcript:

1 アルゴリズムとデータ構造 補足資料11-3 「線形リストのオペレータ」
横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

2 リストのオペレータ 生成 表示（走査） 挿入 削除 p key 21 key 22 key 23 next next next NULL

3 リストのオペレータ 生成 表示（走査） 挿入 削除 p 21 22 23 NULL
key 21 key 22 key 23 next next next NULL void print_list(struct list *p) { while (p != NULL) { printf("<%d> ", p->key); p = p->next; } printf("\n");

4 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p key 21 key 22 key 23 next next next NULL 画面出力

5 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p !=NULL key 21 key 22 key 23 next next next NULL 画面出力

6 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p key 21 key 22 key 23 next next next NULL 画面出力 <21>

7 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p key 21 key 22 key 23 next next next NULL 画面出力 <21>

8 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p !=NULL key 21 key 22 key 23 next next next NULL 画面出力 <21>

9 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p key 21 key 22 key 23 next next next NULL 画面出力 <21> <22>

10 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p key 21 key 22 key 23 next next next NULL 画面出力 <21> <22>

11 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p !=NULL key 21 key 22 key 23 next next next NULL 画面出力 <21> <22>

12 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p key 21 key 22 key 23 next next next NULL 画面出力 <21> <22> <23>

13 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p NULL key 21 key 22 key 23 next next next NULL 画面出力 <21> <22> <23>

14 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p ==NULL NULL key 21 key 22 key 23 next next next NULL 画面出力 <21> <22> <23>

15 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p NULL key 21 key 22 key 23 next next next NULL 画面出力 <21> <22> <23>

16 void print_list(struct list *p) { while (p != NULL) {
printf("<%d> ", p->key); p = p->next; } printf("\n"); p NULL key 21 key 22 key 23 next next next NULL 画面出力 <21> <22> <23> 走査（scan）とは、一つ一つの要素のキーを見ていくこと。 「探索」（search）の際にも使う。

17 リストのオペレータ 生成 表示（走査） 挿入 削除 p 21 22 23 NULL
key 21 key 22 key 23 next next next NULL void insert_after(struct list *x, struct list *p) { x->next = p->next; p->next = x; }

18 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } p key 21 key 22 key 23 next next next NULL ここに挿入する x key 30 next

19 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } p key 21 key 22 key 23 next next next NULL この値をコピー x key 30 next

20 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } p key 21 key 22 key 23 next next next NULL この値をコピー x key 30 next

21 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } p key 21 key 22 key 23 next next next NULL x key 30 next

22 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」
イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 樋口さんの番号 野口さんの番号 NULL ここに挿入する x 夏目さんの番号 夏目

23 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 樋口さんの番号 野口さんの番号 NULL この値をコピー x 夏目さんの番号 夏目 樋口さんの番号

24 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 夏目さんの番号 野口さんの番号 NULL この値をコピー x 夏目さんの番号 夏目 樋口さんの番号

25 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 夏目さんの番号 野口さんの番号 NULL x 夏目さんの番号 夏目 樋口さんの番号

26 void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 夏目 樋口 野口 夏目さんの番号 樋口さんの番号 野口さんの番号 NULL 番号の写し順に注意！

27 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」
イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 樋口さんの番号 野口さんの番号 NULL ここに挿入する x 夏目さんの番号 夏目 番号の写し順に注意！ 先に、福沢さんの覚えている樋口さんの電話番号を、 メモをとらずに（憶えておかずに）夏目さんの電話番号に書き換えてしまうと。。。

28 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」
イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 夏目さんの番号 野口さんの番号 NULL x 夏目さんの番号 夏目 番号の写し順に注意！ 先に、福沢さんの覚えている樋口さんの電話番号を、 メモをとらずに（憶えておかずに）夏目さんの電話番号に書き換えてしまうと。。。

29 ？ void insert_after(struct list *x, struct list *p) {
x->next = p->next; p->next = x; } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを挿入する。」 p 福沢さんの番号 福沢 樋口 野口 夏目さんの番号 野口さんの番号 NULL x 夏目さんの番号 夏目 ？ 番号の写し順に注意！ 先に、福沢さんの覚えている樋口さんの電話番号を、 メモをとらずに（憶えておかずに）夏目さんの電話番号に書き換えてしまうと。。。 樋口さんの電話番号がわからなくなる！　ので、連絡網が切れてしまう。

30 リストのオペレータ 生成 表示（走査） 挿入 削除 p 21 22 23 NULL
key 21 key 22 key 23 next next next NULL void delete_next(struct list *p) { struct list *q;   q = p->next; p->next = q->next; free(q); } 削除がないと、領域を解放しないので、増加しっぱなし。

31 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } p key 21 key 22 key 23 next next next NULL この要素を削除（領域解放）する q

32 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } p key 21 key 23 next next NULL key 22 next q この要素を削除（領域解放）する ※見やすくするために位置をずらしましたが、 　　メモリ内で確保されている領域が 　　移動するわけではありません。

33 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } p key 21 key 23 next next NULL この値をコピー key 22 next q

34 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } p key 21 key 23 next next NULL この値をコピー key 22 next q

35 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } p key 21 key 23 next next NULL key 22 next 領域を解放 q

36 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } p key 21 key 23 next next NULL

37 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; /*free(q);*/ } p key 21 key 23 next next NULL key 22 next 領域解放を忘れると、メモリ内にリンクのない使えない領域が残り続ける。 （メモリリーク：メモリ漏れ； プログラムが進むにつれて、だんだんと使えるメモリが減っていく） 必ず、解放しよう！

38 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」
イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」 p 福沢さんの番号 福沢 野口 樋口さんの番号 NULL 樋口 野口さんの番号 この要素を削除する

39 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」 p 福沢さんの番号 福沢 野口 樋口さんの番号 NULL 樋口 野口さんの番号 q この要素を削除する

40 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」 p 福沢さんの番号 福沢 野口 樋口さんの番号 NULL この値をコピー 樋口 野口さんの番号 q 樋口さんの番号 あとで、本部から樋口さんに 「あなたは連絡網から削除されました」 と電話で伝える（解放する）ために 樋口さんの電話番号をメモしておく

41 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」 p 福沢さんの番号 福沢 野口 野口さんの番号 NULL この値をコピー 樋口 野口さんの番号 q 樋口さんの番号

42 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」 p 福沢さんの番号 福沢 野口 野口さんの番号 NULL 樋口 野口さんの番号 q 樋口さんの番号 本部から樋口さんに 「あなたは連絡網から削除されました」 と電話を入れる（解放する）

43 void delete_next(struct list *p) { struct list *q; q = p->next;
p->next = q->next; free(q); } イメージ：　電話連絡網 この連絡網では、 「各人は、次に連絡を回す相手の電話番号だけ知っている。」 「連絡網が切れないように、途中にメンバーを削除する。」 p 福沢さんの番号 福沢 野口 野口さんの番号 NULL

44 リストのオペレータ 生成 表示（走査） 挿入 削除 struct list * get_list( void ) {
int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p;

45 get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d p newp

46 get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d p newp NULL

47 get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d !=EOD 1 p newp NULL

48 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 1 p newp NULL key next

49 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 1 p newp NULL key 1 next

50 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 1 p newp NULL key 1 next NULL

51 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 1 p newp key 1 next NULL

52 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d !=EOD 2 p newp key 1 next NULL

53 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 2 p newp key key 1 next next NULL

54 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 2 p newp key 2 key 1 next next NULL

55 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 2 p newp key 2 key 1 next next NULL

56 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 2 p newp key 2 key 1 next next NULL

57 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d !=EOD 3 p newp key 2 key 1 next next NULL

58 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 3 p newp key key 2 key 1 next next next NULL

59 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 3 p newp key 3 key 2 key 1 next next next NULL

60 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 3 p newp key 3 key 2 key 1 next next next NULL

61 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 3 p newp key 3 key 2 key 1 next next next NULL

62 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d !=EOD 4 p newp key 3 key 2 key 1 next next next NULL

63 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 4 p newp key key 3 key 2 key 1 next next next next NULL

64 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 4 p newp key 4 key 3 key 2 key 1 next next next next NULL

65 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 4 p newp key 4 key 3 key 2 key 1 next next next next NULL

66 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 4 p newp key 4 key 3 key 2 key 1 next next next next NULL

67 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d !=EOD 5 p newp key 4 key 3 key 2 key 1 next next next next NULL

68 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 5 p newp key key 4 key 3 key 2 key 1 next next next next next NULL

69 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 5 p newp key 5 key 4 key 3 key 2 key 1 next next next next next NULL

70 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 5 p newp key 5 key 4 key 3 key 2 key 1 next next next next next NULL

71 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 5 p newp key 5 key 4 key 3 key 2 key 1 next next next next next NULL

72 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d !=EOD 6 p newp key 5 key 4 key 3 key 2 key 1 next next next next next NULL

73 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 6 p newp key key 5 key 4 key 3 key 2 key 1 next next next next next next NULL

74 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 6 p newp key 6 key 5 key 4 key 3 key 2 key 1 next next next next next next NULL

75 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 6 p newp key 6 key 5 key 4 key 3 key 2 key 1 next next next next next next NULL

76 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d 6 p newp key 6 key 5 key 4 key 3 key 2 key 1 next next next next next next NULL

77 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; d ==EOD -1 p newp key 6 key 5 key 4 key 3 key 2 key 1 next next next next next next NULL

78 struct list * get_list( void ) { int d; struct list *p,*newp;
get_data()関数が返す値リスト a[]={ 1, 2, 3, 4, 5, 6, EOD } ※EOD: -1 struct list * get_list( void ) { int d; struct list *p,*newp; p = NULL; while( ( d = get_data( ) ) != EOD) { newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; newp->next = p; p = newp; } return p; p key 6 key 5 key 4 key 3 key 2 key 1 next next next next next next NULL