引入

按照惯例，我们学习了如何初始化、插入、删除一个静态链表，那么静态链表打底有什么优缺点呢？链表还有什么高级玩法呢？
我们一起来看看~

静态链表的优缺点

• **优点：**插入和删除时，只需要求改游标，不需要移动元素，从而改进了顺序存储结构中需要大量移动元素的缺点。
• **缺点：**没有解决连续存储分配带来得表长难以确定的问题。

总之，静态链表是一个很好的尝试，在没有动态创建、释放内存空间得情况下，利用数组，完成了静态链表。

练习

创建一个20个元素的动态链表，然后快速找到其中间结点。

引入

我们知道了如何初始化一个静态链表，并且知道如何在静态链表中插入一个结点，今天我们来看看如何删除一个结点，并将删除得结点 Free 。

思路

我们先想一下，如果要移除静态链表中的一个结点，会发生什么。

• 该结点的上一个结点找不到移除的这个结点了，链表断了
• 移除的结点内得数据还有，游标指向的是其原来的下个结点
• 移除的结点成了备用链表中的一个结点，0下标的第一个可用结点也需要修改

所以，我们总结如下得思路

• 移除结点，找到前一结点，指向移除结点的后一结点
• 清空移除的结点内的数据
• 移除结点的游标改为0下标指向的第一个可用结点得下标
• 0下标指向的第一个结点为移除的结点

引入

我们说过动态链表是使用malloc( ) 和 free( )这两个函数来实现的，动态插入，动态释放。那么静态链表该如何实现这样的功能呢？

静态链表中插入数据

简单来说就是要分清楚哪些没有使用过，哪些已经在使用了。
我们说

• 备用链表存放的是所有可以用的下标，用游标链接。
• 数组的第一个元素，存放的是备用链表的第一个可用下标
  所以
  每次插入新节点，都可以从备用链表取得第一个结点作为待插入结点。

步骤分解
1、先获取0下标指向的备用链表的第一个可写入下标。
2、第一个可写入的结点的游标传递给0下标。
3、判断插入地址是否合法，不能小于1，不能大于结点长度+1的位置。
4、对第一个可写的节点的 data 赋值
5、通过循环从最后一个结点向前找到要插入的节点之前的结点
6、找到之后新结点的游标改成之前结点的游标
7、前一结点的游标指向新节点的下标。

引入

我们学习了线性表中的顺序存储结构、单链表以及他们的初始化、插入、查找、删除等操作，今天我们来看看，没有动态创建内存空间之前，人们是如何使用链表的~

静态链表

简单来说，我们将用数组描述的链表称为静态链表，这种描述方法叫做游标实现法。
我们知道，链表是由指针域和数据域两个部分组成，静态链表也差不多，但它们是由数据域和游标组成。因为是数组，所以描述时还有一个下标。

• **数据域：**存放的是该静态链表中每个结点的数据。
• **游标：**用于找到下一个结点，类似于指针。
  下标：
• 0号下标存没有数据，游标存储着可以存放数据的下标。
• max 号下标存储着该静态链表第一个结点的位置，类似于 head 指向头结点。
• 其他下标存储的是当前结点数据和下一个结点的下标。

其实简单来说，因为不能动态创建内存空间，那就再顺序存储结构中设置了一个游标，游标类似于指针，存放的不是内存地址，而是下一个结点的下标。

引入

我们基本学习了如何创建、删除、插入、修改一个单链表，那么单链表跟顺序表比真的高效嘛？单链表又适用于什么情况呢？单链表跟顺序表的优缺点呢？我们一起来看看！

效率观察

我们发现，无论是插入还是删除单链表中的元素，其实就分两步

• 遍历查找第 i 个元素
• 实现插入和删除

从算法的角度很容知道它们的时间复杂度都是 O(n);

那么单链表和顺序表岂不是都一样了？既然都是 O(n)，那链表的优势在哪呢？

对比

从第 i 个位置开始，连续插入10个元素

对于顺序存储结构

• 没插入一个都要移动 n-i 个位置
• 每次都是 O(n)

对于链表

• 找到第 i 个位置的指针，此时时间复杂度为 O(n)
• 接下来的赋值移动指针的时间复杂度为 O(1)

所以，对于删除和操作频繁的操作，单链表的效率就越高。

引入

我们学习了用头插法和尾插发创建一个单链表，今天我们在学习如何删除整个单链表。

删除整个单链表

其实就是再内存中将它释放掉，留出空间给其它软件使用。
整表删除思路：

• 声明结点 p 和 q
• 第一个结点给 p，第二个结点给 q
• 释放完 p，将 q 指向的给 p
• 释放完 q，将 p 指向的给 q
• 循环执行，直到完全释放完毕

代码实现

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Student)
struct Student{
    int num;
    char name[20];
    float score;
    struct Student *next;
};

struct Student *create(void){
    struct Student *a,*b,*head;
    a=(struct Student *)malloc(LEN);  //创建结点
    head=(struct Student *)malloc(LEN);
    b=head;  //b 是指向尾部的节点
    printf("请输入学生信息：\n");
    scanf("%d %s %f",&a->num,a->name,&a->score);
    while(a->num!=0){
        b->next=a;
        b=a;
        a=(struct Student *)malloc(LEN);
        scanf("%d %s %f",&a->num,a->name,&a->score);
    }
    b->next=NULL;
    return head;
}

void print(struct Student * p){
    p=p->next;
    while(p!=NULL){
        printf("%d号%s的成绩是:%3.1f\n",p->num,p->name,p->score);
        p=p->next;
    }
}

void delete_p(struct Student * p){
    struct Student *a,*b;
    a=p->next;  //先让 a 指向第一个结点
    while(a){
        b=a->next;  //b 记住 a 的下一个结点
        free(a);  //释放 a
        a=b;  //a 成为第下一个结点
    }
    p->next=NULL;
}

int main(){
    struct Student* stu_p;
    stu_p=create();
    print(stu_p);
    delete_p(stu_p);
    print(stu_p);
    return 0;
}

引入

前面我们学习了头插法创建单链表，既然有头插法就有尾插法，跟头插法思路相同，尾插法是在表尾加入新结点，我们一起来看一下。

尾插法创建单链表

头插法学习完之后，我们发现输入和输出的内容是相反的？为什么呢？因为头插法是在链表的头部插入数据，先插入的数据在尾部，后插入的数据再头部，所以最终保存的链表顺序跟输入顺序是相反的。尾插法就不存在这个问题，输入顺序跟输出顺序相同。

代码实现

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Student)
struct Student{
    int num;
    char name[20];
    float score;
    struct Student *next;
};

struct Student *create(void){
    struct Student *a,*b,*head;
    a=(struct Student *)malloc(LEN);  //创建结点
    head=(struct Student *)malloc(LEN); //创建头部
    b=head;  //b 指向尾巴，现在指向头部
    printf("请输入学生信息：\n");
    scanf("%d %s %f",&a->num,a->name,&a->score);
    while(a->num!=0){
        b->next=a;  //b在队尾，b 的 next 指向尾巴 a
        //也可以理解为：让 b 始终指向最后一个结点
        b=a;  //将 b 指向新节点，永远都指向新生成的节点
        //也可以理解为：让 r 始终在最后
        a=(struct Student *)malloc(LEN);
        scanf("%d %s %f",&a->num,a->name,&a->score);
    }
    b->next=NULL;
    return head;
}

void print(struct Student * p){
    p=p->next;
    while(p!=NULL){
        printf("%d号%s的成绩是:%3.1f\n",p->num,p->name,p->score);
        p=p->next;
    }
}

int main(){
    struct Student* stu_p;
    stu_p=create();
    print(stu_p);
    return 0;
}

引入

我们知道如何查找、插入、删除一个数据元素，那么在最初该如何创建一个单链表呢？单链表的效率真的比顺序表高嘛？高在哪里呢？

整表创建对比

**顺序表的整表创建：**可以用数组的初始化来理解，因为数组就是最常见的顺序表。
**单链表的整表创建：**单链表就跟顺序表有很大不同。

• 单链表的数据没有顺序存储结构这么集中。
• 数据可以是分散在内存各个角落
• 数据增长是动态进行的
• 每个链表的大小和位置不需要预先分配
• 根据系统情况和实际需求即时生成
• 总结就是灵活多变！

单链表的整表创建

首先要明确思路，单链表是动态生成的，从空表开始，依次建立元素结点，并且插入链表中。所以，大致的算法思路如下：

• 声明一个节点 P 和 计数器变量 i
• 初始化一个空链表 L
• 让 L 的头结点指向 NULL，建立一个带有头结点的单链表
• 通过循环插入后继结点

引入

我们知道如何在单链表中插入一个结点，那么现在就再看看如何删除一个结点，删除结点需要注意什么呢？

思考删除单链表中的结点

我们知道链表是一环扣一环，一个压一个。所以，要删除其中的某个结点，只需要将其前一个结点的 next 指针域指向该结点的下一结点即可。

• p->next=p->next->next;
• q=p->next , p->next=q->next
• 上面两种方式都是可以的，思路都是跳过要删除的这个，直接将前一个的指向指向后一个的地址。

引入

前面我们学习了如何找到和读取单链表中的数据，今天我们继续看看，如何在单链表中插入数据元素。

单链表中插入元素

我们既然知道，元素内存储的是数据域和指针域，一个指着另一个，呈链性存储。那么如果要在这样的链表中插入一个元素该如何处理呢？

其实也就是

• S 结点存储的地址，改成 P 存储的地址
• P 存储的地址改成 S 结点的地址
• S-> next = P->next
• P->next = S