这篇笔记是关于链表（Linked list）的.

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

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

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

注：以下的代码是针对本题进行编写的，但实际上链表需要根据情况和题面进行灵活编写，故不建议背诵模板，请务必做到理解每行代码的原因！

基本结构

链表的第一个节点（头节点）的指针指向第一个元素的地址，而第一个元素的指针又指向第二个元素的地址……直到最后一个节点的指针，其指向 NULL.

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

我没有参考教材第九章例题 9.9 和 9.10（因为我好像根本不知道教材是啥...），因此我将会在这里把链表的创建（create）和输出（print）过程进行叙述.

创建

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

对于本题，我们使用如下结构体来保存每个学生的信息：

typedef struct Student {
    long int iNum;
    float iSco;
    struct Student *pNext;
} Stu;

其中 iNum 是学生们的学号，iSco 是学生们的成绩，而 pNext 是一个指向下一位学生的指针.

让我们思考一下链表的创建方式，按步骤梳理，应该包含如下步骤：

1. 定义一个全局变量 iCnt 用于表示链表的长度.
2. 创建两个指针 pHead、pEnd，其中 pHead 指向链表的首节点，pEnd 指向链表的尾节点，初始时 pHead 应该为 NULL.
3. 每当需要加入新元素时，iCnt ++，并创建一个 pNew 用于输入新元素的信息，随后将 pNew->pNext 设为 NULL. 若这是链表中的第一个元素，应令 pHead 指向 pNew，并使 pEnd 指向 pNew，否则，应令原来的尾节点的下一个节点 pEnd->pNext 为 pNew，并将 pEnd 指向 pNew.

思路足够清晰且易懂，我们很容易写出 create() 函数：

int iCnt;
Stu* create() {
    Stu* pHead = NULL;
    iCnt = 0;
    Stu* pEnd, *pNew;
    pNew = pEnd = (Stu *)malloc(sizeof(Stu));
    scanf("%ld,%f", &pNew->iNum, &pNew->iSco);
    while (1) {
        iCnt ++;
        if (iCount == 1) {
            pNew->pNext = pHead;
            pHead = pNew;
            pEnd = pNew;
        } else {
            pNew->pNext = NULL;
            pEnd->pNext = pNew;
            pEnd = pNew;
        }
        pNew = (Stu *)malloc(sizeof(Stu));
        scanf("%ld", &pNew->iNum);
        if (pNew->iNum == 0) {
            break;
        }
        scanf(",%f", &pNew->iSco);
    }
    free(pNew);
    return pHead;
}

以上，链表的创建函数就写完了，它会将创建好的链表的头指针返回，以便后续对该链表进行操作.

输出

链表的输出更加简单，我们只需要一个 pTemp 指向在初始时指向作为参数传入的头指针 pHead，在将我们需要的信息打印后，让 pTemp 变成自己所指向的节点（pTemp = pTemp->pNext），并继续打印即可：

void print(Stu* pHead) {
    Stu* pTemp = pHead;
    while (pTemp != NULL) {
        printf("%ld %5.1f\n", pTemp->iNum, pTemp->iSco);
        pTemp = pTemp->pNext;
    }
    return;
}

删除

链表的删除操作同样非常易懂，我们先梳理一下步骤：

1. 判断删除的节点是否为头节点，如果是，则让 pHead 指向 pHead->pNext，并 iCnt --，随后将新的头指针返回. 如果不是，则进入以下的步骤.
2. 定义两个指针 pTemp 与 pPre，其中 pPre 永远指向 pTemp 所指向的节点的前一个节点. 通过 pTemp = pTemp->pNext 的方法寻找要删除的节点，一旦找到，令 pPre->pNext 指向 pTemp->pNext，并将 pTemp 所在的内存释放掉，随后 iCnt --，这样该节点就不再属于这个链表了.

思路非常清晰，核心代码如下：

Stu* del(Stu* pHead) {
    long int Num;
    scanf("%ld", &Num);
    if (pHead->iNum == Num) {
        pHead = pHead->pNext;
        iCnt --;
        return pHead;
    }
    Stu* pTemp = pHead;
    Stu* pPre = pTemp;
    while (Num != pTemp->iNum) {
        pPre = pTemp;
        pTemp = pTemp->pNext;
    }
    pPre->pNext = pTemp->pNext;
    iCnt --;
    free(pTemp);
    return pHead;
}

其也会将改动后的链表的头指针返回.

插入

有了之前的分析经验，插入节点就如探囊取物般轻松：

1. 还是判断，要插入的节点是否为新的头节点，如果是，则令 pNew->pNext 指向 pHead，并令 pHead 指向 pNew，随后将新的头指针返回，并 iCnt ++. 如果不是，则进入以下的步骤.
2. 与删除操作中同样的要求，定义两个指针 pTemp 与 pPre，通过 pTemp = pTemp->pNext 的方法寻找要插入的位置，随后令 pPre->pNext 指向 pNew，并令 pNew->pNext 指向 pTemp，随后 iCnt ++，这样就完成了节点的插入操作.

以下是核心代码：

Stu* insert(Stu* pHead) {
    Stu* pNew = (Stu *)malloc(sizeof(Stu));
    long long idx;
    scanf("%ld,%f", &pNew->iNum, &pNew->iSco);
    scanf("%lld", idx);
    if (idx == 1) {
        pNew->pNext = pHead;
        pHead = pNew;
        iCnt ++;
        return pHead;
    }
    Stu* pTemp = pHead;
    Stu* pPre = pTemp;
    while (-- idx > 0) {
        pPre = pTemp;
        pTemp = pTemp->pNext;
    }
    pPre->pNext = pNew;
    pNew->pNext = pTemp;
    iCnt ++;
    return pHead;
}

以上就是本题需要的链表相关操作的笔记.