绪论

数据结构

基本概念

数据：描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素：数据的基本单位。一个数据元素可由若干个数据项组成。

结构：各个元素之间的关系

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

数据对象：具有相同性质的数据元素的集合。

数据类型：一个值的集合和定义在集合上的一组操作的总称

1. 原子类型：值不可再分
2. 结构类型：值可以再分解为若干成分（分量）的数据类型
3. 抽象数据类型ADT：抽象数据组织及与之相关的操作。ADT用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现即存储结构无关。定义一个ADT就是定义了数据的逻辑机构和运算，也就是==定义==了一个数据结构。

三要素

逻辑结构

它与数据的存储无关，是独立于计算机的。

分类：

1. 集合（非线性）
2. 线性结构
3. 树形结构（非线性）
4. 网状结构或图状结构（非线性）

存储结构

如何用计算机表示数据元素的逻辑关系。确定一种存储结构就意味着在计算机中表示出数据的逻辑结构，存储结构不同也会导致运算的具体实现不同，确定了存储结构才能==实现==数据结构

分类：

1. 顺序存储（数据元素在物理上必须连续）
2. 链式存储（非顺序）
3. 索引存储（非顺序）
4. 散列存储（非顺序）

影响：

1. 会影响存储空间分配的方便程度
2. 会影响对数据运算速度

数据的运算

运算的定义是针对逻辑结构的

运算的实现是针对存储结构的

学习数据结构思路

在探讨一种数据结构时：

1. 定义逻辑结构
2. 定义数据的运算（基本操作）
3. 确定某种存储结构，实现数据结构并实现一些对数据结构的基本运算

算法

程序 = 数据结构 + 算法

1. 数据结构（如何把现实世界的问题信息化，将信息存进计算机，同时还要实现对数据结构的基本操作）
2. 算法（如何处理这些信息，以解决实际问题）

例如：海底捞排队系统的数据结构可以采用队列，已经实现的基本操作有队头元素出队，新元素入队等。

要解决一个实际问题：带小孩的顾客优先就餐。那就要设计一个算法去实现。

算法特性

1. 有穷性：一个算法必须总在执行有穷步后结束，且每一步都在又穷时间内完成。但是程序可以时无穷的。
2. 确定性：对于相同的输入只能得出相同的输出
3. 可行性：可以通过已经实现的基本运算执行有限次来实现
4. 输入：有零个或多个输入
5. 输出：一个或多个输出

好算法的特质

1. 正确性
2. 可读性
3. 健壮性：非法数据算法能作出反应
4. 效率和低存储量需求：执行速度快，时间复杂度低。

如何评估算法时间开销

让算法先运行？事后统计？

算法估计：

和机器性能有关，和编程语言有关，和编译程序产生的机器指令质量有关，有些算法不能事后统计。

能否排除与算法本身无关的外界因素？能否事先预估？

时间复杂度

一个语句的频度是该语句在算法中被重复执行的次数。（计算时将循环重复次数设为x，去求解x与n的关系）

算法中所有语句的频度之和记为T(n)，他是该算法问题规模n的函数，时间复杂度主要是分析T(n)的数量级。

问题：是否可以忽略表达式的某些部分？如果有好几千行代码是否要按这种方法一行一行数？

解答：

1. 忽略问题规模更低阶的部分，只保留最高阶。主要是分析T(n)的数量级。那么可以用大O表示法去表示同阶，同等数量级。即当n趋于无穷时，二者之比为常数。
2. 顺序执行的代码智慧影响常数项，可以忽略。
3. 只需要挑循环中的一个基本操作分析它的执行次数与n的关系即可
4. 如果有多层嵌套循环，只需要关注最深层循环循环了多少次
5. 一般来说我们只会度量最坏时间复杂度和平均时间复杂度

加法规则乘法规则

求解方法

• 循环主体中的变量参与循环条件的判断

此题应该找出循环主题语句中与T(n)成正比的循环变量，将之带入条件计算

• 循环主体中的变量与循环条件无关

采用数学归纳法或直接累计循环次数。多层循环可以从内到外分析，忽略单步语句，条件判断语句，只关注主体语句执行次数。此类问题分为递归和非递归。递归程序一般使用公式递推，非递归直接累计次数。

小练习

斐波那契数列

斐波那契数列的F(n)有两种常用算法：递归算法和非递归算法。试分析两种算法的时间复杂度。

参考链接：https://www.cnblogs.com/abyss1114/p/7272657.html

递归

#include<iostream>
using namespace std;long Fibonacci(int n) {if (n == 0)return 0;else if (n == 1)return 1;elsereturn Fibonacci(n - 1) + Fibonacci(n-2);
}int main() {cout << "Enter an integer number:" << endl;int N;cin >> N;cout << Fibonacci(N) << endl;system("pause");return 0;
}

时间的复杂度为O(2^n)

非递归

#include<iostream>
using namespace std;long Fibonacci(int n) {if (n <= 2)return 1;else {long num1 = 1;long num2 = 1;for (int i = 2;i < n - 1;i++) {num2 = num1 + num2;num1 = num2 - num1;}return num1 + num2;}
}int main() {cout << "Enter an integer number:" << endl;int N;cin >> N;cout << Fibonacci(N) << endl;system("pause");return 0;
}

时间复杂度为O(n)

空间复杂度

空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。

计算

普通程序

1. 找到所占空间大小与问题规模相关的变量
2. 分析所占空间x与问题规模n的关系
3. x的数量级O(n)就是算法空间复杂度

例子1

例子2

例子3

递归程序

1. 找到递归调用深度x与问题规模n的关系
2. x的数量级O(x)就是算法空间复杂度S(n)

例子