回 帖 发 新 帖 刷新版面

主题:[讨论]一个 简单的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;
}

回复列表 (共2个回复)

沙发

唉,如果您打算拿出来问人,建议就多写点儿注释。
体谅体谅我们吧,天天在单位看代码,回到家帮你们解决问题时又要看代码,一点注释都没有~~~
除非是“门当户对”,或是有极大闲心异或极大兴趣,否则过20行的注释率还不达20%代码真的没人想看~~~~
最最最低条件:你每个函数好歹是干嘛的该写上注释吧。。。
关键的思路、逻辑判断该写上注释吧。。。

板凳

你好.我是全职网赚工作者.
如果你有时间有电脑.
想在网络上创业.请联系我..
项目绝对真实.详情QQ空间资料
加盟请联系 QQ908889846

我来回复

您尚未登录,请登录后再回复。点此登录或注册