定数と演算記号(+または*)からなる数式を表現する二分木を使い、演算子の順序を交換する操作を考える。
二分木のノードとなる構造体は、struct node { int type, val; struct node *left, *right; };とする。ノードの種類を type の値により区別する。数値を示すときは type を'v'とし、type が'o'のとき演算子であるとする。数値の場合には値を valに格納する。演算子(+と*の2種類のみ考える)のときは、val は'+'か'*'のいずれかにする。
各関数の役割を述べる。関数 new_node は、ノードとなる構造体を malloc で確保し、各メンバーの値を引数から得た値から設定し、その構造体を戻り値とする。関数 v_nodeは、引数で与えられた数値を表すノードを作成して返すものである。関数 o_node は、演算子を表すノードを作成して返すもので、演算子の種類を第一引数で('+'または'*'として)指定する。第二~第三引数に従って left,right の値が設定される。関数 calc は、引数で与えられた木について演算結果の値を返す。
関数 printTree は字下げをつけて二分木を右側ノードが上になるよう表示する。関数changeNodes は引数で指定されたノードとその右のノードを交換する。これらの関数を完成させることが課題である。
main では、二分木を作成したのち printTree で二分木を表示し、calc を用いて式の値を表示する。さらに changeNodes を呼び出して演算子の順序を交換する。交換を行った後の二分木について printTree で二分木を表示し、calc を用いて式の値を表示している。
実行結果の例
$ ./a.out
初期状態
v:2
op:+
v:1
op:*
v:3
式の値:9
changeNodes 実行後
v:2
op:+
v:1
op:*
v:3
式の値:5
ノード交換前の状態 ノード交換後の状態
作成する2つの関数について詳しく述べる。
関数 printTree は以下のように作成せよ。
第二引数は字下げ量で、行の先頭からの空白の数を示す。第一引数は表示させる木のノードで、それが NULL なら何もしない。NULL でなければ、以下①~③を行う。①字下げを 3 増やして右部分木を表示する。②引数で渡されたノードの値を表示する。この際に、ノードが数値であれば書式"v:%d"で val を表示し、ノードが演算子であれば書式"op:%c"で val を表示する。③字下げを 3 増やして左部分木を表示する。
関数 changeNodes は以下のように作成せよ。
引数はノードの入れ替えを行う際に先頭とするノード(x)を示す。その右のノード(y)との交換を図のように行うことで、x が y の左になり、y の左であったもの(2)は x の右になる。x の左のもの(1)と y の右のもの(3)はそのままで、関数の戻り値は y になる。なお、x または y が NULL の場合は何もせず x を返す。
提出指示
完成させたソースコードと、「例示用」の箇所をコメントにし、「提出用」の箇所のコメ
ントを外して有効にしたプログラムの実行結果を提出。
未完成プログラム
#include <stdio.h>
#include <stdlib.h>
struct node { int type, val; struct node *left, *right; };
typedef struct node* EXP;
EXP new_node(int t,int v,EXP l,EXP r){ //ノードを作成し値を設定
EXP x;
x=(EXP)malloc(sizeof(struct node));
if(x==NULL){printf("malloc filed");exit(-1);}
x->type=t; x->val=v; x->left=l; x->right=r;
return x;
}
EXP v_node(int v){//数値ノード
return new_node('v',v,NULL,NULL);
}
+
*
1
2 3
x
y
+
*
3
1 2
x
y
プログラミングA演習
第 14 回 最終総合演習
EXP o_node(int o, EXP l, EXP r){ //演算子ノード
return new_node('o',o,l,r);
}
int calc(EXP e){ //二分木で示される式の値を計算
int rv,lv;
if(e->type=='v')return e->val;
rv=calc(e->right);
lv=calc(e->left);
if(e->type=='o'&&e->val=='+')
return rv+lv;
if(e->type=='o'&&e->val=='*')
return rv*lv;
return 0;//デフォルト
}
void printTree(EXP t,int ind){
// この関数を作成
}
EXP changeNodes(EXP t){
// この関数を作成
}
int main(void){
EXP n1,n2,n3;
// 例示用
n2 = o_node('+',v_node(1),v_node(2));
n1 = o_node('*',v_node(3),n2);
printf("初期状態¥n");
printTree(n1,0);
printf("式の値:%d¥n",calc(n1));
n1=changeNodes(n1);
printf("changeNodes 実行後¥n");
printTree(n1,0);
printf("式の値:%d¥n",calc(n1));
/*
// 提出用
n3 = o_node('+',v_node(1),v_node(2));
n2 = o_node('*',v_node(3),n3 );
n1 = o_node('*',v_node(4),n2 );
printf("初期状態¥n");
printTree(n1,0);
printf("式の値:%d¥n",calc(n1));
n1->right=changeNodes(n1->right);
printf("changeNodes-1 実行後¥n");
printTree(n1,0);
printf("式の値:%d¥n",calc(n1));
n1=changeNodes(n1);
printf("changeNodes-2 実行後¥n");
printTree(n1,0);
printf("式の値:%d¥n",calc(n1));
*/
return 0;
A 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
問題文がメチャクチャだ。
> ノード(y)との交換を図のように行うことで
図ってどれだよ?
あと、ノードの表示例がインデント無しになってるんで、何をやってるんだかサッパリ分からん。
こんな、例示だ何だって前後してるような問題を丸投げしてる理由は唯一つ。
ハッキリ言って「問題文をマトモに読みたくない」って程詰まってるんだろ?
やめなさいよ。授業を落とした方が良い。
だってプログラミング楽しくないんでしょ?
他の投稿
プログラミングC言語について次の問題がわかりません:
https://oshiete.goo.ne.jp/qa/12763927.html
も見たけど、この問題とあちらの問題だと差があり過ぎるんだよ。
あっちは、プログラミング入門者用の問題、こっちはアドバンスドクラスの問題だ、平たく言うと。
で、あっちの・・・ぶっちゃけるとUNIXのwcコマンドのダウングレード実装の問題が解けない実力ならこっちの問題は解けない。
wc.c
https://opensource.apple.com/source/text_cmds/te …
なんで初級クラスの問題に躓いてるヤツがアドバンスドクラスの問題をやってるの?
もう初級クラスの時点で「ついていけない」って分かったんでしょ?それ以上のコースを取ろう、なんつーのは自殺行為だ。
今後貴方は、こうやって丸投げしつつ授業をクリアしていくつもり?
絶対無理だ。破綻する。
さっさと授業を落として別の「自分に向いてる分野」を勉強すべきだ。
別にプログラミングが出来る/出来ないのとアタマの良し/悪しは関係ない。
あるのは単に「向き/不向き」なだけだ。戦略的に撤退しなさい。
絶対に貴方が「学んでて楽しい」と思うモノがプログラミングの他にあるはずだから。
(しかし、この短期間に貴方のように「無謀な事をやってる」人間が連続して現れてる事にビックリしてる)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
int type, val;
struct node *left, *right;
};
typedef struct node* EXP;
EXP new_node(int t, int v, EXP l, EXP r) { /* ノードを作成し値を設定 */
EXP x;
x = (EXP)malloc(sizeof(struct node));
if (x == NULL) {
printf("malloc failed");
exit(EXIT_FAILURE);
}
x->type = t;
x->val = v;
x->left = l;
x->right = r;
return x;
}
EXP v_node(int v) { /* 数値ノード */
return new_node('v', v, NULL, NULL);
}
EXP o_node(int o, EXP l, EXP r) { /* 演算子ノード */
return new_node('o', o, l, r);
}
int calc(EXP e) { /* 二分木で示される式の値を計算 */
int rv, lv;
if (e->type == 'v') {
return e->val;
}
rv = calc(e->right);
lv = calc(e->left);
if (e->type == 'o' && e->val == '+') {
return rv + lv;
}
if (e->type == 'o' && e->val == '*') {
return rv * lv;
}
return EXIT_SUCCESS; /* デフォルト */
}
void printTree(EXP t, int ind) {
char str[256];
for (int i = 0; i <= ind; i++) {
if (i < ind) {
str[i] = ' ';
} else {
str[i] = '\0';
}
}
if (t == NULL) {
return;
} else {
printTree(t->right, ind + 3);
t->type == 'v' ? strcat(str, "v:%d\n") : strcat(str, "op:%c\n");
printf(str, t->val);
printTree(t->left, ind + 3);
}
}
EXP changeNodes(EXP t) {
EXP x = (EXP)malloc(sizeof(struct node));
EXP y = (EXP)malloc(sizeof(struct node));
x = t;
y = t->right;
if (x == NULL || y == NULL) {
return x;
} else {
x->right = y->left;
y->left = x;
return y;
}
}
int main(void) {
EXP n1, n2, n3;
/* 例示用 */
n2 = o_node('+', v_node(1), v_node(2));
n1 = o_node('*', v_node(3), n2);
printf("初期状態\n");
printTree(n1, 0);
printf("式の値 : %d\n", calc(n1));
n1 = changeNodes(n1);
printf("changeNodes 実行後\n");
printTree(n1, 0);
printf("式の値 : %d\n", calc(n1));
/* 提出用 */
n3 = o_node('+', v_node(1), v_node(2));
n2 = o_node('*', v_node(3), n3);
n1 = o_node('*', v_node(4), n2);
printf("初期状態\n");
printTree(n1, 0);
printf("式の値 : %d\n", calc(n1));
n1->right = changeNodes(n1->right);
printf("changeNodes-1 実行後\n");
printTree(n1, 0);
printf("式の値 : %d\n", calc(n1));
n1 = changeNodes(n1);
printf("changeNodes-2 実行後\n");
printTree(n1, 0);
printf("式の値 : %d\n", calc(n1));
return EXIT_SUCCESS;
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分 1 2022/07/19 17:03
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 malloc関数を使ってください!お願いします! 最 1 2022/07/21 09:28
- C言語・C++・C# 至急お願いします。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分母 3 2022/07/19 17:09
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
- C言語・C++・C# このプログラミングの問題を教えてほしいです。 キーボードからデータ数nとn個のデータを入力し、平均値 3 2022/12/19 22:51
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ルート要素ノードが2個ある場合?
-
あるノードリストに、特定の名...
-
CPUの考え方を教えてください ...
-
SNMP リンクダウンとノードダ...
-
同じタグ名の項目取得
-
TreeViewの再表示のちらつきを...
-
双方向リストの関数
-
昔Winnyってありましたけど、あ...
-
C言語:文字列の並び替え
-
TreeViewのNodeについて
-
2分探索木の高さを求めるプロ...
-
XML文書の指定した属性値を持つ...
-
ノードとは
-
二分木の高さについて
-
C# TreeView 効率良いノード追...
-
XPathGraphでノードの値を取得...
-
ツリービューを閉じさせたくない。
-
VB6.0でDOMを使用して...
-
VB6.0でDOMを使用して...
-
グラフ色塗り問題のプログラミ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
CPUの考え方を教えてください ...
-
昔Winnyってありましたけど、あ...
-
SNMP リンクダウンとノードダ...
-
ルート要素ノードが2個ある場合?
-
同じタグ名の項目取得
-
ノードとは
-
あるノードリストに、特定の名...
-
TreeView の初期表示について
-
ツリービューのノードをダブル...
-
コンテキストメニュークリック...
-
ノード数とは?
-
XML文書の指定した属性値を持つ...
-
複数のマックPCによる数値計算...
-
C#でtreeviewの指定ノードを選...
-
VB6.0ツリービューについて
-
TreeViewの再表示のちらつきを...
-
VB6.0でDOMを使用して...
-
vbsのDOMDocumentで要素のText...
-
TreeViewで複数ノードの選択は...
-
C# TreeView 効率良いノード追...
おすすめ情報