行きがけ順で表示するプログラムの作成方法
- アルゴリズムの勉強をし始めた初心者のための、行きがけ順で表示するプログラムの作成方法について解説します。
- まず、深さ優先探索を使用して与えられた木を行きがけ順で表示するC言語のプログラムを作成します。
- 配列データが決まっている場合、それらのデータをどのように設定すればいいのかについても説明します。
- ベストアンサー
行きがけ順で表示するプログラム
アルゴリズムの勉強をし始めたものです。 深さ優先探索で 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と決まっている場合、どうやってこれらのデータを設定すればいいのでしょうか？参考書を見てもアルゴリズムの部分しか書かれていなかったので完成形が見えてこないです。 よろしくお願いします。
- hirq
- お礼率11% (1/9)
- C・C++・C#
- 回答数6
- ありがとう数2
- みんなの回答 （6）
- 専門家の回答
質問者が選んだベストアンサー
★アドバイス ０ ／ ＼ １ ２ ／ ＼ ／ ＼ ３ ４５ ６ ／ ＼ ８ ９ ＞の木を行きがけ順で表示（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→『再帰呼び出しで求めたい経路を表示させたい！』 ↑の過去質問も参考にして下さい。 以上。おわり。
その他の回答 (5)
- asuncion
- ベストアンサー率33% (2126/6288)
> このことは次の項に書いてあったので使わないと思ったのですが > 実現不可能ですか？ １つの根から２つの方向へ枝分かれするような、 今回やりたいことを実現することは、 以下お考えになっているデータ構造（単方向リスト）では できません。
- sakusaker7
- ベストアンサー率62% (800/1280)
struct cell { int node; struct cell *next; }; この定義では質問で提示されている構造を表すのは無理でしょう。 どんな参考書をお使いなのかはわかりませんが、これは単方向リストで 使われるデータ構造だと思います。 参考書を読み間違えているか、参考書の出来が悪いのかいずれかではないでしょうか。
#2です ＜下段の訂正＞ >再帰をループネストすると処理系によっては無限ループになります。 >せめて、 if (q == NULL) return; preorder(q -> node, S);/* 再帰 */ q = q -> next; return; でした、すみません。
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);/* 再帰 */ にしたほうが安全ですよ。
- asuncion
- ベストアンサー率33% (2126/6288)
まずは、構造体の定義を見直してください。 二分木の、左部分木へのポインタと右部分木へのポインタの ２つが必要です。
関連するQ&A
- スタックの配列プログラム
スタックを配列で実現するプログラムとして #include<stdio.h> #define stack_size 100 #define stack_el_type int stack_el_type stack[stack_size]; int sp; void init_stack() { sp=-1 } void push(stack_el_type x) { if (sp < stack_size -1) stack[++sp] = x; else{ printf("stack full error.\n"); exit(1); } } stack_el_type pop() { if(sp >= 0 ) return stack[sp--]; else { printf("stack empty error.\n") exit(1); } } 上の完成形を参照として、 他の作り方として int stack[100] int sp void push(int x) int pop() を用いて作成する場合どのようにすればよいのでしょうか？ またスタックを一方向リストで実現するプログラムを作成するとき struct node{ int data; struct node *next; } struct node *push(int x,struct node *root) struct node *pop(struct node *root) を用いて作成する場合どのようにすればよいのでしょうか？ よろしければご教授お願いします
- 締切済み
- C・C++・C#
- このプログラムのポインタを配列に変換したいんですけど
Ｃ言語初心者です。助けてください。 途中までがんばったのですがどうしてもできません。問題はこの構造体の*name→name[25],*email→email[30]に変換させたいのですが、そのまま変換すると左辺値が必要や移植性のないポインタ変換などのエラーが出てしまいます。どうすればいいですか？教えてください。あと関数getlineと構造体は変えないでください。（指定した部分は除く） このプログラムは名前、メールアドレス、年齢を保存していき-1を入力した時出力されるというものです。 よろしくお願いします。 入力例 １０ hakata abc@・・・ 12 yokohama dfg@・・・ -1 -1 -1 出力例 -1 -1 -1 12 yokohama dfg@・・・ １０ hakata abc@・・・ #include <stdio.h> #include<stdlib.h> struct node { char *name; char *email; int age; struct node *next; } heap[100], *hp = heap; void getline(char *s,int n) { int c; while(--n>0&&((c=getchar())!=EOF && c!='\n')) *s++=c; *s='\0'; } char* dupstr(char* strg) { char* newstr; newstr=(char*)malloc(sizeof(char)*strlen(strg)); strcpy(newstr,strg); return newstr; } struct node *new(int n ,char* a, char* b) { hp->age=n; hp->email=a; hp->name=b; hp->next=NULL; return hp++; } struct node *add(struct node *p, struct node *q) { q->next=p; p=q; return p ; } void print_list(struct node *p) { while (p != NULL) { printf("%d ", p->age); printf("%s ", p->name); printf("%s ", p->email); p=p->next; } printf("\n"); } main() { int age,p; char buf[80],a[80],b[80],*email,*name; struct node *root=NULL; while(getline!=NULL) { getline(buf,sizeof(buf)); age=atoi(buf); getline(b,sizeof(b)); getline(a,sizeof(a)); email=dupstr(b); name=dupstr(a); root=add(root,new(age,email,name)); if(age==-1) break; } print_list(root); }
- ベストアンサー
- C・C++・C#
- 双方向リストのバブルソートについて
双方向リストをバブルソートを用いてソートしたいです。 下記がプログラム(一部)ですが、ソートした後にリスト表示すると 無限ループに陥ります。 どこがいけないのでしょうか。 #include <stdio.h> #include <stdlib.h> struct cell{ int data; struct cell *next, *prev; }; void insert_head(struct cell **head, int num){ struct cell *p, *p1; p = *head; p1 = make_cell(); *head = p1; p1->data = num; p1->next = p; if(p1->next != (struct cell *)NULL){ p1->next = p; p->prev = p1; } } void print_list(struct cell *head){ struct cell *p; p = head; printf("data = \n"); while(p != (struct cell *)NULL){ printf("%d\n", p->data); p = p->next; } } void sort_list(struct cell **head){ struct cell *p, *p2; int i, n; n = 0; p = *head; while(p->next != (struct cell *)NULL){ p = p->next; n++; } for(i = 0, p = *head; i < n-2; i++){ if(p->data > p->next->data){ if(p == *head){ *head = p->next; }else{ p->prev->next = p->next; } p2 = p->next; p->next = p->next->next; p->next->next = p; p->next->next->prev = p; p->next->prev = p->prev; p->prev = p2; }else p = p->next; } } int main(void){ struct cell *head = (struct cell *)NULL; int n; while(1){ printf("1:Insert head 2:Insert tail 3:Delete 4:List 5:Sort 6:Exit\n"); scanf("%d", &n); switch(n){ case 1: printf("num = "); scanf("%d", &n); insert_head(&head, n); break; case 2: printf("num = "); scanf("%d", &n); insert_tail(&head, n); break; case 3: printf("num = "); scanf("%d", &n); delete_cell(&head, n); break; case 4: print_list(head); break; case 5: sort_list(&head); break; case 6: return 0; break; } } }
- ベストアンサー
- C・C++・C#
- 二分探索木のプログラム
２分探索木のプログラムを作っているのですが、実行するとセグメテーション違反がでます。何が間違っているんでしょうか？ #include<stdlib.h> struct node{ struct node *left,*right; int datum; }; struct bintree{ struct node *root; }; /*空木を作成*/ void InitTree(struct bintree *p) { p->root=NULL; } /*木全体を削除*/ void ClearTree(struct bintree *p) { struct bintree *q,*r; if(p->root!=NULL){ q->root=p->root->left; ClearTree(q); r->root=p->root->right; ClearTree(r); free(p->root); } } /*第二引数で指定された値が木の節点のラベルに存在すれば、その節点へのポインタを返す。なければ、NULLを返す。*/ struct node * SearchNode(struct bintree *p,int x) { struct bintree *q,*r; struct node *a=p->root; int cond=x-(a->datum); if(a==NULL) return NULL; else if(cond==0) return a; else if(cond<0){ q->root=p->root->left; SearchNode(q,x); } else{ r->root=p->root->right; SearchNode(r,x); } } /*第二引数で指定された値が木の節点のラベルに存在すれば、NULLを返す。なければ、追加して、新たに作成された節点へのポインタを返す。*/ struct node * InsertNode(struct bintree *p,int x) { struct bintree *q,*r; struct node *a=p->root; int cond=x-(a->datum); if(a==NULL){ a=(struct node *)malloc(sizeof(struct node)); a->datum=x; a->left=a->right=NULL; return a; } else if(cond==0) return NULL; else if(cond<0){ q->root=p->root->left; a->left=InsertNode(q,x); } else{ r->root=p->root->right; a->right=InsertNode(r,x); } } int main() { struct bintree *p; struct node *a; InitTree(p); a=InsertNode(p,5); InsertNode(p,3); InsertNode(p,0); InsertNode(p,10); SearchNode(p,5); ClearTree(p); return 0; }
- 締切済み
- C・C++・C#
- リストがわかりません。
下のプログラムはリストに昇順になるように 入力された要素を挿入するプログラムですが、うまくいきません。どうか教えてください。 #include<stdio.h> static int count; struct node_tag{ int data; struct node_tag *next; }; typedef struct node_tag node_t; node_t *insert_node( node_t *t, int d ); node_t *print_list( node_t *r ); int main( void ) { node_t root; int data; root.next = NULL; for ( ;; ) { printf( "> " ); if ( scanf( "%d", &data ) != 1 ) break; insert_node( &root, data ); print_list( &root ); } return; } node_t *insert_node( node_t *t, int d ) { node_t *new_node; new_node = (node_t *)malloc( sizeof(node_t) ); if( new_node == NULL ) return NULL; if(count == 0) { new_node -> data = d; new_node -> next = NULL; t -> next = new_node; count++; } else { for(; t -> next != NULL; t = t -> next) { if(t -> next -> data >= d) break; } if(t -> next -> data == d) return; else if(t -> next -> data > d) { new_node -> data = d; new_node -> next = t -> next; t -> next = new_node; } else if(t -> next == NULL) { new_node -> data = d; t -> next = new_node; new_node -> next = NULL; } } return new_node; } node_t *print_list( node_t *r ) { node_t *p; printf("[ "); for( p = r -> next; p != NULL; p = p -> next) { printf("%d ", p -> data); } printf("]\n"); }
- ベストアンサー
- C・C++・C#
- C言語 二分木探索
今、int型の二分木にデータを追加する関数(引数は二分木へのポインタと追加する値、追加されたノードへのポインタを返す)をつくろうとしてます。 以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。 つくりかたを教えてください。 よろしくお願いします！ struct BinaryTreeNode{ int data; struct BinaryTreeNode *l_next; struct BinaryTreeNode *r_next; }; struct BinaryTree{ int node_num; struct BinaryTreeNode *root; }; BinaryTreeNode *BinaryTreeNodeAlloc(void) { BinaryTreeNode *node; node = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode)); if (node == NULL) { return (NULL); } node->l_next = NULL; node->r_next = NULL; return (node); } BinaryTreeNode *BinaryTreeDataAdd(BinaryTree *list, int x) { BinaryTreeNode *ptr; BinaryTreeNode *prev; BinaryTreeNode *new_node; ptr = list->root; prev = NULL; while (ptr) { ←？？ if (ptr->data < x) { prev = ptr; ptr = ptr->next; } else if (ptr->data == x) { return (NULL); } else { new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); ←？？ } new_node->data = x; new_node->next = ptr; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); } } new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); } new_node->data = x; new_node->r_next = NULL; new_node->l_next = NULL; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); }
- 締切済み
- C・C++・C#
- C言語 リスト
(1) /* list.c */ #include <stdio.h> #include <stdlib.h> struct node { int num; struct node *next; }; main() { struct node *head, *p; int x; head = NULL; while(scanf("%d",&x) != EOF) { p = (struct node *)malloc(sizeof(struct node)); p->num = x; p->next = head; head = p; } // リストの要素のnumの値を先頭から順に表示する p=head; while(p!=NULL) { printf("%d\n" ,p->num); p = p->next; } } (2) struct node *q; q = head; while(q->next != NULL) q = q->next; (1)を(2)を使い新しいノードをリストの最後に追加するようにしたいのですが どう書いたら良いのか教えていただきたいです
- 締切済み
- その他（学問・教育）
- 二分木のデータ入力について
C言語についての質問です。 キューと再起関数を使って2分木にデータを入れようとしたところ、以下のようなエラーが発生いたしました。 ddd.c: 関数 ‘dequeue’ 内: ddd.c:80:9: 警告: 戻りでポインタからキャスト無しに整数を作成しています [-Wint-conversion] return x; ^ ddd.c: 関数 ‘growTree’ 内: ddd.c:100:14: エラー: assignment to expression with array type x->sentence = dequeue(); なんとか解消しようとするのですが、どうしてもエラーが増えるばかりで、うまくいきませんでした。 どの部分をどのように直せばいいのか大変お手数ですが、教えていただけると助かります。 よろしくお願いいたします。 以下が実行したプログラムになっております。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define QUEUE_SIZE 100 /*キューの大きさ*/ /*配列でキューを表現する*/ int front, rear; char queue[3][50] = {"0b", "Ab", "Bb"}; char dequeue();/*キューからデータを取り出す*/ int next(int val);/*キューを配列で表現するとき、現在の次の配列のindexを返す*/ struct node{ char sentence[50];//値 struct node *left; //次のセルへのポインタ(左の子) struct node *right; //次のセルへのポインタ(右の子) }; int Gcount=0; void error(char *s);/*エラーを出力する*/ struct node* make_node();/*nodeをつくって返す*/ //void set_value_of_node(struct node* node,int a);/*nodeに値をセットする*/ struct node* growTree(int i, int k);/*深さiまで木を成長させ、そのルートを返す*/ void displayTree(struct node *node);/*node以下の部分木を表示する*/ int main(void){ struct node *root; int total=2 ; front = 0; rear = front + total + 1; root=growTree(total, 0); printf("\n\n\n前 順 表 示\n"); displayTree(root); return 0; } struct node* make_node(){/*nodeをつくって返す*/ struct node *p; if((p=(struct node*)malloc(sizeof(struct node ))) == NULL) error("メモリが足りません\n"); p->left =NULL; p->right =NULL; return(p); } //id set_value_of_node(struct node* node, int a)/*nodeに値をセットする*/ // //f(node == NULL)error("nodeが空です\n"); //ode->value=a; //rintf("%d ", node->value); // // void error(char *s){/*エラーを出力する*/ fprintf(stderr, s); exit(1); } /*キューからデータを取り出す*/ char dequeue(){ char *x; if(front == rear){ error("\nqueue is empty!!\n"); } x = queue[front]; front = next(front); return x; } /*キューを配列で表現するとき、現在の次の配列のindexを返す*/ int next(int val){ int next; next=(val+1)%QUEUE_SIZE; return(next); } struct node* growTree(int i, int k){/*深さiまで木を成長させ、そのルートを返す*/ /*課題1はここを書く*/ if(i == k) return NULL; k++; struct node *x; x = make_node(); x->sentence = dequeue(); x->left = growTree(i, k); x->right = growTree(i, k); return x; } void displayTree(struct node *node){/*node以下の部分木を表示する*/ /*課題2はここを書く*/ if(node == NULL) return; printf("%s\n", node->sentence); displayTree(node->left); displayTree(node->right); }
- 締切済み
- 情報工学
- 解析木
ノードの中身を表示しながらトラバースする関数 void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node); を再帰を使って書きなさい。 という問題がとけません。どなたかアドバイスをください。 ちなみに、この関数以外は下のように作りました。 #include <stdio.h> #include <stdlib.h> struct node { struct node *right; char key; struct node *left; }; typedef struct node * NodePointer; void treeinitialize(void); NodePointer makenode(char c); void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node); NodePointer head, tail; int main(){ treeinitialize(); //テスト用の木を作成 head->right=makenode('+'); head->right->left=makenode('1'); head->right->right=makenode('*'); head->right->right->left=makenode('2'); head->right->right->right=makenode('3'); //トラバース printf("preorder: "); preorder(head->right); printf("\n"); printf("inorder: "); inorder(head->right); printf("\n"); printf("postorder: "); postorder(head->right); printf("\n"); return 0; } void treeinitialize(void){ head=makenode(-1); tail=makenode(-1); head->right=tail; head->left=tail; } //ノードを作成し、そのノードへのポインタを返す。 NodePointer makenode(char c){ NodePointer x; x=malloc(sizeof(struct node)); x->key=c; x->right=tail; x->left=tail; return x; } void preorder(NodePointer node){ } void inorder(NodePointer node){ } void postorder(NodePointer node){ }
- 締切済み
- C・C++・C#
- 連結リストについて
連結リストについて アルゴリズムの本を買って勉強しているのですが、わからない箇所がありまして。 構造体宣言で (1)struct CELL { struct CELL *next; int val; }; (2)struct CELL { struct CELL *next; int val; }*header; 順番をたどって行く書き方で struct CELL *p; for (p=header; p!=NULL; p=p->next) printf("%d\n", p->value); なぜこれでp->valueの値が変動していくのですか？ それと上記の(1)の書き方でこのforを回すとき、headerはどのように定義すればよいのですか？ よろしくお願いします。
- ベストアンサー
- C・C++・C#
お礼
二分木とは *left; *right; のことですよね。 このことは次の項に書いてあったので使わないと思ったのですが実現不可能ですか？