引入

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

单链表的读取

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

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

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

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

引入

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

思考

我们现在的问题是

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

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

引入

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

思考如何插入元素

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

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

判断

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

计算

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

引入

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

线性表的物理存储结构

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

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

线性表的顺序存储结构

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

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

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

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

引入

上节，我们学习了什么是线性表以及抽象数据类型，今天我们来看看线性表的抽象数据类型如何来使用。

感受抽象

还记得上节课我们讲的那个例子吗？升旗仪式排队:

1号小红
2号小明
3号小强
4号小姗
…
55号小美
56号小力

• 因为我们记不住编号，所以只要记住前面的同学名称就可以了，也就是找到自己唯一的直接前驱同学就行了。这样大家就可以排好队了，这就是线性表的创建和初始化。
• 但是发现55号小美太矮了，2号小明太高了，导致队伍不好看，所以就把队伍解散，老师准备重新根据身高排队。解散的动作就类似线性表重置位空表。
• 刚排好队，发现3号小强请假了，那4号小珊就要向前挪动，4号小姗的前面就是2号小明了，这就是线性表删除数据。
• 下次升旗仪式，3号小强回来了，就要插入2号小明和4号小姗之间，4号小姗退一位，然后3号小强回到自己的位置上。这就是线性表插入数据。
• 升旗过程中呢，有学生会检查，发现我们队55号没有穿校服，就反馈给我，我就查了下花名册（线性结构哦），发现是55号是小红，这就是根据位序得到元素。

引入

之前我们都在学习什么是数据结构以及如何评价一个算法的时间、空间复杂度，今天开始，我们学习一个最简单的数据结构，线性表。

感受数据结构

还记得小时候，排队去参加升旗仪式，老师们会按照高矮个将同学们分好位置，全班50多个人，怎么记住自己的位置呢？

1号小红
2号小明
3号小强
…
55号小美
56号小力

老师肯定不能告诉你，Bliner 你在32位，那你站队的时候还要从1数到32…如果8号没来..你还少数了…这样肯定不行。
所以，老师们一般都会这么告诉你，记住你前面的同学，下次你就站在这儿。
并且，如果有谁不在，也可以一下子就知道，因为肯定有同学会说，我前面的 XX 没来。

线性表

线性表就像刚才排队一样，具有线一样的性质。

**定义:**由 0 个或者多个数据元素组成的有限序列，就称为线性表。

• **必须是序列：**线性表是一个序列，元素之间有先来后到的关系。
• **多个元素：**如果存在多个元素，那么第一个元素无前驱，最后一个元素无后继，其他的元素只有一个前驱和后继。（类似 C 学指针时候的双链表）
• **有限：**线性表强调的是有限，事实上无论计算机发展到多强大，处理的数据一定是有限的。

引入

我们结束了时间复杂度的学习，了解了常见的时间复杂度的计算以及不同时间复杂度之间的关系，今天我们看看最坏情况和平均情况，以及空间复杂度。

最坏情况和平均情况

比如有一个数列，我们想找数字 1

• **最好情况：**数列是从1~10排列，找第一个就找到1了，O(1)就搞定。
• **最坏情况：**最坏的就是数列是从10~1排列，找到最后一个 n 才找到10，那复杂度就是O( n )。
• **平均情况：**我们期望运行的时间，比如我希望3分钟搞定。
• **最坏运行时间：**这是一种保证，也就是说，我的算法在最坏情况也，需要多少时间搞定，通常情况下，我们说的运行时间，都是最坏运行时间。

算法的空间复杂度

在写代码的时候，我们可以用空间换取时间，当然也可以用时间换取空间。

#include <stdio.h>
int main(){
    int year;
    printf("请输入年份（如2018）：\n");
    scanf("%d",&year);
    if((year%4==0 && year%100!=0 )|| year%400==0){
        printf("%d年是闰年！",year);
    }else{
        printf("%d年不是闰年！",year);
    }
}

引入

前面我们讲了普通赋值、输出、打印的时间复杂度、也讲了循环、嵌套循环的时间复杂度，现在我们来看看在函数引用下，时间复杂度有什么不同。

例子

看看下面程序的时间复杂度

int i;  //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
printf("%d\n",count);
}
// 函数就执行了一个 printf 语句 复杂度位 O(1)

上面的循环语句，每执行一次，就会调用一次函数，函数是 1，循环 n 次 1 ，所以上面这个例子的时间复杂度是 O(n) 。

我们再来个复杂点的

int i;  //执行1次
for(i=0;i<n;i++){
function(i);
}
// for 循环，复杂度为 O(n)
void function(int count){
int j;
for (j=0;j<n;j++){
printf("%d",j);
}
}
// 函数内是一个循环，随着 count 的增加，循环次数减少

引入

前一讲，我们介绍了什么是算法的量度，以及如何用渐进函数来看哪些对算法的复杂度影响最大，今天我们就来看看如何计算复杂度。

时间复杂度

• **定义：**在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。所以，算法的时间复杂度，就是算法的时间量度:

  T(n)=O( f(n) )

• **时间复杂度：**它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。称作算法的渐进时间复杂度，简称为时间复杂度。

  f(n) 是问题规模 n 的某个函数（上节我们研究过，能够改变结果的那个函数）

上面的定义很复杂，但只要记住，执行次数==时间就可以了。

引入

前面我们说，算法效率要高，这里的高其实就是算法的执行时间短，时间段效率自然高，那么我们就需要了解，如何判断一个算法的执行效率，也就是执行时间快不快。

事后统计法

我们知道，跑马拉松，选手快不快，是根据到达终点的时间来决定的。算法也一样，我们根据跑完一遍的时间来计算算法的效率。也就是事后统计法。
**事后统计法：**通过设计好的测试程序和数据，利用计算机计时器对不同的算法编程的程序的运行时间进行比较。从而确定算法的效率高低。

事后统计法的缺陷

这种事后统计法是需要测试程序和数据的….
准备测试程序和数据太费功夫了….
因为测试数据和程序要跟算法一对一匹配。
测试失败…不就凉了…

**特别是：**不同的测试环境，测试的结果差别非常大。