Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218Sample Output:
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
此题的关键是如何表示这一个个结点。由于结点的地址和next都是一个具体的5位数，因此不能用链表这种“抽象的”方法来表示“具体的地址”。所以我们需要模拟实际的内存，办法就是用一个数组，数组下标为当前结点的地址，而数组的值就是该结点的next指针的地址。有了这种表示方法之后，后面就容易下手了。从输入中记录头结点的地址，然后一个个结点的next信息放入前面说的数组中，放好之后，实际上就构建好了输入的链表。
下一步是链表反转，按照陈姥姥的说法，最直观的做法是从头结点开始，把下一个结点的next设为上一个结点的地址，全部设置好之后再从头结点开始遍历输出。
而我的做法是用stl的vector，从头结点开始一个一个压入vector中，然后每K个元素进行逆序输出。
姥姥的习题课里说我的做法应该是超时的，而我确实是超了，但是！！！我后来改用了姥姥说的方法，还是超时！！！后来结果表明，超时的原因是我用了C++的cin和cout，改成scanf和printf后就好了。同时在我自己的vector做法里改成scanf和printf后也过了，(⊙﹏⊙)b....
这个题目有几个坑需要注意：
1.K是否能整除N关系到最后一段的输出
2.输入会有多余节点...这个坑我表示实在太大了...后来看了别人的文章才发现会有这个问题。多余节点就是不在链表里的结点，如果不去除，输出肯定不对
3.有一个test case的N很大，这时就要用C的scanf和printf才能不超时。
1 #include<iostream> 2 #include<iomanip> 3 #include<vector> 4 using namespace std; 5 6 struct node{ 7 int data; 8 int addr; 9 }; 10 11 int main() 12 { 13 int N=100000; 14 15 int *data = new int [N]; 16 int *next = new int [N]; 17 18 int begin_address=0; 19 int Nnodes=1; 20 int K=1; 21 22 cin >> begin_address; 23 cin >> Nnodes; 24 cin >> K; 25 int *out = new int [K]; 26 27 int address_in,data_in,next_in; 28 node temp_node; 29 for (int i=0;i<Nnodes;i++) 30 { 31 scanf("%d",&address_in); 32 scanf("%d",&data[address_in]); 33 scanf("%d",&next[address_in]); 34 } 35 36 vector<node> vec1; 37 while (begin_address != -1) 38 { 39 temp_node.data=data[begin_address]; 40 temp_node.addr=begin_address; 41 vec1.push_back(temp_node); 42 begin_address = next[begin_address]; 43 } 44 45 //开始反遍历********************************** 46 Nnodes=vec1.size(); 47 int segments=Nnodes/K;//分成了这么多段 48 int last=Nnodes%K;//最后一段有几个元素，如果=0，说明刚好分完。否则最后一段不用改 49 for (int i=0;i<segments;i++) 50 { 51 for (int j=0;j<K;j++) 52 if (j!=K-1) 53 printf("%05d %d %05d\n", vec1[K*(i+1)-1-j].addr, vec1[K*(i+1)-1-j].data, vec1[K*(i+1)-1-j-1].addr); 54 else 55 if (i==segments-1)//最后一段，分情况了 56 { 57 if (last) 58 { 59 printf("%05d %d %05d\n", vec1[K*(i+1)-1-j].addr, vec1[K*(i+1)-1-j].data, vec1[K*(i+1)].addr); 60 for (int i=K*segments;i<Nnodes;i++) 61 { 62 if (i==Nnodes-1) 63 cout << setw(5) << setfill(‘0‘) << vec1[i].addr << ‘ ‘ << vec1[i].data << ‘ ‘ << -1 << endl; 64 else 65 printf("%05d %d %05d\n",vec1[i].addr, vec1[i].data, vec1[i+1].addr); 66 } 67 } 68 else 69 { 70 cout << setw(5) << setfill(‘0‘) << vec1[K*(i+1)-1-j].addr << ‘ ‘ << vec1[K*(i+1)-1-j].data << ‘ ‘ << -1 << endl; 71 } 72 } 73 else 74 cout << setw(5) << setfill(‘0‘) << vec1[K*(i+1)-1-j].addr << ‘ ‘ << vec1[K*(i+1)-1-j].data << ‘ ‘ << setw(5) << setfill(‘0‘) << vec1[K*(i+2)-1].addr << endl; 75 } 76 77 return 0; 78 }
设计函数求一元多项式的导数。
输入格式：以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式：以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是0，但是表示为“0 0”。
输入样例：3 4 -5 2 6 1 -2 0输出样例：
12 3 -10 1 6 0
本题比较简单，直接输入一项，接着输出一项就可以。但是，本题我有个地方没考虑到。就是如果输入3 0,那么应该输出0 0.
还有个地方值得学习，就是输出的最后不能带有空格。一开始我是想判断什么时候是最后一组输入，发现这样做太麻烦，而且容易出错。最好的办法是先弄第一组输入，输出a_b，后面每组输出_a_b，而不是每一组都输出a_b_
1 #include<iostream> 2 #include<stdio.h> 3 #include<vector> 4 using namespace std; 5 6 int main() 7 { 8 int coeff,expon; 9 scanf("%d %d",&coeff, &expon); 10 11 if (expon == 0) 12 printf("%d %d",0,0); 13 else 14 printf("%d %d",coeff*expon,expon-1); 15 16 while (cin >> coeff >> expon) 17 { 18 if (expon) 19 printf(" %d %d",coeff*expon,expon-1); 20 } 21 22 return 0; 23 }
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。
输入格式说明：
输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、\以及运算数，不同对象（运算数、运算符号）之间以空格分隔。
输出格式说明：
输出前缀表达式的运算结果，精确到小数点后1位，或错误信息“ERROR”。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
+ + 2 * 3 - 7 4 / 8 4 |
13.0 |
| 2 |
/ -25 + * - 2 3 4 / 8 4 |
12.5 |
| 3 |
/ 5 + * - 2 3 4 / 8 2 |
ERROR |
| 4 |
+10.23 |
10.2 |
本题我用的方法是堆栈stack。首先判断第一个输入的元素是什么，如果是数字，则判断是否还有下一个输入，如果有，则出错，输出ERROR，如果没有，则输出前一个数字，程序结束。
如果第一个输入是操作符，则压到堆栈里。当输入数字时，判断栈顶是什么。如果是操作符，再将刚才的数字压入堆栈。如果是数字，则判断再下一个元素是什么，如果是操作符，则可以进行运算了，如果是数字，则ERROR。这一步循环进行到栈顶是操作符或者栈为空。输入完之后，判断堆栈剩下什么。如果是空，或者栈顶是操作符，则ERROR。如果不止一个元素，也ERROR。其余情况输出剩下的那一个数字。
关于这题运算数和运算符的表示，我用了一个结构体，包含了一个string域和double域。输入的时候都输入到string，如果判断到是数字，则用atof把string转换成double型。
1 #include<iostream> 2 #include<iomanip> 3 #include<stack> 4 #include<string> 5 using namespace std; 6 7 struct term 8 { 9 int flag; //0时为运算符，1时为运算数 10 string _operator; 11 double operand; 12 }; 13 14 int main() 15 { 16 term in,temp_operand; 17 stack<term> sta; 18 19 string in_temp; 20 cin >> in_temp; 21 22 if ( !(in_temp == "+" || in_temp == "-" || in_temp == "*" ||in_temp == "/" ) )//第一个输入是数字 23 { 24 in.flag=1;in.operand=atof(in_temp.c_str()); 25 sta.push(in); 26 if (cin >> in_temp) 27 {cout << "ERROR" << endl;return 0;} 28 else 29 {cout << fixed << setprecision(1) << sta.top().operand << endl;return 0;} 30 } 31 else 32 { 33 in.flag=0;in._operator=in_temp; 34 sta.push(in); 35 } 36 37 while (cin >> in_temp) 38 { 39 if ( !(in_temp == "+" || in_temp == "-" || in_temp == "*" ||in_temp == "/" ) ) 40 { 41 in.flag=1;in.operand=atof(in_temp.c_str()); 42 } 43 else 44 { 45 in.flag=0;in._operator=in_temp; 46 } 47 48 if ( in.flag ) //数字，要判断top是什么 49 { 50 if (sta.empty()) 51 {cout << "ERROR" << endl;return 0;} 52 else 53 if ( !sta.top().flag ) //是运算符 54 { 55 sta.push(in); 56 } 57 else 58 { 59 while (!sta.empty() && sta.top().flag) //输入数字，且top也是数字 60 { 61 temp_operand = sta.top(); 62 sta.pop(); 63 if (sta.empty()) 64 {cout << "ERROR" << endl;return 0;} 65 else 66 if ( !sta.top().flag ) 67 { 68 if (sta.top()._operator == "+") 69 temp_operand.operand += in.operand; 70 else if (sta.top()._operator == "-") 71 temp_operand.operand -= in.operand; 72 else if (sta.top()._operator == "*") 73 temp_operand.operand *= in.operand; 74 else 75 if (in.operand == 0) 76 {cout << "ERROR" << endl;return 0;} 77 else 78 temp_operand.operand /= in.operand; 79 sta.pop(); 80 in = temp_operand; 81 } 82 else 83 {cout << "ERROR" << endl;return 0;} 84 85 } 86 sta.push(in); 87 } 88 } 89 else //符号，直接push进去 90 sta.push(in); 91 } 92 93 if (sta.empty()) 94 {cout << "ERROR" << endl;return 0;} 95 else 96 if (!sta.top().flag) 97 cout << "ERROR" << endl; 98 else 99 if (sta.size()==1) 100 cout << fixed << setprecision(1) << sta.top().operand << endl; 101 else 102 cout << "ERROR" << endl; 103 104 return 0; 105 }
原文：http://www.cnblogs.com/xian-ye/p/5193968.html