c - 结构体中的指针指向另一个结构体

Question

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

让我们采用这个结构:

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

我认为现在会发生的是:

1. 假设主函数中有一个 Node 类型的指针 Node* p，并且已分配内存(使用 malloc)。

2. 现在，如果我们有一些数据 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

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,

别难过 - 链表让我在数据结构课(我的第一个“硬”CS 课)中陷入了困境。我比我的同学多花了整整一周的时间才理解这个概念。希望图片有帮助。

编辑

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 );
  ...
}