Cprogramming 简明教程

Self-referential Structures in C

What are Self-referential Structures?

自引用结构是 C 中的一种结构数据类型，其中一个或多个元素是它自身类型变量的指针。自引用用户定义类型在 C 编程中极具用处。它们被广泛用于构建复杂而动态的数据结构，例如 linked lists 和 trees 。

在 C 编程中，会在编译时为 array 分配所需内存，并且在运行时不能修改数组大小。自引用结构让你可以通过动态处理大小来模拟数组。

self referential structure

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

Defining a Self-referential Structure

定义自引用结构的常规语法如下：

strut typename{
   type var1;
   type var2;
   ...
   ...
   struct typename *var3;
}

让我们借助以下 example 了解自引用结构的使用方法。我们定义一个名为 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

Examples of Self-referential Structure

Example 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\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

Example 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

Example 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

Creating a Linked List with Self-referential Structure

在上述示例中，动态构建的链表有三个以指针链接的离散元素。我们可以使用 for loop 通过动态分配内存设置所需数量的元素，并将下一个元素的地址存储在前面的节点中。

Example

以下示例显示了如何使用自引用结构创建链表：

#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

Creating a Doubly Linked List with Self-referential Structure

从头开始遍历链表，直到到达 NULL。你还可以构建 doubly linked list ，其中 structure 有两个指针，每个指针都指向前一个和下一个元素的地址。

doubly linked list

这个结构定义应该如下：

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

Creating a Tree with Self-referential Structure

自引用结构也用于构建非线性数据结构，例如 trees 。二叉查找树逻辑上表示为以下图形：

tree

用于实现树的结构定义如下 −

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

要详细学习这些复杂的数据结构，可以访问 DSA 教程 − Data Structures Algorithms