ACM PUK 题目解答源码100题

#include<iostream.h> #include<math.h> typedef int elemtype; struct snode{ elemtype data; long num; snode *next; }; struct listlk{ snode *head; }; void initlist(listlk &hl) {hl.head=NULL;} void insertlist(listlk &hl,elemtype item,long n) { snode *newp=new snode; snode *p=hl.head; newp->data=item; newp->num=n; newp->next=NULL; if(p!=NULL){while(p->next!=NULL)p=p->next;p->next=newp;} else hl.head=newp; } int emptylist(listlk &hl) {return hl.head==NULL;} int lenthlist(listlk &hl) {snode *p=hl.head;int i=0; while(p!=NULL){ i++;p=p->next; } return i; } void outputlist(listlk &hl) {snode *p=hl.head; while(p!=NULL){ cout<<p->data<<' '<<p->num<<endl; p=p->next; } } void process(listlk &a,listlk &b,int n) { snode *nowp,*p=a.head,*q=b.head,*t=b.head; int i,j,max,temp,premax=500,kong=0,delay=0; long usednum; long *previous,*current,*next; previous=new long[n];current=new long[n];next=new long[n]; nowp=p;usednum=p->num; for(i=0;i<n;i++) { previous[i]=current[i]=nowp->data;usednum--; if(usednum==0) { if(nowp!=NULL)nowp=nowp->next; if(nowp==NULL){for(i=0;i<n;i++)next[i]=current[i];kong=4;break;} usednum=nowp->num; } } for(i=0;i<n;i++) { if(kong==4)break; next[i]=nowp->data;usednum--; if(usednum==0) { if(nowp!=NULL)nowp=nowp->next; if(nowp==NULL){kong=3;break;} usednum=nowp->num; } } delay=0;if(kong==0)kong=1; while(kong!=0) { if(delay==1){ if(q->data!=0){insertlist(b,0,0);q=q->next;} q->num =q->num+usednum-usednum%n; usednum=usednum%n+2*n; //cout<<usednum<<endl; delay=0; for(i=0;i<n;i++){ current[i]=previous[i]=nowp->data; usednum--; } premax=0; for(i=0;i<n;i++) { next[i]=nowp->data;usednum--; //cout<<next[i]<<endl; if(usednum==0) { nowp=nowp->next; if(nowp==NULL){kong=3;break;} usednum=nowp->num; } } } else {if(delay!=0)delay--; else if (usednum>8*n) {delay=3;} max=abs(current[0]-current[1]);temp=abs(current[0]-next[0]); if (temp>max)max=temp;temp=abs(current[0]-next[1]); if (temp>max)max=temp; temp=abs(current[0]-previous[0]); if (temp>max)max=temp;temp=abs(current[0]-previous[1]); if (temp>max)max=temp; if(premax==max)q->num++; else{insertlist(b,max,1);premax=max;if(q==t)q=b.head;else q=q->next;} //cout<<max<<' '<<q->num<<endl;getchar(); for(i=1;i<n-1;i++) { max=abs(current[i]-current[i+1]);temp=abs(current[i]-next[i]); if (temp>max)max=temp; temp=abs(current[i]-current[i-1]); if (temp>max)max=temp; temp=abs(current[i]-previous[i]); if (temp>max)max=temp; temp=abs(current[i]-next[i-1]); if (temp>max)max=temp; temp=abs(current[i]-next[i+1]); if (temp>max)max=temp; temp=abs(current[i]-previous[i+1]); if (temp>max)max=temp; temp=abs(current[i]-previous[i-1]); if (temp>max)max=temp; if(max==premax){q->num++;} else {insertlist(b,max,1);q=q->next;} premax=max; //cout<<max<<' '<<q->num<<endl;getchar(); } max=abs(current[n-2]-current[n-1]);temp=abs(current[n-1]-next[n-1]); if (temp>max)max=temp; temp=abs(current[n-1]-next[n-2]); if (temp>max)max=temp; temp=abs(current[n-1]-previous[n-2]); if (temp>max)max=temp; temp=abs(current[n-1]-previous[n-1]); if (temp>max)max=temp; if(max==premax)q->num++; else {insertlist(b,max,1);q=q->next;} premax=max; //cout<<max<<' '<<q->num<<endl;getchar(); if(kong==4)break; for(i=0;i<n;i++) { previous[i]=current[i];current[i]=next[i]; } if(kong==3){kong=2;for(i=0;i<n;i++)next[i]=current[i];} else if(kong==2)kong=0; else for(i=0;i<n;i++) { next[i]=nowp->data;usednum--; if(usednum==0) { nowp=nowp->next; if(nowp==NULL){kong=3;break;} usednum=nowp->num; } } } } delete previous,current,next; } void clearlist(listlk &hl) {snode *p=hl.head,*q; while(p!=NULL){ q=p; p=p->next; delete q; } hl.head=NULL; } int main() { listlk edge,out; int n,i,j,k=0;; cin>>n;cout<<n<<endl; while(n!=0) { initlist(edge);initlist(out); while(cin>>i>>j) { if(!i&&!j)break; insertlist(edge,i,j); } process(edge,out,n); outputlist(out); cout<<k<<' '<<k<<endl; clearlist(out); clearlist(edge); cin>>n;cout<<n<<endl; } return 0; }