数据结构学习--链表（单链表）的创建和遍历

本文是我的第一篇博客。为什么想到要写博客呢？因为每当我学习新的知识的时候，我总是担心很快就会忘记。往往在学习了新的知识后再过一段时间去追溯自己的学习过程以及学习内容时，总会陷入一段毫无结果的回忆。好记性不如烂笔头，把学到的重要知识点通过博客的形式存储起来即简单又便于日后追溯。

我将以及其详细的说明来写我的每一篇博客！望通过这样的形式既帮助到自己，也能为其他人带来一些帮助。

在学习数据结构时，链表是一个及其重要的知识点，学好链表将为后续的学习打下良好的基础。

数组比较简单，大家一般都能掌握。 链表与数组的相同之处在于：两者都是线性的数据结构。 链表不同于数组的地方在于：数组的数据在内存中是连续存储的，而链表中的节点则是离散存储的。

链表中每个节点包括两个部分：数据域、指针域。数据域存储的就是这个节点所存储的数据，指针域存储的是下一个节点的地址。这样，两个离散的节点之间就通过前一个节点的指针域所连接以来了。

下面是链表的生成函数及遍历函数

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct node  //创建结构体变量，data表示数据域，pNext表示指针域
{
    int data;
    struct node * pNext;
}NODE, * PNODE; // typedef定义，NODE表示struct node，PNODE表示struct node *

PNODE create_list(void); //链表生成函数
void traverse_list(PNODE pHead); //链表遍历函数

int main(void)
{
    PNODE pHead = NULL; 

    pHead = create_list();
    traverse_list(pHead); 

    return 0;
}

PNODE create_list(void)
{
    int len; //链表长度
    int i;
    int val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); //创建头结点
    if (NULL == pHead) //头结点生成成功与否判断
    {
        printf("链表创建失败，程序终止！");
        exit(-1);
    }
    PNODE pTail = pHead; //创建一个pTail，其与pHead存储同一个地址
    pTail->pNext = NULL; //令pTail指向的节点的指针域为NULL，同样的pHead指向的节点的指针域为NULL

    printf("请输入链表的长度: len =");
    scanf("%d", &len);

    for (i=0; i<len; i++)
    {
        printf("请输入链表第%d个元素的值:", i+1);
        scanf("%d", &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE)); //生成一个新的节点
        if (NULL == pNew)
        {
            printf("链表创建失败，程序终止！");
            exit(-1);
        }
        pNew->data = val; //键入的值存放在新生成的节点的数据域
        pTail->pNext = pNew; //新生成的节点的地址挂在pTail指向的节点的地址域，同样的新节点的地址挂在了pHead所指向的头结点的地址域。这样，第一次循环生成的节点与头结点连接在了一起
        pNew->pNext = NULL; //新节点的指针域为NULL
        pTail = pNew; //第一次循环生成的节点的地址给到pTail，供第二次循环时生成的节点与第一次生成的节点产生连接所用。在第二次循环中pTail=pHew1类比于第一次循环中pTail=pHead，以此类推，使新产生的节点与上一个节点连接
    }
    return pHead;
}

void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext; //p的初始值为头结点的指针域

    while (NULL != p)
    {
        printf("%d ", p->data); //第一个输出值为：头结点指针域存储的地址所指向的节点的数据域存储的值
        p = p->pNext; //令p等于p指向的节点的指针域存储的地址，通过循环即可由printf函数输出下一个节点数据域存储的数据
    }

    return;
}

链表的生成函数中pTail的作用相当于是起到了中介的作用，生成一个新节点并与上一节点产生连接时，并不直接对上一个节点进行操作，而是通过pTail来进行操作，弄清楚pTail的作用才能理解链表的生成。

以上是我的理解，有错误的地方欢迎指正，若还有其他对于生成单链表的理解，欢迎相互交流。