问一下一个关于程序的问题。

C++语言 码拜 4年前 (2016-01-31) 207次浏览
最近写程序碰到了一个问题,不知道为什么。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[300005];
struct Node{
int v,rev,ans;
Node *ch[2],*fa;
Node(int val,Node* fa);
void Pushdown();
void Pushup();
}*Null;
Node::Node(int val,Node* fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
printf(“Reset:%d %d %d %d\n”,ch[0],fat,fat==Null,Null);
ans=v=val;
rev=0;
}
void Node::Pushdown(){
if(rev){
if(ch[0]!=Null)ch[0]->rev^=1;
if(ch[1]!=Null)ch[1]->rev^=1;
swap(ch[0],ch[1]);
rev=0;
}
}
void Node::Pushup(){
ans=v;
if(ch[0]!=Null)ans^=ch[0]->v;
if(ch[1]!=Null)ans^=ch[1]->v;
}
int Isroot(Node *x){
return (x->fa->ch[0]!=x)&&(x->fa->ch[1]!=x);
}
void Prepare(Node *x){
if(!Isroot(x))Prepare(x->fa);
x->Pushdown();
}
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
void Splay(Node *x){
Prepare(x);
while(!Isroot(x)){
Node *y=x->fa,*z=y->fa;
if(z==Null){Rotate(x,y->ch[0]==x);}
else {
if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
else {Rotate(x,1);Rotate(x,0);}
}
}
}
struct LCT{
Node *root[300005];
void Access(Node *x);
void Makeroot(Node *x);
void Link(Node *u,Node *v);
void Cut(Node *u,Node *v);
LCT(){
for(int i=1;i<=n;i++)root[i]=new Node(a[i],Null);
}
}*lct;
void LCT::Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){
printf(“AC:%d %d %d %d %d %d NC:%d\n”,x->v,x->ch[0]->v,x->ch[0]->ch[0],x->ch[1]->v,x->fa->v,x->fa->fa,y);
printf(“FUJIA:%d %d | %d %d %d %d\n”,x->v,x==x->ch[0]->ch[0],x->ch[0]->ch[0],x->ch[0]->ch[0]->v,x->ch[0]->ch[0]->ch[0]->v,x->ch[0]->ch[0]->ch[0]);
Splay(x);
printf(“AC:%d %d %d %d %d NC:%d\n”,x->v,x->ch[0]->v,x->ch[1]->v,x->fa->v,x->fa->fa,y);
x->ch[1]=y;
printf(“FUJIA:%d %d | %d %d %d %d\n”,x->v,x==x->ch[0]->ch[0],x->ch[0]->ch[0],x->ch[0]->ch[0]->v,x->ch[0]->ch[0]->ch[0]->v,x->ch[0]->ch[0]->ch[0]);
x->Pushup();
}
}
void LCT::Makeroot(Node *x){
Access(x);Splay(x);x->rev^=1;
}
void LCT::Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}
void LCT::Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}
void PrtTree(Node *x){
if(x->ch[0]!=Null){putchar(“”L””);PrtTree(x->ch[0]);}
printf(“Pt:%d\n”,x->v);
if(x->ch[1]!=Null){putchar(“”R””);PrtTree(x->ch[1]);}
}
Node* Find(Node *u){
puts(“Fir”);
PrtTree(u);
lct->Access(u);
puts(“Sec”);
//PrtTree(u);
Splay(u);
puts(“Thi”);
//PrtTree(u);
//printf(“%d %d %d\n”,u->v,u->ch[0]->v,u->ch[1]->v);
while(u->ch[0]!=Null){u=u->ch[0];}
return u;
}
Node* ToLct(int x){
printf(“This:%d\n”,x);
return lct->root[x];
}
int Xor(int u,int v){
Node *x=ToLct(u),*y=ToLct(v);
lct->Makeroot(x);
lct->Access(y);
Splay(y);
return y->ans;
}
void Add(int u,int v){
Node *x=ToLct(u),*y=ToLct(v);
lct->Link(x,y);
}
void Delete(int u,int v){
Node *x=ToLct(u),*y=ToLct(v);
lct->Cut(x,y);
}
void Change(int u,int v){
Node *x=ToLct(u);
lct->Access(x);
Splay(x);
x->v=v;
x->Pushup();
}
int main(){
freopen(“1474.in”,”r”,stdin);
freopen(“1474.out”,”w”,stdout);
scanf(“%d %d”,&n,&m);
Null=new Node(0,Null);
Null->fa=Null;
Null->ch[0]=Null;
Null->ch[1]=Null;
for(int i=1;i<=n;i++){
scanf(“%d”,&a[i]);
}
lct=new LCT();
//lct->Access(ToLct(2));
//Null->fa=Null;
//printf(“%d %d %d\n”,lct->root[2]->v,Null->fa,Null);
for(int i=1;i<=m;i++){
int opt,u,v;
scanf(“%d %d %d”,&opt,&u,&v);
if(opt==0){
printf(“%d\n”,Xor(u,v));
}
if(opt==1){
if(Find(ToLct(u))!=Find(ToLct(v))){
Add(u,v);
}
}
if(opt==2){
if(Find(ToLct(u))==Find(ToLct(v))){
puts(“YES”);
//Delete(u,v);
}
}
if(opt==3){
Change(u,v);
}
PrtTree(lct->root[1]);
putchar(“”\n””);
PrtTree(lct->root[2]);
putchar(“”\n””);
PrtTree(lct->root[3]);
putchar(“”\n””);
}
return 0;
}
这个程序会在以下的数据中死循环,好像是指针在LCT::Access()中循环了。讨教高手怎么处理。谢谢
3 3
1 2 4
1 3 2
1 3 1
2 2 2
解决方案:40分
一直在Find函数中while(u->ch[0]!=Null){u=u->ch[0];}这里出不来,LZ本人单步调试分析原因
解决方案:30分
别轻易放弃…………假如有时间建议你找出问题
解决方案:30分
代码功能归根结底不是别人帮本人看或讲解或注释出来的;而是被本人静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。
提醒:再牛×的老师也无法代替学生本人领悟和上厕所!
单步调试和设断点调试(VS IDE中编译连接通过以后,按F10或F11键单步执行,按Shift+F11退出当前函数;在某行按F9设断点后按F5执行停在该断点处。)是程序员必须掌握的技能之一。

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明问一下一个关于程序的问题。
喜欢 (0)
[1034331897@qq.com]
分享 (0)