Taro-リストⅢ（公開版）.jtd

Size: px

Start display at page:

Download "Taro-リストⅢ（公開版）.jtd"

あおいやなぎしま
5 years ago
Views:

1 リスト Ⅲ 0. 目次 2. 基本的な操作 2. 1 リストから要素の削除 2. 2 リストの複写 2. 3 リストの連結 2. 4 問題問題 1 問題 2-1 -

2 2. 基本的な操作 2. 1 リストから要素の削除まず一般的な処理を書きつぎに特別な処理を書く一般的な処理は処理 1 : リスト中に削除するデータを見つけ削除する場合への対応特別な処理は処理 2 : 先頭のデータを削除する場合への対応になる処理 1 ( 1 ) 削除前 head x NULL 変数 x : 削除データ ( 2 ) 削除データ xを見つける p head x NULL q 変数 p: 削除データを指すポインタ変数変数 q: 削除データの直前を指すポインタ変数 ( 3 ) 削除データ x を削除するためにポインタを変更する p head x NULL q->next = p->next; ( 4 ) 削除後 q head NULL - 2 -

3 処理 2 ( 1 ) 削除前 head x NULL 変数 x : 削除データ ( 2 ) 削除データ xを見つける p head x NULL q 変数 p: 削除データを指すポインタ変数変数 q: 削除データの直前を指すポインタ変数 ( 3 ) 削除後 head x NULL q->next = p->next; - 3 -

4 処理 1, 処理 2 をまとめて次のプログラムを得るプログラム ( ls211.c) 1 /* << ls211.c >> */ 2 /* リストからデータの削除 */ 3 #include <stdio.h> 4 #include <stdlib.h> 5 struct NODE { 6 int info; 7 struct NODE *next; 8 }; 9 struct NODE *mlist(); 10 void slist(struct NODE *p); int main() { 13 int x; 14 struct NODE *head, /* リストの先頭を指すポインタ変数 */ 15 *p, /* 削除データを指すポインタ変数 */ 16 *q; /* 削除データの直前を指すポインタ変数 */ /* リストの作成 */ 19 head = mlist(); while( 1 ) { 22 /* リストの表示 */ 23 printf(" 現在のリスト : "); 24 slist(head); /* 削除データ xの読込 */ 27 scanf("%d",&x); 28 if( x == 0 ) { break; } 29 printf(" 削除データ : %d \n",x); /* 削除 */ /* 初期設定 */ 34 p = head->next; 35 q = head; /* 削除位置を見つける */ 38 while( p!= NULL ) { 39 if( p->info == x ) { break; } 40 q = p; 41 p = p->next; 42 } /* 削除データが見つかった場合 */ 45 if( p!= NULL ) { 46 q->next = p->next; - 4 -

5 47 } 48 } 49 } 実行結果 % cc ls211.c 現在のリスト : 削除データ : 22 現在のリスト : 削除データ : 22 現在のリスト : 削除データ : 11 現在のリスト : 削除データ : 33 現在のリスト : 0-5 -

6 2. 2 リストの複写考え方元のリストを先頭から末尾へたどりながら新たなリストを作成していく ( 1 ) 複写前 head NULL head1 NULL ( 2 ) 複写中 head NULL head1 11 NULL ( 3 ) 複写中 head NULL head NULL ( 4 ) 複写後 head NULL head NULL - 6 -

7 ひとつずつ要素を複写 ( 1 ) 要素 11の複写前 p ポインタ変数 pは複写の対象要素を指す head NULL head1 NULL p1 ポインタ変数 p1は複写先リストの末尾を指す ( 2 ) 要素 11の複写後 p head NULL head1 11 NULL p1 q ポインタ変数 qは生成された要素を指す ( 3 ) 要素 22の複写前 p head NULL head1 11 NULL p1 q ( 4 ) 要素 22の複写後 p head NULL head NULL p1 q - 7 -

8 プログラム ( ls221.c) 1 /* << ls221.c >> */ 2 /* リストの複写 */ 3 #include <stdio.h> 4 #include <stdlib.h> 5 struct NODE { 6 int info; 7 struct NODE *next; 8 }; 9 struct NODE *mlist(); 10 void slist(struct NODE *p); int main() { 13 struct NODE *head, /* 複写元リストの先頭を指すポインタ変数 */ 14 *p, /* 複写元の対象要素を指すポインタ変数 */ 15 *q, /* データを指すポインタ変数 */ 16 *head1, /* 複写先リストの先頭を指すポインタ変数 */ 17 *t; /* 複写先リストの末尾を指すポインタ変数 */ /* 複写元リストの作成と表示 */ 20 head = mlist(); 21 printf(" 複写元リスト : "); 22 slist(head); /* 複写 */ 25 /* 複写先リストヘッドの作成 */ 26 head1 = (struct NODE *)malloc(sizeof(struct NODE)); 27 head1->next = NULL; p = head->next; /* 複写元の対象要素を指す */ 30 t = head1; /* 複写先リストの末尾を指す */ while( p!= NULL ) { 33 /* 複写先のデータを作成 */ 34 q = (struct NODE *)malloc(sizeof(struct NODE)); 35 q->info = p->info; 36 q->next = NULL; /* 複写先のリストを作成 */ 39 t->next = q; 40 t = q; 41 p = p->next; 42 } /* 複写リストの表示 */ 45 printf(" 複写先リスト : "); 46 slist(head1); 47 } - 8 -

9 実行結果 % cc ls221.c 0 複写元リスト : 複写先リスト : 11 0 複写元リスト : 11 複写先リスト : 複写元リスト : 複写先リスト : 複写元リスト : 複写先リスト :

10 2. 3 リストの連結考え方一方のリストの末尾と他方のリストの先頭をつなぐ ( 1 ) 連結前 head NULL head NULL ( 2 ) 連結後 head head NULL プログラム ( ls231.c) 1 /* << ls231.c >> */ 2 /* 2 つのリストの連結 3 リスト 1 の末尾とリスト 2 の先頭をつなげる */ 4 #include <stdio.h> 5 #include <stdlib.h> 6 struct NODE { 7 int info; 8 struct NODE *next; 9 }; 10 struct NODE *mlist(); 11 void slist(struct NODE *p); int main() { 14 struct NODE *head1, /* リスト 1 の先頭を指すポインタ変数 */ 15 *head2, /* リスト 2 の先頭を指すポインタ変数 */ 16 *p, /* リスト 1 をたどる作業用ポインタ変数 */ 17 *q; /* リスト 1 の末尾を指すポインタ変数 */ /* リスト 1 の作成と表示 */ 20 head1 = mlist(); 21 printf(" リスト 1 : "); 22 slist(head1); /* リスト 2 の作成と表示 */ 25 head2 = mlist(); 26 printf(" リスト 2 : "); 27 slist(head2);

11 29 /* 2 つのリストの連結 */ 30 /* 初期設定 */ 31 p = head1->next; 32 q = head1; /* リスト 1 をたどり末尾の番地をポインタ変数 qに保存する */ 35 while( p!= NULL ) { 36 q = p; 37 p = p->next; 38 } /* リスト 1 にリスト 2 を連結する */ 41 q->next = head2->next; /* 連結リストの表示 */ 44 printf(" リスト 1 + リスト 2 : "); 45 slist(head1); 46 } 実行結果 % cc ls231.c 0 リスト 1 : 0 リスト 2 : リスト 1 + リスト 2 : リスト 1 : リスト 2 : リスト 1 + リスト 2 : リスト 1 : リスト 2 : リスト 1 + リスト 2 : リスト 1 : リスト 2 : リスト 1 + リスト 2 :

12 2. 4 問題問題 1 リストから指定されたすべての要素を削除するプログラムを作成せよプログラム ( ls241.c) 1 /* << ls241.c >> */ 2 /* リストからデータの削除 */ 3 #include <stdio.h> 4 #include <stdlib.h> 5 struct NODE { 6 int info; 7 struct NODE *next; 8 }; 9 struct NODE *mlist(); 10 void slist(struct NODE *p); int main() { 13 int x; 14 struct NODE *head, /* リストの先頭を指すポインタ変数 */ 15 *p, /* 削除データを指すポインタ変数 */ 16 *q; /* 削除データの直前を指すポインタ変数 */ /* リストの作成 */ 19 head = mlist(); while( 1 ) { 22 /* リストの表示 */ 23 printf(" 現在のリスト : "); 24 slist(head); /* 削除データ xの読込 */ 27 scanf("%d",&x); 28 if( x == 0 ) { break; } 29 printf(" 削除データ : %d \n",x); /* 削除データを見つけながら削除する */ 32 p = head->next; 33 q = head; 34 while( p!= 1 ) { 35 if( p->info == x ) { 36 q->next = 2 ; 37 } else { 38 q = 3 ; 39 } 40 p = 4 ; 41 } 42 } 43 }

13 実行結果 % cc ls241.c 現在のリスト : 削除データ : 33 現在のリスト : 削除データ : 22 現在のリスト : 削除データ : 11 現在のリスト :

14 問題 2 リストから指定された k 番目の要素を削除するプログラムを作成せよただし k はリストの先頭から k 番目を意味するまた k が現在のリストの長さより大きい場合何もしない考え方 ( 1 ) 元のリスト ( 2 ) 2 番目の要素を見つけ削除する NULL NULL ( 3 ) 1 番目の要素を見つけ削除する NULL NULL 33 NULL ( 4 ) 3 番目の要素を見つけ削除する 33 NULL ( 5 ) 1 番目の要素を見つけ削除する 33 NULL NULL プログラム ( ls242.c) 1 /* << ls242.c >> */ 2 /* リストからデータの削除 */ 3 #include <stdio.h> 4 #include <stdlib.h> 5 struct NODE { 6 int info; 7 struct NODE *next; 8 }; 9 struct NODE *mlist(); 10 void slist(struct NODE *p); int main() { 13 int count, /* リスト中の要素の個数 */ 14 k;

15 15 struct NODE *head, /* リストの先頭を指すポインタ変数 */ 16 *p, /* 削除データを指すポインタ変数 */ 17 *q; /* 削除データの直前を指すポインタ変数 */ /* リストの作成 */ 20 head = mlist(); while( 1 ) { 23 /* リストの表示 */ 24 printf(" 現在のリスト : "); 25 slist(head); /* 削除位置 kの読込 */ 28 scanf("%d",&k); 29 if( k <= 0 ) { break; } 30 printf(" 削除位置 : %d \n",k); /* 削除 */ /* 初期設定 */ 35 p = head->next; 36 q = head; 37 count = 0; /* 削除位置を見つけ削除する */ 40 while( p!= 5 ) { 41 count++; 42 if( k == count ) { 43 q->next = 6 ; 44 break; 45 } 46 q = 7 ; 47 p = 8 ; 48 } /* リストの表示 */ 51 printf(" リスト : "); 52 slist(head); 53 } 54 }

16 実行結果 % cc ls242.c 現在のリスト : 削除位置 : 3 リスト : 現在のリスト : 削除位置 : 1 リスト : 現在のリスト : 削除位置 : 5 リスト : 現在のリスト : 削除位置 : 3 リスト : 現在のリスト :

Taro-リストⅠ（公開版）.jtd

Taro-リストⅠ（公開版）.jtd 0. 目次 1. 再帰的なデータ構造によるリストの表現 1. 1 リストの作成と表示 1. 1. 1 リストの先頭に追加する方法 1. 1. 2 リストの末尾に追加する方法 1. 1. 3 昇順を保存してリストに追加する方法 1. 2 問題問題 1 問題 2-1 - 1. 再帰的なデータ構造によるリストの表現リストはデータの一部に次のデータの記憶場所を示す情報 ( ポインタという ) を持つ構造をいう