链表

链表是一种使用结构来存储数据的方式，使得程序员可以自动创建新的存储空间来存储数据。具体来说，程序员编写一个结构体定义，其中包含存储某些信息的变量，并且有一个指向相同类型结构体的指针（必须是指针——否则，每次创建元素时，它都会无限地创建新元素）。列表中的每个单独的结构体或类通常被称为节点或元素。

有一种可视化链表的方式，就像火车一样。程序员总是将列表的第一个节点存储在一个指针中，以防止失去访问权限。这将是火车的引擎。指针本身是火车车厢之间的连接器。每次火车添加车厢时，它都会使用连接器来添加一个新车厢。这就像程序员使用 malloc 来创建一个指向新结构体的指针。

在内存中，链表通常被描述为看起来像这样：

----------        ----------
- Data   -        - Data   -    
----------        ----------   
- Pointer- - - -> - Pointer-  
----------        ----------

这种表示方式在细节上并不完全准确，但对于我们的目的来说已经足够。每个大块是一个包含指向另一个块的指针的结构体。记住指针只存储某个内存位置——它本身并不是那个东西——所以箭头指向下一个结构体。在列表的末尾，指针没有东西可以指向，所以它不指向任何地方；它应该是一个空指针或虚拟节点，以防止节点意外地指向内存中的随机位置（这非常糟糕）。

到目前为止，我们已经知道节点结构体应该是什么样子：

#include <stdlib.h>
 
struct node {
  int x;
  struct node *next;
};
 
int main()
{
    /* 这将是不变的第一个节点 */
    struct node *root;      
 
    /* 现在，根指向一个节点结构 */
    root = (struct node *) malloc( sizeof(struct node) ); 
 
    /* 节点根所指向的下一个指针等于空指针集 */
    root->next = 0;  
    /* 通过使用->操作符，您可以修改节点（指针）指向的内容（在本例中为根）。*/
    root->x = 5;     
}

到目前为止，这对于做任何事来说还不太有用。在真正变得有用之前，有必要理解如何遍历（遍历）链表。这将允许我们在列表中存储一些数据，并在稍后找到它，而无需知道它确切的位置。

回想一下火车。让我们想象一个只能通过第一节车厢进入火车、并且只要连接器连接到另一节车厢就能沿着线路走遍整个火车的列车员。这就是程序遍历链表的方式。列车员将是一个指向节点的指针，它首先指向根节点，然后，如果根节点指向下一个节点的指针指向某个东西，那么"列车员"（非技术术语）将被设置为指向下一个节点。以此方式，列表可以被遍历。只要还有指向某个东西的指针，遍历就会继续。一旦它到达一个空指针（或哑节点），意味着没有更多的节点（火车车厢），那么它就到达了列表的末尾，如果需要的话，可以随后添加一个新节点。

下面是它的样子：

#include <stdio.h>
#include <stdlib.h>
 
struct node {
  int x;
  struct node *next;
};
 
int main()
{
    /* This won't change, or we would lose the list in memory */
    struct node *root;       
    /* This will point to each node as it traverses the list */
    struct node *conductor;  
 
    root = malloc( sizeof(struct node) );  
    root->next = 0;   
    root->x = 12;
    conductor = root; 
    if ( conductor != 0 ) {
        while ( conductor->next != 0)
        {
            conductor = conductor->next;
        }
    }
    /* Creates a node at the end of the list */
    conductor->next = malloc( sizeof(struct node) );  
 
    conductor = conductor->next; 
 
    if ( conductor == 0 )
    {
        printf( "Out of memory" );
        return 0;
    }
    /* initialize the new memory */
    conductor->next = 0;         
    conductor->x = 42;
 
    return 0;
}

这就是遍历列表的基本代码。if 语句确保在遍历列表之前内存已经正确分配。如果 if 语句中的条件评估为真，那么可以尝试访问由 conductor 指向的节点。while 循环会持续进行，只要 next 中还有另一个指针。conductor 会简单地沿着链表移动。它通过获取 conductor->next 的地址来改变所指向的内容。

最后，代码末尾可以用来在链表末尾添加一个新节点。一旦 while 循环结束，指针将指向数组中的最后一个节点。（还记得火车司机会一直移动直到没有可移动的地方吗？while 循环的工作原理与此相同。）因此，将 conductor->next 设置为 null，这样就可以为它分配新的内存区域来指向（如果它不是 NULL，那么在指针中存储其他内容会导致我们丢失它所指向的内存）。当我们分配内存时，我们会进行快速检查以确保我们没有超出内存限制，然后指针遍历一个更多元素（就像火车司机移动到新添加的车厢），并确保它将 next 指针设置为 0，这样链表就有了一个结束。0 就像一个句号；它表示没有更多内容。最后，新节点的 x 值被设置。（它可以通过用户输入来设置。我简单地写入了'=42'作为示例。）

要打印链表，遍历函数几乎相同。在我们的第一个示例中，必须在 while 循环结束后打印最后一个元素。（在阅读代码示例之前，看看你是否能想到更好的方法。）

例如：

conductor = root;
if ( conductor != 0 ) { /* Makes sure there is a place to start */
    while ( conductor->next != 0 ) {
        printf( "%d\n", conductor->x );
        conductor = conductor->next;
    }
    printf( "%d\n", conductor->x );
}

最终输出是必要的，因为 while 循环在到达最后一个节点后将不会运行，但它仍然需要输出下一个节点的内容。因此，最后一个输出处理了这个问题。我们可以通过让"司机"离开火车的尾部来避免这种冗余。对"司机"来说很糟糕（如果它是一个真正的人），但代码更简单，因为它还允许我们移除初始的空检查（如果 root 为空，那么 conductor 将立即被设置为空，并且循环将永远不会开始）：

conductor = root;
while ( conductor != NULL ) {
    printf( "%d\n", conductor->x );
    conductor = conductor->next;
}