[算法题] 计算结构体的大小

计算结构体的大小

     C代码中定义的结构体是一块连续内存,各成员按照定义的顺序依次在其中存放。编译器在完成语法分析后,需要计算它的大小,然后才能正确地为结构体分配空间。为了让结构体的所有成员都能正确、快速地访问,需要字节对齐。

     字节对齐体现为:在成员之间可能增加补齐字节,以调整每个成员的偏移;结构体末尾,也可能增加补充字节。所有补齐字节计入结构体的大小。

     请写一个程序来计算结构体的大小,要考虑字节对齐,同时要支持结构体多层嵌套的情况。

结构体大小的计算

成员在结构体内的偏移必须是它的字节对齐值的倍数。

l 字节对齐值: 

   1)基本类型char、short、int、double的字节对齐值依次为1、2、4、8。

   2)数组的字节对齐值等于它的一个元素的字节对齐值。

   3)结构体的字节对齐值等于它的所有成员的字节对齐值的最大值。

2 大小的计算: 

  1)基本类型char、short、int、double的大小依次为1、2、4、8字节。

  2)数组的大小等于它的一个元素的大小乘以元素个数。

  3)结构体的大小要补齐到它自己的字节对齐值的倍数,补齐字节在末尾。

要求

实现以下接口:

1.开始结构体定义 

2.添加基本类型成员

3.添加数组成员 

4.添加嵌套结构体成员

5.结束嵌套结构体成员

6.完成结构体定义,输出它的大小 

调用者会保证: 

1.结构体的开始和结束是匹配的。 

2.不需要考虑空的结构体。

3.数组只限于一维的基本类型的数组。 

4.最多20层嵌套(嵌套的情况参考示例)

StructSize.h

#ifndef _STRUCT_SIZE_H
#define _STRUCT_SIZE_H

enum Type { CHAR_TYPE, SHORT_TYPE, INT_TYPE, DOUBLE_TYPE };

/*********************** 自定义数据结构 **************************/
typedef struct _tblNode
{
    enum Type type;
    int  size;
}tblNode;

typedef struct _structType
{
    int size;
    int align;
}StructType;
/******************************************************************/


/* 功能:开始定义结构体
 * 输入:无
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int start_struct(void);

/* 功能:添加基本类型成员
 * 输入:类型
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int add_basic_type(enum Type type);

/* 功能:添加数组类型成员
 * 输入:type:数组元素类型
 *    number:数组元素数
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int add_array(enum Type type, unsigned int number);

/* 功能:添加嵌套结构体成员
 * 输入:无
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int begin_nested_struct(void);

/* 功能:结束嵌套结构体成员
 * 输入:无
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int end_nested_struct(void);

/* 功能:完成结构体定义,计算它的大小
 * 输入:无
 * 输出:size:结构体大小
 * 返回:正常返回0,失败返回-1
 */
int finish_struct(unsigned int *size);

#endif

StructSize.cpp

// StructSize.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "StructSize.h"
#include <stdio.h>

#define PRINT_ON 0

tblNode g_tbl[] =
{
    {CHAR_TYPE,   1},
    {SHORT_TYPE,  2},
    {INT_TYPE,    4},
    {DOUBLE_TYPE, 8},
};

StructType g_astResult[20] = {0};
int g_iIndex = 0;

void Print(void)
{
#if PRINT_ON   
    printf("\nsize = %d \t align = %d", g_astResult[g_iIndex].size, g_astResult[g_iIndex].align);
#endif
}

/* 功能:开始定义结构体
 * 输入:无
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int start_struct(void)
{
    g_iIndex = 0;
       g_astResult[g_iIndex].size  = 0;
    g_astResult[g_iIndex].align = 1;
    return 0;
}

/* 功能:添加基本类型成员
 * 输入:类型
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int add_basic_type(enum Type type)
{
    int iSize = 0;
    
    if (type > DOUBLE_TYPE)
    {
        return -1;
    }

    iSize = g_tbl[type].size;
    while (0 != g_astResult[g_iIndex].size % iSize)
    {
        g_astResult[g_iIndex].size++;
    }

    g_astResult[g_iIndex].size += iSize;
    g_astResult[g_iIndex].align = (g_astResult[g_iIndex].align > iSize) ? g_astResult[g_iIndex].align : iSize;

    Print();
    return 0;
}

/* 功能:添加数组类型成员
 * 输入:type:数组元素类型
 *    number:数组元素数
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int add_array(enum Type type, unsigned int number)
{
       int iSize = 0;
    
    if (type > DOUBLE_TYPE)
    {
        return -1;
    }

    iSize = g_tbl[type].size;
    while (0 != g_astResult[g_iIndex].size % iSize)
    {
        g_astResult[g_iIndex].size++;
    }

    g_astResult[g_iIndex].size += iSize * number;
    g_astResult[g_iIndex].align = (g_astResult[g_iIndex].align > iSize) ? g_astResult[g_iIndex].align : iSize;

    Print();
    return 0;
}

/* 功能:添加嵌套结构体成员
 * 输入:无
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int begin_nested_struct(void)
{
    g_iIndex++;
    g_astResult[g_iIndex].size  = 0;
    g_astResult[g_iIndex].align = 1;

    Print();
    return 0;
}

/* 功能:结束嵌套结构体成员
 * 输入:无
 * 输出:无
 * 返回:正常返回0,失败返回-1
 */
int end_nested_struct(void)
{
    int iFatherStructSize = 0;
    int iSonStructSize = 0;
    
       while (g_astResult[g_iIndex].size % g_astResult[g_iIndex].align != 0)
    {
        g_astResult[g_iIndex].size++;
    }
    g_iIndex--;

    if (g_iIndex >= 0)
    {
        iFatherStructSize = g_astResult[g_iIndex].align;
        iSonStructSize    = g_astResult[g_iIndex + 1].align;
        g_astResult[g_iIndex].align = (iFatherStructSize > iSonStructSize) ? iFatherStructSize : iSonStructSize;
        while(g_astResult[g_iIndex].size% g_astResult[g_iIndex].align != 0)
        {
            g_astResult[g_iIndex].size++;
        }
        g_astResult[g_iIndex].size += g_astResult[g_iIndex + 1].size;
    }

    Print();
    return 0;
}

/* 功能:完成结构体定义,计算它的大小
 * 输入:无
 * 输出:size:结构体大小
 * 返回:正常返回0,失败返回-1
 */
int finish_struct(unsigned int *size)
{
    if (0 != g_iIndex)
    {
        return -1;
    }

    while (0 != g_astResult[g_iIndex].size % g_astResult[g_iIndex].align)
    {
        g_astResult[g_iIndex].size++;
    }
    *size = g_astResult[g_iIndex].size;
    
    Print();
    return 0;
}

main.cpp

// StructSize.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "StructSize.h"
#include <iostream>

void CPPUNIT_ASSERT(int iRet)
{
    if (0 == iRet)
    {
        printf("ERROR!\r\n");
        system("pause");
    }
}

void TestCase01()
{
    unsigned int size;
    CPPUNIT_ASSERT(0 == start_struct());
    CPPUNIT_ASSERT(0 == add_basic_type(INT_TYPE));
    CPPUNIT_ASSERT(0 == begin_nested_struct());
    CPPUNIT_ASSERT(0 == add_basic_type(SHORT_TYPE));
    CPPUNIT_ASSERT(0 == begin_nested_struct());
    CPPUNIT_ASSERT(0 == add_basic_type(DOUBLE_TYPE));
    CPPUNIT_ASSERT(0 == end_nested_struct());
    CPPUNIT_ASSERT(0 == end_nested_struct());
    CPPUNIT_ASSERT(0 == add_array(CHAR_TYPE, 2));
    CPPUNIT_ASSERT(0 == finish_struct(&size));
    CPPUNIT_ASSERT(size == 32);
    printf("TestCase01 Ok!\r\n");
}

void TestCase02()
{
    unsigned int size = 0;
    CPPUNIT_ASSERT(0 == start_struct());
    CPPUNIT_ASSERT(0 == add_basic_type(INT_TYPE));
    CPPUNIT_ASSERT(0 == add_basic_type(DOUBLE_TYPE));
    CPPUNIT_ASSERT(0 == add_basic_type(SHORT_TYPE));
    CPPUNIT_ASSERT(0 == add_array(CHAR_TYPE, 3));
    CPPUNIT_ASSERT(0 == finish_struct(&size));
    CPPUNIT_ASSERT(size == 24);
    printf("TestCase02 Ok!\r\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    TestCase01();
    TestCase02();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

java:POI导出excel

POI是一个开源项目,专用于java平台上操作MS OFFICE,企业应用开发中可用它方便导出Excel. 下面是使用示例: 1、maven中先添加依赖项 1 ...

36150
来自专栏wannshan(javaer,RPC)

dubbo序列化过程源码分析

先看下dubbo在serialize层的类设计方案 序列化方案的入口,是接口Serialization的实现类。 /** * Serialization. ...

90190
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

16920
来自专栏小樱的经验随笔

Codeforces 842A Kirill And The Game【暴力,水】

A. Kirill And The Game time limit per test:2 seconds memory limit per test:256 m...

29370
来自专栏yl 成长笔记

二叉搜索树 (BST) 的创建以及遍历

二叉搜索树(Binary Search Tree) : 属于二叉树,其中每个节点都含有一个可以比较的键(如需要可以在键上关联值), 且每个节点的键都大于其左子树...

16630
来自专栏lonelydawn的前端猿区

打造专属插件之Easy Slider Bar

引用 <link rel="stylesheet" type="text/css" href="./index.css"> <div id="slider"><...

33750
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

34340
来自专栏Python攻城狮

Python数据科学(七)- 资料清理(Ⅱ)1.资料转换2.处理时间格式资料3.重塑资料4.学习正则表达式5.实例处理

注意:这里的时间转换后的格式可以根据需要设定,eg:dt.strftime('%Y/%m/%d')

12530
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

61460
来自专栏wym

2013年多校赛 hdu4607

   那么就考虑树上最长距离,树的直径, 如果访问的点大于树的直径就要走回头路,答案即多的数乘2加上原来树的直径

13050

扫码关注云+社区

领取腾讯云代金券