質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

1回答

2611閲覧

C言語 深さ優先探索について

Minochan

総合スコア14

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2018/08/02 06:37

C言語での深さ優先探索の実装についての質問です。

下に添付してあるのは幅優先探索のコードです。
このコードを元に深さ優先探索を実装したいのですが、どのように実装すればようでしょうか。

わかる方、教えてください。

また、木構造のTextデータは下のとおりです。

txt

11 2 2 3 3 4 4 5 5 6 6

C

1#include <stdio.h> 2#include <stdlib.h> 3 4#define BUFSIZE 256 5 6struct node{ 7 int value; 8 struct node *left; 9 struct node *right; 10}; 11 12int search_breadth1(int key, struct node *remain[]){ 13 int idx = 0; 14 int last = 1; 15 16 while(remain[idx] != NULL){ 17 if(remain[idx]->value == key){ 18 return 1; 19 }else{ 20 if(remain[idx]->left != NULL){ remain[last++] = remain[idx]->left; } 21 if(remain[idx]->right != NULL){ remain[last++] = remain[idx]->right; } 22 idx++; 23 } 24 } 25 26 return 0; 27} 28 29int search_breadth(struct node *root, int key){ 30 struct node *remain[BUFSIZE]; 31 int i; 32 33 remain[0] = root; 34 for(i = 1; i < BUFSIZE; i++){ remain[i] = NULL; } 35 36 return search_breadth1(key, remain); 37} 38 39struct node *addnode(struct node *root, int depth, int val){ 40 struct node *n, *new; 41 42 new = (struct node *)malloc(sizeof(struct node)); 43 new->value = val; 44 new->left = new->right = NULL; 45 46 if(root == NULL){ 47 return new; 48 }else{ 49 n = root; 50 } 51 52 for( ; depth > 1; depth--){ 53 if(n->right != NULL){ 54 n = n->right; 55 }else if(n->left != NULL){ 56 n = n->left; 57 }else{ 58 return NULL; 59 } 60 } 61 62 if(n->left == NULL){ 63 n->left = new; 64 }else if(n->right == NULL){ 65 n->right = new; 66 }else{ 67 return NULL; 68 } 69 70 return root; 71} 72 73struct node *loaddata(char *filename){ 74 int depth, val; 75 FILE *input; 76 struct node *root = NULL; 77 char line[BUFSIZE]; 78 79 input = fopen(filename, "r"); 80 if(input == NULL){ 81 fprintf(stderr, "Can't open file: %s\n", filename); 82 exit(1); 83 } 84 85 while(fgets(line, sizeof(line), input) != NULL){ 86 depth = 0; 87 while(line[depth] == ' '){ 88 depth++; 89 } 90 91 sscanf(&line[depth], "%d", &val); 92 root = addnode(root, depth, val); 93 if(root == NULL){ 94 fprintf(stderr, "illegal input file: %s\n", line); 95 exit(1); 96 } 97 } 98 99 fclose(input); 100 101 return root; 102} 103 104int main(int ac, char **av){ 105 int result; 106 struct node *root; 107 108 if(ac != 3){ 109 fprintf(stderr, "Usage: %s <datafile> <key>\n", av[0]); 110 exit(1); 111 } 112 113 root = loaddata(av[1]); 114 115 result = search_breadth(root, atoi(av[2])); 116 117 printf("Key \"%s\" is %s.\n", av[2], result == 1 ? "found" : "not found"); 118 119 return 0; 120} 121

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

ソースが長いの、代わりにかいつまんで書くと、
深さ優先とは、
```ここに言語を入力
1
2
3
4
5
6

で、1-2->と進み、3->4 を検査します。3も4も失敗の時は、5に戻って6に進みます。  広さ優先であれば、 1->2->5->3->4->6 という順序で進みます。 else

投稿2018/08/14 02:12

gm300

総合スコア580

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問