木構造の練習問題が解けず
解決http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1217
リンク先はプログラムの練習問題です。
コードを書いてサーバに送信するとサーバ側でgccでコンパイル、テストデータによる自動採点をしてくれるというサイトの問題です。
木構造の勉強だと思ってリンク先問題を解くためのコードを書いてみたのですがサーバにコードを送信してみるとランタイムエラーがでてしまいました。
なにかが悪いと思うのですが自分では見つけることができません。
どなたかご指南ご指摘お願いします。
#include<stdio.h>
#include<vector>
#include<string>
#include<string.h>
#include<map>
void setTree(int x,int y);
struct node{
node* parentNode;//親のノード
std::string name;
std::vector<node> childNodes;//子のノード
};
int main()
{
int x,y;//人数、質問の数
char t;
scanf("%d %d",&x,&y);
while(x!=0 || y!=0){
scanf("%c",&t);
setTree(x,y);
scanf("%d %d",&x,&y);
printf("\n");
}
}
void setTree(int x,int y){
char space[100];//文字列の読み込み
int sCount=0,k,oldCount=0,t;
node topNode;//根元となるノード
topNode.parentNode=&topNode;//安全のためにトップノードをトップノードとリンク
node nAdd;//木構造にADDするノード、名前
node* n1=&topNode;//木構造内での位置
std::map<std::string,node*> nodes;//名前から木構造のどのポイントに対応するかを指ししめす
for(int i=0;i<x;i++){
scanf("%[^\n]%*c",space);//一行ずつ名前の取得
k=sCount=0;
while(space[sCount]==' '){
sCount++;//余分なスペースを削除、ついでにこの人の木構造での階層位置も取得
}
while(space[k+sCount]!='\0'){
space[k]=space[k+sCount];//スペース削除
k++;
}
space[k]='\0';
nAdd.name=space;
t=sCount-oldCount;
if(t<0){
//家族の図が浅い階層に移動したならその分根元に戻る
for(int i=0;i<-t+1;i++){
n1=n1->parentNode;
}
}else if(t==0){
//同じ階層なら、一つ上の階層に戻り、そこから下に幹を一つ伸ばす
n1=n1->parentNode;
}
nAdd.parentNode=n1;//親ノードの設定
n1->childNodes.push_back(nAdd);//新しい幹を追加
n1=&n1->childNodes[n1->childNodes.size()-1];//追加した幹を参照
nodes[n1->name]=n1;//木構造内での位置をマップに保存
oldCount=sCount;//家系図内での階層の深さを保存
}
//ここから質問文に対する評価を行う
char name1[22],name2[22];
char tempCom[12];
std::string command;
for(int i=0;i<y;i++){
scanf("%s",name1);//名前の取得
command="";//質問文の種類
for(int j=0;j<4;j++){
scanf("%s",tempCom);//質問文取得
command+=tempCom;
}
scanf("%s",name2);//名前の取得
name2[strlen(name2)-1]='\0';
char t;
scanf("%c",&t);
//質問文の判断
if(command=="isachildof"){
//name1はname2の子供
if(nodes[name1]->parentNode->name==name2){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="istheparentof"){
//name1はname2の親
if(nodes[name1]->name==nodes[name2]->parentNode->name){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isasiblingof"){
//name1とname2は兄弟
if(nodes[name1]->parentNode->name==nodes[name2]->parentNode->name){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isadescendantof"){
//name２はname1の先祖
n1=nodes[name1];
bool ok=false;
while(n1!=&topNode){
n1=n1->parentNode;
if(n1->name==name2) ok=true;
}
if(ok==true){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isanancestorof"){
//name1はname2の先祖
n1=nodes[name2];
bool ok=false;
while(n1!=&topNode){
n1=n1->parentNode;
if(n1->name==name1) ok=true;
}
if(ok==true){
printf("True\n");
}else{
printf("False\n");
}
}
}
}
ちょっと見ただけですが。
setTree関数内部にノードを宣言しても関数終了時に開放されてしまいます。
ルートを含め、ノードの寿命を考えてみてください。
データセットごとに家族図を表す木構造を一度完全に消去して家族図を作りなおす必要があるので、むしろ完全に解放されないと困ります。
後、読みにくいのでコードにインデントをきかしたいのですがどうすればいいでしょうか？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1217
リンクに間違いがあったようなので張り直しと記ます。
これ自分でデバッガにかけてデバッグしてます？
ステップ実行していけばおかしいところはすぐに分かると思います。
質問文は1行で入力されるはずなのに、プログラム中では名前とコマンドを分けていますよね？
その結果オーバーフローで落ちているのだと思います。
自分でテストデータを用意してテストはしています。
質問文は名前とそれ以外の部分を切り分けるために、複数回に分けて読み込んでいます。
その部分でオーバーフローしてるとは思えないのですが。
scanfの基本は押さえているつもりです。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=1217FamilyTree2.txt
質問文読み込み部分に間違いがあるかどうか検証するために、読み込み部分を書きなおしたバージョンを上げておきます。
これもランタイムエラーが出て駄目でした。
一応インデントをつけたバージョンです。
ファイルのコードはshift_JIS。
今回の訂正で読み込み部分はよほど長い文章が代入されているのでもない限り安全な読み込みになったはずです。
もしかしたら木構造を作る部分に間違いがあるのかもしれません？
そのソース、VC++（ここ、VC++掲示板だからね）などつかって、
コンパイルできるか、動作するか？など試してみましたか？
>自分でテストデータを用意してテストはしています。
テストデータはサンプルのを使ってください。
じゃないと意味ないです。
>質問文は名前とそれ以外の部分を切り分けるために、複数回に分けて読み込んでいます。
勝手に仕様を変えちゃダメでしょうに。
サンプルインプットの後半部分で試してください
---
2 1
abc
xyz
xyz is a child of abc.
0 0
---
貴方のプログラムでは質問文を入れるところでセグメンテーション違反が発生します。
自己解釈で仕様を捻じ曲げたテストで動いたといわれても説得力ないですよ。
あぁ、読み飛ばしてた。
>質問文読み込み部分に間違いがあるかどうか検証するために、読み込み部分を書きなおしたバージョンを上げておきます。
最初からそれで質問してください。
最初に投稿されたものは問題解決のために当初の仕様とはそぐわないものになっている注釈もないし、質問文の読み込みが怪しいとにらんだ根拠もないし。
時間がないので問題のある場所のみ提示します。
103行目の
if(nodes[name1]->parentNode->name==name2)
でセグメンテーションフォールトしてます。
本当にデバッグしていますか？
>テストデータはサンプルのを使ってください。
>じゃないと意味ないです。
サンプルにあるテストデータの場合貧弱すぎてテストデータになりえません。
bcc32で私の環境で実行してみると
2 1
abc
xyz
xyz is a child of abc.
は全くエラーになりません。
>質問文の読み込みが怪しいとにらんだ根拠もないし
>質問文は1行で入力されるはずなのに、プログラム中では名前とコマンドを分けていますよね？
>その結果オーバーフローで落ちているのだと思います。
asdさんがその部分が怪しいというから修正しただけです。
asdさんはscanfの基本的な動作すら理解されてないのに、何を言ってるのですか？
scanf("%s",str)
とするとscanfは一行読み込まず、空白かtabか改行が出てくるまで読み込む使用になっています。
もしかしたら関数終了時の木構造の解法をしてない点に問題があるのかも？
void test() {
std::vector<int> v;
std::map<int, int*> m;
v.reserve(2);
for (int i=0; i < 3; ++i) {
printf("---- %d つ目----\n", i + 1);
v.push_back(0);
m[i] = &v[i];
for (int j=0; j < v.size(); ++j) {
printf(" &vector[%d] == %08x\n", j, &v[j]);
printf(" map[%d] == %08x\n", j, m[j]);
}
}
}
コレがエラーの直接の原因かどうかは知らん。bcc で俺の伝えたい結果が出るかどうかも知らん。
はぁ。
サンプルじゃ十分なテストケースにならないのは正しいけど、
サンプルデータでさえ落ちてたんだけど。
scanfの仕様を間違えていた点は申し訳ありませんが、
その言い方はどうなの？
絶対に間違えない自信はないので貴方の質問には回答しないでおきますね。
>103行目の
>if(nodes[name1]->parentNode->name==name2)
修正後のソースで落ちるところも指摘してるのにそこはスルーされるし、
相手すると疲れる。
...てかこの問題にTreeを必要としない。map<string,string>ひとつで十分とミタ。
クソ。です。
はい、解決。
働け。よ。
ソースも問題の内容自体もまともに見てないので
的外れかもしれませんが……とりあえず
struct node{
node* parentNode;//親のノード
std::string name;
std::vector<node> childNodes;//子のノード
};
なる宣言を見ただけで，動的に木構造を作り上げるのが
とても難しそうに見える…
childNodesをstd::vector<node>からstd::list<node>に変えたら
とりあえず動いたりしませんか？
>修正後のソースで落ちるところも指摘してるのにそこはスルーされるし、
相手すると疲れる。
私の環境では何故か、問題のデータだけでなく他の色々なテストデータを代入しても欠片も落ちないんです。
スルーしたわけじゃなく私の環境では落ちないと書いてますが？
すいません、少し頭を冷やしました。
何かコンパイラ依存の所があるのでしょうか？
bccでなく、別のコンパイラを使うべきでしょうか？
コンパイラの種類や落ちる原因も含めて落ちるというのをもう少し詳しくお願いします。
>.てかこの問題にTreeを必要としない。map<string,string>ひとつで十分とミタ。
ありがとうございます。
問題に同一名が存在しない限り確かにそれで行けそうですね、
実は問題に同一名が存在しないということに100％の自信をもってるわけじゃないのでそこらへんの確認もお願いします。
>gak@水野女史を思い出したさん
ええと私はレベルが低いので読み解けるかわかりませんが、頑張って読み解こうと思います。
毎日プログラムの勉強してレベルアップしているところですがまだまだレベルも低く日々勉強と思って読ませていただきます。
listを使った方法も検証してみます。
木構造の勉強なのでできたら木構造で解けたらと思います。
ありがとうございます。
asdさんのご指摘も正しかったんですね。
すいませんでした。
gak@のご指摘で理解できました。
vectorは値が代入されて要素があふれ拡張される時に、全要素がメモリ内での位置を変化させていく。
vectorにこんな使用があったなんて全く知りませんでした。
一度確保されたデータは静的なものだとばかり思いこんでました。
私の勉強不足、ただただそれに尽きます。
それでも不思議なのは、vectorに要素が一つしか代入されてない
abc xyz の場合でもエラーが起こることです。
これはかなり不思議です。
私の環境ではエラーにならずきちんと木構造内での位置を返すからです。
vectorがあふれて拡張されてないのにエラーが起こる？
かなり不思議です。
テスト方法が不完全だったというのも実感しました。
論理的なテストだけでなく量を大量にそろえたテストも必要なんですね。
気が付きませんでした。
勉強になります。
私まだまだ初心者です。
解けました。
gakさんasdさんありがとうございます。
vectorのメモリ管理を勘違いしていたのが原因でした。
私自身は大した助言が出来てないのと、トゲトゲしい言い回しがあったので
申し訳ないと思うばかりです。
堀江さんの環境では落ちないとのことでしたが、私はLinux のgccでコンパイルして落ちてました(環境を書いて置けばよかったですね)
なんにしても無事に解決したようでよかったです。
私も精進しなくてはと思う次第です。
確かに。勉強不足だな。
がんばれよ。
ありがとうございます。
プログラマの仕事目指して日々頑張っていきます。
そのうちまた質問すると思いますがその時は宜しく。
では今回は解決ということで。
プログラマの仕事目指＞＞どの分野ですかね？
山ほどある種類の中のドコを目指してるんでしょうかね。
プロになるには、学校に行かないと無理ですよ。
↑「学校は関係ない」とは言わんけど、無理なはずがない。
あたしゃそのテの学校行ってないけど30年プロやってますし。
学校？・・・そんなもん無かったよ〜な。
επιστημηさんをはじめ、先人の記事を読むのが勉強。
とかいう世界(vv;)。25年プロやってて、まだ現役(笑)。
失業者か。ん〜うらやましいねぇ。ホント。
オレもプータになりたいよ。金がありゃ〜な。
木構造を調べた。
なんだよ。将棋の思考ルーチンじゃん。（笑）
作れるかね？堀君。
作れたら
ここの村人になれるかもね。
紹介状を書いておくよ（笑）
>επιστημηさんをはじめ、先人の記事を読むのが勉強。
色々なプログラムに関する記事を読む習慣を身につけて行こうかと思います。
こういう話は少し勇気がわきます。
今は偏差値の高い大学を出てないとゲーム系のプログラマは就職できないとか色々な壁があるようなので、自分としては低学歴でもつけるプログラマの世界という現実を探すしかないかなというのが実感です。
>山ほどある種類の中のドコを目指してるんでしょうかね。
>プロになるには、学校に行かないと無理ですよ。
まだ自分は基礎的なアルゴリズムを解いているレベルで、実力としては高校３年生レベル。
最近ようやく大学一年レベルのプログラムができるようになった段階。
どの分野とかまだ決めかねている段階です。
大学行ってないので世にどんな技術分野があるのか良く知らないのです。
確かに大学レベルの研究や教育と結び付いたプログラムの世界は、多分私には手が出ませんし、どうすればプログラマになれるかなと試案してる段階です。
バイオ関係で間接的なデータから高度な数学を無数に駆使して細胞内部の状態やＤＮＡ構造を統計的に推測するとか、Ｂ777の翼形状を遺伝的アルゴリズムで決定したとか、過酷な環境で動作するロボットを制御をするとか、昨今のゲームのキャラ動作ＡＩの高度さとかそういう記事を読んでも凄いと思えど絶対に手が届きませんし、、、
いやもっとレベルが低いところでも手が届かないかな。
私でも手が届くプログラムの世界ってどんなんなんだろう。
まあ悩んでいます。
まだ大学一年レベルのプログラムしかできないので、世に出てプログラムができますなんていうのはまだ先の話。
アルバイトしながら勉強する日々ですね。
| ツイート |  |