结构体的自引用及相互引用

简述

在用C来实现数据结构以及部分算法时,经常用到结构体,比如实现树以及树的子节点时,就需要该结构体包含自身类型的成员变量。而最近在研究OC的匿名函数实现时,也涉及到了类似需求。同时,两个结构体之间相互引用也经常遇到问题。故简单总结一下C语言结构体的自引用语法。

示例

我们以二叉树的节点为例来看一下自引用:

1
2
3
4
5
struct binary_tree {
int data ; // Data area
struct binary_tree * left;
struct binary_tree * right;
};

在树中,我们需要保存其左右子树,所以需要引用自身。

结构体自引用

不使用typedef

如果不适用typedef,那么此时我们需要使用struct [名称]来调用。
但如果按下面的调用方式

1
2
3
4
5
struct binary_tree {
int data;
struct binary_tree left;
struct binary_tree right;
};

则会导致在分配内存的时候循环分配,此时编译器会计算left和right的成员变量并为之分配内存,从而导致嵌套死循环。

1
2
3
4
5
struct binary_tree {
int data;
struct binary_tree * left;
struct binary_tree * right;
};

所以后者是正确的,left和right在分配时是以结构体指针的形式来分配内存的。而意义上我们就是为了将其指向另一个binary_tree,所以这样是复合逻辑的。

使用typedef

使用typedef可以为结构体设置别名,但是要注意的是,typdef的语法为typedef [原类型] [别名];
所以在结构体声明之前,别名是未定义的。所以我们在内部需要使用其原类型来定义成员变量。

1
2
3
4
5
typedef struct binary_tree {
int data;
struct binary_tree * left;
struct binary_tree * right;
}BinTREE;

结构体相互引用

同文件内

使用不完整类型

通过不完整类型语法来实现相互引用

1
2
3
4
5
6
7
8
9
struct s_a {
int id;
struct s_b *B_Ptr;
};

struct s_b {
int id;
A *A_Ptr;
};

使用前向声明

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct s_a A;
typedef struct s_b B;

struct s_a {
int id;
B *B_Ptr;
};

struct s_b {
int id;
A *A_Ptr;
};

不同文件内

对于不同文件,主要有两点需要注意的。

  • 头文件重复包含问题
  • 结构体的声明问题

而前者通过宏定义解决

1
2
3
4
5
6
#ifndef __FILENAME_H
#define __FILENAME_H

// 代码

#endif

后者通过上述的“前向声明”或“不完整类型即可解决”。