算法的概念
算法与指令
算法是有限指令集
算法是对特定问题求解步骤的有限指令集
指令表示计算机内的一个操作
五大特征
输入性：少数算法可以没有输入（例如：随机）
输出性：输出算法的结果
有穷性：有限时间内结束，能够结束，不能有死循环
确定性：没有歧义的
可行性：可以用计算机实现的，每条指令都是可执行的
算法的评价
时间复杂度复和空间复杂度，算法是以宏观评价为主，微观为辅
时间复杂度
用来描述算法在执行过程中所需要的基本运算次数
- 关键语句（基本/核心/最重要 语句）的执行次数
- 不需要统计每条语句的执行时间
- 将时间的长短转换为执行语句的总次数：最耗时间，至少是循环
易错点：
- 算法的时间复杂度 不是计算 算法的执行时间，要搞清楚
- 算法的时间复杂度 与问题的规模、指令的数量 有关，与语句无关
| 关键指标 | 描述 |
|---|---|
| 平均时间复杂度 | 所有时间复杂度的平均值 |
| 最坏时间复杂度 | 所有时间复杂度的最大值 |
| 最优时间复杂度 | 所有时间复杂度的最小值 |
空间复杂度
又可称：空间的大小
指：算法在执行过程中所需要的计算机存储空间，执行时所占的内存
- 包括常用空间和临时空间
- 算法执行时不使用外存空间
有一个循环，循环内5条语言，循环共执行100次，该循环部分的时间复杂度为（）
5 x 100 =500 （次）
从10个数字中查找一个数，指出最坏、最优、平均时间复杂度（）
最坏时间复杂度：10
最优时间复杂度：1
平均时间复杂度：(1+2+3..+10)/10 = 5.5
数据结构
数据结构由数据元素与数据项组成
- 数据元素 是数据的基本单位
- 数据项 是 数据的最小单位
- 一个数据元素由多个数据项组成
也可以这样理解：
数据结构 = 数据 + 结构
数据结构=数据的集合+ 数据之间的关系（是否相邻的关系）的集合
元素之间的关系
两个元素之间：有关系（相邻），无关系（不相邻）
直接前驱和直接后续（是一对的关系）：
- 春是夏的直接前驱
- 夏是春的直接后继
数据结构的分类
数据结构分为：逻辑结构和物理结构
- 逻辑结构分为集合结构，线性结构，树型结构，图形结构
- 非线性逻辑结构指的是逻辑结构和非物理结构
物理结构：指计算机中的结构（存储结构指的就是物理结构）
- 逻辑结构在计算中表示
- 先有逻辑后有物理
物理结构的分类：
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 散列存储结构
数据的存储结构对程序的执行效率影响很大，是最直接的影响因素
逻辑结构与物理结构的关系
- 逻辑结构存在于大脑世界、物理结构存在于计算机内部
- 先有逻辑结构后有物理结构
- 他们不是一一对应的
- 一种逻辑结构可以有多种物理结构
循环队列指就是将队列存储空间的最后一个位置链接到第一个位置，形成运算上的环状空间，供队列循环使用，所以，循环队列属于存储结构
线性结构
- 有且只有一个 头节点
- 有且只有一个 尾节点
- 有且只有一个 根节点
- 头节点外 每个节点有且只有一个 直接前驱
- 尾节点外 每个节点有且只有一个 直接后继
如：一年4个季节
线性表
线性表属于线性结构：线性表是线性结构的一个具体实例，也就是线性表需要满足线性结构的基本特征
杂知识点
- 向量空间指一维空间
- 计算机内部存储是向量式的（也就是0/1）
- 数组空间也是向量式的，数组是顺序存储结构 但是数组可以处理非线性结构（二维数组）
顺序表
顺序表是 线性表的顺序存储结构（物理结构）
- 优点：结构简单，运算简单
- 缺点：插入删除效率低，长度固定
- 所有空间必须连续
- 必须逻辑上的连续：直接前驱，和直接后继 - （a是b的直接前驱，则b一定是a的直接后继）
- 元素在物理存储空间上也必须连续
顺序表基本运算
插入运算
插入后元素之间存储关系必须要保持连续
- 移动的方向：从尾元素开始移动，每个元素往后移一位
- 时间复杂度：移动元素的个数
n个元素顺序表，在 I 号位置插入一个元素，移动元素个数为（）
- 时间复杂度：N-I+1
- 最坏时间复杂度：N
- 最优时间复杂度：0
- 平均时间复杂度：(0+1+…N)/(N+1) = N/2
删除运算
- 移动方向：从被删除的元素的下一个元素开始，往前移动
- 时间复杂度：移动元素的个数
计算方法：n个元素顺序表，删除 I 号位置的元素，移动元素个数为（）
- 最坏时间复杂度：N-1
- 最优时间复杂度： 0
- 平均时间复杂度(从零开始)： (0+1+2…+（N-1）) / N = (N -1) / 2
习题
题1：10个元素的顺序表，在7号位置插入一个元素，移动元素的个数为（）。以及最坏、最优、平均时间复杂度为（）
根据题意得出：
- 从十号开始往后移动，所以时间复杂度为4
- 最坏时间复杂度为：10
- 最优时间复杂度为：0 （可在11号加，就不用移动了）
- 平均时间复杂度：(0+1+2…+10)/11 = 5
题2：10个元素的顺序表，删除7号元素的位置，求事件复杂度、以及最坏、最优、平均时间复杂度为
根据题意得出：
- 从8号开始往前移动，时间复杂度为3
- 最坏时间复杂度：9
- 最优时间复杂度：0
- 平均时间复杂度：（0+1+2…+10）/10 = 4.5
线性链表
线性链表是线性表的链式存储结构（物理）的简称
- 优点：空间上不要求连续，需要空间上可以动态分配，不要求固定
- 线性表可以有多种存储结构
- 尾节点的指针域为空
线性链表结构
每个元素存储空间分为2部分：
| 第一部分 | 第二部分 |
|---|---|
| 数据域 | 指针域 |
| 存放元素的值 | 存放元素之间的关系 |
双向链表
- 双向链表每个元素有三个域（1个数据域和2个指针域）
- 指针域保存直接前驱和直接后继
- 尾节点的指针域为空
双向链表的计算（不考）
栈和队列
栈 和队列 都属于线性结构
栈和队列都只能在端操作
- 线性结构有2端，首端和尾端
- 栈规定只能在1端操作
- 队列规定在 2 端操作
栈
栈：先进后出，后进先出（FILO）
- 类似：桶（一端开，一端封闭）
- 栈顶：可操作的端（可运算）
- 栈底：不可操作的端（不可运算）
- 入栈：插入元素
- 出栈：删除元素
- 栈和队列都是线性表
栈的运算：
题1：入栈顺序ABC，求出栈可能性（）
- 可能出现的顺序：CBA,ABC,ACB等
- 不可能出栈的序列：CAB
题2：ABC一次入栈，然后出栈1次，123再入栈，最后全部出栈，出栈的顺序为（）
根据题意得出：第一次出栈为C，压入123后，此时栈值为AB123。由于后进先出原则，所以逆向出栈
则：出栈顺序为 C321BA
队列
类似站队：一端进一端出，先进先出
- 队头：出的端
- 队尾：进的端
循环队列
- 循环队列属于存储结构
- 栈和队列都是线性表
计算
- 公式：队尾-队头 （如果小于0则加上队列容量）
- 通过队头指针和 队尾指针共同求得循环队列的元素
- 队头指针：开始的位置
- 队尾指针：结束的位置
题：某循环队列容量为50，队头指针为3，队尾指针为40，该队列的个数为（）
由题意得：
- 队尾-队头 = 40-3 = -10
- ∵-10<0
- ∴要加上队列容量:-10+50=40
- 则该队列的个数为40
