问题 C: 结构体（struct）

---

【题目描述】

【题目背景】 在C++等高级语言中，除了int和float等基本类型外，通常还可以自定义结构体类型。在本题当中，你需要模拟一种类似C++的高级语言的结构体定义方式，并计算出相应的内存占用等信息。 【题目描述】 在这种语言中，基本类型共有4种：byte，short，int，long，分别占据1,2,4,8 字节的空间。 定义一个结构体类型时，需要给出类型名和成员，其中每个成员需要按顺序给出类型和名称，类型可以为基本类型，也可以为先前定义过的结构体类型。注意，定义结构体类型时不会定义具体元素，即不占用内存。 定义一个元素时，需要给出元素的类型和名称。元素将按照以下规则占据内存： •元素内的所有成员将按照定义时给出的顺序在内存中排布，对于类型为结构体的成员同理。 •为了保证内存访问的效率，元素的地址占用需要满足对齐规则。即任何类型的大小和该类型元素在内存中的起始地址均对齐到该类型对齐要求的整数倍。具体而言： –对于基本类型：对齐要求等于其占据空间大小，如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次操作，每次操作为以下四种之一： 1.定义一个结构体类型。具体而言，给定正整数k与字符串s,t1,n1,...,tk,nk，其中k表示该类型的成员数量，s表示该类型的类型名，t1,t2,...,tk按顺序分别表示每个成员的类型，n1,n2,...,nk按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求，用一个空格分隔。 2.定义一个元素，具体而言，给定字符串t，n分别表示该元素的类型与名称。所有被定义的元素将按顺序，从内存地址为0开始依次排开，并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。 3.访问某个元素。具体而言，给定字符串s，表示所访问的元素。与C++等语言相同，采用 . 来访问结构体类型的成员。如a.b.c，表示a是一个已定义的元素，它是一个结构体类型，有一个名称为b的成员，它也是一个结构体类型，有一个名称为c的成员。你需要输出如上被访问的最内层元素的起始地址。 4.访问某个内存地址。具体而言，给定非负整数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≤10¹⁸。 所有定义的结构体类型名、成员名称和定义的元素名称均由不超过10个字符的小写字母组成，且都不是byte,short,int,long（即不与基本类型重名）。 所有定义的结构体类型名和元素名称互不相同，同一结构体内成员名称互不相同。但不同的结构体可能有相同的成员名称，某结构体内的成员名称也可能与定义的结构体或元素名称相同。 保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。 保证任意结构体大小及定义的元素占据的最高内存地址均不超过10¹⁸。   特殊性质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为满足o_i-1+s_i-1≤oi且ai整除oi的最小值； –则该结构体的大小s为满足o_k+s_k≤s且a整除s的最小值； 对于定义元素时的内存排布，形式化的定义方式如下： •设第i个被定义的元素大小为si，对齐要求为ai，起始地址为bi； •则b1=0，对于2≤i，bi为满足b_i-1+s_i-1≤bi且ai整除bi的最小值。                  

【输入】

第1行：一个正整数n，表示操作的数量。

接下来若干行，依次描述每个操作，每行第一个正整数op表示操作类型：

•若op=1，首先输入一个字符串s与一个正整数k，表示类型名与成员数量，接下来k行每行输入两个字符串ti，ni，依次表示每个成员的类型与名称。

•若op=2，输入两个字符串t，n，表示该元素的类型与名称。

•若op=3，输入一个字符串s，表示所访问的元素。

•若op=4，输入一个非负整数addr，表示所访问的地址。

【输出】

输出n行，依次表示每个操作的输出结果，输出要求如题目描述中所述。

题目类型~

CSP-S2023 

咻咻~

提交答案 状态 返回作业