结构体(struct)
【题目背景】
在 C++ 等高级语言中，除了 int 和 float 等基本类型外，通常还可以自定义结 构体类型。在本题当中，你需要模拟一种类似 C++ 的高级语言的结构体定义方式，并 计算出相应的内存占用等信息。
【题目描述】
在这种语言中，基本类型共有 4 种:byte，short，int，long，分别占据 1, 2, 4, 8 字节的空间。
定义一个结构体类. 型. 时，需要给出类. 型. 名. 和成. 员. ，其中每个成员需要按顺序给出类. 型. 和名. 称. 。类型可以为基本类型，也可以为先. 前. 定. 义. 过. 的结构体类型。注意，定义结构 体类. 型. 时不会定义具体元素，即不占用内存。
1 2 3 4 5 6
定义一个元. 素. 时，需要给出元素的类. 型. 和名. 称. 。元素将按照以下规则占据内存: • 元素内的所有成员将按照定. 义. 时. 给. 出. 的. 顺. 序. 在内存中排布，对于类型为结构体的
成员同理。
• 为了保证内存访问的效率，元素的地址占用需要满足对. 齐. 规. 则. ，即任何类型的大.
小. 和该类型元素在内存中的起. 始. 地. 址. 均应对齐到该类型对齐要求的整. 数. 倍. 。具体 而言:
– 对于基本类型:对齐要求等于其占据空间大小，如 int 类型需要对齐到 4 字节，其余同理。
– 对于结构体类型:对齐要求等于其成员的对齐要求的最. 大. 值. ，如一个含有 int 和 short 的结构体类型需要对齐到 4 字节。
以下是一个例子(以 C++ 语言的格式书写):
struct d {
short a;
int b;
short c;
};
d e;该代码定义了结构体类型 d 与元素 e。元素 e 包含三个成员 e.a, e.b, e.c，分 别占据第 0 ∼ 1，4 ∼ 7，8 ∼ 9 字节的地址。由于类型d需要对齐到 4 字节，因此e占 据了第 0 ∼ 11 字节的地址，大小为 12 字节。
你需要处理 n 次操作，每次操作为以下四种之一:
定义一个结构体类型。具体而言，给定正整数 k 与字符串 s, t1, n1, . . . , tk, nk，其 中 k 表示该类型的成员数量，s 表示该类型的类型名，t1, t2, . . . , tk 按顺序分别表 示每个成员的类型，n1, n2, . . . , nk 按顺序分别表示每个成员的名称。你需要输出 该结构体类型的大小和对齐要求，用一个空格分隔。
定义一个元素，具体而言，给定字符串 t，n 分别表示该元素的类型与名称。所 有被定义的元素将按顺序，从内存地址为 0 开始依次排开，并需要满足地址对齐 规则。你需要输出新定义的元素的起始地址。
访问某个元素。具体而言，给定字符串 s，表示所访问的元素。与 C++ 等语言 相同，采用 . 来访问结构体类型的成员。如 a.b.c，表示 a 是一个已定义的元 素，它是一个结构体类型，有一个名称为 b 的成员，它也是一个结构体类型，有 一个名称为 c 的成员。你需要输出如上被访问的最. 内. 层. 元素的起始地址。
访问某个内存地址。具体而言，给定非负整数 addr，表示所访问的地址，你需要 判断是否存在一个基. 本. 类. 型. 的元素占据了该地址。若是，则按操作 3 中的访问元 素格式输出该元素;否则输出 ERR。
【输入格式】
从文件 struct.in 中读入数据。
第 1 行:一个正整数 n，表示操作的数量。 接下来若干行，依次描述每个操作，每行第一个正整数 op 表示操作类型:
若 op = 1，首先输入一个字符串 s 与一个正整数 k，表示类型名与成员数量，接 下来 k 行每行输入两个字符串 ti，ni，依次表示每个成员的类型与名称。
若 op = 2，输入两个字符串 t，n，表示该元素的类型与名称。
若 op = 3，输入一个字符串 s，表示所访问的元素。
若 op = 4，输入一个非负整数 addr，表示所访问的地址。
【输出格式】
输出到文件 struct.out 中。
输出 n 行，依次表示每个操作的输出结果，输出要求如题目描述中所述。
【样例 1 输入】
5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10
【样例 1 输出】
8 4
16 8
0 4
x.bb
【样例 1 解释】
结构体类型 a 中，int 类型的成员 aa 占据第 0 ∼ 3 字节地址，short 类型的成员 ab 占据第 4 ∼ 5 字节地址。又由于其对齐要求为 4 字节，可得其大小为 8 字节。由此 可同理计算出结构体类型 b 的大小为 16 字节，对齐要求为 8 字节。
【样例 2】
见选手目录下的 struct/struct2.in 与 struct/struct2.ans。
【样例 2 解释】
第二个操作 4 中，访问的内存地址恰好在为了地址对齐而留下的“洞”里，因此没
有基本类型元素占据它。
【样例 3】
见选手目录下的 struct/struct3.in 与 struct/struct3.ans。
【数据范围】
对于全部数据，满足1 ≤ n ≤ 100，1 ≤ k ≤ 100，0 ≤ addr ≤ 1018。
所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 10 个字符的小 写字母组成，且都不是 byte,short,int,long(即不与基本类型重名)。
所有定义的结构体类型名和元素名称互不相同，同一结构体内成员名称互不相同。 但不同的结构体可能有相同的成员名称，某结构体内的成员名称也可能与定义的结构体 或元素名称相同。
保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。
保证任意结构体大小及定义的元素占据的最高内存地址均不超过 1018。
特殊性质 A:没有操作 1;
特殊性质 B:只有一个操作 1;
特殊性质 C:所有操作 1 中给出的成员类型均为基本类型; 特殊性质 D:基本类型只有 long。
【提示】
对于结构体类型的对齐要求和大小，形式化的定义方式如下:
• 设该结构体内有 k 个成员，其大小分别为 s1, ..., sk，对齐要求分别为 a1, ..., ak; • 则该结构体的对齐要求为 a = max{a1 , ..., ak };
• 再设这些成员排布时的地. 址. 偏. 移. 量. 分别为 o1, ..., ok，则:
– o1 = 0;
– 对于i = 2,...,k，oi 为满足oi−1 +si−1 ≤ oi 且ai 整除oi 的最小值; – 则该结构体的大小s为满足ok +sk ≤ s且a整除s的最小值;
对于定义元素时的内存排布，形式化的定义方式如下:
• 设第 i 个被定义的元素大小为 si，对齐要求为 ai，起始地址为 bi;
• 则b1 = 0，对于2 ≤ i，bi 为满足bi−1 +si−1 ≤ bi 且ai 整除bi 的最小值