C语言中的自引用结构体

上一页
下一页

什么是自引用结构体？

自引用结构体是C语言中的一种结构体数据类型，其中一个或多个元素是指向其自身类型变量的指针。自引用用户定义类型在C编程中具有极其重要的作用。它们被广泛用于构建复杂的动态数据结构，例如链表和树。

在C编程中，数组在编译时分配所需的内存，并且数组大小在运行时无法修改。自引用结构体允许您通过动态处理大小来模拟数组。

Self-referential Structure

操作系统的文件管理系统建立在动态构建的树结构之上，这些结构由自引用结构体操作。自引用结构体也用于许多复杂的算法中。

定义自引用结构体

定义自引用结构体的通用语法如下：

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”是相互独立的，因为它们将位于随机位置，这与所有元素都在相邻位置的数组不同。

Elements Adjacent Locations

自引用结构体的示例

示例1

为了明确建立三个变量之间的链接，我们可以在“x”中存储“y”的地址，在“y”中存储“z”的地址。让我们在下面的程序中实现这一点：

#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\n", p1, x.a, x.b);
   printf("Address of y: %d a: %d Address of next: %d\n", p2, y.a, y.b);
   printf("Address of z: %d a: %d Address of next: %d\n", 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\n", p1, p1->a, p1->b);
   printf("add of y: %d a: %d add of next: %d\n", p2, p2->a, p2->b);
   printf("add of z: %d a: %d add of next: %d\n", 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\n", 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\n", 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。您还可以构建一个双向链表，其中结构体有两个指针，每个指针都指向前一个和下一个元素的地址。

Doubly linked list

为此目的的结构体定义如下：

struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};

使用自引用结构体创建树

自引用结构体也用于构建非线性数据结构，例如树。二叉搜索树由下图逻辑表示：

Tree

实现树的结构体定义如下：

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

要详细了解这些复杂的数据结构，您可以访问DSA教程：数据结构算法

打印页面
上一页
下一页
广告