pat 1074（patrol）

pat 1074（patrol）

1.源码如下： #include #include #define maxn 100000 using namespace std; struct Node{//链表节点 int next;//指针 int data;//数据 int address; //节点下标即作为节点的地址 }; int main(){ Node node[maxn]; Node temp; stack st; int i; int startAddr,num,k;//地址，总数，倒转数 int flag = 0;//标志 int control = 0;//控制输出 int tempAddr; scanf("%d %d %d",&startAddr,&num,&k); for(i = 0;i < num ;i++){ scanf("%d",&tempAddr);//先输入节点的地址-->作为数组的下标 scanf("%d %d",&node[tempAddr].data,&node[tempAddr].next);//再输入data 与 next node[tempAddr].address = tempAddr; } tempAddr = startAddr;//暂存值 int count = 0;//实际有效节点的数目 while(startAddr != -1){ startAddr = node[startAddr].next;//下一位 count++; //计数 } startAddr = tempAddr;//回到原来的值 int count1 = 0, count2 = 0;//总计数 倒转计数 while( count - count1 >= k ) { while(count2 < k){//找节点 st.push(node[startAddr]);//压入栈 startAddr = node[startAddr].next;//改变startAddr的值 count2++; } while(!st.empty()) {//栈不为空则输出 temp = st.top(); if(control == 0 && flag == 0 ){ printf("%05d %d ",temp.address,temp.data); } else if(control != 0 && flag == 1){ printf("%05d\n%05d %d ",temp.address,temp.address,temp.data); } else { printf("%05d\n%05d %d ",temp.address,temp.address,temp.data); //换行输出 } st.pop();//栈顶出栈 control++; } flag = 1; count1 += k;//自加K count2 = 0;//重置为0 } if(count - count1 < k){ if(startAddr != -1) printf("%05d\n",startAddr); else printf("-1\n");//最后一个节点 } while(startAddr != -1){//输出剩余的节点 if(node[startAddr].next != -1) printf("%05d %d %05d\n",node[startAddr].address,node[startAddr].data,node[startAddr].next); else { printf("%05d %d ",node[startAddr].address,node[startAddr].data); printf("-1\n"); } startAddr = node[startAddr].next; } } /* 00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 6 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 6 3 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 6 2 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00000 6 3 00000 1 11111 11111 2 22222 22222 3 33333 33333 4 -1 77777 5 55555 55555 6 -1 00000 6 2 00000 1 11111 11111 2 -1 22222 3 33333 33333 4 -1 77777 5 55555 55555 6 -1 注 1.需要考虑很大的测试用例的情况，否则无法通过；所以采用静态链表比较合适（仔细审题，得知节点地址为5位非负整数），这一点对于思路很重要。 2.需要考虑到无效的节点，否则会导致死循环，运行超时.针对这种情况，需要先遍历找出所有有效节点的数目 **/ 2.下面给出一个运行超时的代码 #include #include #define maxn 100000 using namespace std; struct Node{//链表节点 int next;//指针 int address; //地址 int data;//数据 int value;//有效值 }; int main(){ Node node[maxn]; stack st; Node temp;//暂存信息 int i; int addr,num,k;//地址，总数，倒转数 int flag = 0;//标志 int control = 0;//控制输出 int tempAddr; scanf("%d %d %d",&addr,&num,&k); for(i = 0;i < num ;i++){ scanf("%d %d %d",&node[i].address,&node[i].data,&node[i].next); node[i].value = 0; } tempAddr = addr; int count = 0;//找出实际有效的节点数目 i = 0;//重置为0 while(addr != -1){ if(node[i].address == addr){ node[i].value = 1; addr = node[i].next; count++; } i++; i = i % num; } addr = tempAddr;//回到原来的值 // printf("------\n"); int count1 = 0, count2 = 0;//总计数 倒转计数 while( count - count1 >= k ) { while(count2 < k){ for(i = 0;i< num && count2 < k ; i++){ if(node[i].address == addr && node[i].value == 1){ addr = node[i].next;//改变addr的值 st.push(node[i]);//压入栈 count2++;//找到一个节点，加一 node[i].value = 0; break;//跳出循环 } } if(count2==0){//如果遍历一遍仍然没有找到一个地址 printf(" -1\n"); return 0;//直接返回 } } while(!st.empty()) {//栈不为空则输出 temp = st.top(); if(control == 0 && flag == 0 ){ printf("%05d %d ",temp.address,temp.data); } else if(control != 0 && flag == 1){ printf("%05d\n%05d %d ",temp.address,temp.address,temp.data); } else { printf("%05d\n%05d %d ",temp.address,temp.address,temp.data); //换行输出 } st.pop();//栈顶出栈 control++; } flag = 1; count1 += k;//自加K if(count - count1 < k){ if(addr != -1) printf("%05d\n",addr);//如果恰巧是最后一个 else printf("-1\n"); } count2 = 0;//重置为0 } //输出剩余的节点 int remain = count - count1; while(remain--){ for(i = 0;i< num ;i++){ if(node[i].address == addr){ temp = node[i]; //printf("remain = %d\n",remain); if(remain!=0) printf("%05d %d %05d\n",temp.address,temp.data,temp.next); else { printf("%05d %d ",temp.address,temp.data); printf("-1\n"); } addr = node[i].next; break; } } } } /* 00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 6 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 6 3 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00100 6 2 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00000 6 3 00000 1 11111 11111 2 22222 22222 3 33333 33333 4 -1 77777 5 55555 55555 6 -1 00000 6 2 00000 1 11111 11111 2 -1 22222 3 33333 33333 4 -1 77777 5 55555 55555 6 -1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。