Cprogramming 简明教程

Self-referential Structures in C

What are Self-referential Structures?

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

A self-referential structure is a struct data type in C, where one or more of its elements are pointer to variables of its own type. Self-referential user-defined types are of immense use in C programming. They are extensively used to build complex and dynamic data structures such as linked lists and trees.

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

In C programming, an array is allocated the required memory at compile-time and the array size cannot be modified during the runtime. Self-referential structures let you emulate the arrays by handling the size dynamically.

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

File management systems in Operating Systems are built upon dynamically constructed tree structures, which are manipulated by self-referential structures. Self-referential structures are also employed in many complex algorithms.

Defining a Self-referential Structure

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

A general syntax of defining a self-referential structure is as follows −

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

让我们借助以下 example 了解自引用结构的使用方法。我们定义一个名为 mystruct 的结构类型。它有一个整数元素“ a ”，而“ b ”是指向 mystruct 类型的指针本身。

Let us understand how a self-referential structure is used, with the help of the following example. We define a struct type called mystruct. It has an integer element "a" and "b" is the pointer to mystruct type itself.

我们声明了三个 mystruct 类型变量：

We declare three variables of mystruct type −

struct mystruct x = {10, NULL}, y = {20, NULL}, z = {30, NULL};

接下来，我们声明了三个“mystruct”指针并向它们分配了引用 x 、 y 和 z 。

Next, we declare three "mystruct" pointers and assign the references x, y and z to them.

struct mystruct * p1, *p2, *p3;

p1 = &x;
p2 = &y;
p3 = &z;

变量“x”、“y”和“z”是无关的，因为它们将位于随机位置，这与所有元素都位于相邻位置的数组不同。

The variables "x", "y" and "z" are unrelated as they will be located at random locations, unlike the array where all its elements are in adjacent locations.

Examples of Self-referential Structure

Example 1

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

To explicitly establish a link between the three variable, we can store the address of "y" in "x" and the address of "z" in "y". Let us implement this in the following program −

#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;
}

运行代码并检查其输出：

Run the code and check its output −

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() 函数动态分配内存，该内存的地址存储在指针变量中。然后我们建立三个节点之间的链接，如下所示：

Let us refine the above program further. Instead of declaring variables and then storing their address in pointers, we shall use the malloc() function to dynamically allocate memory whose address is stored in pointer variables. We then establish links between the three nodes as shown below −

#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;
}

运行代码并检查其输出：

Run the code and check its output −

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 循环来显示链表，如下例所示：

We can reach the next element in the link from its address stored in the earlier element, as "p1 → b" points to the address of "p2". We can use a while loop to display the linked list, as shown in this example −

#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;
}

运行代码并检查其输出：

Run the code and check its output −

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 通过动态分配内存设置所需数量的元素，并将下一个元素的地址存储在前面的节点中。

In the above examples, the dynamically constructed list has three discrete elements linked with pointers. We can use a for loop to set up required number of elements by allocating memory dynamically, and store the address of next element in the previous node.

Example

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

The following example shows how you can create a linked list using a self-referential structure −

#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;
}

运行代码并检查其输出：

Run the code and check its output −

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 有两个指针，每个指针都指向前一个和下一个元素的地址。

A linked list is traversed from beginning till it reaches NULL. You can also construct a doubly linked list, where the structure has two pointers, each referring to the address of previous and next element.

这个结构定义应该如下：

The struct definition for this purpose should be as below −

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

Creating a Tree with Self-referential Structure

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

Self-referential structures are also used to construct non-linear data structures such as trees. A binary search tree is logically represented by the following figure −

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

The struct definition for the implementing a tree is as follows −

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

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

To learn these complex data structure in detail, you can visit the DSA tutorial − Data Structures Algorithms