アルゴリズムの勉強をし始めたものです。
深さ優先探索で
0
/ \
1 2
/\ /\
3 4 5 6
/\
8 9
の木を行きがけ順で表示(0,1,3,4,2,5,8,9,6)するC言語のプログラムを作っています。参考書を見ながら途中まで作ってみました
/* 行きがけ順で表示するプログラム */
/* 配列のデータが9個と決まっている場合 */
#include <stdio.h>
#define N 100
struct cell
{
int node;
struct cell *next;
};
void preorder(int n, struct cell **S);/* 前順 */
int main()
{
struct cell *S[N];
int root;
preorder(root, S);
}
void preorder(int n, struct cell **S)/* 前順 */
{
struct cell *q;
printf("%d", n);/* 表示 */
q = S[n];
while(q != NULL)
{
preorder(q -> node, S);/* 再帰 */
q = q -> next;
}
return;
}
ここから例えば配列のデータが1,3,5,7,9,11,13,15,17と決まっている場合、どうやってこれらのデータを設定すればいいのでしょうか?参考書を見てもアルゴリズムの部分しか書かれていなかったので完成形が見えてこないです。
よろしくお願いします。
No.6ベストアンサー
- 回答日時:
★アドバイス
0
/ \
1 2
/ \ / \
3 45 6
/ \
8 9
>の木を行きがけ順で表示(0,1,3,4,2,5,8,9,6)するC言語のプログラムを作っています。参考書を見ながら途中まで作ってみました
↑質問内容に『木』と表現しています。二分木の木でしょ。
それなら left、right の構造体を使って書き換えて下さい。
>次の項に書いてあったので使わないと思ったのですが実現不可能ですか?
↑回答者 No.1 さんのお礼から問題文の次に二分木のアルゴリズムの解説をしているのでは?
>配列のデータが1,3,5,7,9,11,13,15,17と決まっている場合、どうやってこれらのデータを設定すればいいのでしょうか?
↑単純に二分木の構造体に順番に 1~17 のデータを登録(設定)すれば良い。
このためには、二分木用のデータ設定関数を作ります。
・登録の手順
(1)root の左『1』をセット
(2)root の右『3』をセット
(3)右の『3』に『5』をセット
(4)右の『5』に『7』をセット
(5)右の『7』に『9』をセット
(6)右の『9』に『11』をセット
(7)右の『11』に『13』をセット
(8)右の『13』に『15』をセット
(9)右の『15』に『17』をセット
となります。
配列のデータがすでに整列しているので綺麗に二分木に登録されません。→右の枝にずっと
セットすることになってしまう。二分木の場合は、登録するデータがランダムなデータの時
平均化して枝分かれして綺麗に登録できます。これが二分木の特徴。
・http://oshiete1.goo.ne.jp/qa2627991.html→『再帰呼び出しで求めたい経路を表示させたい!』
↑の過去質問も参考にして下さい。
以上。おわり。
参考URL:http://oshiete1.goo.ne.jp/qa2627991.html
No.5
- 回答日時:
> このことは次の項に書いてあったので使わないと思ったのですが
> 実現不可能ですか?
1つの根から2つの方向へ枝分かれするような、
今回やりたいことを実現することは、
以下お考えになっているデータ構造(単方向リスト)では
できません。
No.4
- 回答日時:
struct cell
{
int node;
struct cell *next;
};
この定義では質問で提示されている構造を表すのは無理でしょう。
どんな参考書をお使いなのかはわかりませんが、これは単方向リストで
使われるデータ構造だと思います。
参考書を読み間違えているか、参考書の出来が悪いのかいずれかではないでしょうか。
No.3
- 回答日時:
#2です
<下段の訂正>
>再帰をループネストすると処理系によっては無限ループになります。
>せめて、
if (q == NULL) return;
preorder(q -> node, S);/* 再帰 */
q = q -> next;
return;
でした、すみません。
No.2
- 回答日時:
int root=1,data[N]={3,5,7,9,11,13,15,17,0};
struct cell *S[N];
for (int i=1;i<18;i++)
{
S[i]=(cell*)malloc(sizeof(cell));
S[i]->node=data[i>>1];
}
S[17]=0;
preorder(root, S);
return 0;
で<1,3,5,7,9,11,13,15,17>と出力されますが、
趣旨が違っていたらすみません。
逸脱するのですが、
while(q != NULL)
{
preorder(q -> node, S);/* 再帰 */
q = q -> next;
}
再帰をループネストすると処理系によっては無限ループになります。
せめて、
if (q != NULL) {q = q -> next;return;}
preorder(q -> node, S);/* 再帰 */
にしたほうが安全ですよ。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# 未解決の外部シンボル _printfが関数_mainで参照されました 1 2022/09/18 15:28
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- C言語・C++・C# バイナリファイルをコピーするのにかかる時間を測りたいのですが実行するとFatel error:gli 2 2022/11/03 01:10
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
関数から配列を返すには?
-
配列の要素数に変数を入れたい...
-
C#でのフィボナッチ数列
-
構造体のextern方法
-
define で 配列
-
C#で構造体の配列を持った構造...
-
配列のアドレス部
-
MFC - ダイアログボックスのPic...
-
vector配列の重複を無くすには?
-
C++DLLからC#へのコールバック...
-
構造体の配列 char *' 型は 'ch...
-
C言語についてです 5人のテスト...
-
構造体を引数とする関数について
-
C言語 構造体でつまずいています
-
int i, int i[1];
-
c言語
-
C#で配列が空かを判定するには?
-
構造体の動的確保について
-
関数内に関数は無理でしょうか...
-
C言語において、 配列要素をひ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
関数から配列を返すには?
-
配列の要素数に変数を入れたい...
-
c言語
-
構造体のextern方法
-
define で 配列
-
C#で構造体の配列を持った構造...
-
C言語において、 配列要素をひ...
-
コンボボックスでデフォルト値...
-
2番目の最大値を求める
-
C言語の2次元配列 容量が大き...
-
C#で配列が空かを判定するには?
-
MFCのCArrayを使った二次元配列
-
C言語の課題が出たのですが自力...
-
C言語 ファイルの指定された行...
-
Cのエラー
-
ポインタを使って構造体の配列...
-
配列のアドレス部
-
char型配列をint型に代入するには
-
MFC - ダイアログボックスのPic...
-
C言語から質問です。
おすすめ情報