程序员人生 网站导航

UVa 10562 看图写树

栏目:互联网时间:2014-09-04 05:53:41

题目:题目就是给出一幅ASCII字符构成的树的图,然后转换成由字符括号构成的树的表示形式。可以知道,树有孩子结点的话,正下方会有一个字符 '|' ,紧接着会有一个覆盖所有孩子结点的字符序列“-------”,然后其下就是孩子结点。

思路:先将所有数据读下来。然后递归处理,给定一个左右边界,在该边界内逐个检查字符,如果是结点字符,则判断有无孩子等后续处理。

注意:因为每行会有空格,所以不能用scanf输入,换成fgets的话会保留有换行符(当然,可以进行处理或后续判断),这里使用的是gets来读入,因为可以确保不会溢出。

另外,由scanf改为gets后需要在读第一个整数后来个getchar弃掉换行符。发现每次改输入时都容易有这个问题,下次改输入时要注意。gets和scanf搭配时要注意换行符的问题。

另外,这里不要认为字符串每次都会重新读入,就不用memset初始化了;如果新的数据行数比旧的少,残留的数据还是可能影响到的,因为你有检查h+1和h+2而且没有对其是否超过总行数进行判断。

另外,由于数组中其他字符为'',所以在判断是否为结点字符时加入了不等于空字符这一项。(当然,你可以通过给定的是严格的左右范围,来处理空字符这个问题)

吐槽:由于没把freopen注释掉,导致WA了,还以为是加入不等于空字符导致的~~

递归是个好东西,最近几次写的比较多~

终于做完二叉树小专题的了~感觉比做线性表的还快一点啊~

Code:

#include<stdio.h> #include<string.h> #define MAXN 210 void dfs(int h,int left,int right); char tree[MAXN][MAXN]; int main() { //freopen("10562.in","r",stdin); //freopen("10562.out","w",stdout); int t; scanf("%d",&t); getchar();//弃了换行符,不是在while内。。 while(t-->0) { int hs=0; memset(tree,0,sizeof(tree));//不要认为有gets输入了就不memset了,旧数据有可能影响到。 while(gets(tree[hs])!=NULL && tree[hs++][0]!='#'); dfs(0,0,MAXN); printf(" "); } return 0; } void dfs(int h,int left,int right) { printf("("); for(int i=left;i<right;++i) { char c=tree[h][i]; if(c!='-' && c!='|' && c!=' ' && c!='#' && c!='') {//是一结点字符 printf("%c",c); if(tree[h+1][i]=='|') {//有孩子 int x=i-1; while(tree[h+2][x]=='-') x--; //x++; //不需要这句,因为for循环中是<right,不是小于等于 int y=i+1; while(tree[h+2][y]=='-') y++; //y--; dfs(h+3,x,y); } else printf("()");//printf("%c:()",c); } }//for printf(")"); }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐