C语言中的联合

1 C语言中的Union又称为联合,联合的声明语法与结构的语法一样,但是语义差别很大,联合用不同的字段,引用相同的内存块

2 为什么使用联合?

在一些上下文中,联合的使用能够减小分配空间的总量。 一种应用的情况是,我们事先知道对一个数据结构中的两个不同字段的使用是互斥的(同时只会有一个字段是有意义的),那么将这两个字段声明为联合的一部分,而不是结构的一部分,会减小分配空间的总量。

比如说,我们要实现一个二叉树的数据结构,每个叶子节点都有两个double类型的数据值,而每个内部节点都有指向两个孩子的指针,但是没有数据,如果用Struct做如下声明:

1
2
3
4
5
struct node_s{
struct node_s *left; //8字节
struct node_s *right; //8字节
double data[2]; //2*8=16字节
}

那么,每个结点需要32个字节,而且每个节点都要浪费16个字节,因为如果是内部节点,data字段无意义,如果是叶子节点,left,right指针字段无意义。

如果我们用Union声明:

1
2
3
4
5
6
7
union node_u{
struct{
union node_u *left;
union node_u *right;
}internal;
double data[2];
}

注:一个联合的总的大小等于它最大字段的大小

那么,每个结点就只需要16个字节,相当于系统分配16个字节的内存空间,如果是内部节点,将16字节的第一个8字节作为left指针的存放区域,第二个8字节内存作为right指针的存放区域。如果是叶子节点,则将16个字节的内存空间分配给data数组,实现了内存的共享。

那么问题来了?如果确定一个给定的结点到底是叶子节点还是内部节点呢,通常的方法是引进一个枚举类型,定义这个联合中可能的不同选择,然后再将枚举类型与union放进一个struct里面:如下:

1
2
3
4
5
6
7
8
9
10
11
12
typedef enum{N_LEAF,N_INTERNAL} nodetype_t;

struct{
nodetype_t type; //标签字段 4字节
union node_u{ //联合字段 //16字节
struct{
union node_u *left;
union node_u *right;
}internal;
double data[2];
}info;
}

这个结构总共需要24个字节(type和node_u之间要填充4个字节,这里不展开,或者你当成是20字节就好啦,比之前32个字节少了12个字节呢)。这还只是两个字段共享一块内存区域的情况,如果是更多的字段共享一块内存区域,节省的空间会更加可观。

注:可能有同学会觉得是否可用布尔类型实现标签字段,如果是只有两个字段是可以的,当多个字段,还是得用枚举类型。

(未学过数据结构同学这段可以不看)关于互斥的例子,我记得大二上的时候在讲中序线索二叉树的遍历时就遇到过这种情况,中序线索二叉树每个结点有两个字段leftChild和rightChild。对于某一个结点,当左子女存在时,leftChild指向左子女结点,不存在时,leftChild指向该结点的前驱结点,当右子女存在时,rightChild指向右子女结点,不存在时,rightChild指向的是该节点的后继结点。那么如何区别leftChild和rightChild是子女还是前驱结点或后继结点,当时书里给出的是给两个标志位ltag和rtag,标志位为0时表示子女,为1时表示前驱结点或后序结点。

该二叉树结点的结构大概如下,这段好像没有明显用到联合,但我觉得跟联合的思想很像,就是用一个标志位,根据标志位的不同,判断同一个内存段里面的数据代表的是不同的含义。(或者说,如果去解读这段内存?)

leftChild ltag data rtag rightChild

下面是一个用联合实现的数据类型转换的函数。

联合里面用两个字段,一个是整数字段d,一个是无符号整数字段u,所以内存会分配给union字段8个字节也就是32个位,这时参数为num传进来,num的值为-1,执行temp.d=num=-1,此时分配的内存块里的数据情况是32个1,也就是0xffff ffff(有符号数表示为-1),随后执行return temp.u

temp.u的内存块里的数据是多少?同样也是0xffff ffff,因为它和temp.d共享内存块,所以程序就会以无符号数解读0xffff ffff,返回值4294967295,实现了数据类型的转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
unsigned int double2bits(int num){ //输入整数d,
union{
int d; //union各成员共享一段空间
unsigned int u;
}temp;
temp.d=num;
return temp.u; 返回d的无符号值
};
int main()
{
cout<<"Hello World"<<endl;
cout<<double2bits(-1);
return 0;
}
文章作者: luo
文章链接: https://luo41.top/2021/05/05/C语言中的联合/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 luo's Blog