一、数据结构基本概念
基本概念
什么是数据？
数据是信息的载体，是客观描述事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
数据元素、数据项
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
数据结构、数据对象
结构——各个元素之间的关系
数据结构是互相之间存在一个或多种特定关系的数据元素的集合。
数据对象是具有相同性质的数据元素的集合，是一个数据的子集。
三要素
逻辑结构
即，数据元素之间的逻辑关系是什么？
集合
各个数据元素同属一个集合，别无其它关系
线性结构
数据元素之间是一对一的关系，除了第一个元素，所有元素都有唯一前驱，除了最后一个元素，所有元素都有唯一后继
树形结构
数据元素之间是一对多的关系
图结构
数据元素之间是多对多的关系
物理结构
即，物理结构，如何用计算机表示数据元素的逻辑关系？
顺序存储
把逻辑上相邻的元素存储在物理地址上也相邻的存储单元中，元素之间的关系由存储单元的领接关系来体现。
链式存储
索引存储
散列存储
总结
- 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺存储，则各个数据元素在物理上是可以离散的
- 数据的存储结构会影响存储空间的分配的方便程度
- 数据的存储机构会影响对数据运算的速度
数据的运算
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，正对运算的功能；运算的实现是针对存储结构的，指的是运算实现的具体操作步骤。
数据类型、抽象数据类型
数据类型
数据类型是一个值的集合和定义在此集合的一组操作的总称。
- 原子类型，其值不可再分的数据类型
- 结构类型，其值可以再分解为若干成分（分量）的数据类型
抽象数据类型
Abstract Data Type （ADT）是抽象数据组织及与之相关的操作。
ADT 是用数学化的语言定义数据的逻辑结构、定义运算。与其具体的实现无关（类似于定义类吗？可能）
总结
在探讨一种数据结构时：
- 定义逻辑结构（数据原元素之间的关系）
- 定义数据的运算（针对现实需求，应该对这种逻辑结构进行什么样的运算）
- 确定某种存储结构，实现数据结构，并实现一些对数据结构的基本运算
二、算法基本概念
基本概念
什么是算法？
程序=数据结构+算法
算法的特性
有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
注：算法必须是有穷的，二程序可以是无穷的。
确定性：算法每一条指令必须有确切的含义，对于相同的输入只能得出相同的输出
可行性：算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有0个或多个输入，这些输入取自某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
五个特性，缺一不可
“好”算法的特质
- 正确性：算法应能正确地解决求解问题。
- 可读性：算法应具有良好的可读性，帮助人们理解。
- 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
- 高效率与底存储量需求：执行速度快，时间复杂度低。不费内存，空间复杂度低。
总结
算法效率的度量
如何评估算法时间开销？
让算法先运行，事后统计运行时间？
存在的问题？
- 和机器性能有关，比如：超级计算机VS单片机
- 和编程语言有关，越高级的语言执行效率越低，没错，就是越低
- 和编译程序产生的机器指令质量有关
- 有些算法是不能事后统计的，比如，导弹控制算法。
评价一个算法优劣时，需要排除与算法本身无关的外界因素，能否事先估计？
算法时间复杂度
- 最坏时间复杂度：最坏情况下算法的时间复杂度
- 平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
- 最好时间复杂度：最好情况下算法的时间复杂度
事前预估算法时间开销T(n)与问题规模n的关系（T 表示 time）
如何计算T，例子：
问题1:是否可以忽略表达式某些部分？
加法规则：多项相加，只保留最高阶的项，且系数变为1
乘法规则：多项相乘，都保留
算法时间复杂度阶数顺序
如果有好几千行代码，需要一行一行数？
- 顺序执行的代码只会影响常数项，可以忽略
- 只需要挑循环中的一个基本操作，分析它的执行次数和n的关系就好
- 如果有多层嵌套循环，只需要关注最深层的循环循环了几次
小练习
总结
算法的性能问题只有在n很大时才会暴露出来。
算法空间复杂度
原地工作算法
分析空间复杂度时，只需关注与问题规模相关的变量就好（讲人话，就是，看程序中的变量就好）
加法法则
函数递归调用带来的内存开销
在这种情况下，空间复杂度等于递归调用的深度。
递归调用的过程中，每一次开辟的内存空间也可以不一致，如上例。
总结
