[算法題] 計算結構體的大小

計算結構體的大小

     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      

View Code

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;
}      

View Code