03 Data Structure Summary
2019-06-21 22:29:41 0 举报AI智能生成
数据结构概论
作者其他创作
大纲/内容
概论
基本术语
data<br>
是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称
data element
是数据的基本单位
一个data element可由多个data item组成
data item是数据不可分割的最小单位
data object
是相同数据元素的集合，是数据的一个子集
data structure
data
structure
集合
线性结构
树形结构
网状结构
物理结构(存储结构)
数据元素的表示
element(node)
data field
关系的表示
顺序映像
顺序储存结构
非顺序映像
链式储存结构
pointer
数据+一组操作
data type
定义
值的集合
定义在这个值上的一组操作
分类
原子类
不可分割的
结构类型
由若干成分按某种结构组成
Abstract Data Type
定义
一个数学模型
定义在该数学模型上的一组操作
值的分类
atomic data type<br>
结构类型
fixed-aggregate data type
variable-aggregate data type
polymorphic data type
其值的成分不确定的数据类型
Data Type || Abstract Data Type = (D, S, P)
D -- 数据对象
S-- D上的关系集合
P--对应D的基本操作集合
抽象数据类型的表示与实现
算法和算法分析
algorithm定义
对特定问题求解步骤的一种描述，是指令的有序列，其中每条指令表示一个或多个操作
algorithm的重要特性
有穷性
确定性
可行性
输入
输出
algorithm的设计要求
correctness
readability
robustness
当输入数据非法时，算法能够适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
效率
低存储量需求
指算法执行过程中所需要的最大存储空间
algorithm效率的度量
事后统计法<br>
简单地通过执行时间长短来判别
事前分析估计法
决定因素
依据的算法选用何种策略
问题规模
书写程序的语言
编译程序所产生的机器代码的质量
机器执行指令的速度
两个complexity
asymptotic time complexity
space complexity
0 条评论
下一页
