自引用结构体

2025 年 5 月 13 日 | 阅读 12 分钟

自指结构是指指向同类型结构的结构。它包含一个或多个最终指向同类型结构的指针。

结构是C和C++中一种用户定义的数据结构类型。
创建结构的主要好处是它可以包含不同的预定义数据类型。
它使用struct关键字和结构名称初始化，后跟此struct关键字。
我们可以在同一个结构中轻松地包含不同的数据类型，如整数值、浮点数、字符等。
它降低了程序的复杂性。
使用单个结构可以将值和数据集保存在一个地方。
在C++编程语言中，放置struct关键字是可选的或非强制的，但在C编程语言中是强制的。
自指结构在创建链表等其他数据结构方面起着非常重要的作用。
在这类结构中，同类型结构的对象的指针指向相同的数据结构，并引用同类型结构的数据类型。
它可以有一个或多个指针作为其成员，指向同类型的结构。
自指结构广泛用于动态数据结构，如树、链表等。

为什么我们需要自指结构？

自指结构在链表、树、图等数据结构中发挥着至关重要的作用。通过使用结构，我们可以轻松高效地实现这些数据结构。对于定义特定节点，结构起着非常重要的作用。在链表中，结构用于存储数据信息和给定链表中下一个节点的地址。主要数据部分是整数类型，链接地址部分是指针类型，它保存下一个节点的地址，以便最终形成链接。

正如我们所知，链表的作用是存储相同类型的数据元素，其中地址位置不是连续的。在这个线性链表中，当前节点保存下一个节点的地址，从而最终形成当前节点和下一个节点之间的链接。

在链表中，我们将定义一个通用结构，该结构包含数据和地址指针，用于携带下一个节点的地址，以便形成多个节点，我们通过节点结构来形成每个节点。

与数组等静态数据结构不同，数组的大小限制了可以轻松插入数组的元素数量，自指结构可以动态地扩展或收缩。

在自指结构中，诸如插入或删除节点之类的操作涉及直接修改指针。

链表

链表是一种有用的数据存储方法，在C编程语言中很容易实现。
有几种链表，包括单向链表、双向链表和二叉树。
每种类型都适合特定的数据存储类型。
这些列表的共同点是，数据项之间的链接由它们本身包含的信息（以指针的形式）定义。
链表与数组明显不同，在数组中，数据项之间的链接是由数组的布局和存储产生的。

在这里，我们将使用链表概念更详细地讨论自指结构。

让我们通过下面的示例更详细地理解自指结构的概念

示例 1：在C编程语言中创建随机自指结构。

// Dummy Self-referential structure in C language 
struct node                                           // Creating a node of structure type contains data 
// part of integer type and a pointer of structure type to 
// hold the address of the next node
{
            int d1 ;                          // data 1 of integer type
            int d2 ;                         // data 2 of integer type
struct node * link ;            // Self referential structure link is pointing the same
// structure of the type node
} ;
Int main()
{
          Struct node obj;                                  // Creating an object of the node type, this object is // consists of three parts one is data 1 and 
// second is of data 2, and third is of link type pointer 
// carries the address of the next node.
          Return 0 ;
}

示例 2：在Python编程语言中创建随机自指结构。

# Dummy Self-referential structure in python language 
class node:                                             # Creating a node that contains data 
# part of and a pointer of node type to 
# hold the address of the next node
    def __init__(self):
        self.data1=0
        self.data2=' '
        self.link=None                    # Self-referential structure link is pointing the same
# structure of the type node

 
if __name__ == '__main__':
    ob=node()                              
# Creating a object of node type, this object is 
# consists of three parts one is data 1 and 
# second is of data 2 and third is of link type pointer 
# carries the address of the next node

自指结构的类型

单链自指结构
多链自指结构

单链自指结构

顾名思义，我们可以轻松预测这些结构包含单个链接，主要是指向同类型结构的唯一一个指针链接。为了更好地理解，我们可以将此概念与单向链表联系起来。

在单向链表中，只有一个指针存储下一个节点的地址，该指针变量本身就是结构节点类型。主要用于当我们想要通过从不同地址获取数据项并将它们全部连接起来，方法是将一个数据项的地址存储到另一个节点的链接部分时。这样，我们就可以通过使用这些连接链轻松地连接所有数据项。

让我们通过一个例子来看看单链自指结构的工作原理

// Single link self-referential structure implementation in C language
#include<stdio.h>
#include<stdlib.h>
struct node
{
	int info ;
	struct node *link ;                  // Self-referential structure link is pointing the same
// structure of the type node
};

struct node *START = NULL ;   // start pointer to control the linked list //
struct node* createnode() ;
void insertatlast() ;          // insert node at last //
void deleteatfirst() ;          // delete node at first //
void viewlist() ;
void insertatfirst() ;
int getlength() ;
int menu() ;
void insertafteranynode() ;
void deleteatlast() ;
void deleteatposition() ;

struct node* createnode()           // create node dynamically //
{
    struct node *n ;
    n = malloc( sizeof(struct node) ) ;
	return ( n ) ;
}
void insertatlast()
{   
    struct node *temp ,*t ;
	temp = createnode() ;
	printf( "Enter the data in node \n " ) ;
	scanf( " %d" , &temp->info ) ;
	temp->link = NULL ;
	if ( START == NULL )
	START = temp ;
	else
	{
		t = START ;
		while ( t->link != NULL )
		{
			t = t->link ;
		}
		t->link = temp ;
	}
}
void deleteatfirst()                  // delete node at first //
{
	if ( START == NULL )
	printf ( "List is empty \n " ) ;
	else
	{
		struct node *q ;
		q = START ;
		START = START->link ;
		free( q ) ;
	}
}
void viewlist()
{   struct node* t ;
	if ( START == NULL )
	{
		printf ( "No List \n " ) ;
	}
	else
	{
		t = START ;
		while ( t != NULL )
		{
			printf ( " %d" , t->info ) ;
			t = t->link ;
		}
	}
}
void insertatfirst()
{  struct node*New ;
   New = createnode() ;
   printf ( "Enter the data in node \n " ) ;
   scanf ( " %d" , &New->info ) ;

   if ( START == NULL )
   START = New ;
   else
   {
   	New->link = START ;
   	START = New ;
   }
}
int getlength()
{
	int count = 0 ;
	struct node* t ;
	if ( START == NULL )
	printf ( "List is empty \n " ) ;
	else
	{
		t =START ;
		while ( t != NULL )
		{
			count = count + 1 ;
			t = t->link ;
		}
	}
	return count ;
}
void insertafteranynode()
{
	int position ;
	struct node* newnode ,*t ;
	if ( START == NULL )
	printf ( "List is empty \n " ) ;
	else
	{
		printf ( "Enter position after which you want to add: \n " ) ;
		scanf ( " %d" , &position ) ;
		if ( position > getlength() )
		{
			printf ( "Wrong position \n " ) ;
			insertafteranynode() ;      // recursion //
			     		
		}
		else
		{
			int i = 1 ;
			newnode = createnode() ;
			printf ( "Enter Data \n " ) ;
			scanf ( " %d" , &newnode->info ) ;
			newnode->link = NULL ;
			if ( START == NULL )
			START = newnode ;
			else
			{
				t = START ;
				while ( i < position )
				{
					t = t->link ;
					i++ ;
				}
				newnode->link = t->link ;
				t->link = newnode ;
			}
		}
	}
}
void deleteatlast()
{
	struct node* t , *q ;
	if ( START == NULL )
	{
		printf ( "List is empty \n " ) ;
    }
	else
	{
		t = START ;
		q = START ;
		while ( t->link != NULL )
		{
			q = t ;
			t = t->link ;
		}
		if ( t == START )
		{
			START == NULL ;
		}
		else
		{
		q->link = NULL ;
		free( t ) ;
    	}
	}
}
void deleteatposition()
{
	struct node *t , *q ;
	int position , i = 1 ;
	t = START ;
	if ( START == NULL)
	{
		printf ( "List is empty \n " ) ;
	}
	else
	{
		printf ( "Enter position after which you want to delete: \n " ) ;
		scanf ( " %d" , &position ) ;
		if ( position > getlength() )
		{
			printf ( "Wrong position \n " ) ;
			deleteatposition() ;                  // recursion //
			     		
		}
		else
		{
			while ( i < position )
			{   
			    q = t ;
				t = t->link ;
				i++ ;
	        }
	    if ( t == START )
	    {
	       START == NULL ;	
		}
		else
		{
	        q->link = t->link ;
	        free( t ) ;
        }
		}
	}
}
int menu()
{
	int ch ;
	printf ( " \t \t \t 1.ADD NODE LAST IN LINK \n " ) ;
	printf ( " \t \t \t 2.ADD NODE AT FIRST IN LINK \n " ) ;
	printf ( " \t \t \t 3.VIEW LIST IN LINK \n " ) ;
	printf ( " \t \t \t 4.DELETE NODE AT FIRST IN LINK \n " ) ;
            printf( " \t \t \t 5. TO SEE THE LENGTH OF LIST \n " ) ;
            printf ( " \t \t \t 6. INSERT NODE IN BETWEEN \n " ) ;
            printf ( " \t \t \t 7.DELETE NODE AT LAST IN LINK \n " ) ;
            printf ( " \t \t \t 8.DELETE NODE AT SPECIFIC POSITION IN LINK \n " ) ;
	printf ( " \t \t \t 9.EXIT \n " ) ;
	printf ( "ENTER THE CHOICE \n " ) ;
	scanf ( " %d" , &ch ) ;
	return( ch ) ;
}
void main()
{   int k ;
	while ( 1 )
	{
	switch ( menu() )
	{
	 	case 1 :
			insertatlast() ;
			break ;
		case 2 :
			insertatfirst() ;
			break ;
		case 3 :
			viewlist() ;
			break ;
		case 4 :
			deleteatfirst() ;
			break ;
		case 5 :
		    k = getlength() ;
		    printf ( "THE LENGTH OF THE LIST IS %d \n " , k ) ;
		    break ;
		case 6 :
			insertafteranynode() ;
			break ;
		case 7 :
			deleteatlast() ;
			break ;
		case 8 :
			deleteatposition() ;
			break ;
		case 9 :
			exit( 0 ) ;
			break ;
	    default :
	    	printf ( " Not available \n " ) ;
}
}
}

上述程序的输出为

# Single link self-referential structure implementation in Python language
class node:
	def __init__(self):
		self.d1=0
		self.d2=0
		self.link=None

if __name__ == '__main__':
	obj1=node()                               # Node1

	                                                      # Initialization
	obj1.link = None
	obj1.d1 = 17
	obj1.d2 = 14

	obj2=node()                                 # Node2

	                                                       # Initialization
	obj2.link = None
	obj2.d1 = 36
	obj2.d2 = 24

	                                                        # Linking obj1 and obj2
	obj1.link = obj2

	                                                         # Accessing data members of obj2 using obj1
	print(obj1.link.d1)
	print(obj1.link.d2)

上述程序的输出为

36

24

多链自指结构

顾名思义，我们可以轻松预测这类结构包含多个链接，这里我们将使用指向同类型结构的两个指针链接，为了更好地理解，我们可以将此概念与双向链表联系起来。

在双向链表中，两个单指针存储下一个节点和上一个节点的地址，该指针变量本身就是结构节点类型。主要用于当我们想要通过从不同地址获取数据项并将它们全部连接起来，方法是将一个数据项的地址存储到另一个节点的链接部分时。这样，我们就可以通过使用这些连接链轻松地连接所有数据项。

让我们通过一个例子来看看多链自指结构的工作原理

// Multiple link self-referential structure implementation in C language
#include<stdio.h>
#include<stdlib.h>
struct node
{
	int info ;
	struct node *prev ;            // Self-referential structure link is pointing the same
// structure of the type node but to the previous node

	struct node *next;                // Self-referential structure link is pointing the same
// structure of the type node but to the next node

} ;

struct node * START = NULL ;            // Start pointer of the list and initially it must be null, // represents that no node is present
void insertnodeatfirst() ;
void deleteatfirst() ;
void viewlist() ;
int menu() ;
void insertnodeatfirst()                              // Inserting the node at first
{
	struct node * newnode ;
	newnode = malloc( sizeof( struct node ) ) ;
	printf ( "Enter Data: \n " ) ;
	scanf ( " %d" , &newnode->info ) ;
	newnode->prev = NULL ;
	newnode->next = NULL ;
	if ( START == NULL )
	START = newnode ; 
	else
	{
		START->prev = newnode ;
		newnode->next = START ; 
		START = newnode ;
	}
}
void deleteatfirst()                     // deleting the first node
{
	struct node * temp ;
	if ( START == NULL )
	printf ( "List is empty \n " ) ;
	else
	{
	temp = START ;
	START = START->next ;
	START->prev = NULL ;
	free( temp ) ;
    }
}
void viewlist()                               // displaying all the nodes in the list
{
	struct node * t ;
	if ( START == NULL )
	printf ( "List is empty \n " ) ;
	else
	{
		t = START ;
		while ( t != NULL )
		{
			printf ( " %d \n " , t->info ) ;
			t = t->next ;		
		}
	}
}
int menu()
{   int n ;
	printf ( " \t \t \t 1. VIEW LIST \n " ) ;
	printf ( " \t \t \t 2. INSERT AT FIRST IN LIST \n " ) ;
	printf ( " \t \t \t 3. DELETE AT FIRST IN LIST \n " ) ;
	printf ( " \t \t \t 4. EXIT \n " ) ;
    printf ( "ENTER YOUR CHOICE \n " ) ;
    scanf ( " %d" , &n ) ;
    return ( n ) ;
}
int main()
{  
   while ( 1 )
    {
	switch ( menu() )
	{
		case 1 :
			viewlist() ;
			break ;
		case 2 :
			insertnodeatfirst() ;
			break ;
		case 3 :
			deleteatfirst() ;
			break ;
		case 4 :
		    exit ( 1 ) ;
			break ;	
		default :
			printf ( " NOT AVAILABLE \n " ) ;
	}
}
}

上述程序的输出为

# Multiple link self-referential structure implementation in Python language
class node:
  def __init__(self):
    self.data = 0
    self.prev = None
    self.next = None

if __name__ == '__main__':
  obj1=node()                                              # Node1

                                                                     # Initialization
  obj1.prev = None
  obj1.next = None
  obj1.data = 15

  obj2=node()                                             # Node2

                                                                     # Initialization
  obj2.prev = None
  obj2.next = None
  obj2.data = 20

  obj3 = node()                                             # Node3

                                                                       # Initialization
  obj3.prev = None
  obj3.next = None
  obj3.data = 25

                                                                       # Forward links
  obj1.next = obj2
  obj2.next = obj3

                                                                        # Backward links
  obj2.prev = obj1
  obj3.prev = obj2

                                                                       # Accessing data of obj1, obj2 and obj3 by obj1
  print(obj1.data , end='\t')
  print(obj1.next.data , end='\t')
  print(obj1.next.next.data)

                                                                      # Accessing data of obj1, obj2 and obj3 by obj2
  print(obj2.prev.data , end='\t')
  print(obj2.data , end='\t')
  print(obj2.next.data)

                                                                      # Accessing data of obj1, obj2 and obj3 by obj3
  print(obj3.prev.prev.data , end='\t')
  print(obj3.prev.data , end='\t')
  print(obj3.data)

上述程序的输出为

15            20            25
15            20            25
15            20            25

下一个主题C语言中break和continue的区别

自引用结构体

为什么我们需要自指结构？

链表

自指结构的类型

单链自指结构

多链自指结构

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

自引用结构体

为什么我们需要自指结构？

链表

自指结构的类型

单链自指结构

多链自指结构

相关帖子

C 语言演示 fork() 和 pipe() 的程序

C 语言中的大 O 记法

C 语言 memcmp()

C 语言加法程序

C 语言 Fread() 函数

C 语言中相加 2 个字符串

C 语言中的存储类别是什么

C 语言猜单词游戏程序

C 语言矩阵计算器

C 语言递归类型

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器