C语言对其方式--struct数据结构必学

一、什么是对齐，以及为什么要对齐：

1. 现代计算机中内存空间都是按照byte划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但实际情况是在访问特定变量的时候经常在特定的内存地址访问，这就需要各类型数据按照一定的规则在空间上排列，而不是顺序的一个接一个的排放，这就是对齐。

2. 对齐的作用和原因：各个硬件平台对存储空间的处理上有很大的不同。一些平台对某些特定类型的数据只能从某些特定地址开始存取。其他平台可能没有这种情况， 但是最常见的是如果不按照适合其平台的要求对数据存放进行对齐，会在存取效率上带来损失。比如有些平台每次读都是从偶地址开始，如果一个int型（假设为 32位）如果存放在偶地址开始的地方，那么一个读周期就可以读出，而如果存放在奇地址开始的地方，就可能会需要2个读周期，并对两次读出的结果的高低 字节进行拼凑才能得到该int数据。显然在读取效率上下降很多。这也是空间和时间的博弈。

二、对齐的实现

通常，我们写程序的时候，不需要考虑对齐问题。编译器会替我们选择适合目标平台的对齐策略。当然，我们也可以通知给编译器传递预编译指令而改变对指定数据的对齐方法。
但是，正因为我们一般不需要关心这个问题，所以因为编辑器对数据存放做了对齐，而我们不了解的话，常常会对一些问题感到迷惑。最常见的就是struct数据结构的sizeof结果，出乎意料。为此，我们需要对对齐算法所了解。

相同的对齐方式下 ，结构体内部数据 定义的顺序不同 ，结构体整体占据内存空间也 不同 ，如下：
设结构体如下定义：
struct A
{
     int      a;
     char    b;
     short c;
};
结构体A中包含了4字节长度的int一个，1字节长度的char一个和2字节长度的short型数据一个。所以A用到的空间应该是7字节。但是因为编译器要对数据成员在空间上进行对齐。所以使用sizeof(strcut A)值为 8 。
现在把该结构体调整成员变量的顺序。
struct B
{
     char    b;
      int      a;
      short c;
};
这时候同样是总共7个字节的变量，但是sizeof(struct B)的值却是 12 。

下面我们使用预编译指令#progma pack (value)来告诉编译器，使用我们指定的对齐值来取代缺省的。
#progma pack (2)
struct C
{
      char b;
     int      a;
     short c;
};
#progma pack ()
sizeof(struct C)值是 8 。

修改对齐值为1：
#progma pack (1)
struct D
{
      char b;
      int      a;
      short c;
};
#progma pack ()
sizeof(struct D)值为 7 。

对于char型数据，其自身对齐值为1，对于short型为2，对于int,float,double类型，其自身对齐值为4，单位字节。  

这里面有四个概念值：
1.数据类型自身的对齐值：就是上面交代的基本数据类型的自身对齐值。
2.指定对齐值：#progma pack (value)时的指定对齐值value。
3.结构体或者类的自身对齐值：其数据成员中自身对齐值最大的那个值。
4.数据成员、结构体和类的有效对齐值：自身对齐值和指定对齐值中小的那个值。
有了这些值，我们就可以很方便的来讨论具体数据结构的成员和其自身的对齐方式。有效对齐值N是最终用来决定数据存放地址方式的值，最重要。有效对齐N，就是表示“对齐在N上”，也就是说该数据的"存放起始地址%N=0". 而数据结构中的数据变量都是按定义的先后顺序来排放的。第一个数据变量的起始地址就是数据结构的起始地址。结构体的成员变量要对齐排放，结构体本身也要根据自身的有效对齐值圆整(就是结构体成员变量占用总长度需要是对结构体有效对齐值的整数倍，结合下面例子理解)。这样就不能理解上面的几个例子的值了。
例子分析：
分析例子B；
struct B
{
      char b;
      int      a;
     short c;
};
假设B从地址空间 0x0000 开始排放。该例子中没有定义指定对齐值，在笔者环境下，该值 默认为4 。

第一个成员变量b的自身对齐值是 1 ，比指定或者默认指定对齐值 4 小，所以其有效对齐值为 1 ，所以其存放地址 0x0000 符合 0x0000%1=0 .

第二个成员变量a，其自身对齐值为 4 ，所以有效对齐值也为 4 ，所以只能存放在起始地址为 0x0004 到 0x0007 这四个连续的字节空间中，符合 0x0004%4=0 , 且紧靠第一个变量。

第三个变量c,自身对齐值为 2 ，所以有效对齐值也是 2 ，可以存放在 0x0008 到 0x0009 这两个字节空间中，符合 0x0008%2=0 。所以从0x0000到0x0009存放的都是B内容。

再看数据结构 B的自身对齐值 为其变量中最大对齐值( 这里是b ）所以就是4，所以结构体的有效对齐值也是4。根据结构体圆整的要求，0x0009到0x0000=10字节 ，（10＋2）％4＝0 。所以 0x0000A 到 0x000B 也为结构体B所占用。故B从0x0000到0x000B共有12个字节, sizeof(struct B)=12 ;

-----------------------

对齐方式（变量存放的起始地址相对于结构的起始地址的偏移量）
Char
偏移量必须为sizeof(char)即1的倍数
int
偏移量必须为sizeof(int)即4的倍数
float
偏移量必须为sizeof(float)即4的倍数
double
偏移量必须为sizeof(double)即8的倍数
Short
偏移量必须为sizeof(short)即2的倍数
各成员变量在存放的时候根据在结构中出现的顺序依次申请空间，同时按照上面的对齐方式调整位置，空缺的字节VC会自动填充。同时VC为了确保结构的大小为结构的字节边界数（即该结构中占用最大空间的类型所占用的字节数）的倍数，所以在为最后一个成员变量申请空间后，还会根据需要自动填充空缺的字节。
下面用前面的例子来说明VC到底怎么样来存放结构的。

struct MyStruct
{
double dda1;
char dda;
int type
}；

为上面的结构分配空间的时候，VC根据成员变量出现的顺序和对齐方式，先为第一个成员dda1分配空间，其起始地址跟结构的起始地址相同（刚好偏移量0刚好为sizeof(double)的倍数），该成员变量占用sizeof(double)=8个字节；接下来为第二个成员dda分配空间，这时下一个可以分配的地址对于结构的起始地址的偏移量为8，是sizeof(char)的倍数，所以把dda存放在偏移量为8的地方满足对齐方式，该成员变量占用 sizeof(char)=1个字节；接下来为第三个成员type分配空间，这时下一个可以分配的地址对于结构的起始地址的偏移量为9，不是sizeof (int)=4的倍数，为了满足对齐方式对偏移量的约束问题，VC自动填充3个字节（这三个字节没有放什么东西），这时下一个可以分配的地址对于结构的起始地址的偏移量为12，刚好是sizeof(int)=4的倍数，所以把type存放在偏移量为12的地方，该成员变量占用sizeof(int)=4个字节；这时整个结构的成员变量已经都分配了空间，总的占用的空间大小为：8+1+3+4=16，刚好为结构的字节边界数（即结构中占用最大空间的类型所占用的字节数sizeof(double)=8）的倍数，所以没有空缺的字节需要填充。所以整个结构的大小为：sizeof(MyStruct)=8+1+ 3+4=16，其中有3个字节是VC自动填充的，没有放任何有意义的东西。
下面再举个例子，交换一下上面的MyStruct的成员变量的位置，使它变成下面的情况：

struct MyStruct
{
char dda;
double dda1;  
int type
}；

这个结构占用的空间为多大呢？在VC6.0环境下，可以得到sizeof(MyStruc)为24。结合上面提到的分配空间的一些原则，分析下VC怎么样为上面的结构分配空间的。（简单说明）

struct MyStruct
{
char dda;      //偏移量为0，满足对齐方式，dda占用1个字节；
double dda1;//下一个可用的地址的偏移量为1，不是sizeof(double)=8
                    //的倍数，需要补足7个字节才能使偏移量变为8（满足对齐
                   //方式），因此VC自动填充7个字节，dda1存放在偏移量为8
                  //的地址上，它占用8个字节。
int type；    //下一个可用的地址的偏移量为16，是sizeof(int)=4的倍
           //数，满足int的对齐方式，所以不需要VC自动填充，type存
           //放在偏移量为16的地址上，它占用4个字节。
}；//所有成员变量都分配了空间，空间总的大小为1+7+8+4=20，不是结构
   //的节边界数（即结构中占用最大空间的类型所占用的字节数sizeof
   //(double)=8）的倍数，所以需要填充4个字节，以满足结构的大小为
   //sizeof(double)=8的倍数。

所以该结构总的大小为：sizeof(MyStruc)为1+7+8+4+4=24。其中总的有7+4=11个字节是VC自动填充的，没有放任何有意义的东西。
VC对结构的存储的特殊处理确实提高CPU存储变量的速度，但是有时候也带来了一些麻烦，我们也屏蔽掉变量默认的对齐方式，自己可以设定变量的对齐方式。

VC 中提供了#pragma pack(n)来设定变量以n字节对齐方式。n字节对齐就是说变量存放的起始地址的偏移量有两种情况：第一、如果n大于等于该变量所占用的字节数，那么偏移量必须满足默认的对齐方式，第二、如果n小于该变量的类型所占用的字节数，那么偏移量为n的倍数，不用满足默认的对齐方式。结构的总大小也有个约束条件，分下面两种情况：如果n大于所有成员变量类型所占用的字节数，那么结构的总大小必须为占用空间最大的变量占用的空间数的倍数；
否则必须为n的倍数。下面举例说明其用法。

#pragma pack(push) //保存对齐状态
#pragma pack(4)//设定为4字节对齐
struct test
{
char m1;
double m4;
int m3;
};
#pragma pack(pop)//恢复对齐状态

以上结构的大小为16，下面分析其存储情况，首先为m1分配空间，其偏移量为0，满足我们自己设定的对齐方式（4字节对齐），m1占用1个字节。接着开始为 m4分配空间，这时其偏移量为1，需要补足3个字节，这样使偏移量满足为n=4的倍数（因为sizeof(double)大于n）,m4占用8个字节。接着为m3分配空间，这时其偏移量为12，满足为4的倍数，m3占用4个字节。这时已经为所有成员变量分配了空间，共分配了16个字节，满足为n的倍数。如果把上面的#pragma pack(4)改为#pragma pack(16)，那么我们可以得到结构的大小为24。（请读者自己分析）

============================相关案例===========================

Intel、微软等公司曾经出过一道类似的面试题：

#include <iostream.h>
#pragma pack(8)
struct example1
{
short a;
long b;
};
struct example2
{
char c;
example1 struct1;
short e;
};
#pragma pack()
int main(int argc, char* argv[])
{
example2 struct2;
cout << sizeof(example1) << endl;
cout << sizeof(example2) << endl;
cout << (unsigned int)(&struct2.struct1) - (unsigned int)(&struct2) << endl;
return 0;
}

问程序的输入结果是什么？
答案是：
8
16
4


  面试题的解答
至此，我们可以对Intel、微软的面试题进行全面的解答。
程序中第2 行#pragma pack (8)虽然指定了对界为8，但是由于struct example1 中的成员最大
size 为4（long 变量size 为4），故struct example1 仍然按4 字节对界，struct example1 的size
为8，即第18 行的输出结果；
struct example2 中包含了struct example1，其本身包含的简单数据成员的最大size 为2（short
变量e），但是因为其包含了struct example1，而struct example1 中的最大成员size 为4，struct
example2 也应以4 对界，#pragma pack (8)中指定的对界对struct example2 也不起作用，故19 行的
输出结果为16；
由于struct example2 中的成员以4 为单位对界，故其char 变量c 后应补充3 个空，其后才是
成员struct1 的内存空间，20 行的输出结果为4。

union A
{
int a[5];
char b;
double c;
};

struct B
{
int n;
A a;
char c[10];
}

sizeof(B) = ?

答案：

union A: 
{ 
int a[5]; //20 
char b; //1 
double c; //8 
}

我想的是union中变量共用内存，应以最长的为准，那就是20。可实际不然，sizeof(A)=24，

A中各变量的默认内存对齐方式，必须以最长的double 8字节对齐，故应该是sizeof(A)=24。

struct B
{
int n; // 4字节
A a; // 24字节
char c[10]; // 10字节
};

实际占用38字节，但由于A是8字节对齐的，所以int n和char c[10]也需要8字节对齐，总共8+24+16=48