单链表的初始化

---

1. 链表的节点

链表存储的数据元素，其物理存储位置是随机的。链表给每个数据元素都配备一个指针，用于指向自己的直接后继元素，来表示数据之间逻辑关系

链表中每个数据的存储都由以下两部分组成：

1. 数据元素本身，其所在的区域称为数据域
2. 指向直接后继元素的指针，所在的区域称为指针域；

即链表中各节点的结构如图所示：

链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中：

链表中每个节点的具体实现，需要使用 C 语言中的结构体，具体实现代码为：

typedef struct node
{
    char elem; //代表数据域
    struct node *next; //代表指针域，指向直接后继元素
}Node; //Node为节点名，每个节点都是一个 Node 结构体

---

2. 头节点，头指针和首元节点

• 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据
• 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
• 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；

因此，一个存储 {1,2,3} 的完整链表结构如下图所示：

---

3. 链表的创建

创建一个链表需要做如下工作：

• 声明一个头指针（如果有必要，可以声明一个头节点）；
• 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

例如，创建一个存储 {1,2,3,4} 且无头节点的链表，C 语言实现代码如下：

Node *InitLink()
{
    Node *P = NULL; //创建头指针
    Node *temp = (Node*)malloc(sizeof(Node));   //创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;  
    p = temp;   //头指针指向首元节点
     //从第二个节点开始创建
    for(int i = 2; i < 5; i++)
    {
        //创建一个新节点并初始化
        Node *a = (Node*)malloc(sizeof(Node));
        a->elem = i;
        a->next = NULL;
        //将temp节点与新建立的a节点建立逻辑关系
        temp->next = a;
        //指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对
        temp = temp->next;
    }
    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
    return p;
}

如果想创建一个存储{1,2,3,4}且含头节点的链表，则 C 语言实现代码为：

Node *InitLinkWithHead()
{
    Node *p = (Node*)malloc(sizeof(Node));  //创建一个头结点
    Node *temp = p; //声明一个指针指向头结点
    //生成链表
    for(int i = 1; i < 5; i++)
    {
        Node *a = (Node*)malloc(sizeof(Node));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

---

我们只需在主函数中调用 InitLink 函数，即可轻松创建一个存储 {1,2,3,4} 的链表，C 语言完整代码清单如下：

#include<stdio.h>
#include<stdlib.h>
//链表中节点的结构
typedef struct  Node
{
    int elem;   //代表数据域
    struct Node *next;  //代表指针域，指向直接后继元素
}Node;  //Node为节点名，每个节点都是一个Node结构体

//初始化链表的函数
Node *InitLink();
Node *InitLinkWithHead();
//用于输出链表的函数
void Display(Node *L);

int main()
{
    //初始化链表（1，2，3，4）
    printf("初始化链表为：\n");
    Node *L = InitLink();
    Display(L);
    return 0;
}

Node *InitLink()
{
    Node *p = NULL; //创建头指针
    Node *temp = (Node*)malloc(sizeof(Node));   //创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;  
    p = temp;   //头指针指向首元节点
     //从第二个节点开始创建
    for(int i = 2; i < 5; i++)
    {
        //创建一个新节点并初始化
        Node *a = (Node*)malloc(sizeof(Node));
        a->elem = i;
        a->next = NULL;
        //将temp节点与新建立的a节点建立逻辑关系
        temp->next = a;
        //指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对
        temp = temp->next;
    }
    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
    return p;
}

Node *InitLinkWithHead()
{
    Node *p = (Node*)malloc(sizeof(Node));  //创建一个头结点
    Node *temp = p; //声明一个指针指向头结点
    //生成链表
    for(int i = 1; i < 5; i++)
    {
        Node *a = (Node*)malloc(sizeof(Node));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

void Display(Node *L)
{
    Node *temp = L; //将temp指针指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while(temp)
    {
        printf("%d ", temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

程序运行结果为：

初始化链表为：
1 2 3 4