C语言链表入门教程（非常详细，新手必看）
链表是一种常见的数据结构，读者已经掌握了用数组存放数据，使用数组时要先指定数组中包含元素的个数，即数组的长度。如果向这个数组中加入的元素个数超过数组的长度，便不能将内容完全保存。
例如，在定义一个班级的人数时，如果小班是 30 人，普通班级是 50 人，且定义班级人数时使用的是数组，那么定义数组的大小应为最大人数，也就是最少为 50 个元素，否则不满足最大时的情况，这种方式非常浪费空间。
这时就希望有一种存储方式，其存储元素的个数是不受限制的，当添加元素时存储元素的个数就会随之改变，这种存储方式就是链表。
链表结构的示意图如下图所示：
图 1 链表结构的示意图
从图 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 种插入操作的思路都是一样的。
下面主要介绍第一种插入操作，即在链表的头节点位置插入节点，如下图所示：
图 2 插入节点
插入节点的过程就如手拉手的小朋友连成一条线，这时又来了一个小朋友，他要站在第一位小朋友的前面，那么他只需要牵原来第一位小朋友的手就可以了。这样，这条连成的线还是连在一起的。
设计一个函数用来向链表中添加节点，代码如下：
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 删除节点
通过图 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 { 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