引入

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

效率观察

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

• 遍历查找第 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
• 循环执行，直到完全释放完毕

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#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;
}

引入

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

尾插法创建单链表

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#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

引入

前面我们介绍了什么是链表，以及为什么单链表可以解决顺序表在插入删除时要移动大量元素的问题。也学习了如何封装一个单链表，今天我们来看看如何操作单链表中的数据。

单链表的读取

还记得在顺序表中的读取嘛？我们通过下标索引就可以很轻松的找到顺序表中的数据元素，因为顺序表中的数据元素的存放是紧密相联的。
但是在单链表中，

• 第一个数据存放着第二个数据的存储位置
• 第二个数据存放着第三个数据的存储位置
• 以此类存
• 第 n-1 个数据存放着第 n 个数据的存储位置

获取链表第 i 个数据的算法

• 指向：声明一个节点 p 指向链表中的第一个结点
• 遍历：初始化一个 j，j<i 时，就遍历链表，让 p 指针不断指向下一个结点，然后 j+1
• 失败：若找到链表末尾，p 为空，这说明第 i 个元素不存在
• 成功：返回第 i 个元素的结点 p 中的数据。

引入

前面我们说完了顺序存储结构的线性表的查找、插入和删除等操作，我们分析之后发现，顺训存储结构的线性表最大的缺点就是插入和删除的时候需要移动大量元素，太费时间了，我们能不能针对这个缺陷提出新的结构呢？

思考

我们现在的问题是

插入和删除的时候，要移动大量元素

原因就在于，相邻的两个元素的存储位置也具有邻居关系，也就是说它们在内存中的位置是紧密相联的。所以我们就没有办法从紧密相联的关系中插入和删除元素，并依旧保持它们紧密相联的关系了。所以指针刚好可以派上用场，每个元素多留一个位置存储下一个元素的位置指针，这样第一个元素找到第二个，第二个找到第三个….以此类推即可。

引入

前面，我们知道了如何分装一个线性表顺序存储的结构，也知道了如何使用索引地址转下标法得到某个索引对应的值，今天，我们来看看如何在线性表中插入一个元素。

思考如何插入元素

我们说过，线性表的顺序存储结构具有随机存储结构的特点，时间复杂度位 O (1) 。
输入：

• 线性表指针
• 要插入的位置
• 要插入的数值

判断

• 插入位置是否合理，不合理报错
• 线性表长度大于等于数组长度，报错，或者动态增加数组容量。

计算

• 从最后一个元素开始，遍历到第 i 个位置，将遍历的元素都向后移一位。
• 将要插入的元素填入 i 处
• 线性表的长度+1

引入

我们知道，数据结构分为逻辑结构和物理结构，线性表就是一种逻辑结构，那么线性表对应的物理存储结构是什么呢？如何操作这些存储结构呢？

线性表的物理存储结构

线性表有两种物理存储结构

• 顺序存储结构：顺序存储结构指的是一段地址连续的存储单元一次存储线性表中的数据元素。我们很容易想到的就是数组，数组就是地址相连的一段元素，是顺序存储结构。
• 链式存储结构： 稍后详细介绍。

线性表的顺序存储结构

这节我们主要讲线性表的顺序存储结构，其实顺序存储结构在物理上的存储方式就是：

• 在内存中找到一个初始地址
• 通过占位的形式，把一定的内存空间给占了
• 最后，把相同数据类型的数据元素依次放在这块空间里

线性表顺序存储的结构代码

1
2
3
4
5
6
7
8
9
10

#define MAXSIZE 20  //定义常量 MAXSIZE 为 20
typedef int ElemType;  //将 int 类型 别名位 ElemType
typedef struct {
//定义一个结构体变量包含两个元素
Elemtype data[MAXSIZE];
// 一个整型 data 数组，元素有20个
int length;
// 一个整型的长度
} SqList；
//将结构体类型名设置为 SqList