{m-1} \to b_m\). If \(n≥2m\), you are supposed to reverse and merge the shorter one into the longer one to obtain a list like \(a_1 \to a_2 \to b_m \to a_3 \to a_4 \to b_{m-1} ...\) For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.
Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of \(L_1\) and \(L_2\) , plus a positive \(N (\le 10^5)\) which is the total number of nodes given. 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 a positive integer no more than \(10^5\), and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.
Output Specification
For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
Sample Output
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
题目思路
- 静态链表题
- 接收输入链表后，分别遍历两条链，将结点按链表中的顺序存储在容器中
- 按压入两个长链表的结点就压入一个短链表的结点的顺序将结点压入 result 容器
- 按要求输出 result 容器中的结点
- 注意：读题时想当然的以为要将短链表的结点均匀的并入长链表，其实就是题目里的两长一短即可Orz
AC代码
#include<iostream>
#include<vector>
using namespace std;
struct Node{
int address, data, next;
} node[100001];
int main()
{
int head1, head2, n, address, data, next;
scanf("%d%d%d", &head1, &head2, &n);
for (int i = 0; i < n; i++){
scanf("%d%d%d", &address, &data, &next);
node[address] = {address, data, next};
}
vector<Node> list1, list2, result;
for (int p = head1; p != -1; p = node[p].next)
list1.push_back(node[p]);
for (int p = head2; p != -1; p = node[p].next)
list2.push_back(node[p]);
if (list1.size() > list2.size()){
int j = list2.size() - 1;
for (int i = 0; i < list1.size(); i = i + 2){
result.push_back(list1[i]);
if (i + 1 < list1.size()) result.push_back(list1[i+1]);
if (j >= 0) result.push_back(list2[j--]);
}
}
else{
int j = list1.size() - 1;
for (int i = 0; i < list2.size(); i = i + 2){
result.push_back(list2[i]);
if (i + 1 < list2.size()) result.push_back(list2[i+1]);
if (j >= 0) result.push_back(list1[j--]);
}
}
for (int i = 0; i + 1 < result.size(); i++)
printf("%05d %d %05d\n", result[i].address, result[i].data, result[i+1].address);
printf("%05d %d -1\n", result[result.size()-1].address, result[result.size()-1].data);
return 0;
}
7-3 Postfix Expression (25 分)
Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.
Each input file contains one test case. For each case, the first line gives a positive integer \(N (≤ 20)\) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:
data left_child right_child
where data is a string of no more than 10 characters, left_child and right_child are the indices of this node's left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by ?1. The f