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教程：資料結構演算法

列印頁面
上一頁
下一頁
廣告