01 数据结构起源
数据结构定义
数据结构是一门研究非数值运算的程序设计问题中的操作对象以及它们之间的关系和操作等相关问题的学科。
历史
1968年 美国高德纳 数据的逻辑结构和存储结构及操作
1968年 作为独立课程开始学习
70年代初 软件相对独立 结构程序设计更加重要
程序设计=数据结构+算法
02 数据关系
数据关系图
数据
｜ ①数据 定义：数、字符以及所有能被输入到计算机被程序识别、处理的符号集合
｜ ②数据组成：整型、实型等数值类型 和 字符、声音、图像、视频等非数值类型
｜
数据对象
｜ ①具有相同性质的数据元素的集合，是数据的子集。
｜ ②数据元素具有相同数量和类型。
｜
数据元素
｜ ①数据元素 定义：数据的基本单位，通常作为一个整体考虑；有一定意义的基本单位；在计算机中通常作为整体处理也被称为记录。
｜ ②由若干数据项组成。
｜ ③具有意义，是建立数据模型的着眼点。
｜
数据项
｜ ①构成数据元素的不可分割的最小单位；若干数据项组成了数据元素；
｜ ?②数据项是数据的最小单位。
｜ ③没有意义。
03 抽象数据类型（ADT）
ADT：关注定义域和相关操作（抽象数据组织+与之相关的操作）
定义：
取出事物具有的普遍性的性质
抽出问题的特征而忽略非本质的细节，是对具体事物的概括
只涉及逻辑特性，不涉及物理特性
组成
数据对象
数据关系
基本操作集
标准格式
04 数据类型
定义：
一个值的集合+定义在此集合上的一组操作的总称
DT=DT(值的集合，相关操作）
int 4个字节 32位 -2^31~ 2^31-1
为什么需要数据类型？
计算机内存有限
针对具体类型所设计的操作，分配不同的内存空间以优化内存使用
分类：
原子类型
｜ 值不可再分的数据类型：double,int,bool,char,float
｜
结构类型
｜ 值可以再分为若干成分的数据类型：person{ int age;struct person date'}结构体
抽象数据类型
｜ 抽象数据组织+与之相关的操作 抽象类 03 ADT
05 数据结构
数据：数据元素 结构：关系
数据结构定义
相互之间存在一种或多种特定关系的数据元素的集合
数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合
数据元素之间存在的一种或多种特定关系，也就是数据的组织形式
数据结构三要素
逻辑结构：决定算法设计
物理（存储）结构：决定算法实现
运算
例子：对抽象类的继承，具体实现 对建筑蓝图的具体实现
06 逻辑结构（数据结构三要素之一）
一种逻辑结构可对应多种存储结构
①线性结构：一对一
一般线性表
受限线性表
栈和队列（操作受限）
串（内容受限）
线性表推广
数组
广义表
②非线性结构
树：一对多（思维导图 、文件夹）
一般树
二叉树
图：多对多
有向图
无向图
集合（除同属于一个集合外，再无其他关系）
07 存储结构（数据结构三要素之一）
定义
是数据的逻辑结构在计算机中的表示---映像（存储结构正确反映数据元素之间的逻辑关系）
数据元素的表示
关系的表示
实际上就是如何把数据元素存储到计算机的存储器中
存储器是针对内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来表示
数据域
｜ 数据元素由若干数据项构成时，数据项的表示称为数据域
计算机里表示数据的方式
顺序映像
｜ ①借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系
｜ ②对应顺序存储结构
非顺序映像
｜ ①借助指针表示数据元素之间的逻辑关系
｜ ②对应链式存储结构
分类（存储方法：4种）
①顺序存储
｜ 将逻辑相邻的结点存储在物理位置相邻的存储单元中
｜ 顺序存储结构 一般数组表示
优点
｜ ①可以随机存取（也可以顺序存取）
｜ 随机存取：存取第N个数据时，不需要访问前（N-1）个数据，直接就可以对第N个数据操作。
｜ 非随机存取（顺序存取）：存取第N个数据时，必须先访问前(N-1)个数据。
｜ ②每个元素占用最少的空间
｜
缺点
｜ ①只能使用一整块相邻的存储单元，可能产生较多的外部碎片
②链式存储
｜ 不要求逻辑相邻的节点存储在物理位置相邻的存储单元中
｜ 链式存储结构 一般指针表示
优点
｜ ①不会出现碎片现象
缺点
｜ ①会因为指针而占用额外的存储空间
｜ ②只能顺序存储
节点内存储单元地址一定连续；相邻节点存储空间一定连续
③索引存储
｜ 存储节点时，额外存储地址，形式如<关键字，地址>
｜ 关键字：标识唯一一个节点
｜ 地址：指向上述节点的指针
优点
｜ ①检索速度快
缺点
｜ ①增加了附加的索引表。会占用更多空间
｜ ②增、删数据时要修改索引表。会花费很多时间
④散列存储
｜ 根据节点的关键字计算出节点的存储地址，形如location=Hash(key)
｜ 散列表 顺序存储方法的扩展
｜ key：关键字
｜ Hash():计算地址的方法，散列函数
｜ location:存储该节点的地址
｜
优点
｜ ①检索、增加、删除节点操作快
缺点
｜ ①散列函数不好，会出现元素存储单元冲突，解决冲突会增加时间、空间开销
08 算法的定义（数据结构三要素之一）
施加在数据上的运算，包括运算的定义和实现
定义：针对逻辑结构，指出运算的功能（面向问题）
实现：针对存储结构，指出运算的具体步骤（面向计算机）
引入算法的原因
评价代码的性能
算法的定义
｜ 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中一条指令表示一个或多个操作。
指令
｜ 为了解决某个或者某类问题，需要把指令表示成一定的操作序列。
｜ 操作序列包括一组操作，每一个操作都完成特定的功能。
09 算法的特征（记忆：五行确穷输输）
有穷性
在有穷步骤之后能够完成
每一步能在有穷时间内完成
确定性
每一条指令必须有确切的含义
读者对其理解不会产生二义性
相同的输入得到相同的输出
可行性
算法中的操作都能在有限次执行后结束
输入
（0或者多个）
输出
（1或者多个）
10 算法的评价
正确率
①算法程序没有语法错误
②算法程序对于合法的输入数据能够给产生满足要求的输出结果
③算法程序对于非法的输入数据能够得出满足规格说明的结果
④算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
一般情况下吧层次③当做一个算法是否正确的标准
可读性好
健壮性
对非法输入能进行相应处理
高效率与低存储量
效率：指时间，效率越高越好，时间短的效率高
存储量：指空间，存储量越低越好，指算法在执行过程中需要的最大存储空间，运行时所占用的内存或外部硬盘存储空间
11 效率度量方法
事后分析估算方法
事前分析估算方法
算法采用的策略
编译产生的代码质量
问题的输入规模
机器执行指令的速度
关注点：
一个程序的运行时间，依赖于算法的好坏和问题的输入规模
12 时间复杂度
频度
｜ 一个语句在算法中重复执行的次数
｜
T(n)
｜ 算法中所有语句的频度之和
｜ n：表示该算法问题的规模
｜ T(n)：该算法问题规模n的函数
｜ 分析时间复杂度主要是分析T(n）的数量级
算法的基本操作
｜ 最深处循环内语句
｜ 算法的基本运算的频度与T(n)同数量级
O是T(n)的数量级 T(n)=O(f(n))
常见阶
O(1)：常数阶
O(n)：线性阶
O(logn)：对数阶
O(n^2)：平方阶
常见阶大小关系
复杂度计算规则
加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
乘法规则：T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n))*g(n))
影响时间复杂度的因素
问题规模n
输入数据的性质（输入数据的初始状态）
最坏时间复杂度
定义：最坏情况下的时间复杂度
一般考虑最坏情况下的时间复杂度，以保证算法的运行时间不会比它长
平均时间复杂度
所有输入等概率的情况下，算法期望运行的时间
最好时间复杂度
最好情况下的时间复杂度
13 空间复杂度
S(n) :表示该算法所消耗的空间，它是问题规模n的函数
渐进空间复杂度：S(n)=O(g(n))
分析空间复杂度：只需分析除输入和程序之外的额外空间（存放本身指令、常数、变量、输入数据不考虑在内）就是看消耗的空间和问题规模n是否有关系
原地工作：所需辅助空间为常量，O(1)
一般可以通过空间换时间
索引存储与散列存储
14 分析时空复杂度方法
递归类
非递归类
两种方法
观察法
设循环次数t方法(循环主体中变量与循环条件有关)
|