C 语言中的自引用结构
什么是自引用结构?
自引用结构是 C 语言中的一种结构体数据类型，其一个或多个元素是指向自身类型变量的指针。自引用的用户定义类型在 C 语言编程中用途广泛。它们被广泛用于构建复杂且动态的数据结构，例如链表和树。
在 C 语言编程中，数组在编译时分配所需的内存，并且数组大小在运行时无法修改。自引用结构允许您通过动态处理大小来模拟数组。
操作系统中的文件管理系统建立在动态构建的树形结构之上，这些树形结构由自引用结构操作。许多复杂的算法也使用自引用结构。
定义自引用结构
定义自引用结构的通用语法如下:
strut typename{
type var1;
type var2;
...
...
struct typename *var3;
}
让我们借助以下示例来理解如何使用自引用结构。我们定义一个名为 mystruct 的结构体类型。它包含一个整数元素"a"，而"b"是指向 mystruct 类型本身的指针。
我们声明三个 mystruct 类型的变量 -
struct mystruct x = {10, NULL}, y = {20, NULL}, z = {30, NULL};
接下来，我们声明三个"mystruct"指针，并将引用x、y和z赋值给它们。
struct mystruct * p1, *p2, *p3; p1 = &x; p2 = &y; p3 = &z;
变量"x"、"y"和"z"互不相关，因为它们位于随机位置，这与数组不同，数组的所有元素都位于相邻位置。
自引用结构示例
示例 1
为了明确建立三个变量之间的链接，我们可以将"y"的地址存储在"x"中，将"z"的地址存储在"y"中。让我们在以下程序中实现这一点 -
#include <stdio.h>
struct mystruct{
int a;
struct mystruct *b;
};
int main(){
struct mystruct x = {10, NULL}, y = {20, NULL}, z = {30, NULL};
struct mystruct * p1, *p2, *p3;
p1 = &x;
p2 = &y;
p3 = &z;
x.b = p2;
y.b = p3;
printf("Address of x: %d a: %d Address of next: %d
", p1, x.a, x.b);
printf("Address of y: %d a: %d Address of next: %d
", p2, y.a, y.b);
printf("Address of z: %d a: %d Address of next: %d
", p3, z.a, z.b);
return 0;
}
输出
运行代码并检查其输出 −
Address of x: 659042000 a: 10 Address of next: 659042016 Address of y: 659042016 a: 20 Address of next: 659042032 Address of z: 659042032 a: 30 Address of next: 0
示例 2
让我们进一步完善上述程序。我们不再声明变量并将其地址存储在指针中，而是使用 malloc() 函数动态分配内存，并将地址存储在指针变量中。然后，我们在三个节点之间建立链接，如下所示 -
#include <stdio.h>
#include <stdlib.h>
struct mystruct{
int a;
struct mystruct *b;
};
int main(){
struct mystruct *p1, *p2, *p3;
p1 = (struct mystruct *)malloc(sizeof(struct mystruct));
p2 = (struct mystruct *)malloc(sizeof(struct mystruct));
p3 = (struct mystruct *)malloc(sizeof(struct mystruct));
p1 -> a = 10; p1->b=NULL;
p2 -> a = 20; p2->b=NULL;
p3 -> a =30; p3->b=NULL;
p1 -> b = p2;
p2 -> b = p3;
printf("Add of x: %d a: %d add of next: %d
", p1, p1->a, p1->b);
printf("add of y: %d a: %d add of next: %d
", p2, p2->a, p2->b);
printf("add of z: %d a: %d add of next: %d
", p3, p3->a, p3->b);
return 0;
}
输出
运行代码并检查其输出 −
Add of x: 10032160 a: 10 add of next: 10032192 add of y: 10032192 a: 20 add of next: 10032224 add of z: 10032224 a: 30 add of next: 0
示例 3
我们可以通过存储在前一个元素中的地址，到达链接中的下一个元素，因为"p1 b"指向"p2"的地址。我们可以使用 while 循环来显示链表，如下例所示 -
#include <stdio.h>
#include <stdlib.h>
struct mystruct{
int a;
struct mystruct *b;
};
int main(){
struct mystruct *p1, *p2, *p3;
p1=(struct mystruct *)malloc(sizeof(struct mystruct));
p2=(struct mystruct *)malloc(sizeof(struct mystruct));
p3=(struct mystruct *)malloc(sizeof(struct mystruct));
p1 -> a = 10; p1 -> b = NULL;
p2 -> a = 20; p2 -> b = NULL;
p3 -> a = 30; p3 -> b = NULL;
p1 -> b = p2;
p2 -> b = p3;
while (p1 != NULL){
printf("Add of current: %d a: %d add of next: %d
", p1, p1->a, p1->b);
p1 = p1 -> b;
}
return 0;
}
输出
运行代码并检查其输出 −
Add of current: 10032160 a: 10 add of next: 10032192 Add of current: 10032192 a: 20 add of next: 10032224 Add of current: 10032224 a: 30 add of next: 0
创建具有自引用结构的链表
在上述示例中，动态构造的列表包含三个通过指针链接的离散元素。我们可以使用for循环，通过动态分配内存来设置所需数量的元素，并将下一个元素的地址存储在前一个节点中。
示例
以下示例展示了如何使用自引用结构创建链表 -
#include <stdio.h>
#include <stdlib.h>
struct mystruct{
int a;
struct mystruct *b;
};
int main(){
struct mystruct *p1, *p2, *start;
int i;
p1 = (struct mystruct *)malloc(sizeof(struct mystruct));
p1 -> a = 10; p1 -> b = NULL;
start = p1;
for(i = 1; i <= 5; i++){
p2 = (struct mystruct *)malloc(sizeof(struct mystruct));
p2 -> a = i*2;
p2 -> b = NULL;
p1 -> b = p2;
p1 = p2;
}
p1 = start;
while(p1 != NULL){
printf("Add of current: %d a: %d add of next: %d
", p1, p1 -> a, p1 -> b);
p1 = p1 -> b;
}
return 0;
}
输出
运行代码并检查其输出 −
Add of current: 11408416 a: 10 add of next: 11408448 Add of current: 11408448 a: 2 add of next: 11408480 Add of current: 11408480 a: 4 add of next: 11408512 Add of current: 11408512 a: 6 add of next: 11408544 Add of current: 11408544 a: 8 add of next: 11408576 Add of current: 11408576 a: 10 add of next: 0
创建具有自引用结构的双向链表
链表从头开始遍历，直到到达 NULL。您也可以构建一个双向链表，其中结构包含两个指针，分别指向前一个元素和下一个元素的地址。
用于此目的的结构体定义应如下所示 -
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
创建具有自引用结构的树
自引用结构也用于构建非线性数据结构，例如树。二叉搜索树的逻辑表示如下图所示 -
实现树的结构体定义如下 -
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
要详细了解这些复杂的数据结构，您可以访问 DSA 教程 - 数据结构算法
