Microsoft Word - no206.docx

Transcription

1 3.2 双方向リスト 今までのリストは 前から順にたどることしかできませんでした 今度は逆にもたどることができる 双方向リストを扱います この場合は 構造体には次を表すポインタの他に前を表すポインタを持つ ことになります 今回は最初と最後をポインタを使うと取り扱いが面倒になるので 最初 (start) と最後 (end) を どちらとも構造体 ( 値は意味を持たない ) を使うことにします こうすることによって start を end を渡すときにポインタのポインタを利用しなくても良いことになります しかし データ自身 は 次のノードから入っていますので その点を注意しなければなりません ex31.c /* 双方向リスト */ #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node *prev, *next; node; void insert_list(node *s, node *e, int x); void print_list(node *s, node *e); void print_list_rverse(node *s, node *e); int main(void) { node start, end; int i, x; start.next = &end; end.prev = &start; for(i = 0; i < 5; i++) { printf(" 値を入力してください : "); scanf("%d", &x); insert_list(&start, &end, x); print_list(&start, &end); print_list_rverse(&start, &end); return(0); /* データの挿入 */ void insert_list(node *s, node *e, int x) { node *new, *z; new = (node *)malloc(sizeof(node)); new->value = x; for(z = s ; z->next!= e && z->next->value < x; z = z->next); new->next = z->next; new->prev = z; z->next->prev = new; z->next = new; 41

2 /* データの表示 */ void print_list(node *s, node *e) { for(s = s->next ; s!= e; s = s->next) { printf("%d ", s->value); printf("null n"); /* データの表示 ( 逆順 ) */ void print_list_rverse(node *s, node *e) { for(e = e->prev ; e!= s; e = e->prev) { printf("%d ", e->value); printf("null n"); 練習問題 3.3 指定された値があるときにはそのノードのポインタを なければ指定された値より小さいもののう ち最大のノードのポインタを それも存在しないときには NULL を返す関数 find_node を作成せよ ex92.c /* 双方向リスト */ #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node *prev, *next; node; void insert_list(node *s, node *e, int x); void print_list(node *s, node *e); node *find_node(node *s, node *e, int x); int main(void) { node start, end, *find; int i, x; start.next = &end; end.prev = &start; for(i = 0; i < 5; i++) { printf(" 値を入力してください : "); scanf("%d", &x); insert_list(&start, &end, x); print_list(&start, &end); printf(" 検索する整数 : "); scanf("%d", &x); find = find_node(&start, &end, x); if(find == NULL) { printf(" 見つかりませんでした n"); else { printf(" 見つかりました : %d(%p) n", find->value, find); return(0); 42

3 /* データの挿入 */ void insert_list(node *s, node *e, int x) { node *new, *z; new = (node *)malloc(sizeof(node)); new->value = x; for(z = s ; z->next!= e && z->next->value < x; z = z->next); new->next = z->next; new->prev = z; z->next->prev = new; z->next = new; /* データの表示 */ void print_list(node *s, node *e) { for(s = s->next ; s!= e; s = s->next) { printf("%d ", s->value); printf("null n"); /* データの探索 */ node *find_node(node *s, node *e, int x) { node *p; 43

4 3.3 二分木 リストの一種ですが 二つの子を持つ形で作ります ここでは簡単な例として 右の子は大きい 値 ( 等しい場合を含む ) を持ち 左の子は小さい値を持つリスト を作成してみます そのために 構造体には left と right という二つのポインタを用意します ex33.c #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node *left; /* 左の子 */ struct node *right; /* 右の子 */ node; void add_binary(node **root, int x); void print_binary(node *x); int main(void) { int i, x; node *root = NULL; for(i = 0; i < 6; i++) { printf(" 値を入力してください : "); scanf("%d", &x); add_binary(&root, x); print_binary(root); printf(" n"); return(0); void add_binary(node **root, int data) { node *new, *x, *p; new = (node *)malloc(sizeof(node)); new->value = data; new->left = NULL; new->right = NULL; if(*root == NULL) { *root = new; else { x = *root; while(x!= NULL) { p = x; if(data <= x->value) { x = x->left; else { x = x->right; if(data <= p->value) { p->left = new; else { p->right = new; 44

5 void print_binary(node *x) { if(x!= NULL) { print_binary(x->left); printf("%4d", x->value); print_binary(x->right); 5, 4, 1, 3, 2, 6 と入力されたときに どのような 2 分木ができているか考えてみましょう 1, 4, 5, 3, 2, 6 と入力されたときに どのような 2 分木ができているか考えてみましょう と入力されたときに どのような 2 分木ができているか考えてみましょう 45

6 逆に 次のような二分木ができるのはどのような入力が行われたか考えてみよう どちらも 一通り ではありません ここでの表示順は 通りがけ順 といわれるものです こうすると ちょうどソートと同じ結果にな ります print_binary 関数を変更すれば他の順序で表示することも可能です 実際に 実行して 違いを確かめておいてください 行きがけ順 void print_binary(node *x) { if(x!= NULL) { printf("%4d", x->value); print_binary(x->left); print_binary(x->right); 帰りがけ順 void print_binary(node *x) { if(x!= NULL) { print_binary(x->left); print_binary(x->right); printf("%4d", x->value; 46

7 問題 3.4 最小値を削除し 最小値のノードへのポインタを返す関数 delete_min を作成せよ ex34.c #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node *left; /* 左の子 */ struct node *right; /* 右の子 */ node; void add_binary(node **root, int x); void print_binary(node *x); node *delete_min(node **r); int main(void) { int i, x; node *root = NULL, *min; for(i = 0; i < 6; i++) { printf(" 値を入力してください : "); scanf("%d", &x); add_binary(&root, x); print_binary(root); printf(" n"); min = delete_min(&root); printf(" 最小値 %d を削除しました n", min->value); print_binary(root); printf(" n"); return(0); void add_binary(node **root, int data) { node *new, *x, *p; new = (node *)malloc(sizeof(node)); new->value = data; new->left = NULL; new->right = NULL; if(*root == NULL) { *root = new; else { x = *root; while(x!= NULL) { p = x; if(data <= x->value) { x = x->left; else { x = x->right; if(data <= p->value) { p->left = new; else { p->right = new; 47

8 void print_binary(node *x) { if(x!= NULL) { print_binary(x->left); printf("%4d", x->value); print_binary(x->right); node *delete_min(node **r) { 48