主题:[讨论]一个 简单的ACM题
zoj的1167,请求看一下我的 程序错 在哪里?谢谢!
连接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=167
题目要求是给出一序列字符串,然后构建成树,按水平遍历输出
我的思路是:因为题目给定节点数不出 超过256个,所以申请一个300*300的数组 ,其中行代表深度,列代表在这一层的偏移,如(0,0)表示根,(1,0)表示的是根的左子树;
因为给出的路径表示是L和 R组 成的串,可以按 l=0,R=1,这样求出偏移
我的代码如下(从网上找了好多测试实例都没有错 ,可以提交有错希望各位帮忙解答一下那里出错的,先 谢谢)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int Row=300;
const int Col=300;
string mytree[Row][Col];
int ndepth=0;
const string nNoNode="";
bool isComplete=false;
void mMapIntoTree(const string);
int GetTreePath(const string &);
void coutPutTree();
bool checkTree();
void clearMyMem();
int main()
{
ifstream cin("122.txt");
string str;
while(1){
clearMyMem();
while(cin>>str){
if(str.compare("()")==0) break;
if(!isComplete){
continue;
}
string s=str.substr(1,str.length()-2);
mMapIntoTree(s);
}
coutPutTree();
if(cin.eof()) break;
}
}
void mMapIntoTree(const string str)
{
if(str=="") return;
int x=str.find(',',0);
string numstr=str.substr(0,x);
if(numstr==""){
isComplete=false;
return;
}
string pathstr=str.substr(x+1);
int len=pathstr.length();
if(len>256){
isComplete=false;
return;
}
int col=GetTreePath(pathstr);
if(mytree[len][col]!=nNoNode){
isComplete=false;
return;
}
mytree[len][col]=numstr;
}
int GetTreePath(const string & str)
{
int num=0,x=0;
int len=str.length();
if(len>ndepth) ndepth=len;//get the max depth of tree;
for(int i=0;i<len;i++){
if(str.at(i)=='L') x=0;
if(str.at(i)=='R') x=1;
num+=x*(1<<(len-i-1));
}
return num;
}
bool checkTree()
{
if(!isComplete) return false;
for(int j=ndepth+1;j>0;j--){
for(int i=0;i<Col;i++){
if(mytree[j][i]!=nNoNode){
if(mytree[j-1][i/2]==nNoNode) return false;
}
}
}
return true;
}
void coutPutTree()
{
if(!checkTree()){
cout<<"not complete\n";
return;
}
cout<<mytree[0][0];
for(int x=1;x<ndepth+1;x++){
for(int y=0;y<Col;y++){
if(mytree[x][y]!=nNoNode){
cout<<" "<<mytree[x][y];
}
}
}
cout<<endl;
}
void clearMyMem()
{
for(int i=0;i<Row;i++){
for(int j=0;j<Col;j++){
mytree[i][j]=nNoNode;
}
}
ndepth=0;
isComplete=true;
}
连接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=167
题目要求是给出一序列字符串,然后构建成树,按水平遍历输出
我的思路是:因为题目给定节点数不出 超过256个,所以申请一个300*300的数组 ,其中行代表深度,列代表在这一层的偏移,如(0,0)表示根,(1,0)表示的是根的左子树;
因为给出的路径表示是L和 R组 成的串,可以按 l=0,R=1,这样求出偏移
我的代码如下(从网上找了好多测试实例都没有错 ,可以提交有错希望各位帮忙解答一下那里出错的,先 谢谢)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int Row=300;
const int Col=300;
string mytree[Row][Col];
int ndepth=0;
const string nNoNode="";
bool isComplete=false;
void mMapIntoTree(const string);
int GetTreePath(const string &);
void coutPutTree();
bool checkTree();
void clearMyMem();
int main()
{
ifstream cin("122.txt");
string str;
while(1){
clearMyMem();
while(cin>>str){
if(str.compare("()")==0) break;
if(!isComplete){
continue;
}
string s=str.substr(1,str.length()-2);
mMapIntoTree(s);
}
coutPutTree();
if(cin.eof()) break;
}
}
void mMapIntoTree(const string str)
{
if(str=="") return;
int x=str.find(',',0);
string numstr=str.substr(0,x);
if(numstr==""){
isComplete=false;
return;
}
string pathstr=str.substr(x+1);
int len=pathstr.length();
if(len>256){
isComplete=false;
return;
}
int col=GetTreePath(pathstr);
if(mytree[len][col]!=nNoNode){
isComplete=false;
return;
}
mytree[len][col]=numstr;
}
int GetTreePath(const string & str)
{
int num=0,x=0;
int len=str.length();
if(len>ndepth) ndepth=len;//get the max depth of tree;
for(int i=0;i<len;i++){
if(str.at(i)=='L') x=0;
if(str.at(i)=='R') x=1;
num+=x*(1<<(len-i-1));
}
return num;
}
bool checkTree()
{
if(!isComplete) return false;
for(int j=ndepth+1;j>0;j--){
for(int i=0;i<Col;i++){
if(mytree[j][i]!=nNoNode){
if(mytree[j-1][i/2]==nNoNode) return false;
}
}
}
return true;
}
void coutPutTree()
{
if(!checkTree()){
cout<<"not complete\n";
return;
}
cout<<mytree[0][0];
for(int x=1;x<ndepth+1;x++){
for(int y=0;y<Col;y++){
if(mytree[x][y]!=nNoNode){
cout<<" "<<mytree[x][y];
}
}
}
cout<<endl;
}
void clearMyMem()
{
for(int i=0;i<Row;i++){
for(int j=0;j<Col;j++){
mytree[i][j]=nNoNode;
}
}
ndepth=0;
isComplete=true;
}