文章目录
-
- 数据结构
-
- 数据逻辑结构
-
- 集合
- 线性结构
- 树形结构
- 图状结构
- 数据物理结构
-
- 顺序
- 链式
- 索引
- 散列（hash）
-
- 哈希函数
-
- 直接寻址法
- 数字分析法
- 平方取中法
- 取随机数法
- 除留取余法
- 算法
-
-
- 特性
-
- 输入
- 输出
- 有穷性
- 确定性
- 可行性
- 效率度量
-
- 事前分析
- 事后分析
-
- 大O表示法
-
- 算法与数据结构联系
数据结构
数据逻辑结构
逻辑关系层面的数据，与存储无关
算法设计
集合
线性结构
一对一 如线性表、栈、队列
树形结构
一对多 如树
图状结构
多对多
数据物理结构
即存储结构，是数据的逻辑结构在计算机存储器的映像
算法实现
顺序
存储器的相对位置 表示 逻辑关系
集中存储 底层实现使用数组 一大块连续的物理空间
利于后期数据的遍历操作
链式
指示元素存储地址的指针表示数据元素间的逻辑关系
随机存储数据 利于后期对数据的增删操作
索引
散列（hash）
空间换时间 （缓存中间数值）
给定关键字的值key 直接访问到具体对应值value的一个数据结构
或 通过key访问一个映射表得到value地址
映射表即散列函数或哈希函数
哈希函数
直接寻址法
取关键字或关键字的某个线性函数值为散列地址
数字分析法
如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址
平方取中法
先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址
计算平方之后的中间几位和关键字中的每一位都相关，不同的关键字会以较高的概率产生不同的散列地址。
取随机数法
使用一个随机函数，取关键字的随机值作为散列地址
适用关键字长度不同的场合
除留取余法
取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址
算法
特定问题求解步骤的描述，解决问题的方法和思想
计算机：指令的有限序列
特性
输入
0个或多个输入
输出
1个或多个输出
有穷性
算法在有限的步骤之后会自动结束不会无限循环
确定性
算法每一步都有确定的含义
可行性
效率度量
事前分析
算法采用的策略和方法
问题的输入规模
编译器所产生的代码
计算机执行速度
事后分析
比较不同算法对同一组输入数据的运行处理时间
实施困难 （编写程序 运行环境 选取测试数据 ）
大O表示法
算法的时间复杂度表示
问题规模受限于n，记做 O(n)
算法的空间复杂度
算法执行时所需空间是常数时 空间复杂度为O（1）。
算法与数据结构联系
数据结构是算法需要解决的问题载体
高效的程序需要在数据结构的基础上设计和选择算法
即：程序=数据结构+算法