一、链表什么时候要开辟空间

链表创建链表需要开辟空间，遍历不需要。

1、P 和 Rear 都是指针，是用来存放内存地址的变量。

2、malloc() 函数，申请一段内存（开辟空间），并返回这段内存的首地址。

3、P = (struct Node*)malloc(sizeof(struct PolyNode)); 开辟一段节点大小的空间，返回这段空间的首地址赋值给 P。此时 P 记录着新节点的地址，所以想对这个新节点操作可以直接使用 P 。

4、Rear = P; 将 P 记录的地址赋值给 Rear，所以 Rear 和 P 也可以代表新节点。

5、整个函数 struct Node* ReadPoly() 只开辟一个节点大小的空间，然后对这个新节点作了一些赋值等初始化操作后，返回这个新节点的地址。

链表创建为什么需要使用内存分配

我们知道，在全局定义的结构体变量，存储全局数据区；在函数内定义的结构体变量，存储在栈区；使用malloc函数申请空间来存放结构体变量，则该结构体变量存储在堆空间中。

我们说的链表，其节点数据一般放在堆空间中。

那假如有1000个在函数内部（栈区）或者函数外部（全局数据区）定义好的结构体，能否直接创建链表？可以的，但是这样徒有链表的形式，不具备链表动态扩展的特点。

比如下面段代码，提前定义了结构体数组，然后串联成类似“链表”的形式，但假如节点数目大于6，则难以扩展。

struct MyStruct

{

    int a;

    struct MyStruct* next;

};

int main(void)

{

    struct MyStruct node[6];

    int k;

    for (int i = 0; i < 5; i++)

    {

       scanf(“%d”, &k);

       node[i].a = k;

       node[i].next = &node[i + 1];

    }

    node[5].a = 44;

    node[5].next = NULL;

    struct MyStruct* temp = &node[0];

    while (temp!= NULL)

    {

       printf(“%d”, temp->a);

       temp = temp->next;

    }

    getchar(); getchar();

    return 0;

}

延伸阅读：

二、链表的基本介绍

单链表是以结点方式存放数据的，一个结点由两部分组成，一部分存放元素数据，称为数据域，另一部分存放它的后一个结点的指针，称为地址域。后续没有结点时，地址域的值为0。它们在内存中存放的顺序是不连续的。

上一篇

做ACM算法用什么开发工具?

下一篇

为什么采用线性探测法散列算法?