结构中指向另一个结构的指针

Question

我想了解链表中的指针是如何工作的。到目前为止，我在试图弄清楚指针指向的位置以及类型结构的指针如何工作时遇到了很多麻烦（我知道我们需要从堆中分配内存但不太理解它，但也许那是完全不同的问题）。

让我们采用这个结构：

typedef struct Node {
    int data;
    struct Node *link;
} Node;

我认为现在会发生的是：

假设您在主函数中有一个 Node 类型的指针，Node* p 这是分配的内存（使用 malloc）。
现在如果我们有一些数据 p->data=5; ， p 指向该数据的开头（至少我认为这是正在发生的事情）。

link具体指向哪里？

所以现在，我遇到了这段特殊的代码：

typedef struct Node {
    int data;
    struct Node *link;
} Node;

typedef struct List {
    Node* head;
    int number_of_nodes;
} List;

所以我脑子里一片混乱！ .

现在在结构List中，head在做什么？它指向什么？您将如何使用这两个列表创建一个链表？？

我真的尽我最大的努力去理解链表是如何工作的，但是所有的指针都让人很难跟踪。你可能会建议我从一些简单的事情开始，我做到了，而且我已经提到了我的理解程度。但是第二个结构中的 head 指针让我完全偏离了轨道！

如果有人能在跟踪指针的同时帮助我解释它，那会让我的生活变得更加轻松。

Answer 1

… a pointer of a type struct…

指针不能是属于类型结构。一个指针可以指向到一个结构。

C有对象。对象包括 char、int、double、结构和其他东西。结构是组合在一起的对象的集合。

在 main 中，如果你用 Node *p; 定义 p，那么你就有了一个指针 p。它没有价值，因为你没有赋予它价值。当您执行 p = malloc(sizeof *p); 时，您会为 p 指向 (*p) 的事物的大小请求足够的内存。如果 malloc returns 一个非空指针，那么 p 指向一个 Node 结构。

那么p->data指的是那个结构的data成员。 p->data对于(*p).data是shorthand，其中*p表示“对象p指向”，.data表示“data 该对象中的成员。”

在p = malloc(sizeof *p);和p->data = 5;之后，p->link没有指向任何东西，因为你还没有给它赋值。在链表中，您将使用 malloc 为另一个 Node 获取内存，然后您将在一个 Node 中设置 p->link 以指向新的 [=21] =].在每个 Node 中，其 link 成员指向列表中的下一个 Node。除了，在最后一个 Node 中， p->link 被设置为空指针以指示它是最后一个 Node.

在 List 中，您可以将 head 设置为指向 Node 对象列表中的第一个 Node。

Answer 2

Where exactly does link point to?

link指向另一个相同类型的对象：

+------+------+     +------+------+     +------+------+
| data | link |---->| data | link |---->| data | link | ----> ...
+------+------+     +------+------+     +------+------+

Now in the structure List, what is head doing? What is it pointing to?

head指向列表中的第一个节点：

+-----------------+     +------+------+     +------+------+ 
| head            |---->| data | link |---->| data | link |----> ...
+-----------------+     +------+------+     +------+------+
| number_of_nodes |
+-----------------+

I am really trying my level best to understand how linked lists work,

不要难过 - 链表让我在我的数据结构中陷入循环 class（我的第一个 "hard" CS class）。我花了比 class 伙伴多整整一周的时间来理解这个概念。希望图片能帮到你。

编辑

what happens if you have a pointer to the structure List, memory allocated and all? Where does it point to then (according to the diagrams, which did help by the way)

那么，假设您有以下代码：

/**
 * Create a new list object.  head is initially NULL,
 * number_of_nodes initially 0.
 */
List *newList( void )
{
  List *l = malloc( sizeof *l );
  if ( l )
  {
    l->head = NULL;
    l->number_of_nodes = 0;
  }
  return l;
}

int main( void )
{
  List *l = newList();
  ...
}

那么你的照片是这样的：

+---------+       +--------------------+
| l: addr | ----> | head: NULL         |
+---------+       +--------------------+
                  | number_of_nodes: 0 |
                  +--------------------+

（addr 表示某个任意内存地址）

现在假设您向列表中添加了一个节点：

/**
 * Create a new node object, using the input data
 * link is initially NULL
 */
Node *newNode( int data )
{
  Node *n = malloc( sizeof *n );
  if ( n )
  {
    n->data = data;
    n->link = NULL;
  }
  return n;
}

void insertNode( List *l, int data )
{
  Node *n = newNode( data );
  if ( n )
  {
    /**
     * If list is initially empty, make this new node the head
     * of the list.  Otherwise, add the new node to the end of the
     * list.
     */
    if ( !l->head ) // or n->head == NULL
    {
      l->head = n;
    }
    else
    {
      /**
       * cur initially points to the first element in the list.  
       * While the current element has a non-NULL link, follow
       * that link.
       */
      for ( Node *cur = l->head; cur->link != NULL; cur = cur->link )
        ; // empty loop body
      cur->link = n;
    }
    l->number_of_nodes++;
  }
}

int main( void )
{
  List *l = newList();
  insertNode( l, 5 );
  ...
}

现在你的照片是这样的：

+---------+       +--------------------+      +------------+
| l: addr | ----> | head: addr         | ---> | data: 5    |
+---------+       +--------------------+      +------------+
                  | number_of_nodes: 1 |      | link: NULL |
                  +--------------------+      +------------+

您可以添加另一个节点：

int main( void )
{
  List *l = newList();
  insertNode( l, 5 );
  insertNode( l, 3 );
  ...
}

那么你的照片就变成了

+---------+       +--------------------+      +------------+        +------------+
| l: addr | ----> | head: addr         | ---> | data: 5    |   +--> | data: 3    |
+---------+       +--------------------+      +------------+   |    +------------+
                  | number_of_nodes: 2 |      | link: addr | --+    | link: NULL |
                  +--------------------+      +------------+        +------------+

自然地，您想要添加一些错误检查和消息以防无法分配节点（它发生了）。您可能想要一个有序列表，其中元素按顺序插入（升序、降序等）。但这应该让您了解如何构建列表。

您还需要删除项目和释放内存的函数。以下是我如何释放整个列表：

void freeList( List *l )
{
  Node *prev, *cur = l->head;
  while( cur && cur->link )
  {
    prev = cur;
    cur = cur->link;
    free( prev );
  }
  free( cur );
}

int main( void )
{
  List *l = newList();
  ...
  freeList( l );
  free( l );
  ...
}

结构中指向另一个结构的指针

Pointers in Structure pointing to another strucutre

c

pointers

linked-list

singly-linked-list