struct node{
int money;
vector<struct node*> nextNodes;
};
という構造体を定義してnodeだけを組み合わせて木構造を作り出したいのですが、この定義でいいのか、初期化はどうするのか、枝先を追加するときはどう定義したらいいのか？
よくわからない状態です。
枝の根元はTop変数で、Topから辿って特定の枝に新しい枝先を追加したり
Top変数に枝先を追加するには追加するにはどうすればいいのか。
何かサンプルでもいただければ自分で作れると思うのです。
どなたかオーソドックスな作り方をお願いします。
こんなんでええのかの。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class node {
int money;
vector<node*> nextNodes;
public:
explicit node(int m=0) : money(m) {}
~node() {
for_each(nextNodes.begin(), nextNodes.end(),
[](node* p) { delete p;});
}
void add_node(node* p) { nextNodes.push_back(p); }
int sum() const {
int sum = money;
for_each(nextNodes.begin(), nextNodes.end(),
[&](node* p) { sum += p->sum(); });
return sum;
}
};
int main() {
node* bank = new node(500);
node* safe = new node(100);
safe->add_node(new node(50));
safe->add_node(new node(10));
bank->add_node(safe);
cout << bank->sum() << endl;
delete bank;
}
ありがとうございます。
構造体を飛び越えてクラスのほうがまとまりがよさそうですね。
何かすごく圧縮されたコードのような気がします。
読み解けるか頑張ってみます。
追加質問です。
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2205
リンク先問題を解くために、当たりくじデータを後ろから読み込んであたりくじの木構造を作る処理なのですが、この木構造を安全にfreeする方法を知りたいです。
後、ローカルで簡単なテストをして、リンク先にあるサーバでジャッジしてもらったのですがランタイムエラーになってしまいました。
理由がつかめず困っております。
どなたかアドバイスお願いします。
ランタイムエラーになるコードは下記のとおりです。
#include <stdio.h>
#include <vector>
#include <stdlib.h>
void solve(int n,int m);
struct node* nodeCreat(struct node*,int,char c[9],int m);
void nodeSearch(struct node*,int,char[9]);
long sum;
struct node{
int money;
char no;
std::vector<struct node* > nexts;
};
int main(void)
{
int n,m;
scanf("%d %d",&n,&m);
while(n!=0 && m!=0){
if(n==0 || m==0){
printf("0\n");
}else{
solve(n,m);
}
scanf("%d %d",&n,&m);
}
return 0;
}
void solve(int n,int m)
{
sum=0;
char Ni[9];
int Mi;
struct node* top=(node*)malloc(sizeof(node));
for(int i=0;i<n;i++){
scanf("%s %d",Ni,&Mi);
nodeCreat(top,8,Ni,Mi);
}
for(int i=0;i<m;i++){
scanf("%s",Ni);
nodeSearch(top,8,Ni);
}
printf("%d\n",sum);
}
void nodeSearch(struct node* n,int p,char c[9]){
if(n->money>0)
{
sum+=n->money;
}else
{
for(unsigned int i=0;i<n->nexts.size();i++)
{
if(c[p]==n->nexts[i]->no)
{
nodeSearch(n->nexts[i],p-1,c);
break;
}
}
}
}
struct node* nodeCreat(struct node* n,int p,char c[9],int m)
{
if(n==NULL){
n=(node*)malloc(sizeof(node));
n->no=c[p+1];
}
if(c[p]=='*' || p==-1){
n->money=m;
n->no=c[p+1];
}else{
n->money=0;
int hit=-1;
for(unsigned int i=0;i<(n->nexts.size());i++){
if(n->nexts[i]->no==c[p]){
hit=i;
}
}
if(hit!=-1){
n->nexts[hit]=nodeCreat(n->nexts[hit],p-1,c,m);
}else{
n->nexts.push_back(nodeCreat(0,p-1,c,m));
}
}
return n;
}
> この木構造を安全にfreeする方法を知りたいです。
さっきのコードに書いてあります。
ありがとうございます。
自分で調べて解決しました。
同じく木構造を解く次の問題で悩んでいたりします。
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1056&lang=jp
できるだけ高い精度で問題を解こうとしてるのですが、分類がごちゃごちゃしていて、ちょっと解けそうで解けない微妙な段階です。
#include <stdio.h>
#include <math.h>
void calc(int n);
int main(void){
int n;
scanf("%d",&n);
calc(n);
return 0;
}
void calc(int n){
long double sum=0.0;
long double k=1.0;
long double nextK=0;
int deep=0;
//分類Aの弁当個数期待値の計算
for(int i=0;i<n;i++){
sum+=k;
nextK=k*(k*0.5);
if(nextK-k<=0.000000000000001){
//ここより深い階層は計算に対して影響を与えないので打ち切り
deep=i;
k=nextK;
break;
}
k=nextK;
}
printf("%0.19Lf %0.19Lf",sum,k);
long double m1=1.0;//分類Cの最初の独立な期待値
long double m2=1.5;//分類Cの2つ目の独立な期待値
long double t1,t2;
long double two=2.0;
long double k2=k;
//分類 Bは0なので飛ばして分類Cの最初の確率計算
//桁あふれを防止するためfor文で確率を求める。
//Mi でiがdeepからのデータのみを扱うことになる
for(int i=0;i<n-deep;i++){
if(i%2==1){
m2=m1*0.5+m2*0.5+1.0;
}else{
m1=m1*0.5+m2*0.5+1.0:
}
}
//この辺の計算、ｎ-deep-2やｎ-deepの値の設定が適切か悩んでます
k2=1.0-1.0/powl(two,(long double)(n-depp-2));
for(int i=deep;i<n-2;i++){
k=k*powl(two,(long double)(n-i+1));
k2*=2.0;
if(i%2==1){
m2=m1*0.5+m2*0.5+1.0;
sum+=m2*k2*k;
}else{
m1=m1*0.5+m2*0.5+1.0;
sum+=m1*k2*k;
}
}
}