C语言链表入门教程（非常详细，新手必看）

链表是一种常见的数据结构，读者已经掌握了用数组存放数据，使用数组时要先指定数组中包含元素的个数，即数组的长度。如果向这个数组中加入的元素个数超过数组的长度，便不能将内容完全保存。

例如，在定义一个班级的人数时，如果小班是 30 人，普通班级是 50 人，且定义班级人数时使用的是数组，那么定义数组的大小应为最大人数，也就是最少为 50 个元素，否则不满足最大时的情况，这种方式非常浪费空间。

这时就希望有一种存储方式，其存储元素的个数是不受限制的，当添加元素时存储元素的个数就会随之改变，这种存储方式就是链表。

链表结构的示意图如下图所示：


从图 1 可以看到，head（头）节点指向第 1 个元素，第 1 个元素中的指针又指向第 2 个元素的地址，第 2 个元素的指针又指向第 3 个元素的地址，第 3 个元素的指针指向空。

注意，链表这种数据结构必须利用指针才能实现，因此链表中的节点应该包含一个指针变量来保存下一个节点的地址。

例如，设计一个链表表示一个班级，其中链表中的节点表示学生，代码如下：

struct Student
{
   char cName[20];        /*姓名*/
   int iNumber;           /*学号*/
   struct Student* pNext;  /*指向下一个节点的指针*/
};

可以看到学生的姓名和学号属于数据部分，而 pNext 就是指针部分，用来保存下一个节点的地址。

链表的创建

从前面的讲解不难看出，链表并不是一开始就设定好大小的，而是根据节点的多少确定的，因此链表的创建过程是一个动态的过程。

定义一个 Create() 函数，用来创建链表。该函数会返回链表的头指针，代码如下：

int iCount;       /*全局变量表示链表长度*/

struct Student* Create()
{
    struct Student* pHead = NULL;            /*初始化链表头指针，使其为空*/
    struct Student* pEnd, *pNew;
    iCount = 0;   /*初始化链表长度*/
    pEnd = pNew = (struct Student*)malloc(sizeof(struct Student));
    printf("please first enter Name ,then Number\n");
    scanf("%s", &pNew->cName);
    scanf("%d", &pNew->iNumber);
    while (pNew->iNumber != 0)
    {
        iCount++;
        if (iCount == 1)
        {
            pNew->pNext = pHead;            /*使得指向为空*/
            pEnd = pNew;                    /*跟踪新加入的节点*/
            pHead = pNew;                   /*头指针指向首节点*/
        }
        else
        {
            pNew->pNext = NULL;             /*新节点的指针为空*/
            pEnd->pNext = pNew;             /*原来的尾节点指向新节点*/
            pEnd = pNew;                    /*pEnd指向新节点*/
        }
        pNew = (struct Student*)malloc(sizeof(struct Student));
        /*再次分配节点内存空间*/
        scanf("%s", &pNew->cName);
        scanf("%d", &pNew->iNumber);
    }
    free(pNew);        /*释放没有用到的空间*/
    return pHead;
}

从上述代码中可以看出以下内容：
1) Create() 函数的功能是创建链表，在 Create() 的外部有一个整型的全局变量 iCount，这个变量的作用是表示链表中节点的数量。在 Create() 函数中，首先定义需要用到的指针变量，pHead 表示头节点，pEn指 向原来的尾节点，pNew 指向新创建的节点。

2) 使用 malloc() 函数分配内存，先使 pEnd 和 pNew 两个指针都指向第一个分配的内存，然后输出提示信息，先输入一个学生的姓名，再输入学生的学号。使用 while 语句进行判断，如果学号为 0，则不执行循环语句。

3) 在 while 循环语句中，iCount++ 自加操作表示链表中节点的增加。然后要判断新加入的节点是否为第一次加入的节点，如果为第一次加入的则运行 if 语句块中的代码，否则运行 else 语句块中的代码。

4) 在 if 语句块中，因为第一次加入节点时其中没有节点，所以新节点即首节点，也为最后一个节点，并且要将新加入的节点的指针指向空，即 pHead 的指向。else 语句块实现的是链表中已经有节点存在时的操作。

5) 首先将新节点 pNew 的指针指向空，然后将原来最后一个节点的指针指向新节点，最后将 pEnd 的指针指向最后一个节点。这样节点创建完之后，要再次分配内存，然后向其中输入数据，通过 while 语句再次判断输入的数据是否符合节点的要求。当不符合要求时，调用 free() 函数将不符合要求的节点空间进行释放。

这样，链表就通过动态分配内存空间的方式创建完成了。

链表的输出

链表已经被创建出来，构建数据结构就是为了使用它，以将保存的信息进行输出。接下来介绍如何将链表中的数据输出。代码如下：

void print(struct Student* pHead)
{
   struct Student *pTemp;                  /*循环所用的临时指针*/
   int iIndex = 1;    /*表示链表中节点的序号*/

   printf("----the List has %d members:----\n", iCount);   /*提示信息*/
   printf("\n");      /*换行*/
   pTemp = pHead;     /*指针得到首节点的地址*/

   while (pTemp != NULL)
   {
          printf("the NO%d member is:\n", iIndex);
          printf("the name is: %s\n", pTemp->cName);      /*输出姓名*/
          printf("the number is: %d\n", pTemp->iNumber);  /*输出学号*/
          printf("\n");        /*换行*/
          pTemp = pTemp->pNext;            /*移动临时指针到下一个节点*/
          iIndex++;   /*进行自加运算*/
   }
}

结合创建链表和输出链表的过程，运行程序，结果为：

please first enter Name ,then Number
dahua 1
xiaoning 2
daxhuang 3
lucy 4
exit 0
----the List has 4 members:----

the N01 member is:
the name is: dahua
the number is: 1

the N02 member is:
the name is: xiaoning
the number is: 2

the N03 member is:
the name is: daxhuang
the number is: 3

the N04 member is:
the name is: lucy
the number is: 4

printf() 函数用来将链表中的数据进行输出。在函数的参数中，pHead 表示一个链表的头节点。在函数中，定义一个临时的指针 pTemp 用来进行循环操作。定义一个整型变量表示链表中的节点序号。然后使用临时指针变量 pTemp 保存首节点的地址。

使用 while 语句将所有节点中保存的数据都输出。每输出一个节点的数据后，就移动 pTemp 指针指向下一个节点的地址。当为最后一个节点时，其所有的指针指向空，此时循环结束。

链表的插入和删除

1) 链表的插入操作

链表的插入操作可以在链表的头节点位置进行，也可以在某个节点的位置进行，或者可以像创建结构一样在链表的后面添加节点。这 3 种插入操作的思路都是一样的。

下面主要介绍第一种插入操作，即在链表的头节点位置插入节点，如下图所示：


插入节点的过程就如手拉手的小朋友连成一条线，这时又来了一个小朋友，他要站在第一位小朋友的前面，那么他只需要牵原来第一位小朋友的手就可以了。这样，这条连成的线还是连在一起的。

设计一个函数用来向链表中添加节点，代码如下：

struct Student* Insert(struct Student* pHead)
{
    struct Student* pNew;      /*指向新分配的空间*/
    printf("----Insert member at first----\n");      /*提示信息*/
    pNew = (struct Student*)malloc(sizeof(struct Student));
    /*分配内存空间，并返回指向该内存空间的指针*/
    scanf("%s", &pNew->cName);
    scanf("%d", &pNew->iNumber);
    pNew->pNext = pHead;                     /*新节点指针指向原来的首节点*/
    pHead = pNew; /*头指针指向新节点*/
    iCount++;     /*增加链表节点数量*/
    return pHead; /*返回头指针*/
}

上述代码插入节点的步骤如下：

• 为要插入的新节点分配内存，然后向新节点中输入数据，这样一个节点就创建完成了。
• 将新节点的指针指向原来的首节点，保存首节点的地址，然后将头指针指向新节点，这样就完成了节点的连接操作。

主函数 main() 的代码如下：

int main()
{
    struct Student* pHead;  /*定义头节点*/
    pHead = Create();       /*创建节点*/
    pHead = Insert(pHead);  /*插入节点*/
    Print(pHead);           /*输出链表*/
    return 0;               /*程序结束*/
}

运行程序，结果为：

please first enter Name ,then Number
liuwen 2
suyunjing 3
exit 0
----Insert member at first----
wangjiashen 1
----the List has 3 members:----

the N01 member is:
the name is: wangjiashen
the number is: 1

the N02 member is:
the name is: liuwen
the number is: 2

the N03 member is:
the name is: suyunjing
the number is: 3

2) 链表的删除操作

之前介绍的操作是向链表中添加节点，当希望删除链表中的节点时，应该怎么办呢？还是通过前文中小朋友手拉手的例子进行介绍，队伍中的一个小朋友想离开，使这个队伍不会断开的方法是他两边的小朋友将手拉起来。

例如，在一个链表中删除其中的一个节点，如下图所示：


通过图 3 可以发现，要删除一个节点，先要找到这个节点的位置。例如要删除 NO2 节点，首先要找到 NO2 节点，然后删除该节点，将 NO1 节点的指针指向 NO3 节点，最后释放 NO2 节点的内存空间，这样就完成了节点的删除。

根据这种思想编写删除链表节点的函数，代码如下：

void Delete(struct Student* pHead, int iIndex)
/*pHead表示头节点，iIndex表示要删除的节点索引*/
{
    int i;             /*控制循环的变量*/
    struct Student* pTemp; /*临时指针*/
    struct Student* pPre;  /*表示要删除的节点前的节点*/
    pTemp = pHead;    /*得到头节点*/
    pPre = pTemp;

    printf("----delete NO%d member----\n", iIndex);      /*提示信息*/
    /*for循环使得pTemp指向要删除的节点*/
    for (i = 1; i<iIndex; i++)
    {
        pPre = pTemp;
        pTemp = pTemp->pNext;
    }
    pPre->pNext = pTemp->pNext; /*连接要删除的节点两边的节点*/
    free(pTemp);      /*释放要删除的节点的内存空间*/
    iCount--;         /*减少链表中的元素个数*/
}

为 Delete() 函数传递两个参数，pHead 表示链表的头节点，iIndex 表示要删除的节点的索引。定义整型变量 i 用来控制循环的次数，然后定义两个指针，分别用来表示要删除的节点和这个节点之前的节点。

输出一行提示信息表示要进行删除操作，之后利用 for 语句进行循环操作，找到要删除的节点，使用 pTemp 保存要删除节点的地址，pPre 保存前一个节点的地址。找到要删除的节点后，连接要删除的节点两边的节点，并使用 free() 函数将 pTemp 指向的内存空间释放。

接下来在 main() 函数中添加代码执行删除操作，将链表中的第二个节点删除。代码如下：

int main()
{
    struct Student* pHead;  /*定义头节点*/
    pHead = Create();       /*创建节点*/
    pHead = Insert(pHead);  /*插入节点*/
    Delete(pHead, 2);       /*删除第二个节点的操作*/
    Print(pHead);           /*输出链表*/
    return 0;               /*程序结束*/
}

运行程序，通过运行结果可以看到第二个节点中的数据被删除，结果为：

please first enter Name ,then Number
WangJun 2
LiXin 3
exit 0
----Insert member at first----
XuMing 1
----delete N02 member----
----the List has 2 members:----

the N01 member is:
the name is: XuMing
the number is: 1

the N02 member is:
the name is: LiXin
the number is: 3