一、链表概述

链表是一种常见的数据结构，在链表中可以动态的进行内存分配。也可以将链表看成是一个功能强大的数组，它可以在节点中定义多种数据类型，还可以根据需要随意增加，删除，或者插入节点。

每个链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。

简单来说，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，最后的一个元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

本文仅对单链表进行介绍。

二、链表操作

1、动态创建链表

链表的创建的是一个动态的过程，动态创建一个节点时，要为其分配内存，相关函数介绍如下：

（1）malloc函数

函数功能：在内存中动态地分配一块size大小的内存空间。malloc函数会返回一个指针，该指针指向分配的内存空间，如果出现错误则返回NULL。

malloc函数原型如下：

void *malloc(unsigned int size);

（2）calloc函数

函数功能：在内存中动态分配n个长度为size的连续内存空间数组。calloc函数会返回一个指针，该指针指向动态分配的连续内存空间地址。当分配空间错误时，返回NULL。

calloc函数原型如下：

void *calloc(unsigned n, unsigned size);

（3）free函数

函数功能：使用由指针ptr指向的内存区，使部分内存区能被其他变量使用。ptr是最近一次调用calloc或malloc函数时返回的值。free函数无返回值。（释放内存空间）

函数原型如下：

void free(void *ptr);

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);             // 输入新加入的学生学号// 两步操作：1.将原来的头节点地址给到新节点指向的下一级节点；2.将新节点的地址给到头节点。pNew->pNext = pHead;                    // 新节点指针指向原来的首节点（将原来的头结点地址给到新加入的节点指向的地址）pHead = pNew;                           // 链表头指针指向新节点（新节点变成了头节点）iCount++;                               // 增加链表的节点数return pHead;                           // 返回链表头指针
}

3、链表的删除操作补充内容

链表删除过程中，可以对待删除的链表序号进行判断

（1）在对头结点进行赋值过程中，可以先对链表的头结点进行判断，判断当前链表头节点是否为空, 非空情况下再进行后续的头结点赋值操作；

    if (pHead == NULL)                              // 首先判断链表头是否为空，即整个链表是否为空表{                                               // 若是空表，则输出空printf("\n---The List NULL!---\n");return pHead;}pTemp = pHead;                                  // pHead赋值给pTemp，得到链表的头结点

（2）在执行循环判断语句过程中，可以先判断待删除的节点下标序号是否为pTemp指向的节点；

	while ((iIndex != pTemp->iIndex) && (pTemp->pNext != NULL))     // 当要删除的iIndex不等于pTemp所指向的节点下标且满足pTemp的下一个结点不为空{pPre = pTemp;                               // 将pTemp赋给pPre;pTemp = pTemp->pNext;                       // 再将pTemp指向下一个节点；重复进行，直到找到待删除的节点序号，此时pTemp指向的节点就是所要找的待删除节点}

（3）在进行节点删除过程中，可以先判断待删除的节点是否为第一个节点；

	if (iIndex == pTemp->iIndex) {                          // 除非链表中不存在要寻找的iIndex，否则这个条件是一定成立的，if(pTemp == pHead){                                           // 如果要删除的是第1个节点pHead = pTemp->pNext;                   // 则让pHead指向pTemp的下一个节点，也就是第二个节点}else {pPre->pNext = pTemp->pNext;             // 如果要删除的不是第一个节点，则让pPre的next指向pTemp（要删除的结点）的下一个结点，此时则跳过了这个iIndex，即达到删除的效果}printf("Delete: %d\n", iIndex);iCount = iCount - 1;}

三、链表完整代码实现

本节详细链表操作见代码实现，包括链表的动态创建，插入、删除和输出操作。

#include<stdio.h>
#include<stdlib.h>// 创建链表节点结构，表示每一个学生
struct Student
{char cName[20];             // 学生姓名int iNumber;                // 学号struct Student *pNext;      // 指向下一个节点的指针
};int iCount;                     // 全局变量表示链表长度// Create函数的功能是创建链表，动态分配内存空间的方式创建链表
// 该函数将会返回链表的头指针
//（在链表的尾结点插入）
struct Student *Create()
{struct Student *pHead = NULL;           // 初始换链表头指针为空struct Student *pNew, *pEnd;            // pEnd用来指向原来的尾节点，pNew用来指向新创建的节点iCount = 0;                             // 表示链表中节点的数量pEnd = pNew = (struct Student*)malloc(sizeof(struct Student));     // malloc 函数分配内存，先用pEnd和pNew两个指针都指向第一个分配的内存printf("------Please First Enter Name, The Number------\n");scanf("%s",&pNew->cName);scanf("%d",&pNew->iNumber);while(pNew->iNumber != 0){iCount++;// 第一次加入节点，新节点即为首节点，也是最后一个节点，并且需要将新加入的节点的指针指向NULL，即为pHead指向。if(iCount == 1){pNew->pNext = pHead;            // 使得指针指向为空（新加入的节点为首节点的时候，节点空指针即为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);                             // 不满足新节点要求，跳出循环后调用free函数释放未使用的内存空间return pHead;                           // 该函数返回链表的头指针
}// 定义打印函数Print
// void 函数没有返回值
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++;                                           // 进行自加运算}
}// 链表的插入操作（在链表的头结点插入）
// 该函数将会返回链表的头指针
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);             // 输入新加入的学生学号// 两步操作：1.将原来的头节点地址给到新节点指向的下一级节点；2.将新节点的地址给到头节点。pNew->pNext = pHead;                    // 新节点指针指向原来的首节点（将原来的头结点地址给到新加入的节点指向的地址）pHead = pNew;                           // 链表头指针指向新节点（新节点变成了头节点）iCount++;                               // 增加链表的节点数return pHead;                           // 返回链表头指针
}// 删除链表节点
// 输入：链表头结点pHead，要删除的节点下标iIndex;dd
void Delete(struct Student *pHead, int iIndex)
{int i;                                  // 控制循环变量struct Student *pTemp;                  // 临时指针变量，表示要删除的节点struct Student *pPre;                   // 表示要删除节点之前 的节点pTemp = pHead;                          // pHead赋值给pTemp，得到链表的头结点pPre = pTemp;                           // pPre指向pTemp，将pTemp的地址给到pPreprintf("======Delete NO%d member======\n",iIndex);          // 提示待删除节点位置信息// for语句进行循环操作，使得pTemp指向要删除的节点for(i=1; 1<iIndex; i++){// 将pTemp赋值给pPre，再将pTemp指向下一个节点，重复进行，直到找到需要定位的iIndex节点，此时pTemp指向的节点就是所要找的待删除的节点pPre = pTemp;                       // 定位到要删除的节点pTemppTemp = pTemp->pNext;               // 再将pTemp指向下一个节点}pPre->pNext = pTemp->pNext;             // 连接待删除节点两边的节点地址（将待删除节点两边的地址相关联）（重点！！！）free(pTemp);                            // 释放掉要删除节点的内存空间iCount--;                               // 减少链表中元素的个数
}// 定义主函数
int main()
{struct Student *pHead;                  // 定义头结点pHead = Create();                       // 创建链表节点pHead = Insert(pHead);                  // 插入新的节点Delete(pHead,2);                        // 删除链表中第二个节点的操作Print(pHead);                           // 输出最终的链表return 0;
}