链接列表，结构的创建

发布于 2025-02-10 21:37:29 字数 126 浏览 3 评论 0原文

当未完全定义结构时，我们如何能够在结构节点内创建类型节点的指针。

struct node
    {
        int data;
        node* next;
    }

原文

How are we able to create a pointer of type node inside the struct node when the struct is not fully defined.

struct node
    {
        int data;
        node* next;
    }

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风轻花落早 2025-02-17 21:37:30

要了解这一点，您需要知道计算机不了解诸如结构之类的高级软件概念化。

实际上，当将代码编译为组装时，都不会产生诸如结构之类的东西。取而代之的是，从C编译器的解析/语义分析中，生成了一个明确的结构化代码，您的CPU将通过通过路由表中的不同晶体管中的位置来实现其目的。

typedef struct {
    int x; 
} entity_t;

int main(){
    entity_t entity; 
    entity.x = 34; 
}

汇编代码：简而言之，在主函数的堆栈上发生了一个具有4位权重的静态内存位置的价值分配。

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 34
        mov     eax, 0
        pop     rbp
        ret

这些路由表具有2个规则分类类别，可以通过这些类别是： RAM/CPU缓存的静态/动态位置的内存地址和存储在该内存地址中的值（位）。

由此，丹尼斯·里奇（Dennis Ritchie）提出了子例程作为抽象层的概念，以使我们 管理汇编指针中记忆的所有复杂性。

现在，像递归一样复杂的概念在计算中不可能实现，因为该定义告诉我们，即使未完全定义了递归函数，也必须自称为自身。

面对这个问题，C处理指针的递归，因为指针是具有内存地址的实体，与要应用递归的类型或功能的地址完全不同。因此，对于像链接列表这样的递归数据结构，只能通过指针具有指向同一类型的另一个内存位置的链接。

简而言之，这类型的数据结构可以通过指针进行递归，因为指针本身与包含类型完全不同。。

To understand this, you need to know that the computer doesn't understand high-level software conceptualizations like structs.

In fact, when compiling your code to assembly, no such thing as a structure is ever generated. Instead, from the parsing/semantic analysis of the C compiler, a clearly structured code is generated, where your CPU will fulfill its purpose through the addressing of bits in the different transistors through routing tables.

typedef struct {
    int x; 
} entity_t;

int main(){
    entity_t entity; 
    entity.x = 34; 
}

Assembly Code: Simply, a value assignment to a static memory location with a 4-bit weight occurs on the stack of the main function.

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 34
        mov     eax, 0
        pop     rbp
        ret

These routing tables have 2 rule classification categories to have a data transmission format through the buses, these categories are: The memory address of a static/dynamic location of the RAM/CPU Cache and the value stored in that memory address (bits).

From this, Dennis Ritchie proposed the concept of subroutines as abstraction layers to spare us all the complexity involved in managing memory from assembler pointers.

Now, concepts as complex as recursion, in the first instance would be impossible to implement in computation because the definition tells us that a recursive function must call itself even if it is not completely defined.

Faced with this problem, C handles recursion from pointers, since pointers are entities with a memory address totally different from the address of the type or function to which you want to apply recursion. For this reason, for a recursive data structure like a linked list, it is only possible to have a link to another memory location of the same type through pointers.

In short, recursion in this type of data structure is possible through pointers because the pointer itself is a completely different memory address than the containing type.

回复收藏 0 原文

看海 2025-02-17 21:37:30

远期声明

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

forward declarations

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

回复收藏 0 原文

唔猫 2025-02-17 21:37:29

简短的答案是因为标准是这样说的。

较长的答案是，指针的大小（无论如何是指向数据的指针）总是相同的，因此编译器知道它是什么，即使node尚未完全定义。因此，它可以确定node的布局，而又不知道接下来会发生什么，这足以使其快乐。

将您的代码段与此对比：

struct node
{
    int data;
    node next;
};

现在编译器陷入困境，因为每个next将包含另一个node，它将包含另一个next等等，ad-infinitum。因此，该代码不会编译。但是有了指针，很好。

根据 @goswinvonbrederlow的评论，更正式地struct node将node作为不完整的类型，即使您立即通过{...};以及在node> node的声明中， 节点被视为声明但不完整。

从那以后，潜入标准那：

...允许使用不完整类型的指针...

这就是使您的示例起作用的原因。正如我所说，这是语言的设计方式。 C大致相同。

The short answer is because the standard says so.

The longer answer is that the size of a pointer (a pointer to data, anyway) is always the same and so the compiler knows what it is even though node is not yet fully defined. It is therefore able to determine the layout of node without knowing what is coming next, and that's enough to keep it happy.

Contrast your code snippet with this:

struct node
{
    int data;
    node next;
};

Now the compiler is in trouble, because each next will contain another node which will contain another next and so on, ad-infinitum. This code, therefore, will not compile. But with a pointer, it's fine.

As per @GoswinvonBrederlow's comments, more formally struct node introduces node as an incomplete type, even if you immediately follow it by { ... };, and within the declaration of node, node is considered declared but incomplete.

Following on from that, diving into the standard tells us that: